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