Line data Source code
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 :
13 0 : static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
14 : SkOpSpanBase** endPtr) {
15 0 : while (chase.count()) {
16 : SkOpSpanBase* span;
17 0 : chase.pop(&span);
18 : // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
19 0 : *startPtr = span->ptT()->prev()->span();
20 0 : SkOpSegment* segment = (*startPtr)->segment();
21 0 : bool done = true;
22 0 : *endPtr = nullptr;
23 0 : if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
24 0 : *startPtr = last->start();
25 0 : *endPtr = last->end();
26 : #if TRY_ROTATE
27 : *chase.insert(0) = span;
28 : #else
29 0 : *chase.append() = span;
30 : #endif
31 0 : return last->segment();
32 : }
33 0 : if (done) {
34 0 : continue;
35 : }
36 : int winding;
37 : bool sortable;
38 0 : const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
39 0 : if (!angle) {
40 0 : return nullptr;
41 : }
42 0 : if (winding == SK_MinS32) {
43 0 : continue;
44 : }
45 : int sumMiWinding, sumSuWinding;
46 0 : if (sortable) {
47 0 : segment = angle->segment();
48 0 : sumMiWinding = segment->updateWindingReverse(angle);
49 0 : if (sumMiWinding == SK_MinS32) {
50 0 : SkASSERT(segment->globalState()->debugSkipAssert());
51 0 : return nullptr;
52 : }
53 0 : sumSuWinding = segment->updateOppWindingReverse(angle);
54 0 : if (sumSuWinding == SK_MinS32) {
55 0 : SkASSERT(segment->globalState()->debugSkipAssert());
56 0 : return nullptr;
57 : }
58 0 : if (segment->operand()) {
59 0 : SkTSwap<int>(sumMiWinding, sumSuWinding);
60 : }
61 : }
62 0 : SkOpSegment* first = nullptr;
63 0 : const SkOpAngle* firstAngle = angle;
64 0 : while ((angle = angle->next()) != firstAngle) {
65 0 : segment = angle->segment();
66 0 : SkOpSpanBase* start = angle->start();
67 0 : SkOpSpanBase* end = angle->end();
68 : int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
69 0 : if (sortable) {
70 : segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
71 0 : &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
72 : }
73 0 : if (!segment->done(angle)) {
74 0 : if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
75 0 : first = segment;
76 0 : *startPtr = start;
77 0 : *endPtr = end;
78 : }
79 : // OPTIMIZATION: should this also add to the chase?
80 0 : if (sortable) {
81 : (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
82 0 : oppSumWinding, angle);
83 : }
84 : }
85 : }
86 0 : if (first) {
87 : #if TRY_ROTATE
88 : *chase.insert(0) = span;
89 : #else
90 0 : *chase.append() = span;
91 : #endif
92 0 : return first;
93 : }
94 : }
95 0 : return nullptr;
96 : }
97 :
98 0 : static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
99 : const int xorMask, const int xorOpMask, SkPathWriter* simple) {
100 0 : bool unsortable = false;
101 : do {
102 0 : SkOpSpan* span = FindSortableTop(contourList);
103 0 : if (!span) {
104 0 : break;
105 : }
106 0 : SkOpSegment* current = span->segment();
107 0 : SkOpSpanBase* start = span->next();
108 0 : SkOpSpanBase* end = span;
109 0 : SkTDArray<SkOpSpanBase*> chase;
110 : do {
111 0 : if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
112 0 : do {
113 0 : if (!unsortable && current->done()) {
114 0 : break;
115 : }
116 0 : SkASSERT(unsortable || !current->done());
117 0 : SkOpSpanBase* nextStart = start;
118 0 : SkOpSpanBase* nextEnd = end;
119 : SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
120 0 : &unsortable, op, xorMask, xorOpMask);
121 0 : if (!next) {
122 0 : if (!unsortable && simple->hasMove()
123 0 : && current->verb() != SkPath::kLine_Verb
124 0 : && !simple->isClosed()) {
125 0 : if (!current->addCurveTo(start, end, simple)) {
126 0 : return false;
127 : }
128 0 : if (!simple->isClosed()) {
129 0 : SkPathOpsDebug::ShowActiveSpans(contourList);
130 : }
131 : }
132 0 : 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 0 : if (!current->addCurveTo(start, end, simple)) {
140 0 : return false;
141 : }
142 0 : current = next;
143 0 : start = nextStart;
144 0 : end = nextEnd;
145 0 : } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
146 0 : if (current->activeWinding(start, end) && !simple->isClosed()) {
147 0 : SkOpSpan* spanStart = start->starter(end);
148 0 : if (!spanStart->done()) {
149 0 : if (!current->addCurveTo(start, end, simple)) {
150 0 : return false;
151 : }
152 0 : current->markDone(spanStart);
153 : }
154 : }
155 0 : simple->finishContour();
156 : } else {
157 0 : SkOpSpanBase* last = current->markAndChaseDone(start, end);
158 0 : if (last && !last->chased()) {
159 0 : last->setChased(true);
160 0 : SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
161 0 : *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 0 : current = findChaseOp(chase, &start, &end);
172 0 : SkPathOpsDebug::ShowActiveSpans(contourList);
173 0 : if (!current) {
174 0 : break;
175 0 : }
176 0 : } while (true);
177 : } while (true);
178 0 : return true;
179 : }
180 :
181 : // pretty picture:
182 : // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
183 : static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
184 : // inside minuend outside minuend
185 : // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
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 }},
191 : };
192 :
193 : static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
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 :
201 : #if DEBUG_T_SECT_LOOP_COUNT
202 :
203 : #include "SkMutex.h"
204 :
205 : SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
206 :
207 : SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr)
208 : SkDEBUGPARAMS(nullptr));
209 :
210 : void ReportPathOpsDebugging() {
211 : debugWorstState.debugLoopReport();
212 : }
213 :
214 : extern void (*gVerboseFinalize)();
215 :
216 : #endif
217 :
218 0 : bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
219 : SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
220 : char storage[4096];
221 0 : SkArenaAlloc allocator(storage); // FIXME: add a constant expression here, tune
222 0 : SkOpContour contour;
223 0 : SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
224 : SkOpGlobalState globalState(contourList, &allocator
225 0 : SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
226 0 : 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 0 : op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
236 0 : SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
237 0 : ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
238 0 : SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two));
239 0 : SkPath scaledOne, scaledTwo;
240 : const SkPath* minuend, * subtrahend;
241 0 : if (scaleFactor > SK_Scalar1) {
242 0 : ScalePath(one, 1.f / scaleFactor, &scaledOne);
243 0 : minuend = &scaledOne;
244 0 : ScalePath(two, 1.f / scaleFactor, &scaledTwo);
245 0 : subtrahend = &scaledTwo;
246 : } else {
247 0 : minuend = &one;
248 0 : subtrahend = &two;
249 : }
250 0 : if (op == kReverseDifference_SkPathOp) {
251 0 : SkTSwap(minuend, subtrahend);
252 0 : op = kDifference_SkPathOp;
253 : }
254 : #if DEBUG_SORT
255 : SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
256 : #endif
257 : // turn path into list of segments
258 0 : SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
259 0 : if (builder.unparseable()) {
260 0 : return false;
261 : }
262 0 : const int xorMask = builder.xorMask();
263 0 : builder.addOperand(*subtrahend);
264 0 : if (!builder.finish()) {
265 0 : return false;
266 : }
267 : #if DEBUG_DUMP_SEGMENTS
268 : contourList->dumpSegments("seg", op);
269 : #endif
270 :
271 0 : const int xorOpMask = builder.xorMask();
272 0 : if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
273 : xorOpMask == kEvenOdd_PathOpsMask)) {
274 0 : result->reset();
275 0 : result->setFillType(fillType);
276 0 : return true;
277 : }
278 : // find all intersections between segments
279 0 : SkOpContour* current = contourList;
280 0 : do {
281 0 : SkOpContour* next = current;
282 0 : while (AddIntersectTs(current, next, &coincidence)
283 0 : && (next = next->next()))
284 : ;
285 : } while ((current = current->next()));
286 : #if DEBUG_VALIDATE
287 : globalState.setPhase(SkOpPhase::kWalking);
288 : #endif
289 0 : bool success = HandleCoincidence(contourList, &coincidence);
290 : #if DEBUG_COIN
291 : globalState.debugAddToGlobalCoinDicts();
292 : #endif
293 0 : if (!success) {
294 0 : return false;
295 : }
296 : #if DEBUG_ALIGNMENT
297 : contourList->dumpSegments("aligned");
298 : #endif
299 : // construct closed contours
300 0 : result->reset();
301 0 : result->setFillType(fillType);
302 0 : SkPathWriter wrapper(*result);
303 0 : if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
304 0 : return false;
305 : }
306 0 : 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 0 : if (scaleFactor > 1) {
317 0 : ScalePath(*result, scaleFactor, result);
318 : }
319 0 : return true;
320 : }
321 :
322 0 : 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 0 : return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
334 : }
|
