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