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