SkOpSegment.cpp revision 27c8eb8ffd7e221693d840c2b9279d53fe6f03d4 
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 NULL;
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 NULL;
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 = NULL;
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 NULL;
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 (NULL == firstAngle || NULL == 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 = NULL;
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 = NULL;
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 : NULL;
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 = NULL;
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 = NULL;
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 : NULL;
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
618/*
619 The M and S variable name parts stand for the operators.
620   Mi stands for Minuend (see wiki subtraction, analogous to difference)
621   Su stands for Subtrahend
622 The Opp variable name part designates that the value is for the Opposite operator.
623 Opposite values result from combining coincident spans.
624 */
625SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
626        SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) {
627    SkOpSpanBase* start = *nextStart;
628    SkOpSpanBase* end = *nextEnd;
629    SkASSERT(start != end);
630    int step = start->step(end);
631    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
632    if (other) {
633    // mark the smaller of startIndex, endIndex done, and all adjacent
634    // spans with the same T value (but not 'other' spans)
635#if DEBUG_WINDING
636        SkDebugf("%s simple\n", __FUNCTION__);
637#endif
638        SkOpSpan* startSpan = start->starter(end);
639        if (startSpan->done()) {
640            return NULL;
641        }
642        markDone(startSpan);
643        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
644        return other;
645    }
646    SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
647    SkASSERT(endNear == end);  // is this ever not end?
648    SkASSERT(endNear);
649    SkASSERT(start != endNear);
650    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
651    // more than one viable candidate -- measure angles to find best
652    int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
653    bool sortable = calcWinding != SK_NaN32;
654    if (!sortable) {
655        *unsortable = true;
656        markDone(start->starter(end));
657        return NULL;
658    }
659    SkOpAngle* angle = this->spanToAngle(end, start);
660    if (angle->unorderable()) {
661        *unsortable = true;
662        markDone(start->starter(end));
663        return NULL;
664    }
665#if DEBUG_SORT
666    SkDebugf("%s\n", __FUNCTION__);
667    angle->debugLoop();
668#endif
669    int sumMiWinding = updateWinding(end, start);
670    if (sumMiWinding == SK_MinS32) {
671        *unsortable = true;
672        markDone(start->starter(end));
673        return NULL;
674    }
675    int sumSuWinding = updateOppWinding(end, start);
676    if (operand()) {
677        SkTSwap<int>(sumMiWinding, sumSuWinding);
678    }
679    SkOpAngle* nextAngle = angle->next();
680    const SkOpAngle* foundAngle = NULL;
681    bool foundDone = false;
682    // iterate through the angle, and compute everyone's winding
683    SkOpSegment* nextSegment;
684    int activeCount = 0;
685    do {
686        nextSegment = nextAngle->segment();
687        bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
688                nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
689        if (activeAngle) {
690            ++activeCount;
691            if (!foundAngle || (foundDone && activeCount & 1)) {
692                foundAngle = nextAngle;
693                foundDone = nextSegment->done(nextAngle);
694            }
695        }
696        if (nextSegment->done()) {
697            continue;
698        }
699        if (!activeAngle) {
700            (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
701        }
702        SkOpSpanBase* last = nextAngle->lastMarked();
703        if (last) {
704            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
705            *chase->append() = last;
706#if DEBUG_WINDING
707            SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
708                    last->segment()->debugID(), last->debugID());
709            if (!last->final()) {
710                SkDebugf(" windSum=%d", last->upCast()->windSum());
711            }
712            SkDebugf("\n");
713#endif
714        }
715    } while ((nextAngle = nextAngle->next()) != angle);
716    start->segment()->markDone(start->starter(end));
717    if (!foundAngle) {
718        return NULL;
719    }
720    *nextStart = foundAngle->start();
721    *nextEnd = foundAngle->end();
722    nextSegment = foundAngle->segment();
723#if DEBUG_WINDING
724    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
725            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
726 #endif
727    return nextSegment;
728}
729
730SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
731        SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
732    SkOpSpanBase* start = *nextStart;
733    SkOpSpanBase* end = *nextEnd;
734    SkASSERT(start != end);
735    int step = start->step(end);
736    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
737    if (other) {
738    // mark the smaller of startIndex, endIndex done, and all adjacent
739    // spans with the same T value (but not 'other' spans)
740#if DEBUG_WINDING
741        SkDebugf("%s simple\n", __FUNCTION__);
742#endif
743        SkOpSpan* startSpan = start->starter(end);
744        if (startSpan->done()) {
745            return NULL;
746        }
747        markDone(startSpan);
748        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
749        return other;
750    }
751    SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
752    SkASSERT(endNear == end);  // is this ever not end?
753    SkASSERT(endNear);
754    SkASSERT(start != endNear);
755    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
756    // more than one viable candidate -- measure angles to find best
757    int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
758    bool sortable = calcWinding != SK_NaN32;
759    if (!sortable) {
760        *unsortable = true;
761        markDone(start->starter(end));
762        return NULL;
763    }
764    SkOpAngle* angle = this->spanToAngle(end, start);
765    if (angle->unorderable()) {
766        *unsortable = true;
767        markDone(start->starter(end));
768        return NULL;
769    }
770#if DEBUG_SORT
771    SkDebugf("%s\n", __FUNCTION__);
772    angle->debugLoop();
773#endif
774    int sumWinding = updateWinding(end, start);
775    SkOpAngle* nextAngle = angle->next();
776    const SkOpAngle* foundAngle = NULL;
777    bool foundDone = false;
778    // iterate through the angle, and compute everyone's winding
779    SkOpSegment* nextSegment;
780    int activeCount = 0;
781    do {
782        nextSegment = nextAngle->segment();
783        bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
784                &sumWinding);
785        if (activeAngle) {
786            ++activeCount;
787            if (!foundAngle || (foundDone && activeCount & 1)) {
788                foundAngle = nextAngle;
789                foundDone = nextSegment->done(nextAngle);
790            }
791        }
792        if (nextSegment->done()) {
793            continue;
794        }
795        if (!activeAngle) {
796            (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
797        }
798        SkOpSpanBase* last = nextAngle->lastMarked();
799        if (last) {
800            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
801            *chase->append() = last;
802#if DEBUG_WINDING
803            SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
804                    last->segment()->debugID(), last->debugID());
805            if (!last->final()) {
806                SkDebugf(" windSum=%d", last->upCast()->windSum());
807            }
808            SkDebugf("\n");
809#endif
810        }
811    } while ((nextAngle = nextAngle->next()) != angle);
812    start->segment()->markDone(start->starter(end));
813    if (!foundAngle) {
814        return NULL;
815    }
816    *nextStart = foundAngle->start();
817    *nextEnd = foundAngle->end();
818    nextSegment = foundAngle->segment();
819#if DEBUG_WINDING
820    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
821            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
822 #endif
823    return nextSegment;
824}
825
826SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
827        bool* unsortable) {
828    SkOpSpanBase* start = *nextStart;
829    SkOpSpanBase* end = *nextEnd;
830    SkASSERT(start != end);
831    int step = start->step(end);
832    SkOpSegment* other = this->isSimple(nextStart, &step);  // advances nextStart
833    if (other) {
834    // mark the smaller of startIndex, endIndex done, and all adjacent
835    // spans with the same T value (but not 'other' spans)
836#if DEBUG_WINDING
837        SkDebugf("%s simple\n", __FUNCTION__);
838#endif
839        SkOpSpan* startSpan = start->starter(end);
840        if (startSpan->done()) {
841            return NULL;
842        }
843        markDone(startSpan);
844        *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
845        return other;
846    }
847    SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
848            : (*nextStart)->prev());
849    SkASSERT(endNear == end);  // is this ever not end?
850    SkASSERT(endNear);
851    SkASSERT(start != endNear);
852    SkASSERT((start->t() < endNear->t()) ^ (step < 0));
853    SkOpAngle* angle = this->spanToAngle(end, start);
854    if (!angle || angle->unorderable()) {
855        *unsortable = true;
856        markDone(start->starter(end));
857        return NULL;
858    }
859#if DEBUG_SORT
860    SkDebugf("%s\n", __FUNCTION__);
861    angle->debugLoop();
862#endif
863    SkOpAngle* nextAngle = angle->next();
864    const SkOpAngle* foundAngle = NULL;
865    bool foundDone = false;
866    // iterate through the angle, and compute everyone's winding
867    SkOpSegment* nextSegment;
868    int activeCount = 0;
869    do {
870        nextSegment = nextAngle->segment();
871        ++activeCount;
872        if (!foundAngle || (foundDone && activeCount & 1)) {
873            foundAngle = nextAngle;
874            if (!(foundDone = nextSegment->done(nextAngle))) {
875                break;
876            }
877        }
878        nextAngle = nextAngle->next();
879    } while (nextAngle != angle);
880    start->segment()->markDone(start->starter(end));
881    if (!foundAngle) {
882        return NULL;
883    }
884    *nextStart = foundAngle->start();
885    *nextEnd = foundAngle->end();
886    nextSegment = foundAngle->segment();
887#if DEBUG_WINDING
888    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
889            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
890 #endif
891    return nextSegment;
892}
893
894SkOpGlobalState* SkOpSegment::globalState() const {
895    return contour()->globalState();
896}
897
898void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
899    fContour = contour;
900    fNext = NULL;
901    fOriginal[0] = pts[0];
902    fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)];
903    fPts = pts;
904    fWeight = weight;
905    fVerb = verb;
906    fCubicType = SkDCubic::kUnsplit_SkDCubicType;
907    fCount = 0;
908    fDoneCount = 0;
909    fTopsFound = false;
910    fVisited = false;
911    SkOpSpan* zeroSpan = &fHead;
912    zeroSpan->init(this, NULL, 0, fPts[0]);
913    SkOpSpanBase* oneSpan = &fTail;
914    zeroSpan->setNext(oneSpan);
915    oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
916    SkDEBUGCODE(fID = globalState()->nextSegmentID());
917}
918
919bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
920    SkDPoint cPt = this->dPtAtT(t);
921    SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
922    SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
923    SkIntersections i;
924    (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
925    int used = i.used();
926    for (int index = 0; index < used; ++index) {
927        if (cPt.roughlyEqual(i.pt(index))) {
928            return true;
929        }
930    }
931    return false;
932}
933
934bool SkOpSegment::isXor() const {
935    return fContour->isXor();
936}
937
938void SkOpSegment::markAllDone() {
939    SkOpSpan* span = this->head();
940    do {
941        this->markDone(span);
942    } while ((span = span->next()->upCastable()));
943}
944
945SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) {
946    int step = start->step(end);
947    SkOpSpan* minSpan = start->starter(end);
948    markDone(minSpan);
949    SkOpSpanBase* last = NULL;
950    SkOpSegment* other = this;
951    while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
952        if (other->done()) {
953            SkASSERT(!last);
954            break;
955        }
956        other->markDone(minSpan);
957    }
958    return last;
959}
960
961bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
962        SkOpSpanBase** lastPtr) {
963    SkOpSpan* spanStart = start->starter(end);
964    int step = start->step(end);
965    bool success = markWinding(spanStart, winding);
966    SkOpSpanBase* last = NULL;
967    SkOpSegment* other = this;
968    while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
969        if (spanStart->windSum() != SK_MinS32) {
970            SkASSERT(spanStart->windSum() == winding);
971            SkASSERT(!last);
972            break;
973        }
974        (void) other->markWinding(spanStart, winding);
975    }
976    if (lastPtr) {
977        *lastPtr = last;
978    }
979    return success;
980}
981
982bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
983        int winding, int oppWinding, SkOpSpanBase** lastPtr) {
984    SkOpSpan* spanStart = start->starter(end);
985    int step = start->step(end);
986    bool success = markWinding(spanStart, winding, oppWinding);
987    SkOpSpanBase* last = NULL;
988    SkOpSegment* other = this;
989    while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
990        if (spanStart->windSum() != SK_MinS32) {
991            if (this->operand() == other->operand()) {
992                if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) {
993                    this->globalState()->setWindingFailed();
994                    return false;
995                }
996            } else {
997                SkASSERT(spanStart->windSum() == oppWinding);
998                SkASSERT(spanStart->oppSum() == winding);
999            }
1000            SkASSERT(!last);
1001            break;
1002        }
1003        if (this->operand() == other->operand()) {
1004            (void) other->markWinding(spanStart, winding, oppWinding);
1005        } else {
1006            (void) other->markWinding(spanStart, oppWinding, winding);
1007        }
1008    }
1009    if (lastPtr) {
1010        *lastPtr = last;
1011    }
1012    return success;
1013}
1014
1015SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
1016    SkASSERT(angle->segment() == this);
1017    if (UseInnerWinding(maxWinding, sumWinding)) {
1018        maxWinding = sumWinding;
1019    }
1020    SkOpSpanBase* last;
1021    (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last);
1022#if DEBUG_WINDING
1023    if (last) {
1024        SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
1025                last->segment()->debugID(), last->debugID());
1026        if (!last->final()) {
1027            SkDebugf(" windSum=");
1028            SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
1029        }
1030        SkDebugf("\n");
1031    }
1032#endif
1033    return last;
1034}
1035
1036SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
1037                                   int oppSumWinding, const SkOpAngle* angle) {
1038    SkASSERT(angle->segment() == this);
1039    if (UseInnerWinding(maxWinding, sumWinding)) {
1040        maxWinding = sumWinding;
1041    }
1042    if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
1043        oppMaxWinding = oppSumWinding;
1044    }
1045    SkOpSpanBase* last = NULL;
1046    // caller doesn't require that this marks anything
1047    (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last);
1048#if DEBUG_WINDING
1049    if (last) {
1050        SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
1051                last->segment()->debugID(), last->debugID());
1052        if (!last->final()) {
1053            SkDebugf(" windSum=");
1054            SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
1055        }
1056        SkDebugf(" \n");
1057    }
1058#endif
1059    return last;
1060}
1061
1062void SkOpSegment::markDone(SkOpSpan* span) {
1063    SkASSERT(this == span->segment());
1064    if (span->done()) {
1065        return;
1066    }
1067#if DEBUG_MARK_DONE
1068    debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
1069#endif
1070    span->setDone(true);
1071    ++fDoneCount;
1072    debugValidate();
1073}
1074
1075bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
1076    SkASSERT(this == span->segment());
1077    SkASSERT(winding);
1078    if (span->done()) {
1079        return false;
1080    }
1081#if DEBUG_MARK_DONE
1082    debugShowNewWinding(__FUNCTION__, span, winding);
1083#endif
1084    span->setWindSum(winding);
1085    debugValidate();
1086    return true;
1087}
1088
1089bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
1090    SkASSERT(this == span->segment());
1091    SkASSERT(winding || oppWinding);
1092    if (span->done()) {
1093        return false;
1094    }
1095#if DEBUG_MARK_DONE
1096    debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
1097#endif
1098    span->setWindSum(winding);
1099    span->setOppSum(oppWinding);
1100    debugValidate();
1101    return true;
1102}
1103
1104bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
1105        const SkPoint& testPt) const {
1106    const SkOpSegment* baseParent = base->segment();
1107    if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) {
1108        return true;
1109    }
1110    if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
1111        return false;
1112    }
1113    return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
1114}
1115
1116static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
1117    if (last) {
1118        *last = endSpan;
1119    }
1120    return NULL;
1121}
1122
1123SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
1124        SkOpSpanBase** last) const {
1125    SkOpSpanBase* origStart = *startPtr;
1126    int step = *stepPtr;
1127    SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
1128    SkASSERT(endSpan);
1129    SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
1130    SkOpSpanBase* foundSpan;
1131    SkOpSpanBase* otherEnd;
1132    SkOpSegment* other;
1133    if (angle == NULL) {
1134        if (endSpan->t() != 0 && endSpan->t() != 1) {
1135            return NULL;
1136        }
1137        SkOpPtT* otherPtT = endSpan->ptT()->next();
1138        other = otherPtT->segment();
1139        foundSpan = otherPtT->span();
1140        otherEnd = step > 0 ? foundSpan->upCast()->next() : foundSpan->prev();
1141    } else {
1142        int loopCount = angle->loopCount();
1143        if (loopCount > 2) {
1144            return set_last(last, endSpan);
1145        }
1146        const SkOpAngle* next = angle->next();
1147        if (NULL == next) {
1148            return NULL;
1149        }
1150#if DEBUG_WINDING
1151        if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor()
1152                && !next->segment()->contour()->isXor()) {
1153            SkDebugf("%s mismatched signs\n", __FUNCTION__);
1154        }
1155#endif
1156        other = next->segment();
1157        foundSpan = endSpan = next->start();
1158        otherEnd = next->end();
1159    }
1160    int foundStep = foundSpan->step(otherEnd);
1161    if (*stepPtr != foundStep) {
1162        return set_last(last, endSpan);
1163    }
1164    SkASSERT(*startPtr);
1165    if (!otherEnd) {
1166        return NULL;
1167    }
1168//    SkASSERT(otherEnd >= 0);
1169    SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
1170    SkOpSpan* foundMin = foundSpan->starter(otherEnd);
1171    if (foundMin->windValue() != origMin->windValue()
1172            || foundMin->oppValue() != origMin->oppValue()) {
1173          return set_last(last, endSpan);
1174    }
1175    *startPtr = foundSpan;
1176    *stepPtr = foundStep;
1177    if (minPtr) {
1178        *minPtr = foundMin;
1179    }
1180    return other;
1181}
1182
1183static void clear_visited(SkOpSpanBase* span) {
1184    // reset visited flag back to false
1185    do {
1186        SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1187        while ((ptT = ptT->next()) != stopPtT) {
1188            SkOpSegment* opp = ptT->segment();
1189            opp->resetVisited();
1190        }
1191    } while (!span->final() && (span = span->upCast()->next()));
1192}
1193
1194// look for pairs of undetected coincident curves
1195// assumes that segments going in have visited flag clear
1196// curve/curve intersection should now do a pretty good job of finding coincident runs so
1197// this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
1198// the opp is not a line
1199bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
1200    if (this->verb() != SkPath::kLine_Verb) {
1201        return false;
1202    }
1203    if (this->done()) {
1204        return false;
1205    }
1206    SkOpSpan* prior = NULL;
1207    SkOpSpanBase* spanBase = &fHead;
1208    do {
1209        SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
1210        SkASSERT(ptT->span() == spanBase);
1211        while ((ptT = ptT->next()) != spanStopPtT) {
1212            if (ptT->deleted()) {
1213                continue;
1214            }
1215            SkOpSegment* opp = ptT->span()->segment();
1216            if (opp->verb() == SkPath::kLine_Verb) {
1217                continue;
1218            }
1219            if (opp->done()) {
1220                continue;
1221            }
1222            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
1223            if (!opp->visited()) {
1224                continue;
1225            }
1226            if (spanBase == &fHead) {
1227                continue;
1228            }
1229            SkOpSpan* span = spanBase->upCastable();
1230            // FIXME?: this assumes that if the opposite segment is coincident then no more
1231            // coincidence needs to be detected. This may not be true.
1232            if (span && span->containsCoincidence(opp)) {
1233                continue;
1234            }
1235            if (spanBase->containsCoinEnd(opp)) {
1236                continue;
1237            }
1238            SkOpPtT* priorPtT = NULL, * priorStopPtT;
1239            // find prior span containing opp segment
1240            SkOpSegment* priorOpp = NULL;
1241            SkOpSpan* priorTest = spanBase->prev();
1242            while (!priorOpp && priorTest) {
1243                priorStopPtT = priorPtT = priorTest->ptT();
1244                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
1245                    if (priorPtT->deleted()) {
1246                        continue;
1247                    }
1248                    SkOpSegment* segment = priorPtT->span()->segment();
1249                    if (segment == opp) {
1250                        prior = priorTest;
1251                        priorOpp = opp;
1252                        break;
1253                    }
1254                }
1255                priorTest = priorTest->prev();
1256            }
1257            if (!priorOpp) {
1258                continue;
1259            }
1260            SkOpPtT* oppStart = prior->ptT();
1261            SkOpPtT* oppEnd = spanBase->ptT();
1262            bool swapped = priorPtT->fT > ptT->fT;
1263            if (swapped) {
1264                SkTSwap(priorPtT, ptT);
1265                SkTSwap(oppStart, oppEnd);
1266            }
1267            bool flipped = oppStart->fT > oppEnd->fT;
1268            bool coincident;
1269            if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
1270                goto swapBack;
1271            }
1272            coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
1273            if (coincident) {
1274            // mark coincidence
1275                if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd)
1276                        && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) {
1277                    coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
1278                }
1279                clear_visited(&fHead);
1280                return true;
1281            }
1282    swapBack:
1283            if (swapped) {
1284                SkTSwap(priorPtT, ptT);
1285            }
1286        }
1287    } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next()));
1288    clear_visited(&fHead);
1289    return false;
1290}
1291
1292// if a span has more than one intersection, merge the other segments' span as needed
1293void SkOpSegment::moveMultiples() {
1294    debugValidate();
1295    SkOpSpanBase* test = &fHead;
1296    do {
1297        int addCount = test->spanAddsCount();
1298        SkASSERT(addCount >= 1);
1299        if (addCount == 1) {
1300            continue;
1301        }
1302        SkOpPtT* startPtT = test->ptT();
1303        SkOpPtT* testPtT = startPtT;
1304        do {  // iterate through all spans associated with start
1305            SkOpSpanBase* oppSpan = testPtT->span();
1306            if (oppSpan->spanAddsCount() == addCount) {
1307                continue;
1308            }
1309            if (oppSpan->deleted()) {
1310                continue;
1311            }
1312            SkOpSegment* oppSegment = oppSpan->segment();
1313            if (oppSegment == this) {
1314                continue;
1315            }
1316            // find range of spans to consider merging
1317            SkOpSpanBase* oppPrev = oppSpan;
1318            SkOpSpanBase* oppFirst = oppSpan;
1319            while ((oppPrev = oppPrev->prev())) {
1320                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
1321                    break;
1322                }
1323                if (oppPrev->spanAddsCount() == addCount) {
1324                    continue;
1325                }
1326                if (oppPrev->deleted()) {
1327                    continue;
1328                }
1329                oppFirst = oppPrev;
1330            }
1331            SkOpSpanBase* oppNext = oppSpan;
1332            SkOpSpanBase* oppLast = oppSpan;
1333            while ((oppNext = oppNext->final() ? NULL : oppNext->upCast()->next())) {
1334                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
1335                    break;
1336                }
1337                if (oppNext->spanAddsCount() == addCount) {
1338                    continue;
1339                }
1340                if (oppNext->deleted()) {
1341                    continue;
1342                }
1343                oppLast = oppNext;
1344            }
1345            if (oppFirst == oppLast) {
1346                continue;
1347            }
1348            SkOpSpanBase* oppTest = oppFirst;
1349            do {
1350                if (oppTest == oppSpan) {
1351                    continue;
1352                }
1353                // check to see if the candidate meets specific criteria:
1354                // it contains spans of segments in test's loop but not including 'this'
1355                SkOpPtT* oppStartPtT = oppTest->ptT();
1356                SkOpPtT* oppPtT = oppStartPtT;
1357                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
1358                    SkOpSegment* oppPtTSegment = oppPtT->segment();
1359                    if (oppPtTSegment == this) {
1360                        goto tryNextSpan;
1361                    }
1362                    SkOpPtT* matchPtT = startPtT;
1363                    do {
1364                        if (matchPtT->segment() == oppPtTSegment) {
1365                            goto foundMatch;
1366                        }
1367                    } while ((matchPtT = matchPtT->next()) != startPtT);
1368                    goto tryNextSpan;
1369            foundMatch:  // merge oppTest and oppSpan
1370                    oppSegment->debugValidate();
1371                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
1372                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
1373                        SkASSERT(oppSpan != &oppSegment->fTail);
1374                        oppTest->merge(oppSpan->upCast());
1375                    } else {
1376                        oppSpan->merge(oppTest->upCast());
1377                    }
1378                    oppSegment->debugValidate();
1379                    goto checkNextSpan;
1380                }
1381        tryNextSpan:
1382                ;
1383            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
1384        } while ((testPtT = testPtT->next()) != startPtT);
1385checkNextSpan:
1386        ;
1387    } while ((test = test->final() ? NULL : test->upCast()->next()));
1388    debugValidate();
1389}
1390
1391// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
1392void SkOpSegment::moveNearby() {
1393    debugValidate();
1394    SkOpSpanBase* spanS = &fHead;
1395    do {
1396        SkOpSpanBase* test = spanS->upCast()->next();
1397        SkOpSpanBase* next;
1398        if (spanS->contains(test)) {
1399            if (!test->final()) {
1400                test->upCast()->detach(spanS->ptT());
1401                continue;
1402            } else if (spanS != &fHead) {
1403                spanS->upCast()->detach(test->ptT());
1404                spanS = test;
1405                continue;
1406            }
1407        }
1408        do {  // iterate through all spans associated with start
1409            SkOpPtT* startBase = spanS->ptT();
1410            next = test->final() ? NULL : test->upCast()->next();
1411            do {
1412                SkOpPtT* testBase = test->ptT();
1413                do {
1414                    if (startBase == testBase) {
1415                        goto checkNextSpan;
1416                    }
1417                    if (testBase->duplicate()) {
1418                        continue;
1419                    }
1420                    if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
1421                        if (test == &this->fTail) {
1422                            if (spanS == &fHead) {
1423                                debugValidate();
1424                                return;  // if this span has collapsed, remove it from parent
1425                            }
1426                            this->fTail.merge(spanS->upCast());
1427                            debugValidate();
1428                            return;
1429                        }
1430                        spanS->merge(test->upCast());
1431                        spanS->upCast()->setNext(next);
1432                        goto checkNextSpan;
1433                    }
1434                } while ((testBase = testBase->next()) != test->ptT());
1435            } while ((startBase = startBase->next()) != spanS->ptT());
1436    checkNextSpan:
1437            ;
1438        } while ((test = next));
1439        spanS = spanS->upCast()->next();
1440    } while (!spanS->final());
1441    debugValidate();
1442}
1443
1444bool SkOpSegment::operand() const {
1445    return fContour->operand();
1446}
1447
1448bool SkOpSegment::oppXor() const {
1449    return fContour->oppXor();
1450}
1451
1452bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
1453    if (fVerb == SkPath::kLine_Verb) {
1454        return false;
1455    }
1456    // quads (and cubics) can loop back to nearly a line so that an opposite curve
1457    // hits in two places with very different t values.
1458    // OPTIMIZATION: curves could be preflighted so that, for example, something like
1459    // 'controls contained by ends' could avoid this check for common curves
1460    // 'ends are extremes in x or y' is cheaper to compute and real-world common
1461    // on the other hand, the below check is relatively inexpensive
1462    double midT = (t1 + t2) / 2;
1463    SkPoint midPt = this->ptAtT(midT);
1464    double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2);
1465    return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq;
1466}
1467
1468void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1469        int* maxWinding, int* sumWinding) {
1470    int deltaSum = SpanSign(start, end);
1471    *maxWinding = *sumMiWinding;
1472    *sumWinding = *sumMiWinding -= deltaSum;
1473    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1474}
1475
1476void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1477        int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
1478        int* oppSumWinding) {
1479    int deltaSum = SpanSign(start, end);
1480    int oppDeltaSum = OppSign(start, end);
1481    if (operand()) {
1482        *maxWinding = *sumSuWinding;
1483        *sumWinding = *sumSuWinding -= deltaSum;
1484        *oppMaxWinding = *sumMiWinding;
1485        *oppSumWinding = *sumMiWinding -= oppDeltaSum;
1486    } else {
1487        *maxWinding = *sumMiWinding;
1488        *sumWinding = *sumMiWinding -= deltaSum;
1489        *oppMaxWinding = *sumSuWinding;
1490        *oppSumWinding = *sumSuWinding -= oppDeltaSum;
1491    }
1492    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1493    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
1494}
1495
1496void SkOpSegment::sortAngles() {
1497    SkOpSpanBase* span = &this->fHead;
1498    do {
1499        SkOpAngle* fromAngle = span->fromAngle();
1500        SkOpAngle* toAngle = span->final() ? NULL : span->upCast()->toAngle();
1501        if (!fromAngle && !toAngle) {
1502            continue;
1503        }
1504#if DEBUG_ANGLE
1505        bool wroteAfterHeader = false;
1506#endif
1507        SkOpAngle* baseAngle = fromAngle;
1508        if (fromAngle && toAngle) {
1509#if DEBUG_ANGLE
1510            SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
1511                    span->debugID());
1512            wroteAfterHeader = true;
1513#endif
1514            fromAngle->insert(toAngle);
1515        } else if (!fromAngle) {
1516            baseAngle = toAngle;
1517        }
1518        SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1519        do {
1520            SkOpSpanBase* oSpan = ptT->span();
1521            if (oSpan == span) {
1522                continue;
1523            }
1524            SkOpAngle* oAngle = oSpan->fromAngle();
1525            if (oAngle) {
1526#if DEBUG_ANGLE
1527                if (!wroteAfterHeader) {
1528                    SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1529                            span->t(), span->debugID());
1530                    wroteAfterHeader = true;
1531                }
1532#endif
1533                if (!oAngle->loopContains(baseAngle)) {
1534                    baseAngle->insert(oAngle);
1535                }
1536            }
1537            if (!oSpan->final()) {
1538                oAngle = oSpan->upCast()->toAngle();
1539                if (oAngle) {
1540#if DEBUG_ANGLE
1541                    if (!wroteAfterHeader) {
1542                        SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1543                                span->t(), span->debugID());
1544                        wroteAfterHeader = true;
1545                    }
1546#endif
1547                    if (!oAngle->loopContains(baseAngle)) {
1548                        baseAngle->insert(oAngle);
1549                    }
1550                }
1551            }
1552        } while ((ptT = ptT->next()) != stopPtT);
1553        if (baseAngle->loopCount() == 1) {
1554            span->setFromAngle(NULL);
1555            if (toAngle) {
1556                span->upCast()->setToAngle(NULL);
1557            }
1558            baseAngle = NULL;
1559        }
1560#if DEBUG_SORT
1561        SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
1562#endif
1563    } while (!span->final() && (span = span->upCast()->next()));
1564}
1565
1566// return true if midpoints were computed
1567bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1568        SkOpCurve* edge) const {
1569    SkASSERT(start != end);
1570    const SkOpPtT& startPtT = *start->ptT();
1571    const SkOpPtT& endPtT = *end->ptT();
1572    SkDEBUGCODE(edge->fVerb = fVerb);
1573    edge->fPts[0] = startPtT.fPt;
1574    int points = SkPathOpsVerbToPoints(fVerb);
1575    edge->fPts[points] = endPtT.fPt;
1576    edge->fWeight = 1;
1577    if (fVerb == SkPath::kLine_Verb) {
1578        return false;
1579    }
1580    double startT = startPtT.fT;
1581    double endT = endPtT.fT;
1582    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1583        // don't compute midpoints if we already have them
1584        if (fVerb == SkPath::kQuad_Verb) {
1585            edge->fPts[1] = fPts[1];
1586            return false;
1587        }
1588        if (fVerb == SkPath::kConic_Verb) {
1589            edge->fPts[1] = fPts[1];
1590            edge->fWeight = fWeight;
1591            return false;
1592        }
1593        SkASSERT(fVerb == SkPath::kCubic_Verb);
1594        if (start < end) {
1595            edge->fPts[1] = fPts[1];
1596            edge->fPts[2] = fPts[2];
1597            return false;
1598        }
1599        edge->fPts[1] = fPts[2];
1600        edge->fPts[2] = fPts[1];
1601        return false;
1602    }
1603    const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY},
1604            {edge->fPts[points].fX, edge->fPts[points].fY }};
1605    if (fVerb == SkPath::kQuad_Verb) {
1606        edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
1607    } else if (fVerb == SkPath::kConic_Verb) {
1608        edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1],
1609                startT, endT, &edge->fWeight).asSkPoint();
1610    } else {
1611        SkASSERT(fVerb == SkPath::kCubic_Verb);
1612        SkDPoint ctrl[2];
1613        SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
1614        edge->fPts[1] = ctrl[0].asSkPoint();
1615        edge->fPts[2] = ctrl[1].asSkPoint();
1616    }
1617    return true;
1618}
1619
1620bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1621        SkDCurve* edge) const {
1622    SkASSERT(start != end);
1623    const SkOpPtT& startPtT = *start->ptT();
1624    const SkOpPtT& endPtT = *end->ptT();
1625    SkDEBUGCODE(edge->fVerb = fVerb);
1626    edge->fCubic[0].set(startPtT.fPt);
1627    int points = SkPathOpsVerbToPoints(fVerb);
1628    edge->fCubic[points].set(endPtT.fPt);
1629    if (fVerb == SkPath::kLine_Verb) {
1630        return false;
1631    }
1632    double startT = startPtT.fT;
1633    double endT = endPtT.fT;
1634    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1635        // don't compute midpoints if we already have them
1636        if (fVerb == SkPath::kQuad_Verb) {
1637            edge->fLine[1].set(fPts[1]);
1638            return false;
1639        }
1640        if (fVerb == SkPath::kConic_Verb) {
1641            edge->fConic[1].set(fPts[1]);
1642            edge->fConic.fWeight = fWeight;
1643            return false;
1644        }
1645        SkASSERT(fVerb == SkPath::kCubic_Verb);
1646        if (startT == 0) {
1647            edge->fCubic[1].set(fPts[1]);
1648            edge->fCubic[2].set(fPts[2]);
1649            return false;
1650        }
1651        edge->fCubic[1].set(fPts[2]);
1652        edge->fCubic[2].set(fPts[1]);
1653        return false;
1654    }
1655    if (fVerb == SkPath::kQuad_Verb) {
1656        edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
1657    } else if (fVerb == SkPath::kConic_Verb) {
1658        edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
1659            startT, endT, &edge->fConic.fWeight);
1660    } else {
1661        SkASSERT(fVerb == SkPath::kCubic_Verb);
1662        SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
1663    }
1664    return true;
1665}
1666
1667bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
1668        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp,
1669        SkScalar flatnessLimit) const {
1670    // average t, find mid pt
1671    double midT = (prior->t() + spanBase->t()) / 2;
1672    SkPoint midPt = this->ptAtT(midT);
1673    bool coincident = true;
1674    // if the mid pt is not near either end pt, project perpendicular through opp seg
1675    if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
1676            && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
1677        coincident = false;
1678        SkIntersections i;
1679        SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
1680        SkDLine ray = {{{midPt.fX, midPt.fY}, {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
1681        (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
1682        // measure distance and see if it's small enough to denote coincidence
1683        for (int index = 0; index < i.used(); ++index) {
1684            SkDPoint oppPt = i.pt(index);
1685            if (oppPt.approximatelyEqual(midPt)) {
1686                SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
1687                        opp->weight(), i[index][0]);
1688                oppDxdy.normalize();
1689                dxdy.normalize();
1690                SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
1691                coincident |= flatness < flatnessLimit;
1692            }
1693        }
1694    }
1695    return coincident;
1696}
1697
1698void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) {
1699    SkOpSpan* span = this->head();
1700    do {
1701        if (!span->done()) {
1702            break;
1703        }
1704    } while ((span = span->next()->upCastable()));
1705    SkASSERT(span);
1706    *start = span;
1707    *end = span->next();
1708}
1709
1710int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
1711    const SkOpSpan* lesser = start->starter(end);
1712    int oppWinding = lesser->oppSum();
1713    int oppSpanWinding = SkOpSegment::OppSign(start, end);
1714    if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
1715            && oppWinding != SK_MaxS32) {
1716        oppWinding -= oppSpanWinding;
1717    }
1718    return oppWinding;
1719}
1720
1721int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
1722    const SkOpSpanBase* startSpan = angle->start();
1723    const SkOpSpanBase* endSpan = angle->end();
1724    return updateOppWinding(endSpan, startSpan);
1725}
1726
1727int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
1728    const SkOpSpanBase* startSpan = angle->start();
1729    const SkOpSpanBase* endSpan = angle->end();
1730    return updateOppWinding(startSpan, endSpan);
1731}
1732
1733int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
1734    SkOpSpan* lesser = start->starter(end);
1735    int winding = lesser->windSum();
1736    if (winding == SK_MinS32) {
1737        winding = lesser->computeWindSum();
1738    }
1739    if (winding == SK_MinS32) {
1740        return winding;
1741    }
1742    int spanWinding = SkOpSegment::SpanSign(start, end);
1743    if (winding && UseInnerWinding(winding - spanWinding, winding)
1744            && winding != SK_MaxS32) {
1745        winding -= spanWinding;
1746    }
1747    return winding;
1748}
1749
1750int SkOpSegment::updateWinding(SkOpAngle* angle) {
1751    SkOpSpanBase* startSpan = angle->start();
1752    SkOpSpanBase* endSpan = angle->end();
1753    return updateWinding(endSpan, startSpan);
1754}
1755
1756int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) {
1757    SkOpSpanBase* startSpan = angle->start();
1758    SkOpSpanBase* endSpan = angle->end();
1759    return updateWinding(startSpan, endSpan);
1760}
1761
1762// OPTIMIZATION: does the following also work, and is it any faster?
1763// return outerWinding * innerWinding > 0
1764//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
1765bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
1766    SkASSERT(outerWinding != SK_MaxS32);
1767    SkASSERT(innerWinding != SK_MaxS32);
1768    int absOut = abs(outerWinding);
1769    int absIn = abs(innerWinding);
1770    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
1771    return result;
1772}
1773
1774int SkOpSegment::windSum(const SkOpAngle* angle) const {
1775    const SkOpSpan* minSpan = angle->start()->starter(angle->end());
1776    return minSpan->windSum();
1777}
1778