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