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