1/*
2 * Copyright 2014 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 "src/pathops/SkOpCoincidence.h"
8#include "src/pathops/SkOpContour.h"
9#include "src/pathops/SkOpSegment.h"
10#include "src/pathops/SkPathWriter.h"
11
12bool SkOpPtT::alias() const {
13 return this->span()->ptT() != this;
14}
15
16const SkOpPtT* SkOpPtT::active() const {
17 if (!fDeleted) {
18 return this;
19 }
20 const SkOpPtT* ptT = this;
21 const SkOpPtT* stopPtT = ptT;
22 while ((ptT = ptT->next()) != stopPtT) {
23 if (ptT->fSpan == fSpan && !ptT->fDeleted) {
24 return ptT;
25 }
26 }
27 return nullptr; // should never return deleted; caller must abort
28}
29
30bool SkOpPtT::contains(const SkOpPtT* check) const {
31 SkOPASSERT(this != check);
32 const SkOpPtT* ptT = this;
33 const SkOpPtT* stopPtT = ptT;
34 while ((ptT = ptT->next()) != stopPtT) {
35 if (ptT == check) {
36 return true;
37 }
38 }
39 return false;
40}
41
42bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const {
43 SkASSERT(this->segment() != segment);
44 const SkOpPtT* ptT = this;
45 const SkOpPtT* stopPtT = ptT;
46 while ((ptT = ptT->next()) != stopPtT) {
47 if (ptT->fPt == pt && ptT->segment() == segment) {
48 return true;
49 }
50 }
51 return false;
52}
53
54bool SkOpPtT::contains(const SkOpSegment* segment, double t) const {
55 const SkOpPtT* ptT = this;
56 const SkOpPtT* stopPtT = ptT;
57 while ((ptT = ptT->next()) != stopPtT) {
58 if (ptT->fT == t && ptT->segment() == segment) {
59 return true;
60 }
61 }
62 return false;
63}
64
65const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const {
66 SkASSERT(this->segment() != check);
67 const SkOpPtT* ptT = this;
68 const SkOpPtT* stopPtT = ptT;
69 while ((ptT = ptT->next()) != stopPtT) {
70 if (ptT->segment() == check && !ptT->deleted()) {
71 return ptT;
72 }
73 }
74 return nullptr;
75}
76
77SkOpContour* SkOpPtT::contour() const {
78 return segment()->contour();
79}
80
81const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const {
82 const SkOpPtT* ptT = this;
83 const SkOpPtT* stopPtT = ptT;
84 do {
85 if (ptT->segment() == segment && !ptT->deleted()) {
86 return ptT;
87 }
88 ptT = ptT->fNext;
89 } while (stopPtT != ptT);
90// SkASSERT(0);
91 return nullptr;
92}
93
94SkOpGlobalState* SkOpPtT::globalState() const {
95 return contour()->globalState();
96}
97
98void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
99 fT = t;
100 fPt = pt;
101 fSpan = span;
102 fNext = this;
103 fDuplicatePt = duplicate;
104 fDeleted = false;
105 fCoincident = false;
106 SkDEBUGCODE(fID = span->globalState()->nextPtTID());
107}
108
109bool SkOpPtT::onEnd() const {
110 const SkOpSpanBase* span = this->span();
111 if (span->ptT() != this) {
112 return false;
113 }
114 const SkOpSegment* segment = this->segment();
115 return span == segment->head() || span == segment->tail();
116}
117
118bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const {
119 while (this != check) {
120 if (this->fPt == check->fPt) {
121 return true;
122 }
123 check = check->fNext;
124 }
125 return false;
126}
127
128SkOpPtT* SkOpPtT::prev() {
129 SkOpPtT* result = this;
130 SkOpPtT* next = this;
131 while ((next = next->fNext) != this) {
132 result = next;
133 }
134 SkASSERT(result->fNext == this);
135 return result;
136}
137
138const SkOpSegment* SkOpPtT::segment() const {
139 return span()->segment();
140}
141
142SkOpSegment* SkOpPtT::segment() {
143 return span()->segment();
144}
145
146void SkOpPtT::setDeleted() {
147 SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
148 SkOPASSERT(!fDeleted);
149 fDeleted = true;
150}
151
152bool SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
153 SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
154 if (!oppPrev) {
155 return true;
156 }
157 FAIL_IF(!this->mergeMatches(opp));
158 this->ptT()->addOpp(opp->ptT(), oppPrev);
159 this->checkForCollapsedCoincidence();
160 return true;
161}
162
163SkOpSpanBase::Collapsed SkOpSpanBase::collapsed(double s, double e) const {
164 const SkOpPtT* start = &fPtT;
165 const SkOpPtT* startNext = nullptr;
166 const SkOpPtT* walk = start;
167 double min = walk->fT;
168 double max = min;
169 const SkOpSegment* segment = this->segment();
170 int safetyNet = 100000;
171 while ((walk = walk->next()) != start) {
172 if (!--safetyNet) {
173 return Collapsed::kError;
174 }
175 if (walk == startNext) {
176 return Collapsed::kError;
177 }
178 if (walk->segment() != segment) {
179 continue;
180 }
181 min = std::min(min, walk->fT);
182 max = std::max(max, walk->fT);
183 if (between(min, s, max) && between(min, e, max)) {
184 return Collapsed::kYes;
185 }
186 startNext = start->next();
187 }
188 return Collapsed::kNo;
189}
190
191bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
192 const SkOpPtT* start = &fPtT;
193 const SkOpPtT* check = &span->fPtT;
194 SkOPASSERT(start != check);
195 const SkOpPtT* walk = start;
196 while ((walk = walk->next()) != start) {
197 if (walk == check) {
198 return true;
199 }
200 }
201 return false;
202}
203
204const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const {
205 const SkOpPtT* start = &fPtT;
206 const SkOpPtT* walk = start;
207 while ((walk = walk->next()) != start) {
208 if (walk->deleted()) {
209 continue;
210 }
211 if (walk->segment() == segment && walk->span()->ptT() == walk) {
212 return walk;
213 }
214 }
215 return nullptr;
216}
217
218bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
219 SkASSERT(this->segment() != segment);
220 const SkOpSpanBase* next = this;
221 while ((next = next->fCoinEnd) != this) {
222 if (next->segment() == segment) {
223 return true;
224 }
225 }
226 return false;
227}
228
229SkOpContour* SkOpSpanBase::contour() const {
230 return segment()->contour();
231}
232
233SkOpGlobalState* SkOpSpanBase::globalState() const {
234 return contour()->globalState();
235}
236
237void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
238 fSegment = segment;
239 fPtT.init(this, t, pt, false);
240 fCoinEnd = this;
241 fFromAngle = nullptr;
242 fPrev = prev;
243 fSpanAdds = 0;
244 fAligned = true;
245 fChased = false;
246 SkDEBUGCODE(fCount = 1);
247 SkDEBUGCODE(fID = globalState()->nextSpanID());
248 SkDEBUGCODE(fDebugDeleted = false);
249}
250
251// this pair of spans share a common t value or point; merge them and eliminate duplicates
252// this does not compute the best t or pt value; this merely moves all data into a single list
253void SkOpSpanBase::merge(SkOpSpan* span) {
254 SkOpPtT* spanPtT = span->ptT();
255 SkASSERT(this->t() != spanPtT->fT);
256 SkASSERT(!zero_or_one(spanPtT->fT));
257 span->release(this->ptT());
258 if (this->contains(span)) {
259 SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier
260 return; // merge is already in the ptT loop
261 }
262 SkOpPtT* remainder = spanPtT->next();
263 this->ptT()->insert(spanPtT);
264 while (remainder != spanPtT) {
265 SkOpPtT* next = remainder->next();
266 SkOpPtT* compare = spanPtT->next();
267 while (compare != spanPtT) {
268 SkOpPtT* nextC = compare->next();
269 if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
270 goto tryNextRemainder;
271 }
272 compare = nextC;
273 }
274 spanPtT->insert(remainder);
275tryNextRemainder:
276 remainder = next;
277 }
278 fSpanAdds += span->fSpanAdds;
279}
280
281// please keep in sync with debugCheckForCollapsedCoincidence()
282void SkOpSpanBase::checkForCollapsedCoincidence() {
283 SkOpCoincidence* coins = this->globalState()->coincidence();
284 if (coins->isEmpty()) {
285 return;
286 }
287// the insert above may have put both ends of a coincident run in the same span
288// for each coincident ptT in loop; see if its opposite in is also in the loop
289// this implementation is the motivation for marking that a ptT is referenced by a coincident span
290 SkOpPtT* head = this->ptT();
291 SkOpPtT* test = head;
292 do {
293 if (!test->coincident()) {
294 continue;
295 }
296 coins->markCollapsed(test);
297 } while ((test = test->next()) != head);
298 coins->releaseDeleted();
299}
300
301// please keep in sync with debugMergeMatches()
302// Look to see if pt-t linked list contains same segment more than once
303// if so, and if each pt-t is directly pointed to by spans in that segment,
304// merge them
305// keep the points, but remove spans so that the segment doesn't have 2 or more
306// spans pointing to the same pt-t loop at different loop elements
307bool SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
308 SkOpPtT* test = &fPtT;
309 SkOpPtT* testNext;
310 const SkOpPtT* stop = test;
311 int safetyHatch = 1000000;
312 do {
313 if (!--safetyHatch) {
314 return false;
315 }
316 testNext = test->next();
317 if (test->deleted()) {
318 continue;
319 }
320 SkOpSpanBase* testBase = test->span();
321 SkASSERT(testBase->ptT() == test);
322 SkOpSegment* segment = test->segment();
323 if (segment->done()) {
324 continue;
325 }
326 SkOpPtT* inner = opp->ptT();
327 const SkOpPtT* innerStop = inner;
328 do {
329 if (inner->segment() != segment) {
330 continue;
331 }
332 if (inner->deleted()) {
333 continue;
334 }
335 SkOpSpanBase* innerBase = inner->span();
336 SkASSERT(innerBase->ptT() == inner);
337 // when the intersection is first detected, the span base is marked if there are
338 // more than one point in the intersection.
339 if (!zero_or_one(inner->fT)) {
340 innerBase->upCast()->release(test);
341 } else {
342 SkOPASSERT(inner->fT != test->fT);
343 if (!zero_or_one(test->fT)) {
344 testBase->upCast()->release(inner);
345 } else {
346 segment->markAllDone(); // mark segment as collapsed
347 SkDEBUGCODE(testBase->debugSetDeleted());
348 test->setDeleted();
349 SkDEBUGCODE(innerBase->debugSetDeleted());
350 inner->setDeleted();
351 }
352 }
353#ifdef SK_DEBUG // assert if another undeleted entry points to segment
354 const SkOpPtT* debugInner = inner;
355 while ((debugInner = debugInner->next()) != innerStop) {
356 if (debugInner->segment() != segment) {
357 continue;
358 }
359 if (debugInner->deleted()) {
360 continue;
361 }
362 SkOPASSERT(0);
363 }
364#endif
365 break;
366 } while ((inner = inner->next()) != innerStop);
367 } while ((test = testNext) != stop);
368 this->checkForCollapsedCoincidence();
369 return true;
370}
371
372int SkOpSpan::computeWindSum() {
373 SkOpGlobalState* globals = this->globalState();
374 SkOpContour* contourHead = globals->contourHead();
375 int windTry = 0;
376 while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
377 }
378 return this->windSum();
379}
380
381bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
382 SkASSERT(this->segment() != segment);
383 const SkOpSpan* next = fCoincident;
384 do {
385 if (next->segment() == segment) {
386 return true;
387 }
388 } while ((next = next->fCoincident) != this);
389 return false;
390}
391
392void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
393 SkASSERT(t != 1);
394 initBase(segment, prev, t, pt);
395 fCoincident = this;
396 fToAngle = nullptr;
397 fWindSum = fOppSum = SK_MinS32;
398 fWindValue = 1;
399 fOppValue = 0;
400 fTopTTry = 0;
401 fChased = fDone = false;
402 segment->bumpCount();
403 fAlreadyAdded = false;
404}
405
406// Please keep this in sync with debugInsertCoincidence()
407bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) {
408 if (this->containsCoincidence(segment)) {
409 return true;
410 }
411 SkOpPtT* next = &fPtT;
412 while ((next = next->next()) != &fPtT) {
413 if (next->segment() == segment) {
414 SkOpSpan* span;
415 SkOpSpanBase* base = next->span();
416 if (!ordered) {
417 const SkOpPtT* spanEndPtT = fNext->contains(segment);
418 FAIL_IF(!spanEndPtT);
419 const SkOpSpanBase* spanEnd = spanEndPtT->span();
420 const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
421 FAIL_IF(!start->span()->upCastable());
422 span = const_cast<SkOpSpan*>(start->span()->upCast());
423 } else if (flipped) {
424 span = base->prev();
425 FAIL_IF(!span);
426 } else {
427 FAIL_IF(!base->upCastable());
428 span = base->upCast();
429 }
430 this->insertCoincidence(span);
431 return true;
432 }
433 }
434#if DEBUG_COINCIDENCE
435 SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
436#endif
437 return true;
438}
439
440void SkOpSpan::release(const SkOpPtT* kept) {
441 SkDEBUGCODE(fDebugDeleted = true);
442 SkOPASSERT(kept->span() != this);
443 SkASSERT(!final());
444 SkOpSpan* prev = this->prev();
445 SkASSERT(prev);
446 SkOpSpanBase* next = this->next();
447 SkASSERT(next);
448 prev->setNext(next);
449 next->setPrev(prev);
450 this->segment()->release(this);
451 SkOpCoincidence* coincidence = this->globalState()->coincidence();
452 if (coincidence) {
453 coincidence->fixUp(this->ptT(), kept);
454 }
455 this->ptT()->setDeleted();
456 SkOpPtT* stopPtT = this->ptT();
457 SkOpPtT* testPtT = stopPtT;
458 const SkOpSpanBase* keptSpan = kept->span();
459 do {
460 if (this == testPtT->span()) {
461 testPtT->setSpan(keptSpan);
462 }
463 } while ((testPtT = testPtT->next()) != stopPtT);
464}
465
466void SkOpSpan::setOppSum(int oppSum) {
467 SkASSERT(!final());
468 if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
469 this->globalState()->setWindingFailed();
470 return;
471 }
472 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
473 fOppSum = oppSum;
474}
475
476void SkOpSpan::setWindSum(int windSum) {
477 SkASSERT(!final());
478 if (fWindSum != SK_MinS32 && fWindSum != windSum) {
479 this->globalState()->setWindingFailed();
480 return;
481 }
482 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
483 fWindSum = windSum;
484}
485