1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkOpCoincidence.h"
8#include "SkOpContour.h"
9#include "SkOpSegment.h"
10#include "SkPathWriter.h"
11#include "SkPointPriv.h"
12
13/*
14After computing raw intersections, post process all segments to:
15- find small collections of points that can be collapsed to a single point
16- find missing intersections to resolve differences caused by different algorithms
17
18Consider segments containing tiny or small intervals. Consider coincident segments
19because coincidence finds intersections through distance measurement that non-coincident
20intersection tests cannot.
21 */
22
23#define F (false)      // discard the edge
24#define T (true)       // keep the edge
25
26static const bool gUnaryActiveEdge[2][2] = {
27//  from=0  from=1
28//  to=0,1  to=0,1
29    {F, T}, {T, F},
30};
31
32static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = {
33//                 miFrom=0                              miFrom=1
34//         miTo=0             miTo=1             miTo=0             miTo=1
35//     suFrom=0    1      suFrom=0    1      suFrom=0    1      suFrom=0    1
36//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
37    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}},  // mi - su
38    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}},  // mi & su
39    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}},  // mi | su
40    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}},  // mi ^ su
41};
42
43#undef F
44#undef T
45
46SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
47        SkOpSpanBase** endPtr, bool* done) {
48    if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) {
49        return result;
50    }
51    if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) {
52        return result;
53    }
54    return nullptr;
55}
56
57SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
58        SkOpSpanBase** endPtr, bool* done) {
59    SkOpSpan* upSpan = start->upCastable();
60    if (upSpan) {
61        if (upSpan->windValue() || upSpan->oppValue()) {
62            SkOpSpanBase* next = upSpan->next();
63            if (!*endPtr) {
64                *startPtr = start;
65                *endPtr = next;
66            }
67            if (!upSpan->done()) {
68                if (upSpan->windSum() != SK_MinS32) {
69                    return spanToAngle(start, next);
70                }
71                *done = false;
72            }
73        } else {
74            SkASSERT(upSpan->done());
75        }
76    }
77    SkOpSpan* downSpan = start->prev();
78    // edge leading into junction
79    if (downSpan) {
80        if (downSpan->windValue() || downSpan->oppValue()) {
81            if (!*endPtr) {
82                *startPtr = start;
83                *endPtr = downSpan;
84            }
85            if (!downSpan->done()) {
86                if (downSpan->windSum() != SK_MinS32) {
87                    return spanToAngle(start, downSpan);
88                }
89                *done = false;
90            }
91        } else {
92            SkASSERT(downSpan->done());
93        }
94    }
95    return nullptr;
96}
97
98SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
99        SkOpSpanBase** endPtr, bool* done) {
100    SkOpPtT* oPtT = start->ptT()->next();
101    SkOpSegment* other = oPtT->segment();
102    SkOpSpanBase* oSpan = oPtT->span();
103    return other->activeAngleInner(oSpan, startPtr, endPtr, done);
104}
105
106bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
107        SkPathOp op) {
108    int sumMiWinding = this->updateWinding(end, start);
109    int sumSuWinding = this->updateOppWinding(end, start);
110#if DEBUG_LIMIT_WIND_SUM
111    SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
112    SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
113#endif
114    if (this->operand()) {
115        SkTSwap<int>(sumMiWinding, sumSuWinding);
116    }
117    return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding);
118}
119
120bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
121        SkPathOp op, int* sumMiWinding, int* sumSuWinding) {
122    int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
123    this->setUpWindings(start, end, sumMiWinding, sumSuWinding,
124            &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
125    bool miFrom;
126    bool miTo;
127    bool suFrom;
128    bool suTo;
129    if (operand()) {
130        miFrom = (oppMaxWinding & xorMiMask) != 0;
131        miTo = (oppSumWinding & xorMiMask) != 0;
132        suFrom = (maxWinding & xorSuMask) != 0;
133        suTo = (sumWinding & xorSuMask) != 0;
134    } else {
135        miFrom = (maxWinding & xorMiMask) != 0;
136        miTo = (sumWinding & xorMiMask) != 0;
137        suFrom = (oppMaxWinding & xorSuMask) != 0;
138        suTo = (oppSumWinding & xorSuMask) != 0;
139    }
140    bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
141#if DEBUG_ACTIVE_OP
142    SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
143            __FUNCTION__, debugID(), start->t(), end->t(),
144            SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
145#endif
146    return result;
147}
148
149bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
150    int sumWinding = updateWinding(end, start);
151    return activeWinding(start, end, &sumWinding);
152}
153
154bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
155    int maxWinding;
156    setUpWinding(start, end, &maxWinding, sumWinding);
157    bool from = maxWinding != 0;
158    bool to = *sumWinding  != 0;
159    bool result = gUnaryActiveEdge[from][to];
160    return result;
161}
162
163bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
164        SkPathWriter* path) const {
165    FAIL_IF(start->starter(end)->alreadyAdded());
166    SkDCurveSweep curvePart;
167    start->segment()->subDivide(start, end, &curvePart.fCurve);
168    curvePart.setCurveHullSweep(fVerb);
169    SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb;
170    path->deferredMove(start->ptT());
171    switch (verb) {
172        case SkPath::kLine_Verb:
173            FAIL_IF(!path->deferredLine(end->ptT()));
174            break;
175        case SkPath::kQuad_Verb:
176            path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT());
177            break;
178        case SkPath::kConic_Verb:
179            path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(),
180                    curvePart.fCurve.fConic.fWeight);
181            break;
182        case SkPath::kCubic_Verb:
183            path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(),
184                    curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT());
185            break;
186        default:
187            SkASSERT(0);
188    }
189    return true;
190}
191
192const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
193    const SkOpSpanBase* test = &fHead;
194    const SkOpPtT* testPtT;
195    SkPoint pt = this->ptAtT(t);
196    do {
197        testPtT = test->ptT();
198        if (testPtT->fT == t) {
199            break;
200        }
201        if (!this->match(testPtT, this, t, pt)) {
202            if (t < testPtT->fT) {
203                return nullptr;
204            }
205            continue;
206        }
207        if (!opp) {
208            return testPtT;
209        }
210        const SkOpPtT* loop = testPtT->next();
211        while (loop != testPtT) {
212            if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
213                goto foundMatch;
214            }
215            loop = loop->next();
216        }
217        return nullptr;
218    } while ((test = test->upCast()->next()));
219foundMatch:
220    return opp && !test->contains(opp) ? nullptr : testPtT;
221}
222
223// break the span so that the coincident part does not change the angle of the remainder
224bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
225    if (this->contains(newT)) {
226        return true;
227    }
228    this->globalState()->resetAllocatedOpSpan();
229    FAIL_IF(!between(0, newT, 1));
230    SkOpPtT* newPtT = this->addT(newT);
231    *startOver |= this->globalState()->allocatedOpSpan();
232    if (!newPtT) {
233        return false;
234    }
235    newPtT->fPt = this->ptAtT(newT);
236    SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
237    if (oppPrev) {
238        // const cast away to change linked list; pt/t values stays unchanged
239        SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
240        writableTest->mergeMatches(newPtT->span());
241        writableTest->ptT()->addOpp(newPtT, oppPrev);
242        writableTest->checkForCollapsedCoincidence();
243    }
244    return true;
245}
246
247// Please keep this in sync with debugAddT()
248SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) {
249    debugValidate();
250    SkOpSpanBase* spanBase = &fHead;
251    do {
252        SkOpPtT* result = spanBase->ptT();
253        if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) {
254            spanBase->bumpSpanAdds();
255            return result;
256        }
257        if (t < result->fT) {
258            SkOpSpan* prev = result->span()->prev();
259            FAIL_WITH_NULL_IF(!prev);
260            // marks in global state that new op span has been allocated
261            SkOpSpan* span = this->insert(prev);
262            span->init(this, prev, t, pt);
263            this->debugValidate();
264#if DEBUG_ADD_T
265            SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
266                    span->segment()->debugID(), span->debugID());
267#endif
268            span->bumpSpanAdds();
269            return span->ptT();
270        }
271        FAIL_WITH_NULL_IF(spanBase == &fTail);
272    } while ((spanBase = spanBase->upCast()->next()));
273    SkASSERT(0);
274    return nullptr;  // we never get here, but need this to satisfy compiler
275}
276
277SkOpPtT* SkOpSegment::addT(double t) {
278    return addT(t, this->ptAtT(t));
279}
280
281void SkOpSegment::calcAngles() {
282    bool activePrior = !fHead.isCanceled();
283    if (activePrior && !fHead.simple()) {
284        addStartSpan();
285    }
286    SkOpSpan* prior = &fHead;
287    SkOpSpanBase* spanBase = fHead.next();
288    while (spanBase != &fTail) {
289        if (activePrior) {
290            SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>();
291            priorAngle->set(spanBase, prior);
292            spanBase->setFromAngle(priorAngle);
293        }
294        SkOpSpan* span = spanBase->upCast();
295        bool active = !span->isCanceled();
296        SkOpSpanBase* next = span->next();
297        if (active) {
298            SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
299            angle->set(span, next);
300            span->setToAngle(angle);
301        }
302        activePrior = active;
303        prior = span;
304        spanBase = next;
305    }
306    if (activePrior && !fTail.simple()) {
307        addEndSpan();
308    }
309}
310
311// Please keep this in sync with debugClearAll()
312void SkOpSegment::clearAll() {
313    SkOpSpan* span = &fHead;
314    do {
315        this->clearOne(span);
316    } while ((span = span->next()->upCastable()));
317    this->globalState()->coincidence()->release(this);
318}
319
320// Please keep this in sync with debugClearOne()
321void SkOpSegment::clearOne(SkOpSpan* span) {
322    span->setWindValue(0);
323    span->setOppValue(0);
324    this->markDone(span);
325}
326
327bool SkOpSegment::collapsed(double s, double e) const {
328    const SkOpSpanBase* span = &fHead;
329    do {
330        if (span->collapsed(s, e)) {
331            return true;
332        }
333    } while (span->upCastable() && (span = span->upCast()->next()));
334    return false;
335}
336
337void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
338        SkOpAngle::IncludeType includeType) {
339    SkOpSegment* baseSegment = baseAngle->segment();
340    int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
341    int sumSuWinding;
342    bool binary = includeType >= SkOpAngle::kBinarySingle;
343    if (binary) {
344        sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
345        if (baseSegment->operand()) {
346            SkTSwap<int>(sumMiWinding, sumSuWinding);
347        }
348    }
349    SkOpSegment* nextSegment = nextAngle->segment();
350    int maxWinding, sumWinding;
351    SkOpSpanBase* last;
352    if (binary) {
353        int oppMaxWinding, oppSumWinding;
354        nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
355                &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
356        last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
357                nextAngle);
358    } else {
359        nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
360                &maxWinding, &sumWinding);
361        last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
362    }
363    nextAngle->setLastMarked(last);
364}
365
366void SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
367        SkOpAngle::IncludeType includeType) {
368    SkOpSegment* baseSegment = baseAngle->segment();
369    int sumMiWinding = baseSegment->updateWinding(baseAngle);
370    int sumSuWinding;
371    bool binary = includeType >= SkOpAngle::kBinarySingle;
372    if (binary) {
373        sumSuWinding = baseSegment->updateOppWinding(baseAngle);
374        if (baseSegment->operand()) {
375            SkTSwap<int>(sumMiWinding, sumSuWinding);
376        }
377    }
378    SkOpSegment* nextSegment = nextAngle->segment();
379    int maxWinding, sumWinding;
380    SkOpSpanBase* last;
381    if (binary) {
382        int oppMaxWinding, oppSumWinding;
383        nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
384                &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
385        last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
386                nextAngle);
387    } else {
388        nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
389                &maxWinding, &sumWinding);
390        last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
391    }
392    nextAngle->setLastMarked(last);
393}
394
395// at this point, the span is already ordered, or unorderable
396int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
397        SkOpAngle::IncludeType includeType) {
398    SkASSERT(includeType != SkOpAngle::kUnaryXor);
399    SkOpAngle* firstAngle = this->spanToAngle(end, start);
400    if (nullptr == firstAngle || nullptr == firstAngle->next()) {
401        return SK_NaN32;
402    }
403    // if all angles have a computed winding,
404    //  or if no adjacent angles are orderable,
405    //  or if adjacent orderable angles have no computed winding,
406    //  there's nothing to do
407    // if two orderable angles are adjacent, and both are next to orderable angles,
408    //  and one has winding computed, transfer to the other
409    SkOpAngle* baseAngle = nullptr;
410    bool tryReverse = false;
411    // look for counterclockwise transfers
412    SkOpAngle* angle = firstAngle->previous();
413    SkOpAngle* next = angle->next();
414    firstAngle = next;
415    do {
416        SkOpAngle* prior = angle;
417        angle = next;
418        next = angle->next();
419        SkASSERT(prior->next() == angle);
420        SkASSERT(angle->next() == next);
421        if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
422            baseAngle = nullptr;
423            continue;
424        }
425        int testWinding = angle->starter()->windSum();
426        if (SK_MinS32 != testWinding) {
427            baseAngle = angle;
428            tryReverse = true;
429            continue;
430        }
431        if (baseAngle) {
432            ComputeOneSum(baseAngle, angle, includeType);
433            baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
434        }
435    } while (next != firstAngle);
436    if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) {
437        firstAngle = baseAngle;
438        tryReverse = true;
439    }
440    if (tryReverse) {
441        baseAngle = nullptr;
442        SkOpAngle* prior = firstAngle;
443        do {
444            angle = prior;
445            prior = angle->previous();
446            SkASSERT(prior->next() == angle);
447            next = angle->next();
448            if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
449                baseAngle = nullptr;
450                continue;
451            }
452            int testWinding = angle->starter()->windSum();
453            if (SK_MinS32 != testWinding) {
454                baseAngle = angle;
455                continue;
456            }
457            if (baseAngle) {
458                ComputeOneSumReverse(baseAngle, angle, includeType);
459                baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
460            }
461        } while (prior != firstAngle);
462    }
463    return start->starter(end)->windSum();
464}
465
466bool SkOpSegment::contains(double newT) const {
467    const SkOpSpanBase* spanBase = &fHead;
468    do {
469        if (spanBase->ptT()->contains(this, newT)) {
470            return true;
471        }
472        if (spanBase == &fTail) {
473            break;
474        }
475        spanBase = spanBase->upCast()->next();
476    } while (true);
477    return false;
478}
479
480void SkOpSegment::release(const SkOpSpan* span) {
481    if (span->done()) {
482        --fDoneCount;
483    }
484    --fCount;
485    SkOPASSERT(fCount >= fDoneCount);
486}
487
488#if DEBUG_ANGLE
489// called only by debugCheckNearCoincidence
490double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
491    SkDPoint testPt = this->dPtAtT(t);
492    SkDLine testPerp = {{ testPt, testPt }};
493    SkDVector slope = this->dSlopeAtT(t);
494    testPerp[1].fX += slope.fY;
495    testPerp[1].fY -= slope.fX;
496    SkIntersections i;
497    const SkOpSegment* oppSegment = oppAngle->segment();
498    (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
499    double closestDistSq = SK_ScalarInfinity;
500    for (int index = 0; index < i.used(); ++index) {
501        if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
502            continue;
503        }
504        double testDistSq = testPt.distanceSquared(i.pt(index));
505        if (closestDistSq > testDistSq) {
506            closestDistSq = testDistSq;
507        }
508    }
509    return closestDistSq;
510}
511#endif
512
513/*
514 The M and S variable name parts stand for the operators.
515   Mi stands for Minuend (see wiki subtraction, analogous to difference)
516   Su stands for Subtrahend
517 The Opp variable name part designates that the value is for the Opposite operator.
518 Opposite values result from combining coincident spans.
519 */
520SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
521        SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) {
522    SkOpSpanBase* start = *nextStart;
523    SkOpSpanBase* end = *nextEnd;
524    SkASSERT(start != end);
525    int step = start->step(end);
526    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
527    if (other) {
528    // mark the smaller of startIndex, endIndex done, and all adjacent
529    // spans with the same T value (but not 'other' spans)
530#if DEBUG_WINDING
531        SkDebugf("%s simple\n", __FUNCTION__);
532#endif
533        SkOpSpan* startSpan = start->starter(end);
534        if (startSpan->done()) {
535            return nullptr;
536        }
537        markDone(startSpan);
538        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
539        return other;
540    }
541    SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
542    SkASSERT(endNear == end);  // is this ever not end?
543    SkASSERT(endNear);
544    SkASSERT(start != endNear);
545    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
546    // more than one viable candidate -- measure angles to find best
547    int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
548    bool sortable = calcWinding != SK_NaN32;
549    if (!sortable) {
550        *unsortable = true;
551        markDone(start->starter(end));
552        return nullptr;
553    }
554    SkOpAngle* angle = this->spanToAngle(end, start);
555    if (angle->unorderable()) {
556        *unsortable = true;
557        markDone(start->starter(end));
558        return nullptr;
559    }
560#if DEBUG_SORT
561    SkDebugf("%s\n", __FUNCTION__);
562    angle->debugLoop();
563#endif
564    int sumMiWinding = updateWinding(end, start);
565    if (sumMiWinding == SK_MinS32) {
566        *unsortable = true;
567        markDone(start->starter(end));
568        return nullptr;
569    }
570    int sumSuWinding = updateOppWinding(end, start);
571    if (operand()) {
572        SkTSwap<int>(sumMiWinding, sumSuWinding);
573    }
574    SkOpAngle* nextAngle = angle->next();
575    const SkOpAngle* foundAngle = nullptr;
576    bool foundDone = false;
577    // iterate through the angle, and compute everyone's winding
578    SkOpSegment* nextSegment;
579    int activeCount = 0;
580    do {
581        nextSegment = nextAngle->segment();
582        bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
583                nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
584        if (activeAngle) {
585            ++activeCount;
586            if (!foundAngle || (foundDone && activeCount & 1)) {
587                foundAngle = nextAngle;
588                foundDone = nextSegment->done(nextAngle);
589            }
590        }
591        if (nextSegment->done()) {
592            continue;
593        }
594        if (!activeAngle) {
595            (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
596        }
597        SkOpSpanBase* last = nextAngle->lastMarked();
598        if (last) {
599            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
600            *chase->append() = last;
601#if DEBUG_WINDING
602            SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
603                    last->segment()->debugID(), last->debugID());
604            if (!last->final()) {
605                SkDebugf(" windSum=%d", last->upCast()->windSum());
606            }
607            SkDebugf("\n");
608#endif
609        }
610    } while ((nextAngle = nextAngle->next()) != angle);
611    start->segment()->markDone(start->starter(end));
612    if (!foundAngle) {
613        return nullptr;
614    }
615    *nextStart = foundAngle->start();
616    *nextEnd = foundAngle->end();
617    nextSegment = foundAngle->segment();
618#if DEBUG_WINDING
619    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
620            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
621 #endif
622    return nextSegment;
623}
624
625SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
626        SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
627    SkOpSpanBase* start = *nextStart;
628    SkOpSpanBase* end = *nextEnd;
629    SkASSERT(start != end);
630    int step = start->step(end);
631    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
632    if (other) {
633    // mark the smaller of startIndex, endIndex done, and all adjacent
634    // spans with the same T value (but not 'other' spans)
635#if DEBUG_WINDING
636        SkDebugf("%s simple\n", __FUNCTION__);
637#endif
638        SkOpSpan* startSpan = start->starter(end);
639        if (startSpan->done()) {
640            return nullptr;
641        }
642        markDone(startSpan);
643        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
644        return other;
645    }
646    SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
647    SkASSERT(endNear == end);  // is this ever not end?
648    SkASSERT(endNear);
649    SkASSERT(start != endNear);
650    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
651    // more than one viable candidate -- measure angles to find best
652    int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
653    bool sortable = calcWinding != SK_NaN32;
654    if (!sortable) {
655        *unsortable = true;
656        markDone(start->starter(end));
657        return nullptr;
658    }
659    SkOpAngle* angle = this->spanToAngle(end, start);
660    if (angle->unorderable()) {
661        *unsortable = true;
662        markDone(start->starter(end));
663        return nullptr;
664    }
665#if DEBUG_SORT
666    SkDebugf("%s\n", __FUNCTION__);
667    angle->debugLoop();
668#endif
669    int sumWinding = updateWinding(end, start);
670    SkOpAngle* nextAngle = angle->next();
671    const SkOpAngle* foundAngle = nullptr;
672    bool foundDone = false;
673    // iterate through the angle, and compute everyone's winding
674    SkOpSegment* nextSegment;
675    int activeCount = 0;
676    do {
677        nextSegment = nextAngle->segment();
678        bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
679                &sumWinding);
680        if (activeAngle) {
681            ++activeCount;
682            if (!foundAngle || (foundDone && activeCount & 1)) {
683                foundAngle = nextAngle;
684                foundDone = nextSegment->done(nextAngle);
685            }
686        }
687        if (nextSegment->done()) {
688            continue;
689        }
690        if (!activeAngle) {
691            (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
692        }
693        SkOpSpanBase* last = nextAngle->lastMarked();
694        if (last) {
695            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
696            *chase->append() = last;
697#if DEBUG_WINDING
698            SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
699                    last->segment()->debugID(), last->debugID());
700            if (!last->final()) {
701                SkDebugf(" windSum=%d", last->upCast()->windSum());
702            }
703            SkDebugf("\n");
704#endif
705        }
706    } while ((nextAngle = nextAngle->next()) != angle);
707    start->segment()->markDone(start->starter(end));
708    if (!foundAngle) {
709        return nullptr;
710    }
711    *nextStart = foundAngle->start();
712    *nextEnd = foundAngle->end();
713    nextSegment = foundAngle->segment();
714#if DEBUG_WINDING
715    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
716            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
717 #endif
718    return nextSegment;
719}
720
721SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
722        bool* unsortable) {
723    SkOpSpanBase* start = *nextStart;
724    SkOpSpanBase* end = *nextEnd;
725    SkASSERT(start != end);
726    int step = start->step(end);
727    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
728    if (other) {
729    // mark the smaller of startIndex, endIndex done, and all adjacent
730    // spans with the same T value (but not 'other' spans)
731#if DEBUG_WINDING
732        SkDebugf("%s simple\n", __FUNCTION__);
733#endif
734        SkOpSpan* startSpan = start->starter(end);
735        if (startSpan->done()) {
736            return nullptr;
737        }
738        markDone(startSpan);
739        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
740        return other;
741    }
742    SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
743            : (*nextStart)->prev());
744    SkASSERT(endNear == end);  // is this ever not end?
745    SkASSERT(endNear);
746    SkASSERT(start != endNear);
747    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
748    SkOpAngle* angle = this->spanToAngle(end, start);
749    if (!angle || angle->unorderable()) {
750        *unsortable = true;
751        markDone(start->starter(end));
752        return nullptr;
753    }
754#if DEBUG_SORT
755    SkDebugf("%s\n", __FUNCTION__);
756    angle->debugLoop();
757#endif
758    SkOpAngle* nextAngle = angle->next();
759    const SkOpAngle* foundAngle = nullptr;
760    bool foundDone = false;
761    // iterate through the angle, and compute everyone's winding
762    SkOpSegment* nextSegment;
763    int activeCount = 0;
764    do {
765        nextSegment = nextAngle->segment();
766        ++activeCount;
767        if (!foundAngle || (foundDone && activeCount & 1)) {
768            foundAngle = nextAngle;
769            if (!(foundDone = nextSegment->done(nextAngle))) {
770                break;
771            }
772        }
773        nextAngle = nextAngle->next();
774    } while (nextAngle != angle);
775    start->segment()->markDone(start->starter(end));
776    if (!foundAngle) {
777        return nullptr;
778    }
779    *nextStart = foundAngle->start();
780    *nextEnd = foundAngle->end();
781    nextSegment = foundAngle->segment();
782#if DEBUG_WINDING
783    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
784            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
785 #endif
786    return nextSegment;
787}
788
789SkOpGlobalState* SkOpSegment::globalState() const {
790    return contour()->globalState();
791}
792
793void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
794    fContour = contour;
795    fNext = nullptr;
796    fPts = pts;
797    fWeight = weight;
798    fVerb = verb;
799    fCount = 0;
800    fDoneCount = 0;
801    fVisited = false;
802    SkOpSpan* zeroSpan = &fHead;
803    zeroSpan->init(this, nullptr, 0, fPts[0]);
804    SkOpSpanBase* oneSpan = &fTail;
805    zeroSpan->setNext(oneSpan);
806    oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
807    SkDEBUGCODE(fID = globalState()->nextSegmentID());
808}
809
810bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
811    SkDPoint cPt = this->dPtAtT(t);
812    SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
813    SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
814    SkIntersections i;
815    (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
816    int used = i.used();
817    for (int index = 0; index < used; ++index) {
818        if (cPt.roughlyEqual(i.pt(index))) {
819            return true;
820        }
821    }
822    return false;
823}
824
825bool SkOpSegment::isXor() const {
826    return fContour->isXor();
827}
828
829void SkOpSegment::markAllDone() {
830    SkOpSpan* span = this->head();
831    do {
832        this->markDone(span);
833    } while ((span = span->next()->upCastable()));
834}
835
836SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) {
837    int step = start->step(end);
838    SkOpSpan* minSpan = start->starter(end);
839    markDone(minSpan);
840    SkOpSpanBase* last = nullptr;
841    SkOpSegment* other = this;
842    SkOpSpan* priorDone = nullptr;
843    SkOpSpan* lastDone = nullptr;
844    while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
845        if (other->done()) {
846            SkASSERT(!last);
847            break;
848        }
849        if (lastDone == minSpan || priorDone == minSpan) {
850            return nullptr;
851        }
852        other->markDone(minSpan);
853        priorDone = lastDone;
854        lastDone = minSpan;
855    }
856    return last;
857}
858
859bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
860        SkOpSpanBase** lastPtr) {
861    SkOpSpan* spanStart = start->starter(end);
862    int step = start->step(end);
863    bool success = markWinding(spanStart, winding);
864    SkOpSpanBase* last = nullptr;
865    SkOpSegment* other = this;
866    while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
867        if (spanStart->windSum() != SK_MinS32) {
868//            SkASSERT(spanStart->windSum() == winding);   // FIXME: is this assert too aggressive?
869            SkASSERT(!last);
870            break;
871        }
872        (void) other->markWinding(spanStart, winding);
873    }
874    if (lastPtr) {
875        *lastPtr = last;
876    }
877    return success;
878}
879
880bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
881        int winding, int oppWinding, SkOpSpanBase** lastPtr) {
882    SkOpSpan* spanStart = start->starter(end);
883    int step = start->step(end);
884    bool success = markWinding(spanStart, winding, oppWinding);
885    SkOpSpanBase* last = nullptr;
886    SkOpSegment* other = this;
887    while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
888        if (spanStart->windSum() != SK_MinS32) {
889            if (this->operand() == other->operand()) {
890                if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) {
891                    this->globalState()->setWindingFailed();
892                    return false;
893                }
894            } else {
895                SkASSERT(spanStart->windSum() == oppWinding);
896                SkASSERT(spanStart->oppSum() == winding);
897            }
898            SkASSERT(!last);
899            break;
900        }
901        if (this->operand() == other->operand()) {
902            (void) other->markWinding(spanStart, winding, oppWinding);
903        } else {
904            (void) other->markWinding(spanStart, oppWinding, winding);
905        }
906    }
907    if (lastPtr) {
908        *lastPtr = last;
909    }
910    return success;
911}
912
913SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
914    SkASSERT(angle->segment() == this);
915    if (UseInnerWinding(maxWinding, sumWinding)) {
916        maxWinding = sumWinding;
917    }
918    SkOpSpanBase* last;
919    (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last);
920#if DEBUG_WINDING
921    if (last) {
922        SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
923                last->segment()->debugID(), last->debugID());
924        if (!last->final()) {
925            SkDebugf(" windSum=");
926            SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
927        }
928        SkDebugf("\n");
929    }
930#endif
931    return last;
932}
933
934SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
935                                   int oppSumWinding, const SkOpAngle* angle) {
936    SkASSERT(angle->segment() == this);
937    if (UseInnerWinding(maxWinding, sumWinding)) {
938        maxWinding = sumWinding;
939    }
940    if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
941        oppMaxWinding = oppSumWinding;
942    }
943    SkOpSpanBase* last = nullptr;
944    // caller doesn't require that this marks anything
945    (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last);
946#if DEBUG_WINDING
947    if (last) {
948        SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
949                last->segment()->debugID(), last->debugID());
950        if (!last->final()) {
951            SkDebugf(" windSum=");
952            SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
953        }
954        SkDebugf(" \n");
955    }
956#endif
957    return last;
958}
959
960void SkOpSegment::markDone(SkOpSpan* span) {
961    SkASSERT(this == span->segment());
962    if (span->done()) {
963        return;
964    }
965#if DEBUG_MARK_DONE
966    debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
967#endif
968    span->setDone(true);
969    ++fDoneCount;
970    debugValidate();
971}
972
973bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
974    SkASSERT(this == span->segment());
975    SkASSERT(winding);
976    if (span->done()) {
977        return false;
978    }
979#if DEBUG_MARK_DONE
980    debugShowNewWinding(__FUNCTION__, span, winding);
981#endif
982    span->setWindSum(winding);
983    debugValidate();
984    return true;
985}
986
987bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
988    SkASSERT(this == span->segment());
989    SkASSERT(winding || oppWinding);
990    if (span->done()) {
991        return false;
992    }
993#if DEBUG_MARK_DONE
994    debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
995#endif
996    span->setWindSum(winding);
997    span->setOppSum(oppWinding);
998    debugValidate();
999    return true;
1000}
1001
1002bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
1003        const SkPoint& testPt) const {
1004    SkASSERT(this == base->segment());
1005    if (this == testParent) {
1006        if (precisely_equal(base->fT, testT)) {
1007            return true;
1008        }
1009    }
1010    if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
1011        return false;
1012    }
1013    return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
1014}
1015
1016static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
1017    if (last) {
1018        *last = endSpan;
1019    }
1020    return nullptr;
1021}
1022
1023SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
1024        SkOpSpanBase** last) const {
1025    SkOpSpanBase* origStart = *startPtr;
1026    int step = *stepPtr;
1027    SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
1028    SkASSERT(endSpan);
1029    SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
1030    SkOpSpanBase* foundSpan;
1031    SkOpSpanBase* otherEnd;
1032    SkOpSegment* other;
1033    if (angle == nullptr) {
1034        if (endSpan->t() != 0 && endSpan->t() != 1) {
1035            return nullptr;
1036        }
1037        SkOpPtT* otherPtT = endSpan->ptT()->next();
1038        other = otherPtT->segment();
1039        foundSpan = otherPtT->span();
1040        otherEnd = step > 0
1041                ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr
1042                : foundSpan->prev();
1043    } else {
1044        int loopCount = angle->loopCount();
1045        if (loopCount > 2) {
1046            return set_last(last, endSpan);
1047        }
1048        const SkOpAngle* next = angle->next();
1049        if (nullptr == next) {
1050            return nullptr;
1051        }
1052#if DEBUG_WINDING
1053        if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor()
1054                && !next->segment()->contour()->isXor()) {
1055            SkDebugf("%s mismatched signs\n", __FUNCTION__);
1056        }
1057#endif
1058        other = next->segment();
1059        foundSpan = endSpan = next->start();
1060        otherEnd = next->end();
1061    }
1062    if (!otherEnd) {
1063        return nullptr;
1064    }
1065    int foundStep = foundSpan->step(otherEnd);
1066    if (*stepPtr != foundStep) {
1067        return set_last(last, endSpan);
1068    }
1069    SkASSERT(*startPtr);
1070//    SkASSERT(otherEnd >= 0);
1071    SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
1072    SkOpSpan* foundMin = foundSpan->starter(otherEnd);
1073    if (foundMin->windValue() != origMin->windValue()
1074            || foundMin->oppValue() != origMin->oppValue()) {
1075          return set_last(last, endSpan);
1076    }
1077    *startPtr = foundSpan;
1078    *stepPtr = foundStep;
1079    if (minPtr) {
1080        *minPtr = foundMin;
1081    }
1082    return other;
1083}
1084
1085// Please keep this in sync with DebugClearVisited()
1086void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
1087    // reset visited flag back to false
1088    do {
1089        SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1090        while ((ptT = ptT->next()) != stopPtT) {
1091            SkOpSegment* opp = ptT->segment();
1092            opp->resetVisited();
1093        }
1094    } while (!span->final() && (span = span->upCast()->next()));
1095}
1096
1097// Please keep this in sync with debugMissingCoincidence()
1098// look for pairs of undetected coincident curves
1099// assumes that segments going in have visited flag clear
1100// Even though pairs of curves correct detect coincident runs, a run may be missed
1101// if the coincidence is a product of multiple intersections. For instance, given
1102// curves A, B, and C:
1103// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
1104// the end of C that the intersection is replaced with the end of C.
1105// Even though A-B correctly do not detect an intersection at point 2,
1106// the resulting run from point 1 to point 2 is coincident on A and B.
1107bool SkOpSegment::missingCoincidence() {
1108    if (this->done()) {
1109        return false;
1110    }
1111    SkOpSpan* prior = nullptr;
1112    SkOpSpanBase* spanBase = &fHead;
1113    bool result = false;
1114    do {
1115        SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
1116        SkOPASSERT(ptT->span() == spanBase);
1117        while ((ptT = ptT->next()) != spanStopPtT) {
1118            if (ptT->deleted()) {
1119                continue;
1120            }
1121            SkOpSegment* opp = ptT->span()->segment();
1122            if (opp->done()) {
1123                continue;
1124            }
1125            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
1126            if (!opp->visited()) {
1127                continue;
1128            }
1129            if (spanBase == &fHead) {
1130                continue;
1131            }
1132            if (ptT->segment() == this) {
1133                continue;
1134            }
1135            SkOpSpan* span = spanBase->upCastable();
1136            // FIXME?: this assumes that if the opposite segment is coincident then no more
1137            // coincidence needs to be detected. This may not be true.
1138            if (span && span->containsCoincidence(opp)) {
1139                continue;
1140            }
1141            if (spanBase->containsCoinEnd(opp)) {
1142                continue;
1143            }
1144            SkOpPtT* priorPtT = nullptr, * priorStopPtT;
1145            // find prior span containing opp segment
1146            SkOpSegment* priorOpp = nullptr;
1147            SkOpSpan* priorTest = spanBase->prev();
1148            while (!priorOpp && priorTest) {
1149                priorStopPtT = priorPtT = priorTest->ptT();
1150                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
1151                    if (priorPtT->deleted()) {
1152                        continue;
1153                    }
1154                    SkOpSegment* segment = priorPtT->span()->segment();
1155                    if (segment == opp) {
1156                        prior = priorTest;
1157                        priorOpp = opp;
1158                        break;
1159                    }
1160                }
1161                priorTest = priorTest->prev();
1162            }
1163            if (!priorOpp) {
1164                continue;
1165            }
1166            if (priorPtT == ptT) {
1167                continue;
1168            }
1169            SkOpPtT* oppStart = prior->ptT();
1170            SkOpPtT* oppEnd = spanBase->ptT();
1171            bool swapped = priorPtT->fT > ptT->fT;
1172            if (swapped) {
1173                SkTSwap(priorPtT, ptT);
1174                SkTSwap(oppStart, oppEnd);
1175            }
1176            SkOpCoincidence* coincidences = this->globalState()->coincidence();
1177            SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
1178            SkOpPtT* rootPtT = ptT->span()->ptT();
1179            SkOpPtT* rootOppStart = oppStart->span()->ptT();
1180            SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
1181            if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
1182                goto swapBack;
1183            }
1184            if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
1185            // mark coincidence
1186#if DEBUG_COINCIDENCE_VERBOSE
1187                SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
1188                        rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
1189                        rootOppEnd->debugID());
1190#endif
1191                if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
1192                    coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
1193                }
1194#if DEBUG_COINCIDENCE
1195                SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
1196#endif
1197                result = true;
1198            }
1199    swapBack:
1200            if (swapped) {
1201                SkTSwap(priorPtT, ptT);
1202            }
1203        }
1204    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
1205    ClearVisited(&fHead);
1206    return result;
1207}
1208
1209// please keep this in sync with debugMoveMultiples()
1210// if a span has more than one intersection, merge the other segments' span as needed
1211bool SkOpSegment::moveMultiples() {
1212    debugValidate();
1213    SkOpSpanBase* test = &fHead;
1214    do {
1215        int addCount = test->spanAddsCount();
1216//        FAIL_IF(addCount < 1);
1217        if (addCount <= 1) {
1218            continue;
1219        }
1220        SkOpPtT* startPtT = test->ptT();
1221        SkOpPtT* testPtT = startPtT;
1222        do {  // iterate through all spans associated with start
1223            SkOpSpanBase* oppSpan = testPtT->span();
1224            if (oppSpan->spanAddsCount() == addCount) {
1225                continue;
1226            }
1227            if (oppSpan->deleted()) {
1228                continue;
1229            }
1230            SkOpSegment* oppSegment = oppSpan->segment();
1231            if (oppSegment == this) {
1232                continue;
1233            }
1234            // find range of spans to consider merging
1235            SkOpSpanBase* oppPrev = oppSpan;
1236            SkOpSpanBase* oppFirst = oppSpan;
1237            while ((oppPrev = oppPrev->prev())) {
1238                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
1239                    break;
1240                }
1241                if (oppPrev->spanAddsCount() == addCount) {
1242                    continue;
1243                }
1244                if (oppPrev->deleted()) {
1245                    continue;
1246                }
1247                oppFirst = oppPrev;
1248            }
1249            SkOpSpanBase* oppNext = oppSpan;
1250            SkOpSpanBase* oppLast = oppSpan;
1251            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
1252                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
1253                    break;
1254                }
1255                if (oppNext->spanAddsCount() == addCount) {
1256                    continue;
1257                }
1258                if (oppNext->deleted()) {
1259                    continue;
1260                }
1261                oppLast = oppNext;
1262            }
1263            if (oppFirst == oppLast) {
1264                continue;
1265            }
1266            SkOpSpanBase* oppTest = oppFirst;
1267            do {
1268                if (oppTest == oppSpan) {
1269                    continue;
1270                }
1271                // check to see if the candidate meets specific criteria:
1272                // it contains spans of segments in test's loop but not including 'this'
1273                SkOpPtT* oppStartPtT = oppTest->ptT();
1274                SkOpPtT* oppPtT = oppStartPtT;
1275                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
1276                    SkOpSegment* oppPtTSegment = oppPtT->segment();
1277                    if (oppPtTSegment == this) {
1278                        goto tryNextSpan;
1279                    }
1280                    SkOpPtT* matchPtT = startPtT;
1281                    do {
1282                        if (matchPtT->segment() == oppPtTSegment) {
1283                            goto foundMatch;
1284                        }
1285                    } while ((matchPtT = matchPtT->next()) != startPtT);
1286                    goto tryNextSpan;
1287            foundMatch:  // merge oppTest and oppSpan
1288                    oppSegment->debugValidate();
1289                    oppTest->mergeMatches(oppSpan);
1290                    oppTest->addOpp(oppSpan);
1291                    oppSegment->debugValidate();
1292                    goto checkNextSpan;
1293                }
1294        tryNextSpan:
1295                ;
1296            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
1297        } while ((testPtT = testPtT->next()) != startPtT);
1298checkNextSpan:
1299        ;
1300    } while ((test = test->final() ? nullptr : test->upCast()->next()));
1301    debugValidate();
1302    return true;
1303}
1304
1305// adjacent spans may have points close by
1306bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan,
1307        bool* found) const {
1308    const SkOpPtT* refHead = refSpan->ptT();
1309    const SkOpPtT* checkHead = checkSpan->ptT();
1310// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
1311    if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) {
1312#if DEBUG_COINCIDENCE
1313        // verify that no combination of points are close
1314        const SkOpPtT* dBugRef = refHead;
1315        do {
1316            const SkOpPtT* dBugCheck = checkHead;
1317            do {
1318                SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
1319                dBugCheck = dBugCheck->next();
1320            } while (dBugCheck != checkHead);
1321            dBugRef = dBugRef->next();
1322        } while (dBugRef != refHead);
1323#endif
1324        *found = false;
1325        return true;
1326    }
1327    // check only unique points
1328    SkScalar distSqBest = SK_ScalarMax;
1329    const SkOpPtT* refBest = nullptr;
1330    const SkOpPtT* checkBest = nullptr;
1331    const SkOpPtT* ref = refHead;
1332    do {
1333        if (ref->deleted()) {
1334            continue;
1335        }
1336        while (ref->ptAlreadySeen(refHead)) {
1337            ref = ref->next();
1338            if (ref == refHead) {
1339                goto doneCheckingDistance;
1340            }
1341        }
1342        const SkOpPtT* check = checkHead;
1343        const SkOpSegment* refSeg = ref->segment();
1344        int escapeHatch = 100000;  // defend against infinite loops
1345        do {
1346            if (check->deleted()) {
1347                continue;
1348            }
1349            while (check->ptAlreadySeen(checkHead)) {
1350                check = check->next();
1351                if (check == checkHead) {
1352                    goto nextRef;
1353                }
1354            }
1355            SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt);
1356            if (distSqBest > distSq && (refSeg != check->segment()
1357                    || !refSeg->ptsDisjoint(*ref, *check))) {
1358                distSqBest = distSq;
1359                refBest = ref;
1360                checkBest = check;
1361            }
1362            if (--escapeHatch <= 0) {
1363                return false;
1364            }
1365        } while ((check = check->next()) != checkHead);
1366    nextRef:
1367        ;
1368   } while ((ref = ref->next()) != refHead);
1369doneCheckingDistance:
1370    *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
1371            checkBest->fPt);
1372    return true;
1373}
1374
1375// Please keep this function in sync with debugMoveNearby()
1376// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
1377bool SkOpSegment::moveNearby() {
1378    debugValidate();
1379    // release undeleted spans pointing to this seg that are linked to the primary span
1380    SkOpSpanBase* spanBase = &fHead;
1381    int escapeHatch = 9999;  // the largest count for a regular test is 50; for a fuzzer, 500
1382    do {
1383        SkOpPtT* ptT = spanBase->ptT();
1384        const SkOpPtT* headPtT = ptT;
1385        while ((ptT = ptT->next()) != headPtT) {
1386            if (!--escapeHatch) {
1387                return false;
1388            }
1389            SkOpSpanBase* test = ptT->span();
1390            if (ptT->segment() == this && !ptT->deleted() && test != spanBase
1391                    && test->ptT() == ptT) {
1392                if (test->final()) {
1393                    if (spanBase == &fHead) {
1394                        this->clearAll();
1395                        return true;
1396                    }
1397                    spanBase->upCast()->release(ptT);
1398                } else if (test->prev()) {
1399                    test->upCast()->release(headPtT);
1400                }
1401                break;
1402            }
1403        }
1404        spanBase = spanBase->upCast()->next();
1405    } while (!spanBase->final());
1406    // This loop looks for adjacent spans which are near by
1407    spanBase = &fHead;
1408    do {  // iterate through all spans associated with start
1409        SkOpSpanBase* test = spanBase->upCast()->next();
1410        bool found;
1411        if (!this->spansNearby(spanBase, test, &found)) {
1412            return false;
1413        }
1414        if (found) {
1415            if (test->final()) {
1416                if (spanBase->prev()) {
1417                    test->merge(spanBase->upCast());
1418                } else {
1419                    this->clearAll();
1420                    return true;
1421                }
1422            } else {
1423                spanBase->merge(test->upCast());
1424            }
1425        }
1426        spanBase = test;
1427    } while (!spanBase->final());
1428    debugValidate();
1429    return true;
1430}
1431
1432bool SkOpSegment::operand() const {
1433    return fContour->operand();
1434}
1435
1436bool SkOpSegment::oppXor() const {
1437    return fContour->oppXor();
1438}
1439
1440bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
1441    if (fVerb == SkPath::kLine_Verb) {
1442        return false;
1443    }
1444    // quads (and cubics) can loop back to nearly a line so that an opposite curve
1445    // hits in two places with very different t values.
1446    // OPTIMIZATION: curves could be preflighted so that, for example, something like
1447    // 'controls contained by ends' could avoid this check for common curves
1448    // 'ends are extremes in x or y' is cheaper to compute and real-world common
1449    // on the other hand, the below check is relatively inexpensive
1450    double midT = (t1 + t2) / 2;
1451    SkPoint midPt = this->ptAtT(midT);
1452    double seDistSq = SkTMax(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2);
1453    return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq ||
1454           SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq;
1455}
1456
1457void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1458        int* maxWinding, int* sumWinding) {
1459    int deltaSum = SpanSign(start, end);
1460    *maxWinding = *sumMiWinding;
1461    *sumWinding = *sumMiWinding -= deltaSum;
1462    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1463}
1464
1465void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1466        int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
1467        int* oppSumWinding) {
1468    int deltaSum = SpanSign(start, end);
1469    int oppDeltaSum = OppSign(start, end);
1470    if (operand()) {
1471        *maxWinding = *sumSuWinding;
1472        *sumWinding = *sumSuWinding -= deltaSum;
1473        *oppMaxWinding = *sumMiWinding;
1474        *oppSumWinding = *sumMiWinding -= oppDeltaSum;
1475    } else {
1476        *maxWinding = *sumMiWinding;
1477        *sumWinding = *sumMiWinding -= deltaSum;
1478        *oppMaxWinding = *sumSuWinding;
1479        *oppSumWinding = *sumSuWinding -= oppDeltaSum;
1480    }
1481    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1482    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
1483}
1484
1485bool SkOpSegment::sortAngles() {
1486    SkOpSpanBase* span = &this->fHead;
1487    do {
1488        SkOpAngle* fromAngle = span->fromAngle();
1489        SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle();
1490        if (!fromAngle && !toAngle) {
1491            continue;
1492        }
1493#if DEBUG_ANGLE
1494        bool wroteAfterHeader = false;
1495#endif
1496        SkOpAngle* baseAngle = fromAngle;
1497        if (fromAngle && toAngle) {
1498#if DEBUG_ANGLE
1499            SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
1500                    span->debugID());
1501            wroteAfterHeader = true;
1502#endif
1503            FAIL_IF(!fromAngle->insert(toAngle));
1504        } else if (!fromAngle) {
1505            baseAngle = toAngle;
1506        }
1507        SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1508        do {
1509            SkOpSpanBase* oSpan = ptT->span();
1510            if (oSpan == span) {
1511                continue;
1512            }
1513            SkOpAngle* oAngle = oSpan->fromAngle();
1514            if (oAngle) {
1515#if DEBUG_ANGLE
1516                if (!wroteAfterHeader) {
1517                    SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1518                            span->t(), span->debugID());
1519                    wroteAfterHeader = true;
1520                }
1521#endif
1522                if (!oAngle->loopContains(baseAngle)) {
1523                    baseAngle->insert(oAngle);
1524                }
1525            }
1526            if (!oSpan->final()) {
1527                oAngle = oSpan->upCast()->toAngle();
1528                if (oAngle) {
1529#if DEBUG_ANGLE
1530                    if (!wroteAfterHeader) {
1531                        SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1532                                span->t(), span->debugID());
1533                        wroteAfterHeader = true;
1534                    }
1535#endif
1536                    if (!oAngle->loopContains(baseAngle)) {
1537                        baseAngle->insert(oAngle);
1538                    }
1539                }
1540            }
1541        } while ((ptT = ptT->next()) != stopPtT);
1542        if (baseAngle->loopCount() == 1) {
1543            span->setFromAngle(nullptr);
1544            if (toAngle) {
1545                span->upCast()->setToAngle(nullptr);
1546            }
1547            baseAngle = nullptr;
1548        }
1549#if DEBUG_SORT
1550        SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
1551#endif
1552    } while (!span->final() && (span = span->upCast()->next()));
1553    return true;
1554}
1555
1556bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1557        SkDCurve* edge) const {
1558    SkASSERT(start != end);
1559    const SkOpPtT& startPtT = *start->ptT();
1560    const SkOpPtT& endPtT = *end->ptT();
1561    SkDEBUGCODE(edge->fVerb = fVerb);
1562    edge->fCubic[0].set(startPtT.fPt);
1563    int points = SkPathOpsVerbToPoints(fVerb);
1564    edge->fCubic[points].set(endPtT.fPt);
1565    if (fVerb == SkPath::kLine_Verb) {
1566        return false;
1567    }
1568    double startT = startPtT.fT;
1569    double endT = endPtT.fT;
1570    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1571        // don't compute midpoints if we already have them
1572        if (fVerb == SkPath::kQuad_Verb) {
1573            edge->fLine[1].set(fPts[1]);
1574            return false;
1575        }
1576        if (fVerb == SkPath::kConic_Verb) {
1577            edge->fConic[1].set(fPts[1]);
1578            edge->fConic.fWeight = fWeight;
1579            return false;
1580        }
1581        SkASSERT(fVerb == SkPath::kCubic_Verb);
1582        if (startT == 0) {
1583            edge->fCubic[1].set(fPts[1]);
1584            edge->fCubic[2].set(fPts[2]);
1585            return false;
1586        }
1587        edge->fCubic[1].set(fPts[2]);
1588        edge->fCubic[2].set(fPts[1]);
1589        return false;
1590    }
1591    if (fVerb == SkPath::kQuad_Verb) {
1592        edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
1593    } else if (fVerb == SkPath::kConic_Verb) {
1594        edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
1595            startT, endT, &edge->fConic.fWeight);
1596    } else {
1597        SkASSERT(fVerb == SkPath::kCubic_Verb);
1598        SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
1599    }
1600    return true;
1601}
1602
1603bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
1604        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
1605    // average t, find mid pt
1606    double midT = (prior->t() + spanBase->t()) / 2;
1607    SkPoint midPt = this->ptAtT(midT);
1608    bool coincident = true;
1609    // if the mid pt is not near either end pt, project perpendicular through opp seg
1610    if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
1611            && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
1612        if (priorPtT->span() == ptT->span()) {
1613          return false;
1614        }
1615        coincident = false;
1616        SkIntersections i;
1617        SkDCurve curvePart;
1618        this->subDivide(prior, spanBase, &curvePart);
1619        SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
1620        SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
1621        SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
1622        SkDCurve oppPart;
1623        opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
1624        (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
1625        // measure distance and see if it's small enough to denote coincidence
1626        for (int index = 0; index < i.used(); ++index) {
1627            if (!between(0, i[0][index], 1)) {
1628                continue;
1629            }
1630            SkDPoint oppPt = i.pt(index);
1631            if (oppPt.approximatelyDEqual(midPt)) {
1632                // the coincidence can occur at almost any angle
1633                coincident = true;
1634            }
1635        }
1636    }
1637    return coincident;
1638}
1639
1640SkOpSpan* SkOpSegment::undoneSpan() {
1641    SkOpSpan* span = &fHead;
1642    SkOpSpanBase* next;
1643    do {
1644        next = span->next();
1645        if (!span->done()) {
1646            return span;
1647        }
1648    } while (!next->final() && (span = next->upCast()));
1649    return nullptr;
1650}
1651
1652int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
1653    const SkOpSpan* lesser = start->starter(end);
1654    int oppWinding = lesser->oppSum();
1655    int oppSpanWinding = SkOpSegment::OppSign(start, end);
1656    if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
1657            && oppWinding != SK_MaxS32) {
1658        oppWinding -= oppSpanWinding;
1659    }
1660    return oppWinding;
1661}
1662
1663int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
1664    const SkOpSpanBase* startSpan = angle->start();
1665    const SkOpSpanBase* endSpan = angle->end();
1666    return updateOppWinding(endSpan, startSpan);
1667}
1668
1669int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
1670    const SkOpSpanBase* startSpan = angle->start();
1671    const SkOpSpanBase* endSpan = angle->end();
1672    return updateOppWinding(startSpan, endSpan);
1673}
1674
1675int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
1676    SkOpSpan* lesser = start->starter(end);
1677    int winding = lesser->windSum();
1678    if (winding == SK_MinS32) {
1679        winding = lesser->computeWindSum();
1680    }
1681    if (winding == SK_MinS32) {
1682        return winding;
1683    }
1684    int spanWinding = SkOpSegment::SpanSign(start, end);
1685    if (winding && UseInnerWinding(winding - spanWinding, winding)
1686            && winding != SK_MaxS32) {
1687        winding -= spanWinding;
1688    }
1689    return winding;
1690}
1691
1692int SkOpSegment::updateWinding(SkOpAngle* angle) {
1693    SkOpSpanBase* startSpan = angle->start();
1694    SkOpSpanBase* endSpan = angle->end();
1695    return updateWinding(endSpan, startSpan);
1696}
1697
1698int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) {
1699    SkOpSpanBase* startSpan = angle->start();
1700    SkOpSpanBase* endSpan = angle->end();
1701    return updateWinding(startSpan, endSpan);
1702}
1703
1704// OPTIMIZATION: does the following also work, and is it any faster?
1705// return outerWinding * innerWinding > 0
1706//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
1707bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
1708    SkASSERT(outerWinding != SK_MaxS32);
1709    SkASSERT(innerWinding != SK_MaxS32);
1710    int absOut = SkTAbs(outerWinding);
1711    int absIn = SkTAbs(innerWinding);
1712    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
1713    return result;
1714}
1715
1716int SkOpSegment::windSum(const SkOpAngle* angle) const {
1717    const SkOpSpan* minSpan = angle->start()->starter(angle->end());
1718    return minSpan->windSum();
1719}
1720