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