1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkAddIntersections.h" 8 #include "SkOpEdgeBuilder.h" 9 #include "SkPathOpsCommon.h" 10 #include "SkPathWriter.h" 11 12 // FIXME: this and find chase should be merge together, along with 13 // other code that walks winding in angles 14 // OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure 15 // so it isn't duplicated by walkers like this one 16 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) { 17 while (chase.count()) { 18 SkOpSpan* span; 19 chase.pop(&span); 20 const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); 21 SkOpSegment* segment = backPtr.fOther; 22 nextStart = backPtr.fOtherIndex; 23 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 24 int done = 0; 25 if (segment->activeAngle(nextStart, &done, &angles)) { 26 SkOpAngle* last = angles.end() - 1; 27 nextStart = last->start(); 28 nextEnd = last->end(); 29 #if TRY_ROTATE 30 *chase.insert(0) = span; 31 #else 32 *chase.append() = span; 33 #endif 34 return last->segment(); 35 } 36 if (done == angles.count()) { 37 continue; 38 } 39 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 40 bool sortable = SkOpSegment::SortAngles(angles, &sorted, 41 SkOpSegment::kMayBeUnordered_SortAngleKind); 42 int angleCount = sorted.count(); 43 #if DEBUG_SORT 44 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable); 45 #endif 46 if (!sortable) { 47 continue; 48 } 49 // find first angle, initialize winding to computed fWindSum 50 int firstIndex = -1; 51 const SkOpAngle* angle; 52 do { 53 angle = sorted[++firstIndex]; 54 segment = angle->segment(); 55 } while (segment->windSum(angle) == SK_MinS32); 56 #if DEBUG_SORT 57 segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); 58 #endif 59 int sumMiWinding = segment->updateWindingReverse(angle); 60 int sumSuWinding = segment->updateOppWindingReverse(angle); 61 if (segment->operand()) { 62 SkTSwap<int>(sumMiWinding, sumSuWinding); 63 } 64 int nextIndex = firstIndex + 1; 65 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 66 SkOpSegment* first = NULL; 67 do { 68 SkASSERT(nextIndex != firstIndex); 69 if (nextIndex == angleCount) { 70 nextIndex = 0; 71 } 72 angle = sorted[nextIndex]; 73 segment = angle->segment(); 74 int start = angle->start(); 75 int end = angle->end(); 76 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 77 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, 78 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 79 if (!segment->done(angle)) { 80 if (!first) { 81 first = segment; 82 nextStart = start; 83 nextEnd = end; 84 } 85 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 86 oppSumWinding, true, angle); 87 } 88 } while (++nextIndex != lastIndex); 89 if (first) { 90 #if TRY_ROTATE 91 *chase.insert(0) = span; 92 #else 93 *chase.append() = span; 94 #endif 95 return first; 96 } 97 } 98 return NULL; 99 } 100 101 /* 102 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding, 103 bool windingIsOp, PathOp op) { 104 bool active = windingIsActive(winding, spanWinding); 105 if (!active) { 106 return false; 107 } 108 if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) { 109 switch (op) { 110 case kIntersect_Op: 111 case kUnion_Op: 112 return true; 113 case kDifference_Op: { 114 int absSpan = abs(spanWinding); 115 int absOpp = abs(oppSpanWinding); 116 return windingIsOp ? absSpan < absOpp : absSpan > absOpp; 117 } 118 case kXor_Op: 119 return spanWinding != oppSpanWinding; 120 default: 121 SkASSERT(0); 122 } 123 } 124 bool opActive = oppWinding != 0; 125 return gOpLookup[op][opActive][windingIsOp]; 126 } 127 */ 128 129 static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op, 130 const int xorMask, const int xorOpMask, SkPathWriter* simple) { 131 bool firstContour = true; 132 bool unsortable = false; 133 bool topUnsortable = false; 134 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 135 do { 136 int index, endIndex; 137 bool done; 138 SkOpSegment* current = FindSortableTop(contourList, &firstContour, &index, &endIndex, 139 &topLeft, &topUnsortable, &done, true); 140 if (!current) { 141 if (topUnsortable || !done) { 142 topUnsortable = false; 143 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 144 topLeft.fX = topLeft.fY = SK_ScalarMin; 145 continue; 146 } 147 break; 148 } 149 SkTDArray<SkOpSpan*> chaseArray; 150 do { 151 if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { 152 do { 153 if (!unsortable && current->done()) { 154 #if DEBUG_ACTIVE_SPANS 155 DebugShowActiveSpans(contourList); 156 #endif 157 if (simple->isEmpty()) { 158 simple->init(); 159 break; 160 } 161 } 162 SkASSERT(unsortable || !current->done()); 163 int nextStart = index; 164 int nextEnd = endIndex; 165 SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd, 166 &unsortable, op, xorMask, xorOpMask); 167 if (!next) { 168 if (!unsortable && simple->hasMove() 169 && current->verb() != SkPath::kLine_Verb 170 && !simple->isClosed()) { 171 current->addCurveTo(index, endIndex, simple, true); 172 SkASSERT(simple->isClosed()); 173 } 174 break; 175 } 176 #if DEBUG_FLOW 177 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 178 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 179 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 180 #endif 181 current->addCurveTo(index, endIndex, simple, true); 182 current = next; 183 index = nextStart; 184 endIndex = nextEnd; 185 } while (!simple->isClosed() && (!unsortable 186 || !current->done(SkMin32(index, endIndex)))); 187 if (current->activeWinding(index, endIndex) && !simple->isClosed()) { 188 SkASSERT(unsortable || simple->isEmpty()); 189 int min = SkMin32(index, endIndex); 190 if (!current->done(min)) { 191 current->addCurveTo(index, endIndex, simple, true); 192 current->markDoneBinary(min); 193 } 194 } 195 simple->close(); 196 } else { 197 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); 198 if (last && !last->fLoop) { 199 *chaseArray.append() = last; 200 } 201 } 202 current = findChaseOp(chaseArray, index, endIndex); 203 #if DEBUG_ACTIVE_SPANS 204 DebugShowActiveSpans(contourList); 205 #endif 206 if (!current) { 207 break; 208 } 209 } while (true); 210 } while (true); 211 return simple->someAssemblyRequired(); 212 } 213 214 // pretty picture: 215 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 216 static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = { 217 // inside minuend outside minuend 218 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend 219 {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }}, 220 {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }}, 221 {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }}, 222 {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }}, 223 {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }}, 224 }; 225 226 static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { 227 {{ false, false }, { true, false }}, // diff 228 {{ false, false }, { false, true }}, // sect 229 {{ false, true }, { true, true }}, // union 230 {{ false, true }, { true, false }}, // xor 231 {{ false, true }, { false, false }}, // rev diff 232 }; 233 234 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 235 #if DEBUG_SHOW_TEST_NAME 236 char* debugName = DEBUG_FILENAME_STRING; 237 if (debugName && debugName[0]) { 238 DebugBumpTestName(debugName); 239 DebugShowPath(one, two, op, debugName); 240 } 241 #endif 242 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 243 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 244 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 245 const SkPath* minuend = &one; 246 const SkPath* subtrahend = &two; 247 if (op == kReverseDifference_PathOp) { 248 minuend = &two; 249 subtrahend = &one; 250 op = kDifference_PathOp; 251 } 252 #if DEBUG_SORT || DEBUG_SWAP_TOP 253 gDebugSortCount = gDebugSortCountDefault; 254 #endif 255 // turn path into list of segments 256 SkTArray<SkOpContour> contours; 257 // FIXME: add self-intersecting cubics' T values to segment 258 SkOpEdgeBuilder builder(*minuend, contours); 259 const int xorMask = builder.xorMask(); 260 builder.addOperand(*subtrahend); 261 if (!builder.finish()) { 262 return false; 263 } 264 result->reset(); 265 result->setFillType(fillType); 266 const int xorOpMask = builder.xorMask(); 267 SkTArray<SkOpContour*, true> contourList; 268 MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask, 269 xorOpMask == kEvenOdd_PathOpsMask); 270 SkOpContour** currentPtr = contourList.begin(); 271 if (!currentPtr) { 272 return true; 273 } 274 SkOpContour** listEnd = contourList.end(); 275 // find all intersections between segments 276 do { 277 SkOpContour** nextPtr = currentPtr; 278 SkOpContour* current = *currentPtr++; 279 if (current->containsCubics()) { 280 AddSelfIntersectTs(current); 281 } 282 SkOpContour* next; 283 do { 284 next = *nextPtr++; 285 } while (AddIntersectTs(current, next) && nextPtr != listEnd); 286 } while (currentPtr != listEnd); 287 // eat through coincident edges 288 289 int total = 0; 290 int index; 291 for (index = 0; index < contourList.count(); ++index) { 292 total += contourList[index]->segments().count(); 293 } 294 #if DEBUG_SHOW_WINDING 295 SkOpContour::debugShowWindingValues(contourList); 296 #endif 297 CoincidenceCheck(&contourList, total); 298 #if DEBUG_SHOW_WINDING 299 SkOpContour::debugShowWindingValues(contourList); 300 #endif 301 FixOtherTIndex(&contourList); 302 CheckEnds(&contourList); 303 SortSegments(&contourList); 304 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 305 DebugShowActiveSpans(contourList); 306 #endif 307 // construct closed contours 308 SkPathWriter wrapper(*result); 309 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); 310 { // if some edges could not be resolved, assemble remaining fragments 311 SkPath temp; 312 temp.setFillType(fillType); 313 SkPathWriter assembled(temp); 314 Assemble(wrapper, &assembled); 315 *result = *assembled.nativePath(); 316 result->setFillType(fillType); 317 } 318 return true; 319 } 320
