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