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" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 8 | #include "SkOpCoincidence.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 9 | #include "SkOpEdgeBuilder.h" |
| 10 | #include "SkPathOpsCommon.h" |
| 11 | #include "SkPathWriter.h" |
| 12 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 13 | static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr, |
| 14 | SkOpSpanBase** endPtr) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 15 | while (chase.count()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 16 | SkOpSpanBase* span; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 17 | chase.pop(&span); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 18 | // OPTIMIZE: prev makes this compatible with old code -- but is it necessary? |
| 19 | *startPtr = span->ptT()->prev()->span(); |
| 20 | SkOpSegment* segment = (*startPtr)->segment(); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 21 | bool done = true; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 22 | *endPtr = nullptr; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 23 | if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 24 | *startPtr = last->start(); |
| 25 | *endPtr = last->end(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 26 | #if TRY_ROTATE |
| 27 | *chase.insert(0) = span; |
| 28 | #else |
| 29 | *chase.append() = span; |
| 30 | #endif |
| 31 | return last->segment(); |
| 32 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 33 | if (done) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 34 | continue; |
| 35 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 36 | int winding; |
| 37 | bool sortable; |
| 38 | const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); |
caryclark | aa7ceb6 | 2016-06-29 10:46:08 -0700 | [diff] [blame] | 39 | if (!angle) { |
| 40 | return nullptr; |
| 41 | } |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 42 | if (winding == SK_MinS32) { |
| 43 | continue; |
| 44 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 45 | int sumMiWinding, sumSuWinding; |
| 46 | if (sortable) { |
| 47 | segment = angle->segment(); |
| 48 | sumMiWinding = segment->updateWindingReverse(angle); |
caryclark | 7941809 | 2016-08-26 14:24:24 -0700 | [diff] [blame] | 49 | if (sumMiWinding == SK_MinS32) { |
| 50 | SkASSERT(segment->globalState()->debugSkipAssert()); |
| 51 | return nullptr; |
| 52 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 53 | sumSuWinding = segment->updateOppWindingReverse(angle); |
caryclark | 7941809 | 2016-08-26 14:24:24 -0700 | [diff] [blame] | 54 | if (sumSuWinding == SK_MinS32) { |
| 55 | SkASSERT(segment->globalState()->debugSkipAssert()); |
| 56 | return nullptr; |
| 57 | } |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 58 | if (segment->operand()) { |
| 59 | SkTSwap<int>(sumMiWinding, sumSuWinding); |
| 60 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 61 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 62 | SkOpSegment* first = nullptr; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 63 | const SkOpAngle* firstAngle = angle; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 64 | while ((angle = angle->next()) != firstAngle) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 65 | segment = angle->segment(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 66 | SkOpSpanBase* start = angle->start(); |
| 67 | SkOpSpanBase* end = angle->end(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 68 | int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 69 | if (sortable) { |
| 70 | segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, |
| 71 | &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); |
| 72 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 73 | if (!segment->done(angle)) { |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 74 | if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 75 | first = segment; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 76 | *startPtr = start; |
| 77 | *endPtr = end; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 78 | } |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 79 | // OPTIMIZATION: should this also add to the chase? |
caryclark | bca19f7 | 2015-05-13 08:23:48 -0700 | [diff] [blame] | 80 | if (sortable) { |
| 81 | (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, |
| 82 | oppSumWinding, angle); |
| 83 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 84 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 85 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 86 | if (first) { |
| 87 | #if TRY_ROTATE |
| 88 | *chase.insert(0) = span; |
| 89 | #else |
| 90 | *chase.append() = span; |
| 91 | #endif |
| 92 | return first; |
| 93 | } |
| 94 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 95 | return nullptr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 96 | } |
| 97 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 98 | static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 99 | const int xorMask, const int xorOpMask, SkPathWriter* simple) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 100 | bool unsortable = false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 101 | do { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 102 | SkOpSpan* span = FindSortableTop(contourList); |
| 103 | if (!span) { |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 104 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 105 | } |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 106 | SkOpSegment* current = span->segment(); |
| 107 | SkOpSpanBase* start = span->next(); |
| 108 | SkOpSpanBase* end = span; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 109 | SkTDArray<SkOpSpanBase*> chase; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 110 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 111 | if (current->activeOp(start, end, xorMask, xorOpMask, op)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 112 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 113 | if (!unsortable && current->done()) { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 114 | break; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 115 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 116 | SkASSERT(unsortable || !current->done()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 117 | SkOpSpanBase* nextStart = start; |
| 118 | SkOpSpanBase* nextEnd = end; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 119 | SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 120 | &unsortable, op, xorMask, xorOpMask); |
| 121 | if (!next) { |
| 122 | if (!unsortable && simple->hasMove() |
| 123 | && current->verb() != SkPath::kLine_Verb |
| 124 | && !simple->isClosed()) { |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 125 | if (!current->addCurveTo(start, end, simple)) { |
| 126 | return false; |
| 127 | } |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 128 | if (!simple->isClosed()) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 129 | SkPathOpsDebug::ShowActiveSpans(contourList); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 130 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 131 | } |
| 132 | break; |
| 133 | } |
| 134 | #if DEBUG_FLOW |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 135 | SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, |
| 136 | current->debugID(), start->pt().fX, start->pt().fY, |
| 137 | end->pt().fX, end->pt().fY); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 138 | #endif |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 139 | if (!current->addCurveTo(start, end, simple)) { |
| 140 | return false; |
| 141 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 142 | current = next; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 143 | start = nextStart; |
| 144 | end = nextEnd; |
| 145 | } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); |
| 146 | if (current->activeWinding(start, end) && !simple->isClosed()) { |
| 147 | SkOpSpan* spanStart = start->starter(end); |
| 148 | if (!spanStart->done()) { |
caryclark | ef784fb | 2015-10-30 12:03:06 -0700 | [diff] [blame] | 149 | if (!current->addCurveTo(start, end, simple)) { |
| 150 | return false; |
| 151 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 152 | current->markDone(spanStart); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 153 | } |
| 154 | } |
caryclark | eed356d | 2016-09-14 07:18:20 -0700 | [diff] [blame] | 155 | simple->finishContour(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 156 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 157 | SkOpSpanBase* last = current->markAndChaseDone(start, end); |
| 158 | if (last && !last->chased()) { |
| 159 | last->setChased(true); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 160 | SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); |
| 161 | *chase.append() = last; |
| 162 | #if DEBUG_WINDING |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 163 | SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); |
| 164 | if (!last->final()) { |
| 165 | SkDebugf(" windSum=%d", last->upCast()->windSum()); |
| 166 | } |
| 167 | SkDebugf("\n"); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 168 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 169 | } |
| 170 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 171 | current = findChaseOp(chase, &start, &end); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 172 | SkPathOpsDebug::ShowActiveSpans(contourList); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 173 | if (!current) { |
| 174 | break; |
| 175 | } |
| 176 | } while (true); |
| 177 | } while (true); |
caryclark | eed356d | 2016-09-14 07:18:20 -0700 | [diff] [blame] | 178 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 179 | } |
| 180 | |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 181 | // pretty picture: |
| 182 | // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 183 | static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = { |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 184 | // inside minuend outside minuend |
| 185 | // inside subtrahend outside subtrahend inside subtrahend outside subtrahend |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 186 | {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }}, |
| 187 | {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }}, |
| 188 | {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }}, |
| 189 | {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }}, |
| 190 | {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }}, |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 191 | }; |
| 192 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 193 | static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = { |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 194 | {{ false, false }, { true, false }}, // diff |
| 195 | {{ false, false }, { false, true }}, // sect |
| 196 | {{ false, true }, { true, true }}, // union |
| 197 | {{ false, true }, { true, false }}, // xor |
| 198 | {{ false, true }, { false, false }}, // rev diff |
| 199 | }; |
| 200 | |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 201 | #if DEBUG_T_SECT_LOOP_COUNT |
| 202 | |
| 203 | #include "SkMutex.h" |
| 204 | |
reed | 086eea9 | 2016-05-04 17:12:46 -0700 | [diff] [blame] | 205 | SK_DECLARE_STATIC_MUTEX(debugWorstLoop); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 206 | |
Cary Clark | ab87d7a | 2016-10-04 10:01:04 -0400 | [diff] [blame] | 207 | SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr) |
| 208 | SkDEBUGPARAMS(nullptr)); |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 209 | |
| 210 | void ReportPathOpsDebugging() { |
| 211 | debugWorstState.debugLoopReport(); |
| 212 | } |
| 213 | |
| 214 | extern void (*gVerboseFinalize)(); |
| 215 | |
| 216 | #endif |
| 217 | |
caryclark | 3f0753d | 2016-06-28 09:23:57 -0700 | [diff] [blame] | 218 | bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result |
| 219 | SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { |
Florin Malita | 14a6430 | 2017-05-24 14:53:44 -0400 | [diff] [blame] | 220 | SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 221 | SkOpContour contour; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 222 | SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 223 | SkOpGlobalState globalState(contourList, &allocator |
| 224 | SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName)); |
| 225 | SkOpCoincidence coincidence(&globalState); |
Cary Clark | 918fb1f | 2016-11-15 13:22:25 -0500 | [diff] [blame] | 226 | #if DEBUG_DUMP_VERIFY |
| 227 | #ifndef SK_DEBUG |
| 228 | const char* testName = "release"; |
| 229 | #endif |
caryclark | 1326068 | 2016-10-24 05:10:14 -0700 | [diff] [blame] | 230 | if (SkPathOpsDebug::gDumpOp) { |
| 231 | SkPathOpsDebug::DumpOp(one, two, op, testName); |
| 232 | } |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 233 | #endif |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 234 | op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 235 | SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] |
| 236 | ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 237 | SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two)); |
| 238 | SkPath scaledOne, scaledTwo; |
| 239 | const SkPath* minuend, * subtrahend; |
| 240 | if (scaleFactor > SK_Scalar1) { |
| 241 | ScalePath(one, 1.f / scaleFactor, &scaledOne); |
| 242 | minuend = &scaledOne; |
| 243 | ScalePath(two, 1.f / scaleFactor, &scaledTwo); |
| 244 | subtrahend = &scaledTwo; |
| 245 | } else { |
| 246 | minuend = &one; |
| 247 | subtrahend = &two; |
| 248 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 249 | if (op == kReverseDifference_SkPathOp) { |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 250 | SkTSwap(minuend, subtrahend); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 251 | op = kDifference_SkPathOp; |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 252 | } |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 253 | #if DEBUG_SORT |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 254 | SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 255 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 256 | // turn path into list of segments |
caryclark | eed356d | 2016-09-14 07:18:20 -0700 | [diff] [blame] | 257 | SkOpEdgeBuilder builder(*minuend, contourList, &globalState); |
caryclark | d751ac0 | 2014-10-03 05:36:27 -0700 | [diff] [blame] | 258 | if (builder.unparseable()) { |
| 259 | return false; |
| 260 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 261 | const int xorMask = builder.xorMask(); |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 262 | builder.addOperand(*subtrahend); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 263 | if (!builder.finish()) { |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 264 | return false; |
| 265 | } |
caryclark | 03b03ca | 2015-04-23 09:13:37 -0700 | [diff] [blame] | 266 | #if DEBUG_DUMP_SEGMENTS |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 267 | contourList->dumpSegments("seg", op); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 268 | #endif |
| 269 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 270 | const int xorOpMask = builder.xorMask(); |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 271 | if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, |
| 272 | xorOpMask == kEvenOdd_PathOpsMask)) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 273 | result->reset(); |
| 274 | result->setFillType(fillType); |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 275 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 276 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 277 | // find all intersections between segments |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 278 | SkOpContour* current = contourList; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 279 | do { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 280 | SkOpContour* next = current; |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 281 | while (AddIntersectTs(current, next, &coincidence) |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 282 | && (next = next->next())) |
| 283 | ; |
| 284 | } while ((current = current->next())); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 285 | #if DEBUG_VALIDATE |
Cary Clark | ab87d7a | 2016-10-04 10:01:04 -0400 | [diff] [blame] | 286 | globalState.setPhase(SkOpPhase::kWalking); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 287 | #endif |
Cary Clark | ab87d7a | 2016-10-04 10:01:04 -0400 | [diff] [blame] | 288 | bool success = HandleCoincidence(contourList, &coincidence); |
| 289 | #if DEBUG_COIN |
| 290 | globalState.debugAddToGlobalCoinDicts(); |
| 291 | #endif |
| 292 | if (!success) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 293 | return false; |
| 294 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 295 | #if DEBUG_ALIGNMENT |
| 296 | contourList->dumpSegments("aligned"); |
| 297 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 298 | // construct closed contours |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 299 | result->reset(); |
| 300 | result->setFillType(fillType); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 301 | SkPathWriter wrapper(*result); |
caryclark | eed356d | 2016-09-14 07:18:20 -0700 | [diff] [blame] | 302 | if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) { |
| 303 | return false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 304 | } |
caryclark | eed356d | 2016-09-14 07:18:20 -0700 | [diff] [blame] | 305 | wrapper.assemble(); // if some edges could not be resolved, assemble remaining |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 306 | #if DEBUG_T_SECT_LOOP_COUNT |
| 307 | { |
| 308 | SkAutoMutexAcquire autoM(debugWorstLoop); |
| 309 | if (!gVerboseFinalize) { |
| 310 | gVerboseFinalize = &ReportPathOpsDebugging; |
| 311 | } |
| 312 | debugWorstState.debugDoYourWorst(&globalState); |
| 313 | } |
| 314 | #endif |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 315 | if (scaleFactor > 1) { |
| 316 | ScalePath(*result, scaleFactor, result); |
| 317 | } |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 318 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 319 | } |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 320 | |
| 321 | bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { |
Cary Clark | 918fb1f | 2016-11-15 13:22:25 -0500 | [diff] [blame] | 322 | #if DEBUG_DUMP_VERIFY |
caryclark | 1326068 | 2016-10-24 05:10:14 -0700 | [diff] [blame] | 323 | if (SkPathOpsDebug::gVerifyOp) { |
| 324 | if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) { |
| 325 | SkPathOpsDebug::ReportOpFail(one, two, op); |
| 326 | return false; |
| 327 | } |
| 328 | SkPathOpsDebug::VerifyOp(one, two, op, *result); |
| 329 | return true; |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 330 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 331 | #endif |
caryclark | 1326068 | 2016-10-24 05:10:14 -0700 | [diff] [blame] | 332 | return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr)); |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 333 | } |