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