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