1/*
2 * Copyright 2015 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/SkOpSegment.h"
9#include "src/pathops/SkPathOpsTSect.h"
10
11#include <utility>
12
13// returns true if coincident span's start and end are the same
14bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
15 return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
16 || (fCoinPtTEnd == test && fCoinPtTStart->contains(test))
17 || (fOppPtTStart == test && fOppPtTEnd->contains(test))
18 || (fOppPtTEnd == test && fOppPtTStart->contains(test));
19}
20
21// out of line since this function is referenced by address
22const SkOpPtT* SkCoincidentSpans::coinPtTEnd() const {
23 return fCoinPtTEnd;
24}
25
26// out of line since this function is referenced by address
27const SkOpPtT* SkCoincidentSpans::coinPtTStart() const {
28 return fCoinPtTStart;
29}
30
31// sets the span's end to the ptT referenced by the previous-next
32void SkCoincidentSpans::correctOneEnd(
33 const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
34 void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) {
35 const SkOpPtT* origPtT = (this->*getEnd)();
36 const SkOpSpanBase* origSpan = origPtT->span();
37 const SkOpSpan* prev = origSpan->prev();
38 const SkOpPtT* testPtT = prev ? prev->next()->ptT()
39 : origSpan->upCast()->next()->prev()->ptT();
40 if (origPtT != testPtT) {
41 (this->*setEnd)(testPtT);
42 }
43}
44
45/* Please keep this in sync with debugCorrectEnds */
46// FIXME: member pointers have fallen out of favor and can be replaced with
47// an alternative approach.
48// makes all span ends agree with the segment's spans that define them
49void SkCoincidentSpans::correctEnds() {
50 this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart);
51 this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd);
52 this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart);
53 this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd);
54}
55
56/* Please keep this in sync with debugExpand */
57// expand the range by checking adjacent spans for coincidence
58bool SkCoincidentSpans::expand() {
59 bool expanded = false;
60 const SkOpSegment* segment = coinPtTStart()->segment();
61 const SkOpSegment* oppSegment = oppPtTStart()->segment();
62 do {
63 const SkOpSpan* start = coinPtTStart()->span()->upCast();
64 const SkOpSpan* prev = start->prev();
65 const SkOpPtT* oppPtT;
66 if (!prev || !(oppPtT = prev->contains(oppSegment))) {
67 break;
68 }
69 double midT = (prev->t() + start->t()) / 2;
70 if (!segment->isClose(midT, oppSegment)) {
71 break;
72 }
73 setStarts(prev->ptT(), oppPtT);
74 expanded = true;
75 } while (true);
76 do {
77 const SkOpSpanBase* end = coinPtTEnd()->span();
78 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
79 if (next && next->deleted()) {
80 break;
81 }
82 const SkOpPtT* oppPtT;
83 if (!next || !(oppPtT = next->contains(oppSegment))) {
84 break;
85 }
86 double midT = (end->t() + next->t()) / 2;
87 if (!segment->isClose(midT, oppSegment)) {
88 break;
89 }
90 setEnds(next->ptT(), oppPtT);
91 expanded = true;
92 } while (true);
93 return expanded;
94}
95
96// increase the range of this span
97bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
98 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
99 bool result = false;
100 if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped()
101 ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) {
102 this->setStarts(coinPtTStart, oppPtTStart);
103 result = true;
104 }
105 if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped()
106 ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) {
107 this->setEnds(coinPtTEnd, oppPtTEnd);
108 result = true;
109 }
110 return result;
111}
112
113// set the range of this span
114void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart,
115 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
116 SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart));
117 fNext = next;
118 this->setStarts(coinPtTStart, oppPtTStart);
119 this->setEnds(coinPtTEnd, oppPtTEnd);
120}
121
122// returns true if both points are inside this
123bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const {
124 if (s->fT > e->fT) {
125 using std::swap;
126 swap(s, e);
127 }
128 if (s->segment() == fCoinPtTStart->segment()) {
129 return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT;
130 } else {
131 SkASSERT(s->segment() == fOppPtTStart->segment());
132 double oppTs = fOppPtTStart->fT;
133 double oppTe = fOppPtTEnd->fT;
134 if (oppTs > oppTe) {
135 using std::swap;
136 swap(oppTs, oppTe);
137 }
138 return oppTs <= s->fT && e->fT <= oppTe;
139 }
140}
141
142// out of line since this function is referenced by address
143const SkOpPtT* SkCoincidentSpans::oppPtTStart() const {
144 return fOppPtTStart;
145}
146
147// out of line since this function is referenced by address
148const SkOpPtT* SkCoincidentSpans::oppPtTEnd() const {
149 return fOppPtTEnd;
150}
151
152// A coincident span is unordered if the pairs of points in the main and opposite curves'
153// t values do not ascend or descend. For instance, if a tightly arced quadratic is
154// coincident with another curve, it may intersect it out of order.
155bool SkCoincidentSpans::ordered(bool* result) const {
156 const SkOpSpanBase* start = this->coinPtTStart()->span();
157 const SkOpSpanBase* end = this->coinPtTEnd()->span();
158 const SkOpSpanBase* next = start->upCast()->next();
159 if (next == end) {
160 *result = true;
161 return true;
162 }
163 bool flipped = this->flipped();
164 const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
165 double oppLastT = fOppPtTStart->fT;
166 do {
167 const SkOpPtT* opp = next->contains(oppSeg);
168 if (!opp) {
169// SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed
170 return false;
171 }
172 if ((oppLastT > opp->fT) != flipped) {
173 *result = false;
174 return true;
175 }
176 oppLastT = opp->fT;
177 if (next == end) {
178 break;
179 }
180 if (!next->upCastable()) {
181 *result = false;
182 return true;
183 }
184 next = next->upCast()->next();
185 } while (true);
186 *result = true;
187 return true;
188}
189
190// if there is an existing pair that overlaps the addition, extend it
191bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
192 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
193 SkCoincidentSpans* test = fHead;
194 if (!test) {
195 return false;
196 }
197 const SkOpSegment* coinSeg = coinPtTStart->segment();
198 const SkOpSegment* oppSeg = oppPtTStart->segment();
199 if (!Ordered(coinPtTStart, oppPtTStart)) {
200 using std::swap;
201 swap(coinSeg, oppSeg);
202 swap(coinPtTStart, oppPtTStart);
203 swap(coinPtTEnd, oppPtTEnd);
204 if (coinPtTStart->fT > coinPtTEnd->fT) {
205 swap(coinPtTStart, coinPtTEnd);
206 swap(oppPtTStart, oppPtTEnd);
207 }
208 }
209 double oppMinT = std::min(oppPtTStart->fT, oppPtTEnd->fT);
210 SkDEBUGCODE(double oppMaxT = std::max(oppPtTStart->fT, oppPtTEnd->fT));
211 do {
212 if (coinSeg != test->coinPtTStart()->segment()) {
213 continue;
214 }
215 if (oppSeg != test->oppPtTStart()->segment()) {
216 continue;
217 }
218 double oTestMinT = std::min(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
219 double oTestMaxT = std::max(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
220 // if debug check triggers, caller failed to check if extended already exists
221 SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT
222 || coinPtTEnd->fT > test->coinPtTEnd()->fT
223 || oTestMinT > oppMinT || oppMaxT > oTestMaxT);
224 if ((test->coinPtTStart()->fT <= coinPtTEnd->fT
225 && coinPtTStart->fT <= test->coinPtTEnd()->fT)
226 || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) {
227 test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
228 return true;
229 }
230 } while ((test = test->next()));
231 return false;
232}
233
234// verifies that the coincidence hasn't already been added
235static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart,
236 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
237#if DEBUG_COINCIDENCE
238 while (check) {
239 SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd
240 || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd);
241 SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd
242 || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd);
243 check = check->next();
244 }
245#endif
246}
247
248// adds a new coincident pair
249void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
250 SkOpPtT* oppPtTEnd) {
251 // OPTIMIZE: caller should have already sorted
252 if (!Ordered(coinPtTStart, oppPtTStart)) {
253 if (oppPtTStart->fT < oppPtTEnd->fT) {
254 this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd);
255 } else {
256 this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
257 }
258 return;
259 }
260 SkASSERT(Ordered(coinPtTStart, oppPtTStart));
261 // choose the ptT at the front of the list to track
262 coinPtTStart = coinPtTStart->span()->ptT();
263 coinPtTEnd = coinPtTEnd->span()->ptT();
264 oppPtTStart = oppPtTStart->span()->ptT();
265 oppPtTEnd = oppPtTEnd->span()->ptT();
266 SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT);
267 SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT);
268 SkOPASSERT(!coinPtTStart->deleted());
269 SkOPASSERT(!coinPtTEnd->deleted());
270 SkOPASSERT(!oppPtTStart->deleted());
271 SkOPASSERT(!oppPtTEnd->deleted());
272 DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
273 DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
274 SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>();
275 coinRec->init(SkDEBUGCODE(fGlobalState));
276 coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
277 fHead = coinRec;
278}
279
280// description below
281bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) {
282 const SkOpPtT* testPtT = testSpan->ptT();
283 const SkOpPtT* stopPtT = testPtT;
284 const SkOpSegment* baseSeg = base->segment();
285 int escapeHatch = 100000; // this is 100 times larger than the debugLoopLimit test
286 while ((testPtT = testPtT->next()) != stopPtT) {
287 if (--escapeHatch <= 0) {
288 return false; // if triggered (likely by a fuzz-generated test) too complex to succeed
289 }
290 const SkOpSegment* testSeg = testPtT->segment();
291 if (testPtT->deleted()) {
292 continue;
293 }
294 if (testSeg == baseSeg) {
295 continue;
296 }
297 if (testPtT->span()->ptT() != testPtT) {
298 continue;
299 }
300 if (this->contains(baseSeg, testSeg, testPtT->fT)) {
301 continue;
302 }
303 // intersect perp with base->ptT() with testPtT->segment()
304 SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
305 const SkPoint& pt = base->pt();
306 SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
307 SkIntersections i SkDEBUGCODE((this->globalState()));
308 (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
309 for (int index = 0; index < i.used(); ++index) {
310 double t = i[0][index];
311 if (!between(0, t, 1)) {
312 continue;
313 }
314 SkDPoint oppPt = i.pt(index);
315 if (!oppPt.approximatelyEqual(pt)) {
316 continue;
317 }
318 SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
319 SkOpPtT* oppStart = writableSeg->addT(t);
320 if (oppStart == testPtT) {
321 continue;
322 }
323 SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
324 oppStart->span()->addOpp(writableBase);
325 if (oppStart->deleted()) {
326 continue;
327 }
328 SkOpSegment* coinSeg = base->segment();
329 SkOpSegment* oppSeg = oppStart->segment();
330 double coinTs, coinTe, oppTs, oppTe;
331 if (Ordered(coinSeg, oppSeg)) {
332 coinTs = base->t();
333 coinTe = testSpan->t();
334 oppTs = oppStart->fT;
335 oppTe = testPtT->fT;
336 } else {
337 using std::swap;
338 swap(coinSeg, oppSeg);
339 coinTs = oppStart->fT;
340 coinTe = testPtT->fT;
341 oppTs = base->t();
342 oppTe = testSpan->t();
343 }
344 if (coinTs > coinTe) {
345 using std::swap;
346 swap(coinTs, coinTe);
347 swap(oppTs, oppTe);
348 }
349 bool added;
350 FAIL_IF(!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added));
351 }
352 }
353 return true;
354}
355
356// description below
357bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
358 FAIL_IF(!ptT->span()->upCastable());
359 const SkOpSpan* base = ptT->span()->upCast();
360 const SkOpSpan* prev = base->prev();
361 FAIL_IF(!prev);
362 if (!prev->isCanceled()) {
363 if (!this->addEndMovedSpans(base, base->prev())) {
364 return false;
365 }
366 }
367 if (!base->isCanceled()) {
368 if (!this->addEndMovedSpans(base, base->next())) {
369 return false;
370 }
371 }
372 return true;
373}
374
375/* If A is coincident with B and B includes an endpoint, and A's matching point
376 is not the endpoint (i.e., there's an implied line connecting B-end and A)
377 then assume that the same implied line may intersect another curve close to B.
378 Since we only care about coincidence that was undetected, look at the
379 ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
380 next door) and see if the A matching point is close enough to form another
381 coincident pair. If so, check for a new coincident span between B-end/A ptT loop
382 and the adjacent ptT loop.
383*/
384bool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
385 DEBUG_SET_PHASE();
386 SkCoincidentSpans* span = fHead;
387 if (!span) {
388 return true;
389 }
390 fTop = span;
391 fHead = nullptr;
392 do {
393 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
394 FAIL_IF(1 == span->coinPtTStart()->fT);
395 bool onEnd = span->coinPtTStart()->fT == 0;
396 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
397 if (onEnd) {
398 if (!oOnEnd) { // if both are on end, any nearby intersect was already found
399 if (!this->addEndMovedSpans(span->oppPtTStart())) {
400 return false;
401 }
402 }
403 } else if (oOnEnd) {
404 if (!this->addEndMovedSpans(span->coinPtTStart())) {
405 return false;
406 }
407 }
408 }
409 if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
410 bool onEnd = span->coinPtTEnd()->fT == 1;
411 bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
412 if (onEnd) {
413 if (!oOnEnd) {
414 if (!this->addEndMovedSpans(span->oppPtTEnd())) {
415 return false;
416 }
417 }
418 } else if (oOnEnd) {
419 if (!this->addEndMovedSpans(span->coinPtTEnd())) {
420 return false;
421 }
422 }
423 }
424 } while ((span = span->next()));
425 this->restoreHead();
426 return true;
427}
428
429/* Please keep this in sync with debugAddExpanded */
430// for each coincident pair, match the spans
431// if the spans don't match, add the missing pt to the segment and loop it in the opposite span
432bool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
433 DEBUG_SET_PHASE();
434 SkCoincidentSpans* coin = this->fHead;
435 if (!coin) {
436 return true;
437 }
438 do {
439 const SkOpPtT* startPtT = coin->coinPtTStart();
440 const SkOpPtT* oStartPtT = coin->oppPtTStart();
441 double priorT = startPtT->fT;
442 double oPriorT = oStartPtT->fT;
443 FAIL_IF(!startPtT->contains(oStartPtT));
444 SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
445 const SkOpSpanBase* start = startPtT->span();
446 const SkOpSpanBase* oStart = oStartPtT->span();
447 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
448 const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
449 FAIL_IF(oEnd->deleted());
450 FAIL_IF(!start->upCastable());
451 const SkOpSpanBase* test = start->upCast()->next();
452 FAIL_IF(!coin->flipped() && !oStart->upCastable());
453 const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
454 FAIL_IF(!oTest);
455 SkOpSegment* seg = start->segment();
456 SkOpSegment* oSeg = oStart->segment();
457 while (test != end || oTest != oEnd) {
458 const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
459 const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
460 if (!containedOpp || !containedThis) {
461 // choose the ends, or the first common pt-t list shared by both
462 double nextT, oNextT;
463 if (containedOpp) {
464 nextT = test->t();
465 oNextT = containedOpp->fT;
466 } else if (containedThis) {
467 nextT = containedThis->fT;
468 oNextT = oTest->t();
469 } else {
470 // iterate through until a pt-t list found that contains the other
471 const SkOpSpanBase* walk = test;
472 const SkOpPtT* walkOpp;
473 do {
474 FAIL_IF(!walk->upCastable());
475 walk = walk->upCast()->next();
476 } while (!(walkOpp = walk->ptT()->contains(oSeg))
477 && walk != coin->coinPtTEnd()->span());
478 FAIL_IF(!walkOpp);
479 nextT = walk->t();
480 oNextT = walkOpp->fT;
481 }
482 // use t ranges to guess which one is missing
483 double startRange = nextT - priorT;
484 FAIL_IF(!startRange);
485 double startPart = (test->t() - priorT) / startRange;
486 double oStartRange = oNextT - oPriorT;
487 FAIL_IF(!oStartRange);
488 double oStartPart = (oTest->t() - oPriorT) / oStartRange;
489 FAIL_IF(startPart == oStartPart);
490 bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
491 : !!containedThis;
492 bool startOver = false;
493 bool success = addToOpp ? oSeg->addExpanded(
494 oPriorT + oStartRange * startPart, test, &startOver)
495 : seg->addExpanded(
496 priorT + startRange * oStartPart, oTest, &startOver);
497 FAIL_IF(!success);
498 if (startOver) {
499 test = start;
500 oTest = oStart;
501 }
502 end = coin->coinPtTEnd()->span();
503 oEnd = coin->oppPtTEnd()->span();
504 }
505 if (test != end) {
506 FAIL_IF(!test->upCastable());
507 priorT = test->t();
508 test = test->upCast()->next();
509 }
510 if (oTest != oEnd) {
511 oPriorT = oTest->t();
512 if (coin->flipped()) {
513 oTest = oTest->prev();
514 } else {
515 FAIL_IF(!oTest->upCastable());
516 oTest = oTest->upCast()->next();
517 }
518 FAIL_IF(!oTest);
519 }
520
521 }
522 } while ((coin = coin->next()));
523 return true;
524}
525
526// given a t span, map the same range on the coincident span
527/*
528the curves may not scale linearly, so interpolation may only happen within known points
529remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
530then repeat to capture over1e
531*/
532double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
533 const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) {
534 const SkOpSpanBase* work = overS->span();
535 const SkOpPtT* foundStart = nullptr;
536 const SkOpPtT* foundEnd = nullptr;
537 const SkOpPtT* coinStart = nullptr;
538 const SkOpPtT* coinEnd = nullptr;
539 do {
540 const SkOpPtT* contained = work->contains(coinSeg);
541 if (!contained) {
542 if (work->final()) {
543 break;
544 }
545 continue;
546 }
547 if (work->t() <= t) {
548 coinStart = contained;
549 foundStart = work->ptT();
550 }
551 if (work->t() >= t) {
552 coinEnd = contained;
553 foundEnd = work->ptT();
554 break;
555 }
556 SkASSERT(work->ptT() != overE);
557 } while ((work = work->upCast()->next()));
558 if (!coinStart || !coinEnd) {
559 return 1;
560 }
561 // while overS->fT <=t and overS contains coinSeg
562 double denom = foundEnd->fT - foundStart->fT;
563 double sRatio = denom ? (t - foundStart->fT) / denom : 1;
564 return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
565}
566
567// return true if span overlaps existing and needs to adjust the coincident list
568bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
569 const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
570 double coinTs, double coinTe, double oppTs, double oppTe,
571 SkTDArray<SkCoincidentSpans*>* overlaps) const {
572 if (!Ordered(coinSeg, oppSeg)) {
573 if (oppTs < oppTe) {
574 return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe,
575 overlaps);
576 }
577 return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps);
578 }
579 bool swapOpp = oppTs > oppTe;
580 if (swapOpp) {
581 using std::swap;
582 swap(oppTs, oppTe);
583 }
584 do {
585 if (check->coinPtTStart()->segment() != coinSeg) {
586 continue;
587 }
588 if (check->oppPtTStart()->segment() != oppSeg) {
589 continue;
590 }
591 double checkTs = check->coinPtTStart()->fT;
592 double checkTe = check->coinPtTEnd()->fT;
593 bool coinOutside = coinTe < checkTs || coinTs > checkTe;
594 double oCheckTs = check->oppPtTStart()->fT;
595 double oCheckTe = check->oppPtTEnd()->fT;
596 if (swapOpp) {
597 if (oCheckTs <= oCheckTe) {
598 return false;
599 }
600 using std::swap;
601 swap(oCheckTs, oCheckTe);
602 }
603 bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
604 if (coinOutside && oppOutside) {
605 continue;
606 }
607 bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
608 bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
609 if (coinInside && oppInside) { // already included, do nothing
610 return false;
611 }
612 *overlaps->append() = check; // partial overlap, extend existing entry
613 } while ((check = check->next()));
614 return true;
615}
616
617/* Please keep this in sync with debugAddIfMissing() */
618// note that over1s, over1e, over2s, over2e are ordered
619bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
620 double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added
621 SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
622 SkASSERT(tStart < tEnd);
623 SkASSERT(over1s->fT < over1e->fT);
624 SkASSERT(between(over1s->fT, tStart, over1e->fT));
625 SkASSERT(between(over1s->fT, tEnd, over1e->fT));
626 SkASSERT(over2s->fT < over2e->fT);
627 SkASSERT(between(over2s->fT, tStart, over2e->fT));
628 SkASSERT(between(over2s->fT, tEnd, over2e->fT));
629 SkASSERT(over1s->segment() == over1e->segment());
630 SkASSERT(over2s->segment() == over2e->segment());
631 SkASSERT(over1s->segment() == over2s->segment());
632 SkASSERT(over1s->segment() != coinSeg);
633 SkASSERT(over1s->segment() != oppSeg);
634 SkASSERT(coinSeg != oppSeg);
635 double coinTs, coinTe, oppTs, oppTe;
636 coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e));
637 coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e));
638 SkOpSpanBase::Collapsed result = coinSeg->collapsed(coinTs, coinTe);
639 if (SkOpSpanBase::Collapsed::kNo != result) {
640 return SkOpSpanBase::Collapsed::kYes == result;
641 }
642 oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e));
643 oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e));
644 result = oppSeg->collapsed(oppTs, oppTe);
645 if (SkOpSpanBase::Collapsed::kNo != result) {
646 return SkOpSpanBase::Collapsed::kYes == result;
647 }
648 if (coinTs > coinTe) {
649 using std::swap;
650 swap(coinTs, coinTe);
651 swap(oppTs, oppTe);
652 }
653 (void) this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
654 return true;
655}
656
657/* Please keep this in sync with debugAddOrOverlap() */
658// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
659// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
660bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
661 double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
662 SkTDArray<SkCoincidentSpans*> overlaps;
663 FAIL_IF(!fTop);
664 if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
665 return true;
666 }
667 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
668 coinTe, oppTs, oppTe, &overlaps)) {
669 return true;
670 }
671 SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
672 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
673 SkCoincidentSpans* test = overlaps[index];
674 if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
675 overlap->setCoinPtTStart(test->coinPtTStart());
676 }
677 if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
678 overlap->setCoinPtTEnd(test->coinPtTEnd());
679 }
680 if (overlap->flipped()
681 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
682 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
683 overlap->setOppPtTStart(test->oppPtTStart());
684 }
685 if (overlap->flipped()
686 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
687 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
688 overlap->setOppPtTEnd(test->oppPtTEnd());
689 }
690 if (!fHead || !this->release(fHead, test)) {
691 SkAssertResult(this->release(fTop, test));
692 }
693 }
694 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
695 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
696 if (overlap && cs && ce && overlap->contains(cs, ce)) {
697 return true;
698 }
699 FAIL_IF(cs == ce && cs);
700 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
701 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
702 if (overlap && os && oe && overlap->contains(os, oe)) {
703 return true;
704 }
705 FAIL_IF(cs && cs->deleted());
706 FAIL_IF(os && os->deleted());
707 FAIL_IF(ce && ce->deleted());
708 FAIL_IF(oe && oe->deleted());
709 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
710 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
711 FAIL_IF(csExisting && csExisting == ceExisting);
712// FAIL_IF(csExisting && (csExisting == ce ||
713// csExisting->contains(ceExisting ? ceExisting : ce)));
714 FAIL_IF(ceExisting && (ceExisting == cs ||
715 ceExisting->contains(csExisting ? csExisting : cs)));
716 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
717 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
718 FAIL_IF(osExisting && osExisting == oeExisting);
719 FAIL_IF(osExisting && (osExisting == oe ||
720 osExisting->contains(oeExisting ? oeExisting : oe)));
721 FAIL_IF(oeExisting && (oeExisting == os ||
722 oeExisting->contains(osExisting ? osExisting : os)));
723 // extra line in debug code
724 this->debugValidate();
725 if (!cs || !os) {
726 SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
727 : coinSeg->addT(coinTs);
728 if (csWritable == ce) {
729 return true;
730 }
731 SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
732 : oppSeg->addT(oppTs);
733 FAIL_IF(!csWritable || !osWritable);
734 csWritable->span()->addOpp(osWritable->span());
735 cs = csWritable;
736 os = osWritable->active();
737 FAIL_IF(!os);
738 FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted()));
739 }
740 if (!ce || !oe) {
741 SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
742 : coinSeg->addT(coinTe);
743 SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
744 : oppSeg->addT(oppTe);
745 FAIL_IF(!ceWritable->span()->addOpp(oeWritable->span()));
746 ce = ceWritable;
747 oe = oeWritable;
748 }
749 this->debugValidate();
750 FAIL_IF(cs->deleted());
751 FAIL_IF(os->deleted());
752 FAIL_IF(ce->deleted());
753 FAIL_IF(oe->deleted());
754 FAIL_IF(cs->contains(ce) || os->contains(oe));
755 bool result = true;
756 if (overlap) {
757 if (overlap->coinPtTStart()->segment() == coinSeg) {
758 result = overlap->extend(cs, ce, os, oe);
759 } else {
760 if (os->fT > oe->fT) {
761 using std::swap;
762 swap(cs, ce);
763 swap(os, oe);
764 }
765 result = overlap->extend(os, oe, cs, ce);
766 }
767#if DEBUG_COINCIDENCE_VERBOSE
768 if (result) {
769 overlaps[0]->debugShow();
770 }
771#endif
772 } else {
773 this->add(cs, ce, os, oe);
774#if DEBUG_COINCIDENCE_VERBOSE
775 fHead->debugShow();
776#endif
777 }
778 this->debugValidate();
779 if (result) {
780 *added = true;
781 }
782 return true;
783}
784
785// Please keep this in sync with debugAddMissing()
786/* detects overlaps of different coincident runs on same segment */
787/* does not detect overlaps for pairs without any segments in common */
788// returns true if caller should loop again
789bool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) {
790 SkCoincidentSpans* outer = fHead;
791 *added = false;
792 if (!outer) {
793 return true;
794 }
795 fTop = outer;
796 fHead = nullptr;
797 do {
798 // addifmissing can modify the list that this is walking
799 // save head so that walker can iterate over old data unperturbed
800 // addifmissing adds to head freely then add saved head in the end
801 const SkOpPtT* ocs = outer->coinPtTStart();
802 FAIL_IF(ocs->deleted());
803 const SkOpSegment* outerCoin = ocs->segment();
804 FAIL_IF(outerCoin->done());
805 const SkOpPtT* oos = outer->oppPtTStart();
806 if (oos->deleted()) {
807 return true;
808 }
809 const SkOpSegment* outerOpp = oos->segment();
810 SkOPASSERT(!outerOpp->done());
811 SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
812 SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
813 SkCoincidentSpans* inner = outer;
814#ifdef IS_FUZZING_WITH_LIBFUZZER
815 int safetyNet = 1000;
816#endif
817 while ((inner = inner->next())) {
818#ifdef IS_FUZZING_WITH_LIBFUZZER
819 if (!--safetyNet) {
820 return false;
821 }
822#endif
823 this->debugValidate();
824 double overS, overE;
825 const SkOpPtT* ics = inner->coinPtTStart();
826 FAIL_IF(ics->deleted());
827 const SkOpSegment* innerCoin = ics->segment();
828 FAIL_IF(innerCoin->done());
829 const SkOpPtT* ios = inner->oppPtTStart();
830 FAIL_IF(ios->deleted());
831 const SkOpSegment* innerOpp = ios->segment();
832 SkOPASSERT(!innerOpp->done());
833 SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
834 SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
835 if (outerCoin == innerCoin) {
836 const SkOpPtT* oce = outer->coinPtTEnd();
837 if (oce->deleted()) {
838 return true;
839 }
840 const SkOpPtT* ice = inner->coinPtTEnd();
841 FAIL_IF(ice->deleted());
842 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
843 FAIL_IF(!this->addIfMissing(ocs->starter(oce), ics->starter(ice),
844 overS, overE, outerOppWritable, innerOppWritable, added
845 SkDEBUGPARAMS(ocs->debugEnder(oce))
846 SkDEBUGPARAMS(ics->debugEnder(ice))));
847 }
848 } else if (outerCoin == innerOpp) {
849 const SkOpPtT* oce = outer->coinPtTEnd();
850 FAIL_IF(oce->deleted());
851 const SkOpPtT* ioe = inner->oppPtTEnd();
852 FAIL_IF(ioe->deleted());
853 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
854 FAIL_IF(!this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
855 overS, overE, outerOppWritable, innerCoinWritable, added
856 SkDEBUGPARAMS(ocs->debugEnder(oce))
857 SkDEBUGPARAMS(ios->debugEnder(ioe))));
858 }
859 } else if (outerOpp == innerCoin) {
860 const SkOpPtT* ooe = outer->oppPtTEnd();
861 FAIL_IF(ooe->deleted());
862 const SkOpPtT* ice = inner->coinPtTEnd();
863 FAIL_IF(ice->deleted());
864 SkASSERT(outerCoin != innerOpp);
865 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
866 FAIL_IF(!this->addIfMissing(oos->starter(ooe), ics->starter(ice),
867 overS, overE, outerCoinWritable, innerOppWritable, added
868 SkDEBUGPARAMS(oos->debugEnder(ooe))
869 SkDEBUGPARAMS(ics->debugEnder(ice))));
870 }
871 } else if (outerOpp == innerOpp) {
872 const SkOpPtT* ooe = outer->oppPtTEnd();
873 FAIL_IF(ooe->deleted());
874 const SkOpPtT* ioe = inner->oppPtTEnd();
875 if (ioe->deleted()) {
876 return true;
877 }
878 SkASSERT(outerCoin != innerCoin);
879 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
880 FAIL_IF(!this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
881 overS, overE, outerCoinWritable, innerCoinWritable, added
882 SkDEBUGPARAMS(oos->debugEnder(ooe))
883 SkDEBUGPARAMS(ios->debugEnder(ioe))));
884 }
885 }
886 this->debugValidate();
887 }
888 } while ((outer = outer->next()));
889 this->restoreHead();
890 return true;
891}
892
893bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
894 const SkOpSegment* seg2, const SkOpSegment* seg2o,
895 const SkOpPtT* overS, const SkOpPtT* overE) {
896 const SkOpPtT* s1 = overS->find(seg1);
897 const SkOpPtT* e1 = overE->find(seg1);
898 FAIL_IF(!s1);
899 FAIL_IF(!e1);
900 if (!s1->starter(e1)->span()->upCast()->windValue()) {
901 s1 = overS->find(seg1o);
902 e1 = overE->find(seg1o);
903 FAIL_IF(!s1);
904 FAIL_IF(!e1);
905 if (!s1->starter(e1)->span()->upCast()->windValue()) {
906 return true;
907 }
908 }
909 const SkOpPtT* s2 = overS->find(seg2);
910 const SkOpPtT* e2 = overE->find(seg2);
911 FAIL_IF(!s2);
912 FAIL_IF(!e2);
913 if (!s2->starter(e2)->span()->upCast()->windValue()) {
914 s2 = overS->find(seg2o);
915 e2 = overE->find(seg2o);
916 FAIL_IF(!s2);
917 FAIL_IF(!e2);
918 if (!s2->starter(e2)->span()->upCast()->windValue()) {
919 return true;
920 }
921 }
922 if (s1->segment() == s2->segment()) {
923 return true;
924 }
925 if (s1->fT > e1->fT) {
926 using std::swap;
927 swap(s1, e1);
928 swap(s2, e2);
929 }
930 this->add(s1, e1, s2, e2);
931 return true;
932}
933
934bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const {
935 if (this->contains(fHead, seg, opp, oppT)) {
936 return true;
937 }
938 if (this->contains(fTop, seg, opp, oppT)) {
939 return true;
940 }
941 return false;
942}
943
944bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
945 const SkOpSegment* opp, double oppT) const {
946 if (!coin) {
947 return false;
948 }
949 do {
950 if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp
951 && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) {
952 return true;
953 }
954 if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp
955 && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) {
956 return true;
957 }
958 } while ((coin = coin->next()));
959 return false;
960}
961
962bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
963 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
964 const SkCoincidentSpans* test = fHead;
965 if (!test) {
966 return false;
967 }
968 const SkOpSegment* coinSeg = coinPtTStart->segment();
969 const SkOpSegment* oppSeg = oppPtTStart->segment();
970 if (!Ordered(coinPtTStart, oppPtTStart)) {
971 using std::swap;
972 swap(coinSeg, oppSeg);
973 swap(coinPtTStart, oppPtTStart);
974 swap(coinPtTEnd, oppPtTEnd);
975 if (coinPtTStart->fT > coinPtTEnd->fT) {
976 swap(coinPtTStart, coinPtTEnd);
977 swap(oppPtTStart, oppPtTEnd);
978 }
979 }
980 double oppMinT = std::min(oppPtTStart->fT, oppPtTEnd->fT);
981 double oppMaxT = std::max(oppPtTStart->fT, oppPtTEnd->fT);
982 do {
983 if (coinSeg != test->coinPtTStart()->segment()) {
984 continue;
985 }
986 if (coinPtTStart->fT < test->coinPtTStart()->fT) {
987 continue;
988 }
989 if (coinPtTEnd->fT > test->coinPtTEnd()->fT) {
990 continue;
991 }
992 if (oppSeg != test->oppPtTStart()->segment()) {
993 continue;
994 }
995 if (oppMinT < std::min(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
996 continue;
997 }
998 if (oppMaxT > std::max(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
999 continue;
1000 }
1001 return true;
1002 } while ((test = test->next()));
1003 return false;
1004}
1005
1006void SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1007 DEBUG_SET_PHASE();
1008 SkCoincidentSpans* coin = fHead;
1009 if (!coin) {
1010 return;
1011 }
1012 do {
1013 coin->correctEnds();
1014 } while ((coin = coin->next()));
1015}
1016
1017// walk span sets in parallel, moving winding from one to the other
1018bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1019 DEBUG_SET_PHASE();
1020 SkCoincidentSpans* coin = fHead;
1021 if (!coin) {
1022 return true;
1023 }
1024 do {
1025 SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span();
1026 FAIL_IF(!startSpan->upCastable());
1027 SkOpSpan* start = startSpan->upCast();
1028 if (start->deleted()) {
1029 continue;
1030 }
1031 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1032 FAIL_IF(start != start->starter(end));
1033 bool flipped = coin->flipped();
1034 SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable()
1035 : coin->oppPtTStartWritable())->span();
1036 FAIL_IF(!oStartBase->upCastable());
1037 SkOpSpan* oStart = oStartBase->upCast();
1038 if (oStart->deleted()) {
1039 continue;
1040 }
1041 const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
1042 SkASSERT(oStart == oStart->starter(oEnd));
1043 SkOpSegment* segment = start->segment();
1044 SkOpSegment* oSegment = oStart->segment();
1045 bool operandSwap = segment->operand() != oSegment->operand();
1046 if (flipped) {
1047 if (oEnd->deleted()) {
1048 continue;
1049 }
1050 do {
1051 SkOpSpanBase* oNext = oStart->next();
1052 if (oNext == oEnd) {
1053 break;
1054 }
1055 FAIL_IF(!oNext->upCastable());
1056 oStart = oNext->upCast();
1057 } while (true);
1058 }
1059 do {
1060 int windValue = start->windValue();
1061 int oppValue = start->oppValue();
1062 int oWindValue = oStart->windValue();
1063 int oOppValue = oStart->oppValue();
1064 // winding values are added or subtracted depending on direction and wind type
1065 // same or opposite values are summed depending on the operand value
1066 int windDiff = operandSwap ? oOppValue : oWindValue;
1067 int oWindDiff = operandSwap ? oppValue : windValue;
1068 if (!flipped) {
1069 windDiff = -windDiff;
1070 oWindDiff = -oWindDiff;
1071 }
1072 bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff
1073 && oWindValue <= oWindDiff));
1074 if (addToStart ? start->done() : oStart->done()) {
1075 addToStart ^= true;
1076 }
1077 if (addToStart) {
1078 if (operandSwap) {
1079 using std::swap;
1080 swap(oWindValue, oOppValue);
1081 }
1082 if (flipped) {
1083 windValue -= oWindValue;
1084 oppValue -= oOppValue;
1085 } else {
1086 windValue += oWindValue;
1087 oppValue += oOppValue;
1088 }
1089 if (segment->isXor()) {
1090 windValue &= 1;
1091 }
1092 if (segment->oppXor()) {
1093 oppValue &= 1;
1094 }
1095 oWindValue = oOppValue = 0;
1096 } else {
1097 if (operandSwap) {
1098 using std::swap;
1099 swap(windValue, oppValue);
1100 }
1101 if (flipped) {
1102 oWindValue -= windValue;
1103 oOppValue -= oppValue;
1104 } else {
1105 oWindValue += windValue;
1106 oOppValue += oppValue;
1107 }
1108 if (oSegment->isXor()) {
1109 oWindValue &= 1;
1110 }
1111 if (oSegment->oppXor()) {
1112 oOppValue &= 1;
1113 }
1114 windValue = oppValue = 0;
1115 }
1116#if 0 && DEBUG_COINCIDENCE
1117 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(),
1118 start->debugID(), windValue, oppValue);
1119 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(),
1120 oStart->debugID(), oWindValue, oOppValue);
1121#endif
1122 FAIL_IF(windValue <= -1);
1123 start->setWindValue(windValue);
1124 start->setOppValue(oppValue);
1125 FAIL_IF(oWindValue <= -1);
1126 oStart->setWindValue(oWindValue);
1127 oStart->setOppValue(oOppValue);
1128 if (!windValue && !oppValue) {
1129 segment->markDone(start);
1130 }
1131 if (!oWindValue && !oOppValue) {
1132 oSegment->markDone(oStart);
1133 }
1134 SkOpSpanBase* next = start->next();
1135 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
1136 if (next == end) {
1137 break;
1138 }
1139 FAIL_IF(!next->upCastable());
1140 start = next->upCast();
1141 // if the opposite ran out too soon, just reuse the last span
1142 if (!oNext || !oNext->upCastable()) {
1143 oNext = oStart;
1144 }
1145 oStart = oNext->upCast();
1146 } while (true);
1147 } while ((coin = coin->next()));
1148 return true;
1149}
1150
1151// Please keep this in sync with debugRelease()
1152bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) {
1153 SkCoincidentSpans* head = coin;
1154 SkCoincidentSpans* prev = nullptr;
1155 SkCoincidentSpans* next;
1156 do {
1157 next = coin->next();
1158 if (coin == remove) {
1159 if (prev) {
1160 prev->setNext(next);
1161 } else if (head == fHead) {
1162 fHead = next;
1163 } else {
1164 fTop = next;
1165 }
1166 break;
1167 }
1168 prev = coin;
1169 } while ((coin = next));
1170 return coin != nullptr;
1171}
1172
1173void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
1174 if (!coin) {
1175 return;
1176 }
1177 SkCoincidentSpans* head = coin;
1178 SkCoincidentSpans* prev = nullptr;
1179 SkCoincidentSpans* next;
1180 do {
1181 next = coin->next();
1182 if (coin->coinPtTStart()->deleted()) {
1183 SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
1184 coin->oppPtTStart()->deleted());
1185 if (prev) {
1186 prev->setNext(next);
1187 } else if (head == fHead) {
1188 fHead = next;
1189 } else {
1190 fTop = next;
1191 }
1192 } else {
1193 SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
1194 !coin->oppPtTStart()->deleted());
1195 prev = coin;
1196 }
1197 } while ((coin = next));
1198}
1199
1200void SkOpCoincidence::releaseDeleted() {
1201 this->releaseDeleted(fHead);
1202 this->releaseDeleted(fTop);
1203}
1204
1205void SkOpCoincidence::restoreHead() {
1206 SkCoincidentSpans** headPtr = &fHead;
1207 while (*headPtr) {
1208 headPtr = (*headPtr)->nextPtr();
1209 }
1210 *headPtr = fTop;
1211 fTop = nullptr;
1212 // segments may have collapsed in the meantime; remove empty referenced segments
1213 headPtr = &fHead;
1214 while (*headPtr) {
1215 SkCoincidentSpans* test = *headPtr;
1216 if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
1217 *headPtr = test->next();
1218 continue;
1219 }
1220 headPtr = (*headPtr)->nextPtr();
1221 }
1222}
1223
1224// Please keep this in sync with debugExpand()
1225// expand the range by checking adjacent spans for coincidence
1226bool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1227 DEBUG_SET_PHASE();
1228 SkCoincidentSpans* coin = fHead;
1229 if (!coin) {
1230 return false;
1231 }
1232 bool expanded = false;
1233 do {
1234 if (coin->expand()) {
1235 // check to see if multiple spans expanded so they are now identical
1236 SkCoincidentSpans* test = fHead;
1237 do {
1238 if (coin == test) {
1239 continue;
1240 }
1241 if (coin->coinPtTStart() == test->coinPtTStart()
1242 && coin->oppPtTStart() == test->oppPtTStart()) {
1243 this->release(fHead, test);
1244 break;
1245 }
1246 } while ((test = test->next()));
1247 expanded = true;
1248 }
1249 } while ((coin = coin->next()));
1250 return expanded;
1251}
1252
1253bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const {
1254 DEBUG_SET_PHASE();
1255 overlaps->fHead = overlaps->fTop = nullptr;
1256 SkCoincidentSpans* outer = fHead;
1257 while (outer) {
1258 const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
1259 const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
1260 SkCoincidentSpans* inner = outer;
1261 while ((inner = inner->next())) {
1262 const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
1263 if (outerCoin == innerCoin) {
1264 continue; // both winners are the same segment, so there's no additional overlap
1265 }
1266 const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
1267 const SkOpPtT* overlapS;
1268 const SkOpPtT* overlapE;
1269 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(),
1270 outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS,
1271 &overlapE))
1272 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(),
1273 outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1274 &overlapS, &overlapE))
1275 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
1276 outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1277 &overlapS, &overlapE))) {
1278 if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
1279 overlapS, overlapE)) {
1280 return false;
1281 }
1282 }
1283 }
1284 outer = outer->next();
1285 }
1286 return true;
1287}
1288
1289void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
1290 SkOPASSERT(deleted != kept);
1291 if (fHead) {
1292 this->fixUp(fHead, deleted, kept);
1293 }
1294 if (fTop) {
1295 this->fixUp(fTop, deleted, kept);
1296 }
1297}
1298
1299void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) {
1300 SkCoincidentSpans* head = coin;
1301 do {
1302 if (coin->coinPtTStart() == deleted) {
1303 if (coin->coinPtTEnd()->span() == kept->span()) {
1304 this->release(head, coin);
1305 continue;
1306 }
1307 coin->setCoinPtTStart(kept);
1308 }
1309 if (coin->coinPtTEnd() == deleted) {
1310 if (coin->coinPtTStart()->span() == kept->span()) {
1311 this->release(head, coin);
1312 continue;
1313 }
1314 coin->setCoinPtTEnd(kept);
1315 }
1316 if (coin->oppPtTStart() == deleted) {
1317 if (coin->oppPtTEnd()->span() == kept->span()) {
1318 this->release(head, coin);
1319 continue;
1320 }
1321 coin->setOppPtTStart(kept);
1322 }
1323 if (coin->oppPtTEnd() == deleted) {
1324 if (coin->oppPtTStart()->span() == kept->span()) {
1325 this->release(head, coin);
1326 continue;
1327 }
1328 coin->setOppPtTEnd(kept);
1329 }
1330 } while ((coin = coin->next()));
1331}
1332
1333// Please keep this in sync with debugMark()
1334/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
1335bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1336 DEBUG_SET_PHASE();
1337 SkCoincidentSpans* coin = fHead;
1338 if (!coin) {
1339 return true;
1340 }
1341 do {
1342 SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span();
1343 FAIL_IF(!startBase->upCastable());
1344 SkOpSpan* start = startBase->upCast();
1345 FAIL_IF(start->deleted());
1346 SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1347 SkOPASSERT(!end->deleted());
1348 SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1349 SkOPASSERT(!oStart->deleted());
1350 SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1351 FAIL_IF(oEnd->deleted());
1352 bool flipped = coin->flipped();
1353 if (flipped) {
1354 using std::swap;
1355 swap(oStart, oEnd);
1356 }
1357 /* coin and opp spans may not match up. Mark the ends, and then let the interior
1358 get marked as many times as the spans allow */
1359 FAIL_IF(!oStart->upCastable());
1360 start->insertCoincidence(oStart->upCast());
1361 end->insertCoinEnd(oEnd);
1362 const SkOpSegment* segment = start->segment();
1363 const SkOpSegment* oSegment = oStart->segment();
1364 SkOpSpanBase* next = start;
1365 SkOpSpanBase* oNext = oStart;
1366 bool ordered;
1367 FAIL_IF(!coin->ordered(&ordered));
1368 while ((next = next->upCast()->next()) != end) {
1369 FAIL_IF(!next->upCastable());
1370 FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered));
1371 }
1372 while ((oNext = oNext->upCast()->next()) != oEnd) {
1373 FAIL_IF(!oNext->upCastable());
1374 FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered));
1375 }
1376 } while ((coin = coin->next()));
1377 return true;
1378}
1379
1380// Please keep in sync with debugMarkCollapsed()
1381void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
1382 SkCoincidentSpans* head = coin;
1383 while (coin) {
1384 if (coin->collapsed(test)) {
1385 if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
1386 coin->coinPtTStartWritable()->segment()->markAllDone();
1387 }
1388 if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
1389 coin->oppPtTStartWritable()->segment()->markAllDone();
1390 }
1391 this->release(head, coin);
1392 }
1393 coin = coin->next();
1394 }
1395}
1396
1397// Please keep in sync with debugMarkCollapsed()
1398void SkOpCoincidence::markCollapsed(SkOpPtT* test) {
1399 markCollapsed(fHead, test);
1400 markCollapsed(fTop, test);
1401}
1402
1403bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) {
1404 if (coinSeg->verb() < oppSeg->verb()) {
1405 return true;
1406 }
1407 if (coinSeg->verb() > oppSeg->verb()) {
1408 return false;
1409 }
1410 int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2;
1411 const SkScalar* cPt = &coinSeg->pts()[0].fX;
1412 const SkScalar* oPt = &oppSeg->pts()[0].fX;
1413 for (int index = 0; index < count; ++index) {
1414 if (*cPt < *oPt) {
1415 return true;
1416 }
1417 if (*cPt > *oPt) {
1418 return false;
1419 }
1420 ++cPt;
1421 ++oPt;
1422 }
1423 return true;
1424}
1425
1426bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
1427 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
1428 SkASSERT(coin1s->segment() == coin2s->segment());
1429 *overS = std::max(std::min(coin1s->fT, coin1e->fT), std::min(coin2s->fT, coin2e->fT));
1430 *overE = std::min(std::max(coin1s->fT, coin1e->fT), std::max(coin2s->fT, coin2e->fT));
1431 return *overS < *overE;
1432}
1433
1434// Commented-out lines keep this in sync with debugRelease()
1435void SkOpCoincidence::release(const SkOpSegment* deleted) {
1436 SkCoincidentSpans* coin = fHead;
1437 if (!coin) {
1438 return;
1439 }
1440 do {
1441 if (coin->coinPtTStart()->segment() == deleted
1442 || coin->coinPtTEnd()->segment() == deleted
1443 || coin->oppPtTStart()->segment() == deleted
1444 || coin->oppPtTEnd()->segment() == deleted) {
1445 this->release(fHead, coin);
1446 }
1447 } while ((coin = coin->next()));
1448}
1449