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