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