SkOpSegment.cpp revision bdbb2422b9f20372597367a032d822b4297eab41 
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 "SkIntersections.h"
8#include "SkOpContour.h"
9#include "SkOpSegment.h"
10#include "SkPathWriter.h"
11#include "SkTSort.h"
12
13#define F (false)      // discard the edge
14#define T (true)       // keep the edge
15
16static const bool gUnaryActiveEdge[2][2] = {
17//  from=0  from=1
18//  to=0,1  to=0,1
19    {F, T}, {T, F},
20};
21
22static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
23//                 miFrom=0                              miFrom=1
24//         miTo=0             miTo=1             miTo=0             miTo=1
25//     suFrom=0    1      suFrom=0    1      suFrom=0    1      suFrom=0    1
26//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
27    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}},  // mi - su
28    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}},  // mi & su
29    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}},  // mi | su
30    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}},  // mi ^ su
31};
32
33#undef F
34#undef T
35
36enum {
37    kOutsideTrackedTCount = 16,  // FIXME: determine what this should be
38    kMissingSpanCount = 4,  // FIXME: determine what this should be
39};
40
41const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done,
42        bool* sortable) const {
43    if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) {
44        return result;
45    }
46    double referenceT = fTs[index].fT;
47    int lesser = index;
48    while (--lesser >= 0
49            && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
50        if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) {
51            return result;
52        }
53    }
54    do {
55        if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) {
56            return result;
57        }
58        if (++index == fTs.count()) {
59            break;
60        }
61        if (fTs[index - 1].fTiny) {
62            referenceT = fTs[index].fT;
63            continue;
64        }
65    } while (precisely_negative(fTs[index].fT - referenceT));
66    return NULL;
67}
68
69const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done,
70        bool* sortable) const {
71    int next = nextExactSpan(index, 1);
72    if (next > 0) {
73        const SkOpSpan& upSpan = fTs[index];
74        if (upSpan.fWindValue || upSpan.fOppValue) {
75            if (*end < 0) {
76                *start = index;
77                *end = next;
78            }
79            if (!upSpan.fDone) {
80                if (upSpan.fWindSum != SK_MinS32) {
81                    return spanToAngle(index, next);
82                }
83                *done = false;
84            }
85        } else {
86            SkASSERT(upSpan.fDone);
87        }
88    }
89    int prev = nextExactSpan(index, -1);
90    // edge leading into junction
91    if (prev >= 0) {
92        const SkOpSpan& downSpan = fTs[prev];
93        if (downSpan.fWindValue || downSpan.fOppValue) {
94            if (*end < 0) {
95                *start = index;
96                *end = prev;
97            }
98            if (!downSpan.fDone) {
99                if (downSpan.fWindSum != SK_MinS32) {
100                    return spanToAngle(index, prev);
101                }
102                *done = false;
103            }
104        } else {
105            SkASSERT(downSpan.fDone);
106        }
107    }
108    return NULL;
109}
110
111const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done,
112        bool* sortable) const {
113    const SkOpSpan* span = &fTs[index];
114    SkOpSegment* other = span->fOther;
115    int oIndex = span->fOtherIndex;
116    return other->activeAngleInner(oIndex, start, end, done, sortable);
117}
118
119SkPoint SkOpSegment::activeLeftTop(int* firstT) const {
120    SkASSERT(!done());
121    SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
122    int count = fTs.count();
123    // see if either end is not done since we want smaller Y of the pair
124    bool lastDone = true;
125    double lastT = -1;
126    for (int index = 0; index < count; ++index) {
127        const SkOpSpan& span = fTs[index];
128        if (span.fDone && lastDone) {
129            goto next;
130        }
131        if (approximately_negative(span.fT - lastT)) {
132            goto next;
133        }
134        {
135            const SkPoint& xy = xyAtT(&span);
136            if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
137                topPt = xy;
138                if (firstT) {
139                    *firstT = index;
140                }
141            }
142            if (fVerb != SkPath::kLine_Verb && !lastDone) {
143                SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
144                if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
145                        && topPt.fX > curveTop.fX)) {
146                    topPt = curveTop;
147                    if (firstT) {
148                        *firstT = index;
149                    }
150                }
151            }
152            lastT = span.fT;
153        }
154next:
155        lastDone = span.fDone;
156    }
157    return topPt;
158}
159
160bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
161    int sumMiWinding = updateWinding(endIndex, index);
162    int sumSuWinding = updateOppWinding(endIndex, index);
163    if (fOperand) {
164        SkTSwap<int>(sumMiWinding, sumSuWinding);
165    }
166    return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding);
167}
168
169bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
170        int* sumMiWinding, int* sumSuWinding) {
171    int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
172    setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
173            &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
174    bool miFrom;
175    bool miTo;
176    bool suFrom;
177    bool suTo;
178    if (operand()) {
179        miFrom = (oppMaxWinding & xorMiMask) != 0;
180        miTo = (oppSumWinding & xorMiMask) != 0;
181        suFrom = (maxWinding & xorSuMask) != 0;
182        suTo = (sumWinding & xorSuMask) != 0;
183    } else {
184        miFrom = (maxWinding & xorMiMask) != 0;
185        miTo = (sumWinding & xorMiMask) != 0;
186        suFrom = (oppMaxWinding & xorSuMask) != 0;
187        suTo = (oppSumWinding & xorSuMask) != 0;
188    }
189    bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
190#if DEBUG_ACTIVE_OP
191    SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
192            __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT,
193            SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
194#endif
195    return result;
196}
197
198bool SkOpSegment::activeWinding(int index, int endIndex) {
199    int sumWinding = updateWinding(endIndex, index);
200    return activeWinding(index, endIndex, &sumWinding);
201}
202
203bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) {
204    int maxWinding;
205    setUpWinding(index, endIndex, &maxWinding, sumWinding);
206    bool from = maxWinding != 0;
207    bool to = *sumWinding  != 0;
208    bool result = gUnaryActiveEdge[from][to];
209    return result;
210}
211
212void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
213        SkOpSegment* other) {
214    int tIndex = -1;
215    int tCount = fTs.count();
216    int oIndex = -1;
217    int oCount = other->fTs.count();
218    do {
219        ++tIndex;
220    } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
221    int tIndexStart = tIndex;
222    do {
223        ++oIndex;
224    } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
225    int oIndexStart = oIndex;
226    const SkPoint* nextPt;
227    do {
228        nextPt = &fTs[++tIndex].fPt;
229        SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
230    } while (startPt == *nextPt);
231    double nextT = fTs[tIndex].fT;
232    const SkPoint* oNextPt;
233    do {
234        oNextPt = &other->fTs[++oIndex].fPt;
235        SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
236    } while (endPt == *oNextPt);
237    double oNextT = other->fTs[oIndex].fT;
238    // at this point, spans before and after are at:
239    //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
240    // if tIndexStart == 0, no prior span
241    // if nextT == 1, no following span
242
243    // advance the span with zero winding
244    // if the following span exists (not past the end, non-zero winding)
245    // connect the two edges
246    if (!fTs[tIndexStart].fWindValue) {
247        if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
248#if DEBUG_CONCIDENT
249            SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
250                    __FUNCTION__, fID, other->fID, tIndexStart - 1,
251                    fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
252                    xyAtT(tIndexStart).fY);
253#endif
254            SkPoint copy = fTs[tIndexStart].fPt;  // add t pair may move the point array
255            addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false, copy);
256        }
257        if (nextT < 1 && fTs[tIndex].fWindValue) {
258#if DEBUG_CONCIDENT
259            SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
260                    __FUNCTION__, fID, other->fID, tIndex,
261                    fTs[tIndex].fT, xyAtT(tIndex).fX,
262                    xyAtT(tIndex).fY);
263#endif
264            SkPoint copy = fTs[tIndex].fPt;  // add t pair may move the point array
265            addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, copy);
266        }
267    } else {
268        SkASSERT(!other->fTs[oIndexStart].fWindValue);
269        if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
270#if DEBUG_CONCIDENT
271            SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
272                    __FUNCTION__, fID, other->fID, oIndexStart - 1,
273                    other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
274                    other->xyAtT(oIndexStart).fY);
275            other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
276#endif
277        }
278        if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
279#if DEBUG_CONCIDENT
280            SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
281                    __FUNCTION__, fID, other->fID, oIndex,
282                    other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
283                    other->xyAtT(oIndex).fY);
284            other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
285#endif
286        }
287    }
288}
289
290void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
291        SkOpSegment* other) {
292    // walk this to startPt
293    // walk other to startPt
294    // if either is > 0, add a pointer to the other, copying adjacent winding
295    int tIndex = -1;
296    int oIndex = -1;
297    do {
298        ++tIndex;
299    } while (startPt != fTs[tIndex].fPt);
300    int ttIndex = tIndex;
301    bool checkOtherTMatch = false;
302    do {
303        const SkOpSpan& span = fTs[ttIndex];
304        if (startPt != span.fPt) {
305            break;
306        }
307        if (span.fOther == other && span.fPt == startPt) {
308            checkOtherTMatch = true;
309            break;
310        }
311    } while (++ttIndex < count());
312    do {
313        ++oIndex;
314    } while (startPt != other->fTs[oIndex].fPt);
315    bool skipAdd = false;
316    if (checkOtherTMatch) {
317        int ooIndex = oIndex;
318        do {
319            const SkOpSpan& oSpan = other->fTs[ooIndex];
320            if (startPt != oSpan.fPt) {
321                break;
322            }
323            if (oSpan.fT == fTs[ttIndex].fOtherT) {
324                skipAdd = true;
325                break;
326            }
327        } while (++ooIndex < other->count());
328    }
329    if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) {
330        addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
331    }
332    SkPoint nextPt = startPt;
333    do {
334        const SkPoint* workPt;
335        do {
336            workPt = &fTs[++tIndex].fPt;
337        } while (nextPt == *workPt);
338        const SkPoint* oWorkPt;
339        do {
340            oWorkPt = &other->fTs[++oIndex].fPt;
341        } while (nextPt == *oWorkPt);
342        nextPt = *workPt;
343        double tStart = fTs[tIndex].fT;
344        double oStart = other->fTs[oIndex].fT;
345        if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
346            break;
347        }
348        if (*workPt == *oWorkPt) {
349            addTPair(tStart, other, oStart, false, nextPt);
350        }
351    } while (endPt != nextPt);
352}
353
354void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
355    init(pts, SkPath::kCubic_Verb, operand, evenOdd);
356    fBounds.setCubicBounds(pts);
357}
358
359void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
360    SkPoint edge[4];
361    const SkPoint* ePtr;
362    int lastT = fTs.count() - 1;
363    if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
364        ePtr = fPts;
365    } else {
366    // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
367        subDivide(start, end, edge);
368        ePtr = edge;
369    }
370    if (active) {
371        bool reverse = ePtr == fPts && start != 0;
372        if (reverse) {
373            path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
374            switch (fVerb) {
375                case SkPath::kLine_Verb:
376                    path->deferredLine(ePtr[0]);
377                    break;
378                case SkPath::kQuad_Verb:
379                    path->quadTo(ePtr[1], ePtr[0]);
380                    break;
381                case SkPath::kCubic_Verb:
382                    path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
383                    break;
384                default:
385                    SkASSERT(0);
386            }
387   //         return ePtr[0];
388       } else {
389            path->deferredMoveLine(ePtr[0]);
390            switch (fVerb) {
391                case SkPath::kLine_Verb:
392                    path->deferredLine(ePtr[1]);
393                    break;
394                case SkPath::kQuad_Verb:
395                    path->quadTo(ePtr[1], ePtr[2]);
396                    break;
397                case SkPath::kCubic_Verb:
398                    path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
399                    break;
400                default:
401                    SkASSERT(0);
402            }
403        }
404    }
405  //  return ePtr[SkPathOpsVerbToPoints(fVerb)];
406}
407
408void SkOpSegment::addEndSpan(int endIndex) {
409    SkASSERT(span(endIndex).fT == 1 || (span(endIndex).fTiny
410            && approximately_greater_than_one(span(endIndex).fT)));
411    int spanCount = fTs.count();
412    int startIndex = endIndex - 1;
413    while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) {
414        --startIndex;
415        SkASSERT(startIndex > 0);
416        --endIndex;
417    }
418    SkOpAngle& angle = fAngles.push_back();
419    angle.set(this, spanCount - 1, startIndex);
420#if DEBUG_ANGLE
421    debugCheckPointsEqualish(endIndex, spanCount);
422#endif
423    setFromAngle(endIndex, &angle);
424}
425
426void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) {
427    int spanCount = fTs.count();
428    do {
429        fTs[endIndex].fFromAngle = angle;
430    } while (++endIndex < spanCount);
431}
432
433void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
434    init(pts, SkPath::kLine_Verb, operand, evenOdd);
435    fBounds.set(pts, 2);
436}
437
438// add 2 to edge or out of range values to get T extremes
439void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
440    SkOpSpan& span = fTs[index];
441    if (precisely_zero(otherT)) {
442        otherT = 0;
443    } else if (precisely_equal(otherT, 1)) {
444        otherT = 1;
445    }
446    span.fOtherT = otherT;
447    span.fOtherIndex = otherIndex;
448}
449
450void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
451    init(pts, SkPath::kQuad_Verb, operand, evenOdd);
452    fBounds.setQuadBounds(pts);
453}
454
455SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
456    int spanIndex = count() - 1;
457    int startIndex = nextExactSpan(spanIndex, -1);
458    SkASSERT(startIndex >= 0);
459    SkOpAngle& angle = fAngles.push_back();
460    *anglePtr = &angle;
461    angle.set(this, spanIndex, startIndex);
462    setFromAngle(spanIndex, &angle);
463    SkOpSegment* other;
464    int oStartIndex, oEndIndex;
465    do {
466        const SkOpSpan& span = fTs[spanIndex];
467        SkASSERT(span.fT > 0);
468        other = span.fOther;
469        oStartIndex = span.fOtherIndex;
470        oEndIndex = other->nextExactSpan(oStartIndex, 1);
471        if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) {
472            break;
473        }
474        oEndIndex = oStartIndex;
475        oStartIndex = other->nextExactSpan(oEndIndex, -1);
476        --spanIndex;
477    } while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum);
478    SkOpAngle& oAngle = other->fAngles.push_back();
479    oAngle.set(other, oStartIndex, oEndIndex);
480    other->setToAngle(oEndIndex, &oAngle);
481    *otherPtr = other;
482    return &oAngle;
483}
484
485SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
486    int endIndex = nextExactSpan(0, 1);
487    SkASSERT(endIndex > 0);
488    SkOpAngle& angle = fAngles.push_back();
489    *anglePtr = &angle;
490    angle.set(this, 0, endIndex);
491    setToAngle(endIndex, &angle);
492    int spanIndex = 0;
493    SkOpSegment* other;
494    int oStartIndex, oEndIndex;
495    do {
496        const SkOpSpan& span = fTs[spanIndex];
497        SkASSERT(span.fT < 1);
498        other = span.fOther;
499        oEndIndex = span.fOtherIndex;
500        oStartIndex = other->nextExactSpan(oEndIndex, -1);
501        if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) {
502            break;
503        }
504        oStartIndex = oEndIndex;
505        oEndIndex = other->nextExactSpan(oStartIndex, 1);
506        ++spanIndex;
507    } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue);
508    SkOpAngle& oAngle = other->fAngles.push_back();
509    oAngle.set(other, oEndIndex, oStartIndex);
510    other->setFromAngle(oEndIndex, &oAngle);
511    *otherPtr = other;
512    return &oAngle;
513}
514
515SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
516    SkOpSegment* other;
517    SkOpAngle* angle, * otherAngle;
518    if (step > 0) {
519        otherAngle = addSingletonAngleUp(&other, &angle);
520    } else {
521        otherAngle = addSingletonAngleDown(&other, &angle);
522    }
523    angle->insert(otherAngle);
524    return angle;
525}
526
527void SkOpSegment::addStartSpan(int endIndex) {
528    int index = 0;
529    SkOpAngle& angle = fAngles.push_back();
530    angle.set(this, index, endIndex);
531#if DEBUG_ANGLE
532    debugCheckPointsEqualish(index, endIndex);
533#endif
534    setToAngle(endIndex, &angle);
535}
536
537void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) {
538    int index = 0;
539    do {
540        fTs[index].fToAngle = angle;
541    } while (++index < endIndex);
542}
543
544    // Defer all coincident edge processing until
545    // after normal intersections have been computed
546
547// no need to be tricky; insert in normal T order
548// resolve overlapping ts when considering coincidence later
549
550    // add non-coincident intersection. Resulting edges are sorted in T.
551int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
552    SkASSERT(this != other || fVerb == SkPath::kCubic_Verb);
553 #if 0  // this needs an even rougher association to be useful
554    SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt));
555 #endif
556    const SkPoint& firstPt = fPts[0];
557    const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
558    SkASSERT(newT == 0 || !precisely_zero(newT));
559    SkASSERT(newT == 1 || !precisely_equal(newT, 1));
560    // FIXME: in the pathological case where there is a ton of intercepts,
561    //  binary search?
562    int insertedAt = -1;
563    int tCount = fTs.count();
564    for (int index = 0; index < tCount; ++index) {
565        // OPTIMIZATION: if there are three or more identical Ts, then
566        // the fourth and following could be further insertion-sorted so
567        // that all the edges are clockwise or counterclockwise.
568        // This could later limit segment tests to the two adjacent
569        // neighbors, although it doesn't help with determining which
570        // circular direction to go in.
571        const SkOpSpan& span = fTs[index];
572        if (newT < span.fT) {
573            insertedAt = index;
574            break;
575        }
576        if (newT == span.fT) {
577            if (pt == span.fPt) {
578                insertedAt = index;
579                break;
580            }
581            if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
582                insertedAt = index;
583                break;
584            }
585        }
586    }
587    SkOpSpan* span;
588    if (insertedAt >= 0) {
589        span = fTs.insert(insertedAt);
590    } else {
591        insertedAt = tCount;
592        span = fTs.append();
593    }
594    span->fT = newT;
595    span->fOtherT = -1;
596    span->fOther = other;
597    span->fPt = pt;
598#if 0
599    // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
600    SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
601            && approximately_equal(xyAtT(newT).fY, pt.fY));
602#endif
603    span->fFromAngle = NULL;
604    span->fToAngle = NULL;
605    span->fWindSum = SK_MinS32;
606    span->fOppSum = SK_MinS32;
607    span->fWindValue = 1;
608    span->fOppValue = 0;
609    span->fChased = false;
610    span->fCoincident = false;
611    span->fLoop = false;
612    span->fNear = false;
613    span->fMultiple = false;
614    span->fSmall = false;
615    span->fTiny = false;
616    if ((span->fDone = newT == 1)) {
617        ++fDoneSpans;
618    }
619    int less = -1;
620// FIXME: note that this relies on spans being a continguous array
621// find range of spans with nearly the same point as this one
622    while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
623        if (fVerb == SkPath::kCubic_Verb) {
624            double tInterval = newT - span[less].fT;
625            double tMid = newT - tInterval / 2;
626            SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
627            if (!midPt.approximatelyEqual(xyAtT(span))) {
628                break;
629            }
630        }
631        --less;
632    }
633    int more = 1;
634    while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) {
635        if (fVerb == SkPath::kCubic_Verb) {
636            double tEndInterval = span[more].fT - newT;
637            double tMid = newT - tEndInterval / 2;
638            SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
639            if (!midEndPt.approximatelyEqual(xyAtT(span))) {
640                break;
641            }
642        }
643        ++more;
644    }
645    ++less;
646    --more;
647    while (more - 1 > less && span[more].fPt == span[more - 1].fPt
648            && span[more].fT == span[more - 1].fT) {
649        --more;
650    }
651    if (less == more) {
652        return insertedAt;
653    }
654    if (precisely_negative(span[more].fT - span[less].fT)) {
655        return insertedAt;
656    }
657// if the total range of t values is big enough, mark all tiny
658    bool tiny = span[less].fPt == span[more].fPt;
659    int index = less;
660    do {
661        fSmall = span[index].fSmall = true;
662        fTiny |= span[index].fTiny = tiny;
663        if (!span[index].fDone) {
664            span[index].fDone = true;
665            ++fDoneSpans;
666        }
667    } while (++index < more);
668    return insertedAt;
669}
670
671// set spans from start to end to decrement by one
672// note this walks other backwards
673// FIXME: there's probably an edge case that can be constructed where
674// two span in one segment are separated by float epsilon on one span but
675// not the other, if one segment is very small. For this
676// case the counts asserted below may or may not be enough to separate the
677// spans. Even if the counts work out, what if the spans aren't correctly
678// sorted? It feels better in such a case to match the span's other span
679// pointer since both coincident segments must contain the same spans.
680// FIXME? It seems that decrementing by one will fail for complex paths that
681// have three or more coincident edges. Shouldn't this subtract the difference
682// between the winding values?
683/*                                      |-->                           |-->
684this     0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4
685other         2<<<<1<<<<0               2<<<<1<<<<0               2<<<<1<<<<0
686              ^         ^                 <--|                           <--|
687           startPt    endPt        test/oTest first pos      test/oTest final pos
688*/
689void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
690    bool binary = fOperand != other->fOperand;
691    int index = 0;
692    while (startPt != fTs[index].fPt) {
693        SkASSERT(index < fTs.count());
694        ++index;
695    }
696    while (index > 0 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) {
697        --index;
698    }
699    bool oFoundEnd = false;
700    int oIndex = other->fTs.count();
701    while (startPt != other->fTs[--oIndex].fPt) {  // look for startPt match
702        SkASSERT(oIndex > 0);
703    }
704    double oStartT = other->fTs[oIndex].fT;
705    // look for first point beyond match
706    while (startPt == other->fTs[--oIndex].fPt || precisely_equal(oStartT, other->fTs[oIndex].fT)) {
707        SkASSERT(oIndex > 0);
708    }
709    SkOpSpan* test = &fTs[index];
710    SkOpSpan* oTest = &other->fTs[oIndex];
711    SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
712    SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
713    bool decrement, track, bigger;
714    int originalWindValue;
715    const SkPoint* testPt;
716    const SkPoint* oTestPt;
717    do {
718        SkASSERT(test->fT < 1);
719        SkASSERT(oTest->fT < 1);
720        decrement = test->fWindValue && oTest->fWindValue;
721        track = test->fWindValue || oTest->fWindValue;
722        bigger = test->fWindValue >= oTest->fWindValue;
723        testPt = &test->fPt;
724        double testT = test->fT;
725        oTestPt = &oTest->fPt;
726        double oTestT = oTest->fT;
727        do {
728            if (decrement) {
729                if (binary && bigger) {
730                    test->fOppValue--;
731                } else {
732                    decrementSpan(test);
733                }
734            } else if (track) {
735                TrackOutsidePair(&outsidePts, *testPt, *oTestPt);
736            }
737            SkASSERT(index < fTs.count() - 1);
738            test = &fTs[++index];
739        } while (*testPt == test->fPt || precisely_equal(testT, test->fT));
740        originalWindValue = oTest->fWindValue;
741        do {
742            SkASSERT(oTest->fT < 1);
743            SkASSERT(originalWindValue == oTest->fWindValue);
744            if (decrement) {
745                if (binary && !bigger) {
746                    oTest->fOppValue--;
747                } else {
748                    other->decrementSpan(oTest);
749                }
750            } else if (track) {
751                TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
752            }
753            if (!oIndex) {
754                break;
755            }
756            oFoundEnd |= endPt == oTest->fPt;
757            oTest = &other->fTs[--oIndex];
758        } while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT));
759    } while (endPt != test->fPt && test->fT < 1);
760    // FIXME: determine if canceled edges need outside ts added
761    if (!oFoundEnd) {
762        for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) {
763            SkOpSpan* oTst2 = &other->fTs[oIdx2];
764            if (originalWindValue != oTst2->fWindValue) {
765                goto skipAdvanceOtherCancel;
766            }
767            if (!oTst2->fWindValue) {
768                goto skipAdvanceOtherCancel;
769            }
770            if (endPt == other->fTs[oIdx2].fPt) {
771                break;
772            }
773        }
774        do {
775            SkASSERT(originalWindValue == oTest->fWindValue);
776            if (decrement) {
777                if (binary && !bigger) {
778                    oTest->fOppValue--;
779                } else {
780                    other->decrementSpan(oTest);
781                }
782            } else if (track) {
783                TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
784            }
785            if (!oIndex) {
786                break;
787            }
788            oTest = &other->fTs[--oIndex];
789            oFoundEnd |= endPt == oTest->fPt;
790        } while (!oFoundEnd || endPt == oTest->fPt);
791    }
792skipAdvanceOtherCancel:
793    int outCount = outsidePts.count();
794    if (!done() && outCount) {
795        addCancelOutsides(outsidePts[0], outsidePts[1], other);
796        if (outCount > 2) {
797            addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
798        }
799    }
800    if (!other->done() && oOutsidePts.count()) {
801        other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
802    }
803    setCoincidentRange(startPt, endPt, other);
804    other->setCoincidentRange(startPt, endPt, this);
805}
806
807int SkOpSegment::addSelfT(const SkPoint& pt, double newT) {
808    // if the tail nearly intersects itself but not quite, the caller records this separately
809    int result = addT(this, pt, newT);
810    SkOpSpan* span = &fTs[result];
811    fLoop = span->fLoop = true;
812    return result;
813}
814
815// find the starting or ending span with an existing loop of angles
816// FIXME? replicate for all identical starting/ending spans?
817// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
818// FIXME? assert that only one other span has a valid windValue or oppValue
819void SkOpSegment::addSimpleAngle(int index) {
820    SkOpSpan* span = &fTs[index];
821    int idx;
822    int start, end;
823    if (span->fT == 0) {
824        idx = 0;
825        span = &fTs[0];
826        do {
827            if (span->fToAngle) {
828                SkASSERT(span->fToAngle->loopCount() == 2);
829                SkASSERT(!span->fFromAngle);
830                span->fFromAngle = span->fToAngle->next();
831                return;
832            }
833            span = &fTs[++idx];
834        } while (span->fT == 0);
835        SkASSERT(!fTs[0].fTiny && fTs[idx].fT > 0);
836        addStartSpan(idx);
837        start = 0;
838        end = idx;
839    } else {
840        idx = count() - 1;
841        span = &fTs[idx];
842        do {
843            if (span->fFromAngle) {
844                SkASSERT(span->fFromAngle->loopCount() == 2);
845                SkASSERT(!span->fToAngle);
846                span->fToAngle = span->fFromAngle->next();
847                return;
848            }
849            span = &fTs[--idx];
850        } while (span->fT == 1);
851        SkASSERT(!fTs[idx].fTiny && fTs[idx].fT < 1);
852        addEndSpan(++idx);
853        start = idx;
854        end = count();
855    }
856    SkOpSegment* other;
857    SkOpSpan* oSpan;
858    index = start;
859    do {
860        span = &fTs[index];
861        other = span->fOther;
862        int oFrom = span->fOtherIndex;
863        oSpan = &other->fTs[oFrom];
864        if (oSpan->fT < 1 && oSpan->fWindValue) {
865            break;
866        }
867        if (oSpan->fT == 0) {
868            continue;
869        }
870        oFrom = other->nextExactSpan(oFrom, -1);
871        SkOpSpan* oFromSpan = &other->fTs[oFrom];
872        SkASSERT(oFromSpan->fT < 1);
873        if (oFromSpan->fWindValue) {
874            break;
875        }
876    } while (++index < end);
877    SkOpAngle* angle, * oAngle;
878    if (span->fT == 0) {
879        SkASSERT(span->fOtherIndex - 1 >= 0);
880        SkASSERT(span->fOtherT == 1);
881        SkDEBUGCODE(int oPriorIndex = other->nextExactSpan(span->fOtherIndex, -1));
882        SkDEBUGCODE(const SkOpSpan& oPrior = other->span(oPriorIndex));
883        SkASSERT(!oPrior.fTiny && oPrior.fT < 1);
884        other->addEndSpan(span->fOtherIndex);
885        angle = span->fToAngle;
886        oAngle = oSpan->fFromAngle;
887    } else {
888        SkASSERT(span->fOtherIndex + 1 < other->count());
889        SkASSERT(span->fOtherT == 0);
890        SkASSERT(!oSpan->fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0
891                || (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL
892                && other->fTs[span->fOtherIndex + 1].fToAngle == NULL)));
893        int oIndex = 1;
894        do {
895            const SkOpSpan& osSpan = other->span(oIndex);
896            if (osSpan.fFromAngle || osSpan.fT > 0) {
897                break;
898            }
899            ++oIndex;
900            SkASSERT(oIndex < other->count());
901        } while (true);
902        other->addStartSpan(oIndex);
903        angle = span->fFromAngle;
904        oAngle = oSpan->fToAngle;
905    }
906    angle->insert(oAngle);
907}
908
909void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
910    debugValidate();
911    int count = this->count();
912    for (int index = 0; index < count; ++index) {
913        SkOpSpan& span = fTs[index];
914        if (!span.fMultiple) {
915            continue;
916        }
917        int end = nextExactSpan(index, 1);
918        SkASSERT(end > index + 1);
919        const SkPoint& thisPt = span.fPt;
920        while (index < end - 1) {
921            SkOpSegment* other1 = span.fOther;
922            int oCnt = other1->count();
923            for (int idx2 = index + 1; idx2 < end; ++idx2) {
924                SkOpSpan& span2 = fTs[idx2];
925                SkOpSegment* other2 = span2.fOther;
926                for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
927                    SkOpSpan& oSpan = other1->fTs[oIdx];
928                    if (oSpan.fOther != other2) {
929                        continue;
930                    }
931                    if (oSpan.fPt == thisPt) {
932                        goto skipExactMatches;
933                    }
934                }
935                for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
936                    SkOpSpan& oSpan = other1->fTs[oIdx];
937                    if (oSpan.fOther != other2) {
938                        continue;
939                    }
940                    if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) {
941                        SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex];
942                        if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT)
943                                || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) {
944                            return;
945                        }
946                        if (!way_roughly_equal(span.fOtherT, oSpan.fT)
947                                || !way_roughly_equal(span2.fOtherT, oSpan2.fT)
948                                || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT)
949                                || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) {
950                            return;
951                        }
952                        alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT,
953                                other2, &oSpan, alignedArray);
954                        alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT,
955                                other1, &oSpan2, alignedArray);
956                        break;
957                    }
958                }
959        skipExactMatches:
960                ;
961            }
962            ++index;
963        }
964    }
965    debugValidate();
966}
967
968void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other,
969        double otherT, const SkOpSegment* other2, SkOpSpan* oSpan,
970        SkTDArray<AlignedSpan>* alignedArray) {
971    AlignedSpan* aligned = alignedArray->append();
972    aligned->fOldPt = oSpan->fPt;
973    aligned->fPt = newPt;
974    aligned->fOldT = oSpan->fT;
975    aligned->fT = newT;
976    aligned->fSegment = this;  // OPTIMIZE: may be unused, can remove
977    aligned->fOther1 = other;
978    aligned->fOther2 = other2;
979    SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt));
980    oSpan->fPt = newPt;
981//    SkASSERT(way_roughly_equal(oSpan->fT, newT));
982    oSpan->fT = newT;
983//    SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT));
984    oSpan->fOtherT = otherT;
985}
986
987bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) {
988    bool aligned = false;
989    SkOpSpan* span = &fTs[index];
990    SkOpSegment* other = span->fOther;
991    int oIndex = span->fOtherIndex;
992    SkOpSpan* oSpan = &other->fTs[oIndex];
993    if (span->fT != thisT) {
994        span->fT = thisT;
995        oSpan->fOtherT = thisT;
996        aligned = true;
997    }
998    if (span->fPt != thisPt) {
999        span->fPt = thisPt;
1000        oSpan->fPt = thisPt;
1001        aligned = true;
1002    }
1003    double oT = oSpan->fT;
1004    if (oT == 0) {
1005        return aligned;
1006    }
1007    int oStart = other->nextSpan(oIndex, -1) + 1;
1008    oSpan = &other->fTs[oStart];
1009    int otherIndex = oStart;
1010    if (oT == 1) {
1011        if (aligned) {
1012            while (oSpan->fPt == thisPt && oSpan->fT != 1) {
1013                oSpan->fTiny = true;
1014                ++oSpan;
1015            }
1016        }
1017        return aligned;
1018    }
1019    oT = oSpan->fT;
1020    int oEnd = other->nextSpan(oIndex, 1);
1021    bool oAligned = false;
1022    if (oSpan->fPt != thisPt) {
1023        oAligned |= other->alignSpan(oStart, oT, thisPt);
1024    }
1025    while (++otherIndex < oEnd) {
1026        SkOpSpan* oNextSpan = &other->fTs[otherIndex];
1027        if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) {
1028            oAligned |= other->alignSpan(otherIndex, oT, thisPt);
1029        }
1030    }
1031    if (oAligned) {
1032        other->alignSpanState(oStart, oEnd);
1033    }
1034    return aligned;
1035}
1036
1037void SkOpSegment::alignSpanState(int start, int end) {
1038    SkOpSpan* lastSpan = &fTs[--end];
1039    bool allSmall = lastSpan->fSmall;
1040    bool allTiny = lastSpan->fTiny;
1041    bool allDone = lastSpan->fDone;
1042    SkDEBUGCODE(int winding = lastSpan->fWindValue);
1043    SkDEBUGCODE(int oppWinding = lastSpan->fOppValue);
1044    int index = start;
1045    while (index < end) {
1046        SkOpSpan* span = &fTs[index];
1047        span->fSmall = allSmall;
1048        span->fTiny = allTiny;
1049        if (span->fDone != allDone) {
1050            span->fDone = allDone;
1051            fDoneSpans += allDone ? 1 : -1;
1052        }
1053        SkASSERT(span->fWindValue == winding);
1054        SkASSERT(span->fOppValue == oppWinding);
1055        ++index;
1056    }
1057}
1058
1059void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) {
1060    bool binary = fOperand != other->fOperand;
1061    int index = 0;
1062    int last = this->count();
1063    do {
1064        SkOpSpan& span = this->fTs[--last];
1065        if (span.fT != 1 && !span.fSmall) {
1066            break;
1067        }
1068        span.fCoincident = true;
1069    } while (true);
1070    int oIndex = other->count();
1071    do {
1072        SkOpSpan& oSpan = other->fTs[--oIndex];
1073        if (oSpan.fT != 1 && !oSpan.fSmall) {
1074            break;
1075        }
1076        oSpan.fCoincident = true;
1077    } while (true);
1078    do {
1079        SkOpSpan* test = &this->fTs[index];
1080        int baseWind = test->fWindValue;
1081        int baseOpp = test->fOppValue;
1082        int endIndex = index;
1083        while (++endIndex <= last) {
1084            SkOpSpan* endSpan = &this->fTs[endIndex];
1085            SkASSERT(endSpan->fT < 1);
1086            if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1087                break;
1088            }
1089            endSpan->fCoincident = true;
1090        }
1091        SkOpSpan* oTest = &other->fTs[oIndex];
1092        int oBaseWind = oTest->fWindValue;
1093        int oBaseOpp = oTest->fOppValue;
1094        int oStartIndex = oIndex;
1095        while (--oStartIndex >= 0) {
1096            SkOpSpan* oStartSpan = &other->fTs[oStartIndex];
1097            if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) {
1098                break;
1099            }
1100            oStartSpan->fCoincident = true;
1101        }
1102        bool decrement = baseWind && oBaseWind;
1103        bool bigger = baseWind >= oBaseWind;
1104        do {
1105            SkASSERT(test->fT < 1);
1106            if (decrement) {
1107                if (binary && bigger) {
1108                    test->fOppValue--;
1109                } else {
1110                    decrementSpan(test);
1111                }
1112            }
1113            test->fCoincident = true;
1114            test = &fTs[++index];
1115        } while (index < endIndex);
1116        do {
1117            SkASSERT(oTest->fT < 1);
1118            if (decrement) {
1119                if (binary && !bigger) {
1120                    oTest->fOppValue--;
1121                } else {
1122                    other->decrementSpan(oTest);
1123                }
1124            }
1125            oTest->fCoincident = true;
1126            oTest = &other->fTs[--oIndex];
1127        } while (oIndex > oStartIndex);
1128    } while (index <= last && oIndex >= 0);
1129    SkASSERT(index > last);
1130    SkASSERT(oIndex < 0);
1131}
1132
1133void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) {
1134    bool binary = fOperand != other->fOperand;
1135    int index = 0;
1136    int last = this->count();
1137    do {
1138        SkOpSpan& span = this->fTs[--last];
1139        if (span.fT != 1 && !span.fSmall) {
1140            break;
1141        }
1142        span.fCoincident = true;
1143    } while (true);
1144    int oIndex = 0;
1145    int oLast = other->count();
1146    do {
1147        SkOpSpan& oSpan = other->fTs[--oLast];
1148        if (oSpan.fT != 1 && !oSpan.fSmall) {
1149            break;
1150        }
1151        oSpan.fCoincident = true;
1152    } while (true);
1153    do {
1154        SkOpSpan* test = &this->fTs[index];
1155        int baseWind = test->fWindValue;
1156        int baseOpp = test->fOppValue;
1157        int endIndex = index;
1158        SkOpSpan* endSpan;
1159        while (++endIndex <= last) {
1160            endSpan = &this->fTs[endIndex];
1161            SkASSERT(endSpan->fT < 1);
1162            if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1163                break;
1164            }
1165            endSpan->fCoincident = true;
1166        }
1167        SkOpSpan* oTest = &other->fTs[oIndex];
1168        int oBaseWind = oTest->fWindValue;
1169        int oBaseOpp = oTest->fOppValue;
1170        int oEndIndex = oIndex;
1171        SkOpSpan* oEndSpan;
1172        while (++oEndIndex <= oLast) {
1173            oEndSpan = &this->fTs[oEndIndex];
1174            SkASSERT(oEndSpan->fT < 1);
1175            if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) {
1176                break;
1177            }
1178            oEndSpan->fCoincident = true;
1179        }
1180        // consolidate the winding count even if done
1181        if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) {
1182            if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1183                bumpCoincidentBlind(binary, index, endIndex);
1184                other->bumpCoincidentOBlind(oIndex, oEndIndex);
1185            } else {
1186                other->bumpCoincidentBlind(binary, oIndex, oEndIndex);
1187                bumpCoincidentOBlind(index, endIndex);
1188            }
1189        }
1190        index = endIndex;
1191        oIndex = oEndIndex;
1192    } while (index <= last && oIndex <= oLast);
1193    SkASSERT(index > last);
1194    SkASSERT(oIndex > oLast);
1195}
1196
1197void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) {
1198    const SkOpSpan& oTest = fTs[index];
1199    int oWindValue = oTest.fWindValue;
1200    int oOppValue = oTest.fOppValue;
1201    if (binary) {
1202        SkTSwap<int>(oWindValue, oOppValue);
1203    }
1204    do {
1205        (void) bumpSpan(&fTs[index], oWindValue, oOppValue);
1206    } while (++index < endIndex);
1207}
1208
1209void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
1210        SkTArray<SkPoint, true>* outsideTs) {
1211    int index = *indexPtr;
1212    int oWindValue = oTest.fWindValue;
1213    int oOppValue = oTest.fOppValue;
1214    if (binary) {
1215        SkTSwap<int>(oWindValue, oOppValue);
1216    }
1217    SkOpSpan* const test = &fTs[index];
1218    SkOpSpan* end = test;
1219    const SkPoint& oStartPt = oTest.fPt;
1220    do {
1221        if (bumpSpan(end, oWindValue, oOppValue)) {
1222            TrackOutside(outsideTs, oStartPt);
1223        }
1224        end = &fTs[++index];
1225    } while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1);
1226    *indexPtr = index;
1227}
1228
1229void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) {
1230    do {
1231        zeroSpan(&fTs[index]);
1232    } while (++index < endIndex);
1233}
1234
1235// because of the order in which coincidences are resolved, this and other
1236// may not have the same intermediate points. Compute the corresponding
1237// intermediate T values (using this as the master, other as the follower)
1238// and walk other conditionally -- hoping that it catches up in the end
1239void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
1240        SkTArray<SkPoint, true>* oOutsidePts) {
1241    int oIndex = *oIndexPtr;
1242    SkOpSpan* const oTest = &fTs[oIndex];
1243    SkOpSpan* oEnd = oTest;
1244    const SkPoint& oStartPt = oTest->fPt;
1245    double oStartT = oTest->fT;
1246#if 0  // FIXME : figure out what disabling this breaks
1247    const SkPoint& startPt = test.fPt;
1248    // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition
1249    if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1250        TrackOutside(oOutsidePts, startPt);
1251    }
1252#endif
1253    while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1254        zeroSpan(oEnd);
1255        oEnd = &fTs[++oIndex];
1256    }
1257    *oIndexPtr = oIndex;
1258}
1259
1260// FIXME: need to test this case:
1261// contourA has two segments that are coincident
1262// contourB has two segments that are coincident in the same place
1263// each ends up with +2/0 pairs for winding count
1264// since logic below doesn't transfer count (only increments/decrements) can this be
1265// resolved to +4/0 ?
1266
1267// set spans from start to end to increment the greater by one and decrement
1268// the lesser
1269void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
1270        SkOpSegment* other) {
1271    bool binary = fOperand != other->fOperand;
1272    int index = 0;
1273    while (startPt != fTs[index].fPt) {
1274        SkASSERT(index < fTs.count());
1275        ++index;
1276    }
1277    double startT = fTs[index].fT;
1278    while (index > 0 && precisely_equal(fTs[index - 1].fT, startT)) {
1279        --index;
1280    }
1281    int oIndex = 0;
1282    while (startPt != other->fTs[oIndex].fPt) {
1283        SkASSERT(oIndex < other->fTs.count());
1284        ++oIndex;
1285    }
1286    double oStartT = other->fTs[oIndex].fT;
1287    while (oIndex > 0 && precisely_equal(other->fTs[oIndex - 1].fT, oStartT)) {
1288        --oIndex;
1289    }
1290    SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
1291    SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
1292    SkOpSpan* test = &fTs[index];
1293    const SkPoint* testPt = &test->fPt;
1294    double testT = test->fT;
1295    SkOpSpan* oTest = &other->fTs[oIndex];
1296    const SkPoint* oTestPt = &oTest->fPt;
1297    SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1298    do {
1299        SkASSERT(test->fT < 1);
1300        SkASSERT(oTest->fT < 1);
1301
1302        // consolidate the winding count even if done
1303        if ((test->fWindValue == 0 && test->fOppValue == 0)
1304                || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
1305            SkDEBUGCODE(int firstWind = test->fWindValue);
1306            SkDEBUGCODE(int firstOpp = test->fOppValue);
1307            do {
1308                SkASSERT(firstWind == fTs[index].fWindValue);
1309                SkASSERT(firstOpp == fTs[index].fOppValue);
1310                ++index;
1311                SkASSERT(index < fTs.count());
1312            } while (*testPt == fTs[index].fPt);
1313            SkDEBUGCODE(firstWind = oTest->fWindValue);
1314            SkDEBUGCODE(firstOpp = oTest->fOppValue);
1315            do {
1316                SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
1317                SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
1318                ++oIndex;
1319                SkASSERT(oIndex < other->fTs.count());
1320            } while (*oTestPt == other->fTs[oIndex].fPt);
1321        } else {
1322            if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1323                bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
1324                other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1325            } else {
1326                other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1327                bumpCoincidentOther(*oTest, &index, &outsidePts);
1328            }
1329        }
1330        test = &fTs[index];
1331        testPt = &test->fPt;
1332        testT = test->fT;
1333        oTest = &other->fTs[oIndex];
1334        oTestPt = &oTest->fPt;
1335        if (endPt == *testPt || precisely_equal(endT, testT)) {
1336            break;
1337        }
1338//        SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1339    } while (endPt != *oTestPt);
1340    // in rare cases, one may have ended before the other
1341    if (endPt != *testPt && !precisely_equal(endT, testT)) {
1342        int lastWind = test[-1].fWindValue;
1343        int lastOpp = test[-1].fOppValue;
1344        bool zero = lastWind == 0 && lastOpp == 0;
1345        do {
1346            if (test->fWindValue || test->fOppValue) {
1347                test->fWindValue = lastWind;
1348                test->fOppValue = lastOpp;
1349                if (zero) {
1350                    test->fDone = true;
1351                    ++fDoneSpans;
1352                }
1353            }
1354            test = &fTs[++index];
1355            testPt = &test->fPt;
1356        } while (endPt != *testPt);
1357    }
1358    if (endPt != *oTestPt) {
1359        // look ahead to see if zeroing more spans will allows us to catch up
1360        int oPeekIndex = oIndex;
1361        bool success = true;
1362        SkOpSpan* oPeek;
1363        int oCount = other->count();
1364        do {
1365            oPeek = &other->fTs[oPeekIndex];
1366            if (++oPeekIndex == oCount) {
1367                success = false;
1368                break;
1369            }
1370        } while (endPt != oPeek->fPt);
1371        if (success) {
1372            // make sure the matching point completes the coincidence span
1373            success = false;
1374            do {
1375                if (oPeek->fOther == this) {
1376                    success = true;
1377                    break;
1378                }
1379                if (++oPeekIndex == oCount) {
1380                    break;
1381                }
1382                oPeek = &other->fTs[oPeekIndex];
1383            } while (endPt == oPeek->fPt);
1384        }
1385        if (success) {
1386            do {
1387                if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1388                    other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1389                } else {
1390                    other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1391                }
1392                oTest = &other->fTs[oIndex];
1393                oTestPt = &oTest->fPt;
1394            } while (endPt != *oTestPt);
1395        }
1396    }
1397    int outCount = outsidePts.count();
1398    if (!done() && outCount) {
1399        addCoinOutsides(outsidePts[0], endPt, other);
1400    }
1401    if (!other->done() && oOutsidePts.count()) {
1402        other->addCoinOutsides(oOutsidePts[0], endPt, this);
1403    }
1404    setCoincidentRange(startPt, endPt, other);
1405    other->setCoincidentRange(startPt, endPt, this);
1406}
1407
1408// FIXME: this doesn't prevent the same span from being added twice
1409// fix in caller, SkASSERT here?
1410const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1411        const SkPoint& pt, const SkPoint& pt2) {
1412    int tCount = fTs.count();
1413    for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1414        const SkOpSpan& span = fTs[tIndex];
1415        if (!approximately_negative(span.fT - t)) {
1416            break;
1417        }
1418        if (approximately_negative(span.fT - t) && span.fOther == other
1419                && approximately_equal(span.fOtherT, otherT)) {
1420#if DEBUG_ADD_T_PAIR
1421            SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1422                    __FUNCTION__, fID, t, other->fID, otherT);
1423#endif
1424            return NULL;
1425        }
1426    }
1427#if DEBUG_ADD_T_PAIR
1428    SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1429            __FUNCTION__, fID, t, other->fID, otherT);
1430#endif
1431    int insertedAt = addT(other, pt, t);
1432    int otherInsertedAt = other->addT(this, pt2, otherT);
1433    addOtherT(insertedAt, otherT, otherInsertedAt);
1434    other->addOtherT(otherInsertedAt, t, insertedAt);
1435    matchWindingValue(insertedAt, t, borrowWind);
1436    other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
1437    SkOpSpan& span = this->fTs[insertedAt];
1438    if (pt != pt2) {
1439        span.fNear = true;
1440        SkOpSpan& oSpan = other->fTs[otherInsertedAt];
1441        oSpan.fNear = true;
1442    }
1443    return &span;
1444}
1445
1446const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1447                           const SkPoint& pt) {
1448    return addTPair(t, other, otherT, borrowWind, pt, pt);
1449}
1450
1451bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
1452    const SkPoint midPt = ptAtT(midT);
1453    SkPathOpsBounds bounds;
1454    bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1455    bounds.sort();
1456    return bounds.almostContains(midPt);
1457}
1458
1459bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
1460    if (lesser > greater) {
1461        SkTSwap<int>(lesser, greater);
1462    }
1463    return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
1464}
1465
1466// in extreme cases (like the buffer overflow test) return false to abort
1467// for now, if one t value represents two different points, then the values are too extreme
1468// to generate meaningful results
1469bool SkOpSegment::calcAngles() {
1470    int spanCount = fTs.count();
1471    if (spanCount <= 2) {
1472        return spanCount == 2;
1473    }
1474    int index = 1;
1475    const SkOpSpan* firstSpan = &fTs[index];
1476    int activePrior = checkSetAngle(0);
1477    const SkOpSpan* span = &fTs[0];
1478    if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) {
1479        index = findStartSpan(0);  // curve start intersects
1480        SkASSERT(index > 0);
1481        if (activePrior >= 0) {
1482            addStartSpan(index);
1483        }
1484    }
1485    bool addEnd;
1486    int endIndex = spanCount - 1;
1487    span = &fTs[endIndex - 1];
1488    if ((addEnd = span->fT == 1 || span->fTiny)) {  // if curve end intersects
1489        endIndex = findEndSpan(endIndex);
1490        SkASSERT(endIndex > 0);
1491    } else {
1492        addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts();
1493    }
1494    SkASSERT(endIndex >= index);
1495    int prior = 0;
1496    while (index < endIndex) {
1497        const SkOpSpan& fromSpan = fTs[index];  // for each intermediate intersection
1498        const SkOpSpan* lastSpan;
1499        span = &fromSpan;
1500        int start = index;
1501        do {
1502            lastSpan = span;
1503            span = &fTs[++index];
1504            SkASSERT(index < spanCount);
1505            if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) {
1506                break;
1507            }
1508            if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) {
1509                return false;
1510            }
1511        } while (true);
1512        SkOpAngle* angle = NULL;
1513        SkOpAngle* priorAngle;
1514        if (activePrior >= 0) {
1515            int pActive = firstActive(prior);
1516            SkASSERT(pActive < start);
1517            priorAngle = &fAngles.push_back();
1518            priorAngle->set(this, start, pActive);
1519        }
1520        int active = checkSetAngle(start);
1521        if (active >= 0) {
1522            SkASSERT(active < index);
1523            angle = &fAngles.push_back();
1524            angle->set(this, active, index);
1525        }
1526    #if DEBUG_ANGLE
1527        debugCheckPointsEqualish(start, index);
1528    #endif
1529        prior = start;
1530        do {
1531            const SkOpSpan* startSpan = &fTs[start - 1];
1532            if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle
1533                    || startSpan->fToAngle) {
1534                break;
1535            }
1536            --start;
1537        } while (start > 0);
1538        do {
1539            if (activePrior >= 0) {
1540                SkASSERT(fTs[start].fFromAngle == NULL);
1541                fTs[start].fFromAngle = priorAngle;
1542            }
1543            if (active >= 0) {
1544                SkASSERT(fTs[start].fToAngle == NULL);
1545                fTs[start].fToAngle = angle;
1546            }
1547        } while (++start < index);
1548        activePrior = active;
1549    }
1550    if (addEnd && activePrior >= 0) {
1551        addEndSpan(endIndex);
1552    }
1553    return true;
1554}
1555
1556int SkOpSegment::checkSetAngle(int tIndex) const {
1557    const SkOpSpan* span = &fTs[tIndex];
1558    while (span->fTiny /* || span->fSmall */) {
1559        span = &fTs[++tIndex];
1560    }
1561    return isCanceled(tIndex) ? -1 : tIndex;
1562}
1563
1564// at this point, the span is already ordered, or unorderable
1565int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) {
1566    SkASSERT(includeType != SkOpAngle::kUnaryXor);
1567    SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex);
1568    if (NULL == firstAngle) {
1569        return SK_NaN32;
1570    }
1571    // if all angles have a computed winding,
1572    //  or if no adjacent angles are orderable,
1573    //  or if adjacent orderable angles have no computed winding,
1574    //  there's nothing to do
1575    // if two orderable angles are adjacent, and both are next to orderable angles,
1576    //  and one has winding computed, transfer to the other
1577    SkOpAngle* baseAngle = NULL;
1578    bool tryReverse = false;
1579    // look for counterclockwise transfers
1580    SkOpAngle* angle = firstAngle->previous();
1581    SkOpAngle* next = angle->next();
1582    firstAngle = next;
1583    do {
1584        SkOpAngle* prior = angle;
1585        angle = next;
1586        next = angle->next();
1587        SkASSERT(prior->next() == angle);
1588        SkASSERT(angle->next() == next);
1589        if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1590            baseAngle = NULL;
1591            continue;
1592        }
1593        int testWinding = angle->segment()->windSum(angle);
1594        if (SK_MinS32 != testWinding) {
1595            baseAngle = angle;
1596            tryReverse = true;
1597            continue;
1598        }
1599        if (baseAngle) {
1600            ComputeOneSum(baseAngle, angle, includeType);
1601            baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1602        }
1603    } while (next != firstAngle);
1604    if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
1605        firstAngle = baseAngle;
1606        tryReverse = true;
1607    }
1608    if (tryReverse) {
1609        baseAngle = NULL;
1610        SkOpAngle* prior = firstAngle;
1611        do {
1612            angle = prior;
1613            prior = angle->previous();
1614            SkASSERT(prior->next() == angle);
1615            next = angle->next();
1616            if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1617                baseAngle = NULL;
1618                continue;
1619            }
1620            int testWinding = angle->segment()->windSum(angle);
1621            if (SK_MinS32 != testWinding) {
1622                baseAngle = angle;
1623                continue;
1624            }
1625            if (baseAngle) {
1626                ComputeOneSumReverse(baseAngle, angle, includeType);
1627                baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1628            }
1629        } while (prior != firstAngle);
1630    }
1631    int minIndex = SkMin32(startIndex, endIndex);
1632    return windSum(minIndex);
1633}
1634
1635void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1636        SkOpAngle::IncludeType includeType) {
1637    const SkOpSegment* baseSegment = baseAngle->segment();
1638    int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
1639    int sumSuWinding;
1640    bool binary = includeType >= SkOpAngle::kBinarySingle;
1641    if (binary) {
1642        sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
1643        if (baseSegment->operand()) {
1644            SkTSwap<int>(sumMiWinding, sumSuWinding);
1645        }
1646    }
1647    SkOpSegment* nextSegment = nextAngle->segment();
1648    int maxWinding, sumWinding;
1649    SkOpSpan* last;
1650    if (binary) {
1651        int oppMaxWinding, oppSumWinding;
1652        nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1653                &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1654        last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1655                nextAngle);
1656    } else {
1657        nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1658                &maxWinding, &sumWinding);
1659        last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1660    }
1661    nextAngle->setLastMarked(last);
1662}
1663
1664void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1665        SkOpAngle::IncludeType includeType) {
1666    const SkOpSegment* baseSegment = baseAngle->segment();
1667    int sumMiWinding = baseSegment->updateWinding(baseAngle);
1668    int sumSuWinding;
1669    bool binary = includeType >= SkOpAngle::kBinarySingle;
1670    if (binary) {
1671        sumSuWinding = baseSegment->updateOppWinding(baseAngle);
1672        if (baseSegment->operand()) {
1673            SkTSwap<int>(sumMiWinding, sumSuWinding);
1674        }
1675    }
1676    SkOpSegment* nextSegment = nextAngle->segment();
1677    int maxWinding, sumWinding;
1678    SkOpSpan* last;
1679    if (binary) {
1680        int oppMaxWinding, oppSumWinding;
1681        nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1682                &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1683        last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1684                nextAngle);
1685    } else {
1686        nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1687                &maxWinding, &sumWinding);
1688        last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1689    }
1690    nextAngle->setLastMarked(last);
1691}
1692
1693bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
1694    int step = index < endIndex ? 1 : -1;
1695    do {
1696        const SkOpSpan& span = this->span(index);
1697        if (span.fPt == pt) {
1698            const SkOpSpan& endSpan = this->span(endIndex);
1699            return span.fT == endSpan.fT && pt != endSpan.fPt;
1700        }
1701        index += step;
1702    } while (index != endIndex);
1703    return false;
1704}
1705
1706bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const {
1707    int count = this->count();
1708    for (int index = 0; index < count; ++index) {
1709        const SkOpSpan& span = fTs[index];
1710        if (t < span.fT) {
1711            return false;
1712        }
1713        if (t == span.fT) {
1714            if (other != span.fOther) {
1715                continue;
1716            }
1717            if (other->fVerb != SkPath::kCubic_Verb) {
1718                return true;
1719            }
1720            if (!other->fLoop) {
1721                return true;
1722            }
1723            double otherMidT = (otherT + span.fOtherT) / 2;
1724            SkPoint otherPt = other->ptAtT(otherMidT);
1725            return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
1726        }
1727    }
1728    return false;
1729}
1730
1731int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
1732                              bool* hitSomething, double mid, bool opp, bool current) const {
1733    SkScalar bottom = fBounds.fBottom;
1734    int bestTIndex = -1;
1735    if (bottom <= *bestY) {
1736        return bestTIndex;
1737    }
1738    SkScalar top = fBounds.fTop;
1739    if (top >= basePt.fY) {
1740        return bestTIndex;
1741    }
1742    if (fBounds.fLeft > basePt.fX) {
1743        return bestTIndex;
1744    }
1745    if (fBounds.fRight < basePt.fX) {
1746        return bestTIndex;
1747    }
1748    if (fBounds.fLeft == fBounds.fRight) {
1749        // if vertical, and directly above test point, wait for another one
1750        return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
1751    }
1752    // intersect ray starting at basePt with edge
1753    SkIntersections intersections;
1754    // OPTIMIZE: use specialty function that intersects ray with curve,
1755    // returning t values only for curve (we don't care about t on ray)
1756    intersections.allowNear(false);
1757    int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
1758            (fPts, top, bottom, basePt.fX, false);
1759    if (pts == 0 || (current && pts == 1)) {
1760        return bestTIndex;
1761    }
1762    if (current) {
1763        SkASSERT(pts > 1);
1764        int closestIdx = 0;
1765        double closest = fabs(intersections[0][0] - mid);
1766        for (int idx = 1; idx < pts; ++idx) {
1767            double test = fabs(intersections[0][idx] - mid);
1768            if (closest > test) {
1769                closestIdx = idx;
1770                closest = test;
1771            }
1772        }
1773        intersections.quickRemoveOne(closestIdx, --pts);
1774    }
1775    double bestT = -1;
1776    for (int index = 0; index < pts; ++index) {
1777        double foundT = intersections[0][index];
1778        if (approximately_less_than_zero(foundT)
1779                    || approximately_greater_than_one(foundT)) {
1780            continue;
1781        }
1782        SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
1783        if (approximately_negative(testY - *bestY)
1784                || approximately_negative(basePt.fY - testY)) {
1785            continue;
1786        }
1787        if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1788            return SK_MinS32;  // if the intersection is edge on, wait for another one
1789        }
1790        if (fVerb > SkPath::kLine_Verb) {
1791            SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
1792            if (approximately_zero(dx)) {
1793                return SK_MinS32;  // hit vertical, wait for another one
1794            }
1795        }
1796        *bestY = testY;
1797        bestT = foundT;
1798    }
1799    if (bestT < 0) {
1800        return bestTIndex;
1801    }
1802    SkASSERT(bestT >= 0);
1803    SkASSERT(bestT <= 1);
1804    int start;
1805    int end = 0;
1806    do {
1807        start = end;
1808        end = nextSpan(start, 1);
1809    } while (fTs[end].fT < bestT);
1810    // FIXME: see next candidate for a better pattern to find the next start/end pair
1811    while (start + 1 < end && fTs[start].fDone) {
1812        ++start;
1813    }
1814    if (!isCanceled(start)) {
1815        *hitT = bestT;
1816        bestTIndex = start;
1817        *hitSomething = true;
1818    }
1819    return bestTIndex;
1820}
1821
1822bool SkOpSegment::decrementSpan(SkOpSpan* span) {
1823    SkASSERT(span->fWindValue > 0);
1824    if (--(span->fWindValue) == 0) {
1825        if (!span->fOppValue && !span->fDone) {
1826            span->fDone = true;
1827            ++fDoneSpans;
1828            return true;
1829        }
1830    }
1831    return false;
1832}
1833
1834bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
1835    SkASSERT(!span->fDone || span->fTiny || span->fSmall);
1836    span->fWindValue += windDelta;
1837    SkASSERT(span->fWindValue >= 0);
1838    span->fOppValue += oppDelta;
1839    SkASSERT(span->fOppValue >= 0);
1840    if (fXor) {
1841        span->fWindValue &= 1;
1842    }
1843    if (fOppXor) {
1844        span->fOppValue &= 1;
1845    }
1846    if (!span->fWindValue && !span->fOppValue) {
1847        span->fDone = true;
1848        ++fDoneSpans;
1849        return true;
1850    }
1851    return false;
1852}
1853
1854const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const {
1855    const SkOpSpan* firstSpan = &thisSpan; // rewind to the start
1856    const SkOpSpan* beginSpan = fTs.begin();
1857    const SkPoint& testPt = thisSpan.fPt;
1858    while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) {
1859        --firstSpan;
1860    }
1861    return *firstSpan;
1862}
1863
1864const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const {
1865    const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be small
1866    const SkOpSpan* lastSpan = &thisSpan;  // find the end
1867    const SkPoint& testPt = thisSpan.fPt;
1868    while (lastSpan < endSpan && lastSpan[1].fPt == testPt) {
1869        ++lastSpan;
1870    }
1871    return *lastSpan;
1872}
1873
1874// with a loop, the comparison is move involved
1875// scan backwards and forwards to count all matching points
1876// (verify that there are twp scans marked as loops)
1877// compare that against 2 matching scans for loop plus other results
1878bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) {
1879    const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start
1880    const SkOpSpan& lastSpan = this->lastSpan(thisSpan);  // find the end
1881    double firstLoopT = -1, lastLoopT = -1;
1882    const SkOpSpan* testSpan = &firstSpan - 1;
1883    while (++testSpan <= &lastSpan) {
1884        if (testSpan->fLoop) {
1885            firstLoopT = testSpan->fT;
1886            break;
1887        }
1888    }
1889    testSpan = &lastSpan + 1;
1890    while (--testSpan >= &firstSpan) {
1891        if (testSpan->fLoop) {
1892            lastLoopT = testSpan->fT;
1893            break;
1894        }
1895    }
1896    SkASSERT((firstLoopT == -1) == (lastLoopT == -1));
1897    if (firstLoopT == -1) {
1898        return false;
1899    }
1900    SkASSERT(firstLoopT < lastLoopT);
1901    testSpan = &firstSpan - 1;
1902    smallCounts[0] = smallCounts[1] = 0;
1903    while (++testSpan <= &lastSpan) {
1904        SkASSERT(approximately_equal(testSpan->fT, firstLoopT) +
1905                approximately_equal(testSpan->fT, lastLoopT) == 1);
1906        smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++;
1907    }
1908    return true;
1909}
1910
1911double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max,
1912        double hiEnd, const SkOpSegment* other, int thisStart) {
1913    if (max >= hiEnd) {
1914        return -1;
1915    }
1916    int end = findOtherT(hiEnd, ref);
1917    if (end < 0) {
1918        return -1;
1919    }
1920    double tHi = span(end).fT;
1921    double tLo, refLo;
1922    if (thisStart >= 0) {
1923        tLo = span(thisStart).fT;
1924        refLo = min;
1925    } else {
1926        int start1 = findOtherT(loEnd, ref);
1927        SkASSERT(start1 >= 0);
1928        tLo = span(start1).fT;
1929        refLo = loEnd;
1930    }
1931    double missingT = (max - refLo) / (hiEnd - refLo);
1932    missingT = tLo + missingT * (tHi - tLo);
1933    return missingT;
1934}
1935
1936double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max,
1937        double hiEnd, const SkOpSegment* other, int thisEnd) {
1938    if (min <= loEnd) {
1939        return -1;
1940    }
1941    int start = findOtherT(loEnd, ref);
1942    if (start < 0) {
1943        return -1;
1944    }
1945    double tLo = span(start).fT;
1946    double tHi, refHi;
1947    if (thisEnd >= 0) {
1948        tHi = span(thisEnd).fT;
1949        refHi = max;
1950    } else {
1951        int end1 = findOtherT(hiEnd, ref);
1952        if (end1 < 0) {
1953            return -1;
1954        }
1955        tHi = span(end1).fT;
1956        refHi = hiEnd;
1957    }
1958    double missingT = (min - loEnd) / (refHi - loEnd);
1959    missingT = tLo + missingT * (tHi - tLo);
1960    return missingT;
1961}
1962
1963// see if spans with two or more intersections have the same number on the other end
1964void SkOpSegment::checkDuplicates() {
1965    debugValidate();
1966    SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1967    int index;
1968    int endIndex = 0;
1969    bool endFound;
1970    do {
1971        index = endIndex;
1972        endIndex = nextExactSpan(index, 1);
1973        if ((endFound = endIndex < 0)) {
1974            endIndex = count();
1975        }
1976        int dupCount = endIndex - index;
1977        if (dupCount < 2) {
1978            continue;
1979        }
1980        do {
1981            const SkOpSpan* thisSpan = &fTs[index];
1982            if (thisSpan->fNear) {
1983                continue;
1984            }
1985            SkOpSegment* other = thisSpan->fOther;
1986            int oIndex = thisSpan->fOtherIndex;
1987            int oStart = other->nextExactSpan(oIndex, -1) + 1;
1988            int oEnd = other->nextExactSpan(oIndex, 1);
1989            if (oEnd < 0) {
1990                oEnd = other->count();
1991            }
1992            int oCount = oEnd - oStart;
1993            // force the other to match its t and this pt if not on an end point
1994            if (oCount != dupCount) {
1995                MissingSpan& missing = missingSpans.push_back();
1996                missing.fOther = NULL;
1997                SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
1998                missing.fPt = thisSpan->fPt;
1999                const SkOpSpan& oSpan = other->span(oIndex);
2000                if (oCount > dupCount) {
2001                    missing.fSegment = this;
2002                    missing.fT = thisSpan->fT;
2003                    other->checkLinks(&oSpan, &missingSpans);
2004                } else {
2005                    missing.fSegment = other;
2006                    missing.fT = oSpan.fT;
2007                    checkLinks(thisSpan, &missingSpans);
2008                }
2009                if (!missingSpans.back().fOther) {
2010                    missingSpans.pop_back();
2011                }
2012            }
2013        } while (++index < endIndex);
2014    } while (!endFound);
2015    int missingCount = missingSpans.count();
2016    if (missingCount == 0) {
2017        return;
2018    }
2019    SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence;
2020    for (index = 0; index < missingCount; ++index)  {
2021        MissingSpan& missing = missingSpans[index];
2022        SkOpSegment* missingOther = missing.fOther;
2023        if (missing.fSegment == missing.fOther) {
2024            continue;
2025        }
2026#if 0  // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks
2027       // skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why
2028        if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) {
2029#if DEBUG_DUPLICATES
2030            SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID,
2031                    missing.fT, missing.fOther->fID, missing.fOtherT);
2032#endif
2033            continue;
2034        }
2035        if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) {
2036#if DEBUG_DUPLICATES
2037            SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID,
2038                    missing.fOtherT, missing.fSegment->fID, missing.fT);
2039#endif
2040            continue;
2041        }
2042#endif
2043        // skip if adding would insert point into an existing coincindent span
2044        if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther)
2045                && missingOther->inCoincidentSpan(missing.fOtherT, this)) {
2046            continue;
2047        }
2048        // skip if the created coincident spans are small
2049        if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther)
2050                && missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) {
2051            continue;
2052        }
2053        const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther,
2054                missing.fOtherT, false, missing.fPt);
2055        if (added && added->fSmall) {
2056            missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence);
2057        }
2058    }
2059    for (index = 0; index < missingCount; ++index)  {
2060        MissingSpan& missing = missingSpans[index];
2061        missing.fSegment->fixOtherTIndex();
2062        missing.fOther->fixOtherTIndex();
2063    }
2064    for (index = 0; index < missingCoincidence.count(); ++index) {
2065        MissingSpan& missing = missingCoincidence[index];
2066        missing.fSegment->fixOtherTIndex();
2067    }
2068    debugValidate();
2069}
2070
2071// look to see if the curve end intersects an intermediary that intersects the other
2072void SkOpSegment::checkEnds() {
2073    debugValidate();
2074    SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2075    int count = fTs.count();
2076    for (int index = 0; index < count; ++index) {
2077        const SkOpSpan& span = fTs[index];
2078        double otherT = span.fOtherT;
2079        if (otherT != 0 && otherT != 1) { // only check ends
2080            continue;
2081        }
2082        const SkOpSegment* other = span.fOther;
2083        // peek start/last describe the range of spans that match the other t of this span
2084        int peekStart = span.fOtherIndex;
2085        while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
2086            ;
2087        int otherCount = other->fTs.count();
2088        int peekLast = span.fOtherIndex;
2089        while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
2090            ;
2091        if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
2092            continue;
2093        }
2094        // t start/last describe the range of spans that match the t of this span
2095        double t = span.fT;
2096        double tBottom = -1;
2097        int tStart = -1;
2098        int tLast = count;
2099        bool lastSmall = false;
2100        double afterT = t;
2101        for (int inner = 0; inner < count; ++inner) {
2102            double innerT = fTs[inner].fT;
2103            if (innerT <= t && innerT > tBottom) {
2104                if (innerT < t || !lastSmall) {
2105                    tStart = inner - 1;
2106                }
2107                tBottom = innerT;
2108            }
2109            if (innerT > afterT) {
2110                if (t == afterT && lastSmall) {
2111                    afterT = innerT;
2112                } else {
2113                    tLast = inner;
2114                    break;
2115                }
2116            }
2117            lastSmall = innerT <= t ? fTs[inner].fSmall : false;
2118        }
2119        for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
2120            if (peekIndex == span.fOtherIndex) {  // skip the other span pointed to by this span
2121                continue;
2122            }
2123            const SkOpSpan& peekSpan = other->fTs[peekIndex];
2124            SkOpSegment* match = peekSpan.fOther;
2125            if (match->done()) {
2126                continue;  // if the edge has already been eaten (likely coincidence), ignore it
2127            }
2128            const double matchT = peekSpan.fOtherT;
2129            // see if any of the spans match the other spans
2130            for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
2131                const SkOpSpan& tSpan = fTs[tIndex];
2132                if (tSpan.fOther == match) {
2133                    if (tSpan.fOtherT == matchT) {
2134                        goto nextPeekIndex;
2135                    }
2136                    double midT = (tSpan.fOtherT + matchT) / 2;
2137                    if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
2138                        goto nextPeekIndex;
2139                    }
2140                }
2141            }
2142            if (missingSpans.count() > 0) {
2143                const MissingSpan& lastMissing = missingSpans.back();
2144                if (lastMissing.fT == t
2145                        && lastMissing.fOther == match
2146                        && lastMissing.fOtherT == matchT) {
2147                    SkASSERT(lastMissing.fPt == peekSpan.fPt);
2148                    continue;
2149                }
2150            }
2151#if DEBUG_CHECK_ENDS
2152            SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
2153                    __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
2154#endif
2155            // this segment is missing a entry that the other contains
2156            // remember so we can add the missing one and recompute the indices
2157            {
2158                MissingSpan& missing = missingSpans.push_back();
2159                SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2160                missing.fT = t;
2161                missing.fOther = match;
2162                missing.fOtherT = matchT;
2163                missing.fPt = peekSpan.fPt;
2164            }
2165            break;
2166nextPeekIndex:
2167            ;
2168        }
2169    }
2170    if (missingSpans.count() == 0) {
2171        debugValidate();
2172        return;
2173    }
2174    debugValidate();
2175    int missingCount = missingSpans.count();
2176    for (int index = 0; index < missingCount; ++index)  {
2177        MissingSpan& missing = missingSpans[index];
2178        if (this != missing.fOther) {
2179            addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
2180        }
2181    }
2182    fixOtherTIndex();
2183    // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2184    // avoid this
2185    for (int index = 0; index < missingCount; ++index)  {
2186        missingSpans[index].fOther->fixOtherTIndex();
2187    }
2188    debugValidate();
2189}
2190
2191void SkOpSegment::checkLinks(const SkOpSpan* base,
2192        SkTArray<MissingSpan, true>* missingSpans) const {
2193    const SkOpSpan* first = fTs.begin();
2194    const SkOpSpan* last = fTs.end() - 1;
2195    SkASSERT(base >= first && last >= base);
2196    const SkOpSegment* other = base->fOther;
2197    const SkOpSpan* oFirst = other->fTs.begin();
2198    const SkOpSpan* oLast = other->fTs.end() - 1;
2199    const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex];
2200    const SkOpSpan* test = base;
2201    const SkOpSpan* missing = NULL;
2202    while (test > first && (--test)->fPt == base->fPt) {
2203        CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2204    }
2205    test = base;
2206    while (test < last && (++test)->fPt == base->fPt) {
2207        CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2208    }
2209}
2210
2211// see if spans with two or more intersections all agree on common t and point values
2212void SkOpSegment::checkMultiples() {
2213    debugValidate();
2214    int index;
2215    int end = 0;
2216    while (fTs[++end].fT == 0)
2217        ;
2218    while (fTs[end].fT < 1) {
2219        int start = index = end;
2220        end = nextExactSpan(index, 1);
2221        if (end <= index) {
2222            return;  // buffer overflow example triggers this
2223        }
2224        if (index + 1 == end) {
2225            continue;
2226        }
2227        // force the duplicates to agree on t and pt if not on the end
2228        SkOpSpan& span = fTs[index];
2229        double thisT = span.fT;
2230        const SkPoint& thisPt = span.fPt;
2231        span.fMultiple = true;
2232        bool aligned = false;
2233        while (++index < end) {
2234            aligned |= alignSpan(index, thisT, thisPt);
2235        }
2236        if (aligned) {
2237            alignSpanState(start, end);
2238        }
2239        fMultiples = true;
2240    }
2241    debugValidate();
2242}
2243
2244void SkOpSegment::CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
2245        const SkOpSpan* oFirst, const SkOpSpan* oLast, const SkOpSpan** missingPtr,
2246        SkTArray<MissingSpan, true>* missingSpans) {
2247    SkASSERT(oSpan->fPt == test->fPt);
2248    const SkOpSpan* oTest = oSpan;
2249    while (oTest > oFirst && (--oTest)->fPt == test->fPt) {
2250        if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2251            return;
2252        }
2253    }
2254    oTest = oSpan;
2255    while (oTest < oLast && (++oTest)->fPt == test->fPt) {
2256        if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2257            return;
2258        }
2259    }
2260    if (*missingPtr) {
2261        missingSpans->push_back();
2262    }
2263    MissingSpan& lastMissing = missingSpans->back();
2264    if (*missingPtr) {
2265        lastMissing = missingSpans->end()[-2];
2266    }
2267    *missingPtr = test;
2268    lastMissing.fOther = test->fOther;
2269    lastMissing.fOtherT = test->fOtherT;
2270}
2271
2272bool SkOpSegment::checkSmall(int index) const {
2273    if (fTs[index].fSmall) {
2274        return true;
2275    }
2276    double tBase = fTs[index].fT;
2277    while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
2278        ;
2279    return fTs[index].fSmall;
2280}
2281
2282// a pair of curves may turn into coincident lines -- small may be a hint that that happened
2283// if a cubic contains a loop, the counts must be adjusted
2284void SkOpSegment::checkSmall() {
2285    SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2286    const SkOpSpan* beginSpan = fTs.begin();
2287    const SkOpSpan* thisSpan = beginSpan - 1;
2288    const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be small
2289    while (++thisSpan < endSpan) {
2290        if (!thisSpan->fSmall) {
2291            continue;
2292        }
2293        if (!thisSpan->fWindValue) {
2294            continue;
2295        }
2296        const SkOpSpan& firstSpan = this->firstSpan(*thisSpan);
2297        const SkOpSpan& lastSpan = this->lastSpan(*thisSpan);
2298        const SkOpSpan* nextSpan = &firstSpan + 1;
2299        ptrdiff_t smallCount = &lastSpan - &firstSpan + 1;
2300        SkASSERT(1 <= smallCount && smallCount < count());
2301        if (smallCount <= 1 && !nextSpan->fSmall) {
2302            SkASSERT(1 == smallCount);
2303            checkSmallCoincidence(firstSpan, NULL);
2304            continue;
2305        }
2306        // at this point, check for missing computed intersections
2307        const SkPoint& testPt = firstSpan.fPt;
2308        thisSpan = &firstSpan - 1;
2309        SkOpSegment* other = NULL;
2310        while (++thisSpan <= &lastSpan) {
2311            other = thisSpan->fOther;
2312            if (other != this) {
2313                break;
2314            }
2315        }
2316        SkASSERT(other != this);
2317        int oIndex = thisSpan->fOtherIndex;
2318        const SkOpSpan& oSpan = other->span(oIndex);
2319        const SkOpSpan& oFirstSpan = other->firstSpan(oSpan);
2320        const SkOpSpan& oLastSpan = other->lastSpan(oSpan);
2321        ptrdiff_t oCount = &oLastSpan - &oFirstSpan + 1;
2322        if (fLoop) {
2323            int smallCounts[2];
2324            SkASSERT(!other->fLoop);  // FIXME: we need more complicated logic for pair of loops
2325            if (calcLoopSpanCount(*thisSpan, smallCounts)) {
2326                if (smallCounts[0] && oCount != smallCounts[0]) {
2327                    SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2328                }
2329                if (smallCounts[1] && oCount != smallCounts[1]) {
2330                    SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2331                }
2332                goto nextSmallCheck;
2333            }
2334        }
2335        if (other->fLoop) {
2336            int otherCounts[2];
2337            if (other->calcLoopSpanCount(other->span(oIndex), otherCounts)) {
2338                if (otherCounts[0] && otherCounts[0] != smallCount) {
2339                    SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2340                }
2341                if (otherCounts[1] && otherCounts[1] != smallCount) {
2342                    SkASSERT(0);  // FIXME: need a working test case to properly code & debug
2343                }
2344                goto nextSmallCheck;
2345            }
2346        }
2347        if (oCount != smallCount) {  // check if number of pts in this match other
2348            MissingSpan& missing = missingSpans.push_back();
2349            missing.fOther = NULL;
2350            SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2351            missing.fPt = testPt;
2352            const SkOpSpan& oSpan = other->span(oIndex);
2353            if (oCount > smallCount) {
2354                missing.fSegment = this;
2355                missing.fT = thisSpan->fT;
2356                other->checkLinks(&oSpan, &missingSpans);
2357            } else {
2358                missing.fSegment = other;
2359                missing.fT = oSpan.fT;
2360                checkLinks(thisSpan, &missingSpans);
2361            }
2362            if (!missingSpans.back().fOther || missing.fSegment->done()) {
2363                missingSpans.pop_back();
2364            }
2365        }
2366nextSmallCheck:
2367        thisSpan = &lastSpan;
2368    }
2369    int missingCount = missingSpans.count();
2370    for (int index = 0; index < missingCount; ++index)  {
2371        MissingSpan& missing = missingSpans[index];
2372        SkOpSegment* missingOther = missing.fOther;
2373        // note that add t pair may edit span arrays, so prior pointers to spans are no longer valid
2374        if (!missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false,
2375                missing.fPt)) {
2376            continue;
2377        }
2378        int otherTIndex = missingOther->findT(missing.fOtherT, missing.fPt, missing.fSegment);
2379        const SkOpSpan& otherSpan = missingOther->span(otherTIndex);
2380        if (otherSpan.fSmall) {
2381            const SkOpSpan* nextSpan = &otherSpan;
2382            do {
2383                ++nextSpan;
2384            } while (nextSpan->fSmall);
2385            missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt, nextSpan->fT,
2386                    missingOther);
2387        } else if (otherSpan.fT > 0) {
2388            const SkOpSpan* priorSpan = &otherSpan;
2389            do {
2390                --priorSpan;
2391            } while (priorSpan->fT == otherSpan.fT);
2392            if (priorSpan->fSmall) {
2393                missing.fSegment->addTCancel(missing.fPt, priorSpan->fPt, missingOther);
2394            }
2395        }
2396    }
2397    // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2398    // avoid this
2399    for (int index = 0; index < missingCount; ++index)  {
2400        MissingSpan& missing = missingSpans[index];
2401        missing.fSegment->fixOtherTIndex();
2402        missing.fOther->fixOtherTIndex();
2403    }
2404    debugValidate();
2405}
2406
2407void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
2408        SkTArray<MissingSpan, true>* checkMultiple) {
2409    SkASSERT(span.fSmall);
2410    if (0 && !span.fWindValue) {
2411        return;
2412    }
2413    SkASSERT(&span < fTs.end() - 1);
2414    const SkOpSpan* next = &span + 1;
2415    SkASSERT(!next->fSmall || checkMultiple);
2416    if (checkMultiple) {
2417        while (next->fSmall) {
2418            ++next;
2419            SkASSERT(next < fTs.end());
2420        }
2421    }
2422    SkOpSegment* other = span.fOther;
2423    while (other != next->fOther) {
2424        if (!checkMultiple) {
2425            return;
2426        }
2427        const SkOpSpan* test = next + 1;
2428        if (test == fTs.end()) {
2429            return;
2430        }
2431        if (test->fPt != next->fPt || !precisely_equal(test->fT, next->fT)) {
2432            return;
2433        }
2434        next = test;
2435    }
2436    SkASSERT(span.fT < next->fT);
2437    int oStartIndex = other->findExactT(span.fOtherT, this);
2438    int oEndIndex = other->findExactT(next->fOtherT, this);
2439    // FIXME: be overly conservative by limiting this to the caller that allows multiple smalls
2440    if (!checkMultiple || fVerb != SkPath::kLine_Verb || other->fVerb != SkPath::kLine_Verb) {
2441        SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2442        const SkOpSpan& oSpanStart = other->fTs[oStartIndex];
2443        const SkOpSpan& oSpanEnd = other->fTs[oEndIndex];
2444        SkPoint oMid = other->ptAtT((oSpanStart.fT + oSpanEnd.fT) / 2);
2445        if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2446            return;
2447        }
2448    }
2449    // FIXME: again, be overly conservative to avoid breaking existing tests
2450    const SkOpSpan& oSpan = oStartIndex < oEndIndex ? other->fTs[oStartIndex]
2451            : other->fTs[oEndIndex];
2452    if (checkMultiple && !oSpan.fSmall) {
2453        return;
2454    }
2455    SkASSERT(oSpan.fSmall);
2456    if (oStartIndex < oEndIndex) {
2457        addTCoincident(span.fPt, next->fPt, next->fT, other);
2458    } else {
2459        addTCancel(span.fPt, next->fPt, other);
2460    }
2461    if (!checkMultiple) {
2462        return;
2463    }
2464    // check to see if either segment is coincident with a third segment -- if it is, and if
2465    // the opposite segment is not already coincident with the third, make it so
2466    // OPTIMIZE: to make this check easier, add coincident and cancel could set a coincident bit
2467    if (span.fWindValue != 1 || span.fOppValue != 0) {
2468//        start here;
2469        // iterate through the spans, looking for the third coincident case
2470        // if we find one, we need to return state to the caller so that the indices can be fixed
2471        // this also suggests that all of this function is fragile since it relies on a valid index
2472    }
2473    // probably should make this a common function rather than copy/paste code
2474    if (oSpan.fWindValue != 1 || oSpan.fOppValue != 0) {
2475        const SkOpSpan* oTest = &oSpan;
2476        while (--oTest >= other->fTs.begin()) {
2477            if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2478                break;
2479            }
2480            SkOpSegment* testOther = oTest->fOther;
2481            SkASSERT(testOther != this);
2482            // look in both directions to see if there is a coincident span
2483            const SkOpSpan* tTest = testOther->fTs.begin();
2484            for (int testIndex = 0; testIndex < testOther->count(); ++testIndex) {
2485                if (tTest->fPt != span.fPt) {
2486                    ++tTest;
2487                    continue;
2488                }
2489                if (testOther->verb() != SkPath::kLine_Verb
2490                        || other->verb() != SkPath::kLine_Verb) {
2491                    SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2492                    SkPoint oMid = other->ptAtT((oTest->fOtherT + tTest->fT) / 2);
2493                    if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2494                        continue;
2495                    }
2496                }
2497#if DEBUG_CONCIDENT
2498                SkDebugf("%s coincident found=%d %1.9g %1.9g\n", __FUNCTION__, testOther->fID,
2499                        oTest->fOtherT, tTest->fT);
2500#endif
2501                if (tTest->fT < oTest->fOtherT) {
2502                    addTCoincident(span.fPt, next->fPt, next->fT, testOther);
2503                } else {
2504                    addTCancel(span.fPt, next->fPt, testOther);
2505                }
2506                MissingSpan missing;
2507                missing.fSegment = testOther;
2508                checkMultiple->push_back(missing);
2509                break;
2510            }
2511        }
2512        oTest = &oSpan;
2513        while (++oTest < other->fTs.end()) {
2514            if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2515                break;
2516            }
2517
2518        }
2519    }
2520}
2521
2522// if pair of spans on either side of tiny have the same end point and mid point, mark
2523// them as parallel
2524void SkOpSegment::checkTiny() {
2525    SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2526    SkOpSpan* thisSpan = fTs.begin() - 1;
2527    const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be tiny
2528    while (++thisSpan < endSpan) {
2529        if (!thisSpan->fTiny) {
2530            continue;
2531        }
2532        SkOpSpan* nextSpan = thisSpan + 1;
2533        double thisT = thisSpan->fT;
2534        double nextT = nextSpan->fT;
2535        if (thisT == nextT) {
2536            continue;
2537        }
2538        SkASSERT(thisT < nextT);
2539        SkASSERT(thisSpan->fPt == nextSpan->fPt);
2540        SkOpSegment* thisOther = thisSpan->fOther;
2541        SkOpSegment* nextOther = nextSpan->fOther;
2542        int oIndex = thisSpan->fOtherIndex;
2543        for (int oStep = -1; oStep <= 1; oStep += 2) {
2544            int oEnd = thisOther->nextExactSpan(oIndex, oStep);
2545            if (oEnd < 0) {
2546                continue;
2547            }
2548            const SkOpSpan& oSpan = thisOther->span(oEnd);
2549            int nIndex = nextSpan->fOtherIndex;
2550            for (int nStep = -1; nStep <= 1; nStep += 2) {
2551                int nEnd = nextOther->nextExactSpan(nIndex, nStep);
2552                if (nEnd < 0) {
2553                    continue;
2554                }
2555                const SkOpSpan& nSpan = nextOther->span(nEnd);
2556                if (oSpan.fPt != nSpan.fPt) {
2557                    continue;
2558                }
2559                double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
2560                const SkPoint& oPt = thisOther->ptAtT(oMidT);
2561                double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
2562                const SkPoint& nPt = nextOther->ptAtT(nMidT);
2563                if (!AlmostEqualUlps(oPt, nPt)) {
2564                    continue;
2565                }
2566#if DEBUG_CHECK_TINY
2567                SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
2568                    thisOther->fID, nextOther->fID);
2569#endif
2570                // this segment is missing a entry that the other contains
2571                // remember so we can add the missing one and recompute the indices
2572                MissingSpan& missing = missingSpans.push_back();
2573                SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2574                missing.fSegment = thisOther;
2575                missing.fT = thisSpan->fOtherT;
2576                missing.fOther = nextOther;
2577                missing.fOtherT = nextSpan->fOtherT;
2578                missing.fPt = thisSpan->fPt;
2579            }
2580        }
2581    }
2582    int missingCount = missingSpans.count();
2583    if (!missingCount) {
2584        return;
2585    }
2586    for (int index = 0; index < missingCount; ++index)  {
2587        MissingSpan& missing = missingSpans[index];
2588        if (missing.fSegment != missing.fOther) {
2589            missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false,
2590                    missing.fPt);
2591        }
2592    }
2593    // OPTIMIZE: consolidate to avoid multiple calls to fix index
2594    for (int index = 0; index < missingCount; ++index)  {
2595        MissingSpan& missing = missingSpans[index];
2596        missing.fSegment->fixOtherTIndex();
2597        missing.fOther->fixOtherTIndex();
2598    }
2599}
2600
2601bool SkOpSegment::coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const {
2602    int count = this->count();
2603    for (int index = 0; index < count; ++index) {
2604        const SkOpSpan& span = this->span(index);
2605        if (span.fOther != other) {
2606            continue;
2607        }
2608        if (span.fPt == pt) {
2609            continue;
2610        }
2611        if (!AlmostEqualUlps(span.fPt, pt)) {
2612            continue;
2613        }
2614        if (fVerb != SkPath::kCubic_Verb) {
2615            return true;
2616        }
2617        double tInterval = t - span.fT;
2618        double tMid = t - tInterval / 2;
2619        SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
2620        return midPt.approximatelyEqual(xyAtT(t));
2621    }
2622    return false;
2623}
2624
2625bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
2626        int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
2627    SkASSERT(span->fT == 0 || span->fT == 1);
2628    SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
2629    const SkOpSpan* otherSpan = &other->span(oEnd);
2630    double refT = otherSpan->fT;
2631    const SkPoint& refPt = otherSpan->fPt;
2632    const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
2633    do {
2634        const SkOpSegment* match = span->fOther;
2635        if (match == otherSpan->fOther) {
2636            // find start of respective spans and see if both have winding
2637            int startIndex, endIndex;
2638            if (span->fOtherT == 1) {
2639                endIndex = span->fOtherIndex;
2640                startIndex = match->nextExactSpan(endIndex, -1);
2641            } else {
2642                startIndex = span->fOtherIndex;
2643                endIndex = match->nextExactSpan(startIndex, 1);
2644            }
2645            const SkOpSpan& startSpan = match->span(startIndex);
2646            if (startSpan.fWindValue != 0) {
2647                // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
2648                // to other segment.
2649                const SkOpSpan& endSpan = match->span(endIndex);
2650                SkDLine ray;
2651                SkVector dxdy;
2652                if (span->fOtherT == 1) {
2653                    ray.fPts[0].set(startSpan.fPt);
2654                    dxdy = match->dxdy(startIndex);
2655                } else {
2656                    ray.fPts[0].set(endSpan.fPt);
2657                    dxdy = match->dxdy(endIndex);
2658                }
2659                ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
2660                ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
2661                SkIntersections i;
2662                int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
2663                for (int index = 0; index < roots; ++index) {
2664                    if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
2665                        double matchMidT = (match->span(startIndex).fT
2666                                + match->span(endIndex).fT) / 2;
2667                        SkPoint matchMidPt = match->ptAtT(matchMidT);
2668                        double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
2669                        SkPoint otherMidPt = other->ptAtT(otherMidT);
2670                        if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
2671                            *startPt = startSpan.fPt;
2672                            *endPt = endSpan.fPt;
2673                            *endT = endSpan.fT;
2674                            return true;
2675                        }
2676                    }
2677                }
2678            }
2679            return false;
2680        }
2681        if (otherSpan == lastSpan) {
2682            break;
2683        }
2684        otherSpan += step;
2685    } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
2686    return false;
2687}
2688
2689int SkOpSegment::findEndSpan(int endIndex) const {
2690    const SkOpSpan* span = &fTs[--endIndex];
2691    const SkPoint& lastPt = span->fPt;
2692    double endT = span->fT;
2693    do {
2694        span = &fTs[--endIndex];
2695    } while (SkDPoint::ApproximatelyEqual(span->fPt, lastPt) && (span->fT == endT || span->fTiny));
2696    return endIndex + 1;
2697}
2698
2699/*
2700 The M and S variable name parts stand for the operators.
2701   Mi stands for Minuend (see wiki subtraction, analogous to difference)
2702   Su stands for Subtrahend
2703 The Opp variable name part designates that the value is for the Opposite operator.
2704 Opposite values result from combining coincident spans.
2705 */
2706SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
2707                                     bool* unsortable, SkPathOp op, const int xorMiMask,
2708                                     const int xorSuMask) {
2709    const int startIndex = *nextStart;
2710    const int endIndex = *nextEnd;
2711    SkASSERT(startIndex != endIndex);
2712    SkDEBUGCODE(const int count = fTs.count());
2713    SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2714    int step = SkSign32(endIndex - startIndex);
2715    *nextStart = startIndex;
2716    SkOpSegment* other = isSimple(nextStart, &step);
2717    if (other)
2718    {
2719    // mark the smaller of startIndex, endIndex done, and all adjacent
2720    // spans with the same T value (but not 'other' spans)
2721#if DEBUG_WINDING
2722        SkDebugf("%s simple\n", __FUNCTION__);
2723#endif
2724        int min = SkMin32(startIndex, endIndex);
2725        if (fTs[min].fDone) {
2726            return NULL;
2727        }
2728        markDoneBinary(min);
2729        double startT = other->fTs[*nextStart].fT;
2730        *nextEnd = *nextStart;
2731        do {
2732            *nextEnd += step;
2733        } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2734        SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2735        if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2736            *unsortable = true;
2737            return NULL;
2738        }
2739        return other;
2740    }
2741    const int end = nextExactSpan(startIndex, step);
2742    SkASSERT(end >= 0);
2743    SkASSERT(startIndex - endIndex != 0);
2744    SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2745    // more than one viable candidate -- measure angles to find best
2746
2747    int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp);
2748    bool sortable = calcWinding != SK_NaN32;
2749    if (!sortable) {
2750        *unsortable = true;
2751        markDoneBinary(SkMin32(startIndex, endIndex));
2752        return NULL;
2753    }
2754    SkOpAngle* angle = spanToAngle(end, startIndex);
2755    if (angle->unorderable()) {
2756        *unsortable = true;
2757        markDoneBinary(SkMin32(startIndex, endIndex));
2758        return NULL;
2759    }
2760#if DEBUG_SORT
2761    SkDebugf("%s\n", __FUNCTION__);
2762    angle->debugLoop();
2763#endif
2764    int sumMiWinding = updateWinding(endIndex, startIndex);
2765    if (sumMiWinding == SK_MinS32) {
2766        *unsortable = true;
2767        markDoneBinary(SkMin32(startIndex, endIndex));
2768        return NULL;
2769    }
2770    int sumSuWinding = updateOppWinding(endIndex, startIndex);
2771    if (operand()) {
2772        SkTSwap<int>(sumMiWinding, sumSuWinding);
2773    }
2774    SkOpAngle* nextAngle = angle->next();
2775    const SkOpAngle* foundAngle = NULL;
2776    bool foundDone = false;
2777    // iterate through the angle, and compute everyone's winding
2778    SkOpSegment* nextSegment;
2779    int activeCount = 0;
2780    do {
2781        nextSegment = nextAngle->segment();
2782        bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2783                nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
2784        if (activeAngle) {
2785            ++activeCount;
2786            if (!foundAngle || (foundDone && activeCount & 1)) {
2787                if (nextSegment->isTiny(nextAngle)) {
2788                    *unsortable = true;
2789                    markDoneBinary(SkMin32(startIndex, endIndex));
2790                    return NULL;
2791                }
2792                foundAngle = nextAngle;
2793                foundDone = nextSegment->done(nextAngle);
2794            }
2795        }
2796        if (nextSegment->done()) {
2797            continue;
2798        }
2799        if (nextSegment->isTiny(nextAngle)) {
2800            continue;
2801        }
2802        if (!activeAngle) {
2803            (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
2804        }
2805        SkOpSpan* last = nextAngle->lastMarked();
2806        if (last) {
2807            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2808            *chase->append() = last;
2809#if DEBUG_WINDING
2810            SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2811                    last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2812                    last->fSmall);
2813#endif
2814        }
2815    } while ((nextAngle = nextAngle->next()) != angle);
2816#if DEBUG_ANGLE
2817    if (foundAngle) {
2818        foundAngle->debugSameAs(foundAngle);
2819    }
2820#endif
2821
2822    markDoneBinary(SkMin32(startIndex, endIndex));
2823    if (!foundAngle) {
2824        return NULL;
2825    }
2826    *nextStart = foundAngle->start();
2827    *nextEnd = foundAngle->end();
2828    nextSegment = foundAngle->segment();
2829#if DEBUG_WINDING
2830    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2831            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2832 #endif
2833    return nextSegment;
2834}
2835
2836SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
2837                                          int* nextEnd, bool* unsortable) {
2838    const int startIndex = *nextStart;
2839    const int endIndex = *nextEnd;
2840    SkASSERT(startIndex != endIndex);
2841    SkDEBUGCODE(const int count = fTs.count());
2842    SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2843    int step = SkSign32(endIndex - startIndex);
2844    *nextStart = startIndex;
2845    SkOpSegment* other = isSimple(nextStart, &step);
2846    if (other)
2847    {
2848    // mark the smaller of startIndex, endIndex done, and all adjacent
2849    // spans with the same T value (but not 'other' spans)
2850#if DEBUG_WINDING
2851        SkDebugf("%s simple\n", __FUNCTION__);
2852#endif
2853        int min = SkMin32(startIndex, endIndex);
2854        if (fTs[min].fDone) {
2855            return NULL;
2856        }
2857        markDoneUnary(min);
2858        double startT = other->fTs[*nextStart].fT;
2859        *nextEnd = *nextStart;
2860        do {
2861            *nextEnd += step;
2862        } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2863        SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2864        if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2865            *unsortable = true;
2866            return NULL;
2867        }
2868        return other;
2869    }
2870    const int end = nextExactSpan(startIndex, step);
2871    SkASSERT(end >= 0);
2872    SkASSERT(startIndex - endIndex != 0);
2873    SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2874    // more than one viable candidate -- measure angles to find best
2875
2876    int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding);
2877    bool sortable = calcWinding != SK_NaN32;
2878    if (!sortable) {
2879        *unsortable = true;
2880        markDoneUnary(SkMin32(startIndex, endIndex));
2881        return NULL;
2882    }
2883    SkOpAngle* angle = spanToAngle(end, startIndex);
2884#if DEBUG_SORT
2885    SkDebugf("%s\n", __FUNCTION__);
2886    angle->debugLoop();
2887#endif
2888    int sumWinding = updateWinding(endIndex, startIndex);
2889    SkOpAngle* nextAngle = angle->next();
2890    const SkOpAngle* foundAngle = NULL;
2891    bool foundDone = false;
2892    SkOpSegment* nextSegment;
2893    int activeCount = 0;
2894    do {
2895        nextSegment = nextAngle->segment();
2896        bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
2897                &sumWinding);
2898        if (activeAngle) {
2899            ++activeCount;
2900            if (!foundAngle || (foundDone && activeCount & 1)) {
2901                if (nextSegment->isTiny(nextAngle)) {
2902                    *unsortable = true;
2903                    markDoneUnary(SkMin32(startIndex, endIndex));
2904                    return NULL;
2905                }
2906                foundAngle = nextAngle;
2907                foundDone = nextSegment->done(nextAngle);
2908            }
2909        }
2910        if (nextSegment->done()) {
2911            continue;
2912        }
2913        if (nextSegment->isTiny(nextAngle)) {
2914            continue;
2915        }
2916        if (!activeAngle) {
2917            nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
2918        }
2919        SkOpSpan* last = nextAngle->lastMarked();
2920        if (last) {
2921            SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2922            *chase->append() = last;
2923#if DEBUG_WINDING
2924            SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2925                    last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2926                    last->fSmall);
2927#endif
2928        }
2929    } while ((nextAngle = nextAngle->next()) != angle);
2930    markDoneUnary(SkMin32(startIndex, endIndex));
2931    if (!foundAngle) {
2932        return NULL;
2933    }
2934    *nextStart = foundAngle->start();
2935    *nextEnd = foundAngle->end();
2936    nextSegment = foundAngle->segment();
2937#if DEBUG_WINDING
2938    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2939            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2940 #endif
2941    return nextSegment;
2942}
2943
2944SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
2945    const int startIndex = *nextStart;
2946    const int endIndex = *nextEnd;
2947    SkASSERT(startIndex != endIndex);
2948    SkDEBUGCODE(int count = fTs.count());
2949    SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2950    int step = SkSign32(endIndex - startIndex);
2951// Detect cases where all the ends canceled out (e.g.,
2952// there is no angle) and therefore there's only one valid connection
2953    *nextStart = startIndex;
2954    SkOpSegment* other = isSimple(nextStart, &step);
2955    if (other)
2956    {
2957#if DEBUG_WINDING
2958        SkDebugf("%s simple\n", __FUNCTION__);
2959#endif
2960        int min = SkMin32(startIndex, endIndex);
2961        if (fTs[min].fDone) {
2962            return NULL;
2963        }
2964        markDone(min, 1);
2965        double startT = other->fTs[*nextStart].fT;
2966        // FIXME: I don't know why the logic here is difference from the winding case
2967        SkDEBUGCODE(bool firstLoop = true;)
2968        if ((approximately_less_than_zero(startT) && step < 0)
2969                || (approximately_greater_than_one(startT) && step > 0)) {
2970            step = -step;
2971            SkDEBUGCODE(firstLoop = false;)
2972        }
2973        do {
2974            *nextEnd = *nextStart;
2975            do {
2976                *nextEnd += step;
2977            } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2978            if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
2979                break;
2980            }
2981            SkASSERT(firstLoop);
2982            SkDEBUGCODE(firstLoop = false;)
2983            step = -step;
2984        } while (true);
2985        SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2986        return other;
2987    }
2988    SkASSERT(startIndex - endIndex != 0);
2989    SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2990    // parallel block above with presorted version
2991    int end = nextExactSpan(startIndex, step);
2992    SkASSERT(end >= 0);
2993    SkOpAngle* angle = spanToAngle(end, startIndex);
2994    SkASSERT(angle);
2995#if DEBUG_SORT
2996    SkDebugf("%s\n", __FUNCTION__);
2997    angle->debugLoop();
2998#endif
2999    SkOpAngle* nextAngle = angle->next();
3000    const SkOpAngle* foundAngle = NULL;
3001    bool foundDone = false;
3002    SkOpSegment* nextSegment;
3003    int activeCount = 0;
3004    do {
3005        nextSegment = nextAngle->segment();
3006        ++activeCount;
3007        if (!foundAngle || (foundDone && activeCount & 1)) {
3008            if (nextSegment->isTiny(nextAngle)) {
3009                *unsortable = true;
3010                return NULL;
3011            }
3012            foundAngle = nextAngle;
3013            if (!(foundDone = nextSegment->done(nextAngle))) {
3014                break;
3015            }
3016        }
3017        nextAngle = nextAngle->next();
3018    } while (nextAngle != angle);
3019    markDone(SkMin32(startIndex, endIndex), 1);
3020    if (!foundAngle) {
3021        return NULL;
3022    }
3023    *nextStart = foundAngle->start();
3024    *nextEnd = foundAngle->end();
3025    nextSegment = foundAngle->segment();
3026#if DEBUG_WINDING
3027    SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
3028            __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
3029 #endif
3030    return nextSegment;
3031}
3032
3033int SkOpSegment::findStartSpan(int startIndex) const {
3034    int index = startIndex;
3035    const SkOpSpan* span = &fTs[index];
3036    const SkPoint& firstPt = span->fPt;
3037    double firstT = span->fT;
3038    const SkOpSpan* prior;
3039    do {
3040        prior = span;
3041        span = &fTs[++index];
3042    } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt)
3043            && (span->fT == firstT || prior->fTiny));
3044    return index;
3045}
3046
3047int SkOpSegment::findExactT(double t, const SkOpSegment* match) const {
3048    int count = this->count();
3049    for (int index = 0; index < count; ++index) {
3050        const SkOpSpan& span = fTs[index];
3051        if (span.fT == t && span.fOther == match) {
3052            return index;
3053        }
3054    }
3055    SkASSERT(0);
3056    return -1;
3057}
3058
3059int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const {
3060    int count = this->count();
3061    for (int index = 0; index < count; ++index) {
3062        const SkOpSpan& span = fTs[index];
3063        if (span.fOtherT == t && span.fOther == match) {
3064            return index;
3065        }
3066    }
3067    return -1;
3068}
3069
3070int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const {
3071    int count = this->count();
3072    // prefer exact matches over approximate matches
3073    for (int index = 0; index < count; ++index) {
3074        const SkOpSpan& span = fTs[index];
3075        if (span.fT == t && span.fOther == match) {
3076            return index;
3077        }
3078    }
3079    for (int index = 0; index < count; ++index) {
3080        const SkOpSpan& span = fTs[index];
3081        if (approximately_equal_orderable(span.fT, t) && span.fOther == match) {
3082            return index;
3083        }
3084    }
3085    // Usually, the pair of ts are an exact match. It's possible that the t values have
3086    // been adjusted to make multiple intersections align. In this rare case, look for a
3087    // matching point / match pair instead.
3088    for (int index = 0; index < count; ++index) {
3089        const SkOpSpan& span = fTs[index];
3090        if (span.fPt == pt && span.fOther == match) {
3091            return index;
3092        }
3093    }
3094    SkASSERT(0);
3095    return -1;
3096}
3097
3098SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
3099        bool firstPass) {
3100    // iterate through T intersections and return topmost
3101    // topmost tangent from y-min to first pt is closer to horizontal
3102    SkASSERT(!done());
3103    int firstT = -1;
3104    /* SkPoint topPt = */ activeLeftTop(&firstT);
3105    if (firstT < 0) {
3106        *unsortable = !firstPass;
3107        firstT = 0;
3108        while (fTs[firstT].fDone) {
3109            SkASSERT(firstT < fTs.count());
3110            ++firstT;
3111        }
3112        *tIndexPtr = firstT;
3113        *endIndexPtr = nextExactSpan(firstT, 1);
3114        return this;
3115    }
3116    // sort the edges to find the leftmost
3117    int step = 1;
3118    int end;
3119    if (span(firstT).fDone || (end = nextSpan(firstT, step)) == -1) {
3120        step = -1;
3121        end = nextSpan(firstT, step);
3122        SkASSERT(end != -1);
3123    }
3124    // if the topmost T is not on end, or is three-way or more, find left
3125    // look for left-ness from tLeft to firstT (matching y of other)
3126    SkASSERT(firstT - end != 0);
3127    SkOpAngle* markAngle = spanToAngle(firstT, end);
3128    if (!markAngle) {
3129        markAngle = addSingletonAngles(step);
3130    }
3131    markAngle->markStops();
3132    const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle
3133            : markAngle->findFirst();
3134    if (!baseAngle) {
3135        return NULL;  // nothing to do
3136    }
3137    SkScalar top = SK_ScalarMax;
3138    const SkOpAngle* firstAngle = NULL;
3139    const SkOpAngle* angle = baseAngle;
3140    do {
3141        if (!angle->unorderable()) {
3142            SkOpSegment* next = angle->segment();
3143            SkPathOpsBounds bounds;
3144            next->subDivideBounds(angle->end(), angle->start(), &bounds);
3145            if (approximately_greater(top, bounds.fTop)) {
3146                top = bounds.fTop;
3147                firstAngle = angle;
3148            }
3149        }
3150        angle = angle->next();
3151    } while (angle != baseAngle);
3152    SkASSERT(firstAngle);
3153#if DEBUG_SORT
3154    SkDebugf("%s\n", __FUNCTION__);
3155    firstAngle->debugLoop();
3156#endif
3157    // skip edges that have already been processed
3158    angle = firstAngle;
3159    SkOpSegment* leftSegment = NULL;
3160    bool looped = false;
3161    do {
3162        *unsortable = angle->unorderable();
3163        if (firstPass || !*unsortable) {
3164            leftSegment = angle->segment();
3165            *tIndexPtr = angle->end();
3166            *endIndexPtr = angle->start();
3167            if (!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone) {
3168                break;
3169            }
3170        }
3171        angle = angle->next();
3172        looped = true;
3173    } while (angle != firstAngle);
3174    if (angle == firstAngle && looped) {
3175        return NULL;
3176    }
3177    if (leftSegment->verb() >= SkPath::kQuad_Verb) {
3178        const int tIndex = *tIndexPtr;
3179        const int endIndex = *endIndexPtr;
3180        bool swap;
3181        if (!leftSegment->clockwise(tIndex, endIndex, &swap)) {
3182    #if DEBUG_SWAP_TOP
3183            SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n",
3184                    __FUNCTION__,
3185                    swap, leftSegment->debugInflections(tIndex, endIndex),
3186                    leftSegment->serpentine(tIndex, endIndex),
3187                    leftSegment->controlsContainedByEnds(tIndex, endIndex),
3188                    leftSegment->monotonicInY(tIndex, endIndex));
3189    #endif
3190            if (swap) {
3191    // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
3192    // sorted but merely the first not already processed (i.e., not done)
3193                SkTSwap(*tIndexPtr, *endIndexPtr);
3194            }
3195        }
3196    }
3197    SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
3198    return leftSegment;
3199}
3200
3201int SkOpSegment::firstActive(int tIndex) const {
3202    while (fTs[tIndex].fTiny) {
3203        SkASSERT(!isCanceled(tIndex));
3204        ++tIndex;
3205    }
3206    return tIndex;
3207}
3208
3209// FIXME: not crazy about this
3210// when the intersections are performed, the other index is into an
3211// incomplete array. As the array grows, the indices become incorrect
3212// while the following fixes the indices up again, it isn't smart about
3213// skipping segments whose indices are already correct
3214// assuming we leave the code that wrote the index in the first place
3215// FIXME: if called after remove, this needs to correct tiny
3216void SkOpSegment::fixOtherTIndex() {
3217    int iCount = fTs.count();
3218    for (int i = 0; i < iCount; ++i) {
3219        SkOpSpan& iSpan = fTs[i];
3220        double oT = iSpan.fOtherT;
3221        SkOpSegment* other = iSpan.fOther;
3222        int oCount = other->fTs.count();
3223        SkDEBUGCODE(iSpan.fOtherIndex = -1);
3224        for (int o = 0; o < oCount; ++o) {
3225            SkOpSpan& oSpan = other->fTs[o];
3226            if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
3227                iSpan.fOtherIndex = o;
3228                oSpan.fOtherIndex = i;
3229                break;
3230            }
3231        }
3232        SkASSERT(iSpan.fOtherIndex >= 0);
3233    }
3234}
3235
3236bool SkOpSegment::inCoincidentSpan(double t, const SkOpSegment* other) const {
3237    int foundEnds = 0;
3238    int count = this->count();
3239    for (int index = 0; index < count; ++index) {
3240        const SkOpSpan& span = this->span(index);
3241        if (span.fCoincident) {
3242            foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.fT));
3243        }
3244    }
3245    SkASSERT(foundEnds != 7);
3246    return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6;  // two bits set
3247}
3248
3249void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
3250    fDoneSpans = 0;
3251    fOperand = operand;
3252    fXor = evenOdd;
3253    fPts = pts;
3254    fVerb = verb;
3255    fLoop = fMultiples = fSmall = fTiny = false;
3256}
3257
3258void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) {
3259    int local = spanSign(start, end);
3260    if (angleIncludeType == SkOpAngle::kBinarySingle) {
3261        int oppLocal = oppSign(start, end);
3262        (void) markAndChaseWinding(start, end, local, oppLocal);
3263    // OPTIMIZATION: the reverse mark and chase could skip the first marking
3264        (void) markAndChaseWinding(end, start, local, oppLocal);
3265    } else {
3266        (void) markAndChaseWinding(start, end, local);
3267    // OPTIMIZATION: the reverse mark and chase could skip the first marking
3268        (void) markAndChaseWinding(end, start, local);
3269    }
3270}
3271
3272/*
3273when we start with a vertical intersect, we try to use the dx to determine if the edge is to
3274the left or the right of vertical. This determines if we need to add the span's
3275sign or not. However, this isn't enough.
3276If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
3277If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
3278from has the same x direction as this span, the winding should change. If the dx is opposite, then
3279the same winding is shared by both.
3280*/
3281void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
3282                              int oppWind, SkScalar hitOppDx) {
3283    SkASSERT(hitDx || !winding);
3284    SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
3285    SkASSERT(dx);
3286    int windVal = windValue(SkMin32(start, end));
3287#if DEBUG_WINDING_AT_T
3288    SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding,
3289            hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3290#endif
3291    int sideWind = winding + (dx < 0 ? windVal : -windVal);
3292    if (abs(winding) < abs(sideWind)) {
3293        winding = sideWind;
3294    }
3295    SkDEBUGCODE(int oppLocal = oppSign(start, end));
3296    SkASSERT(hitOppDx || !oppWind || !oppLocal);
3297    int oppWindVal = oppValue(SkMin32(start, end));
3298    if (!oppWind) {
3299        oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3300    } else if (hitOppDx * dx >= 0) {
3301        int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3302        if (abs(oppWind) < abs(oppSideWind)) {
3303            oppWind = oppSideWind;
3304        }
3305    }
3306#if DEBUG_WINDING_AT_T
3307    SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind);
3308#endif
3309    (void) markAndChaseWinding(start, end, winding, oppWind);
3310    // OPTIMIZATION: the reverse mark and chase could skip the first marking
3311    (void) markAndChaseWinding(end, start, winding, oppWind);
3312}
3313
3314bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const {
3315    if (!baseAngle->inLoop()) {
3316        return false;
3317    }
3318    int index = *indexPtr;
3319    SkOpAngle* from = fTs[index].fFromAngle;
3320    SkOpAngle* to = fTs[index].fToAngle;
3321    while (++index < spanCount) {
3322        SkOpAngle* nextFrom = fTs[index].fFromAngle;
3323        SkOpAngle* nextTo = fTs[index].fToAngle;
3324        if (from != nextFrom || to != nextTo) {
3325            break;
3326        }
3327    }
3328    *indexPtr = index;
3329    return true;
3330}
3331
3332// OPTIMIZE: successive calls could start were the last leaves off
3333// or calls could specialize to walk forwards or backwards
3334bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
3335    int tCount = fTs.count();
3336    for (int index = 0; index < tCount; ++index) {
3337        const SkOpSpan& span = fTs[index];
3338        if (approximately_zero(startT - span.fT) && pt == span.fPt) {
3339            return false;
3340        }
3341    }
3342    return true;
3343}
3344
3345
3346SkOpSegment* SkOpSegment::isSimple(int* end, int* step) {
3347    return nextChase(end, step, NULL, NULL);
3348}
3349
3350bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
3351    int start = angle->start();
3352    int end = angle->end();
3353    const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
3354    return mSpan.fTiny;
3355}
3356
3357bool SkOpSegment::isTiny(int index) const {
3358    return fTs[index].fTiny;
3359}
3360
3361// look pair of active edges going away from coincident edge
3362// one of them should be the continuation of other
3363// if both are active, look to see if they both the connect to another coincident pair
3364// if at least one is a line, then make the pair coincident
3365// if neither is a line, test for coincidence
3366bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt,
3367        int step, bool cancel) {
3368    int otherTIndex = other->findT(otherT, otherPt, this);
3369    int next = other->nextExactSpan(otherTIndex, step);
3370    int otherMin = SkMin32(otherTIndex, next);
3371    int otherWind = other->span(otherMin).fWindValue;
3372    if (otherWind == 0) {
3373        return false;
3374    }
3375    SkASSERT(next >= 0);
3376    int tIndex = 0;
3377    do {
3378        SkOpSpan* test = &fTs[tIndex];
3379        SkASSERT(test->fT == 0);
3380        if (test->fOther == other || test->fOtherT != 1) {
3381            continue;
3382        }
3383        SkPoint startPt, endPt;
3384        double endT;
3385        if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
3386            SkOpSegment* match = test->fOther;
3387            if (cancel) {
3388                match->addTCancel(startPt, endPt, other);
3389            } else {
3390                match->addTCoincident(startPt, endPt, endT, other);
3391            }
3392            return true;
3393        }
3394    } while (fTs[++tIndex].fT == 0);
3395    return false;
3396}
3397
3398// this span is excluded by the winding rule -- chase the ends
3399// as long as they are unambiguous to mark connections as done
3400// and give them the same winding value
3401
3402SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
3403    int step = SkSign32(endIndex - index);
3404    int min = SkMin32(index, endIndex);
3405    markDoneBinary(min);
3406    SkOpSpan* last = NULL;
3407    SkOpSegment* other = this;
3408    while ((other = other->nextChase(&index, &step, &min, &last))) {
3409        if (other->done()) {
3410            SkASSERT(!last);
3411            break;
3412        }
3413        other->markDoneBinary(min);
3414    }
3415    return last;
3416}
3417
3418SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
3419    int step = SkSign32(endIndex - index);
3420    int min = SkMin32(index, endIndex);
3421    markDoneUnary(min);
3422    SkOpSpan* last = NULL;
3423    SkOpSegment* other = this;
3424    while ((other = other->nextChase(&index, &step, &min, &last))) {
3425        if (other->done()) {
3426            SkASSERT(!last);
3427            break;
3428        }
3429        other->markDoneUnary(min);
3430    }
3431    return last;
3432}
3433
3434SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) {
3435    int index = angle->start();
3436    int endIndex = angle->end();
3437    int step = SkSign32(endIndex - index);
3438    int min = SkMin32(index, endIndex);
3439    markWinding(min, winding);
3440    SkOpSpan* last = NULL;
3441    SkOpSegment* other = this;
3442    while ((other = other->nextChase(&index, &step, &min, &last))) {
3443        if (other->fTs[min].fWindSum != SK_MinS32) {
3444//            SkASSERT(other->fTs[min].fWindSum == winding);
3445            SkASSERT(!last);
3446            break;
3447        }
3448        other->markWinding(min, winding);
3449    }
3450    return last;
3451}
3452
3453SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) {
3454    int min = SkMin32(index, endIndex);
3455    int step = SkSign32(endIndex - index);
3456    markWinding(min, winding);
3457    SkOpSpan* last = NULL;
3458    SkOpSegment* other = this;
3459    while ((other = other->nextChase(&index, &step, &min, &last))) {
3460        if (other->fTs[min].fWindSum != SK_MinS32) {
3461            SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
3462            SkASSERT(!last);
3463            break;
3464        }
3465        other->markWinding(min, winding);
3466    }
3467    return last;
3468}
3469
3470SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3471    int min = SkMin32(index, endIndex);
3472    int step = SkSign32(endIndex - index);
3473    markWinding(min, winding, oppWinding);
3474    SkOpSpan* last = NULL;
3475    SkOpSegment* other = this;
3476    while ((other = other->nextChase(&index, &step, &min, &last))) {
3477        if (other->fTs[min].fWindSum != SK_MinS32) {
3478#ifdef SK_DEBUG
3479            if (!other->fTs[min].fLoop) {
3480                if (fOperand == other->fOperand) {
3481// FIXME: this is probably a bug -- rects4 asserts here
3482//                    SkASSERT(other->fTs[min].fWindSum == winding);
3483// FIXME: this is probably a bug -- rects3 asserts here
3484//                    SkASSERT(other->fTs[min].fOppSum == oppWinding);
3485                } else {
3486                    SkASSERT(other->fTs[min].fWindSum == oppWinding);
3487// FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
3488//                    SkASSERT(other->fTs[min].fOppSum == winding);
3489                }
3490            }
3491            SkASSERT(!last);
3492#endif
3493            break;
3494        }
3495        if (fOperand == other->fOperand) {
3496            other->markWinding(min, winding, oppWinding);
3497        } else {
3498            other->markWinding(min, oppWinding, winding);
3499        }
3500    }
3501    return last;
3502}
3503
3504SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
3505    int start = angle->start();
3506    int end = angle->end();
3507    return markAndChaseWinding(start, end, winding, oppWinding);
3508}
3509
3510SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
3511    SkASSERT(angle->segment() == this);
3512    if (UseInnerWinding(maxWinding, sumWinding)) {
3513        maxWinding = sumWinding;
3514    }
3515    SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
3516#if DEBUG_WINDING
3517    if (last) {
3518        SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3519                last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3520        SkPathOpsDebug::WindingPrintf(last->fWindSum);
3521        SkDebugf(" small=%d\n", last->fSmall);
3522    }
3523#endif
3524    return last;
3525}
3526
3527SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
3528                                 int oppSumWinding, const SkOpAngle* angle) {
3529    SkASSERT(angle->segment() == this);
3530    if (UseInnerWinding(maxWinding, sumWinding)) {
3531        maxWinding = sumWinding;
3532    }
3533    if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
3534        oppMaxWinding = oppSumWinding;
3535    }
3536    SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3537#if DEBUG_WINDING
3538    if (last) {
3539        SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3540                last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3541        SkPathOpsDebug::WindingPrintf(last->fWindSum);
3542        SkDebugf(" small=%d\n", last->fSmall);
3543    }
3544#endif
3545    return last;
3546}
3547
3548// FIXME: this should also mark spans with equal (x,y)
3549// This may be called when the segment is already marked done. While this
3550// wastes time, it shouldn't do any more than spin through the T spans.
3551// OPTIMIZATION: abort on first done found (assuming that this code is
3552// always called to mark segments done).
3553void SkOpSegment::markDone(int index, int winding) {
3554  //  SkASSERT(!done());
3555    SkASSERT(winding);
3556    double referenceT = fTs[index].fT;
3557    int lesser = index;
3558    while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3559        markOneDone(__FUNCTION__, lesser, winding);
3560    }
3561    do {
3562        markOneDone(__FUNCTION__, index, winding);
3563    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3564    debugValidate();
3565}
3566
3567void SkOpSegment::markDoneBinary(int index) {
3568    double referenceT = fTs[index].fT;
3569    int lesser = index;
3570    while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3571        markOneDoneBinary(__FUNCTION__, lesser);
3572    }
3573    do {
3574        markOneDoneBinary(__FUNCTION__, index);
3575    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3576    debugValidate();
3577}
3578
3579void SkOpSegment::markDoneUnary(int index) {
3580    double referenceT = fTs[index].fT;
3581    int lesser = index;
3582    while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3583        markOneDoneUnary(__FUNCTION__, lesser);
3584    }
3585    do {
3586        markOneDoneUnary(__FUNCTION__, index);
3587    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3588    debugValidate();
3589}
3590
3591void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
3592    SkOpSpan* span = markOneWinding(funName, tIndex, winding);
3593    if (!span || span->fDone) {
3594        return;
3595    }
3596    span->fDone = true;
3597    fDoneSpans++;
3598}
3599
3600void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
3601    SkOpSpan* span = verifyOneWinding(funName, tIndex);
3602    if (!span) {
3603        return;
3604    }
3605    SkASSERT(!span->fDone);
3606    span->fDone = true;
3607    fDoneSpans++;
3608}
3609
3610void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
3611    SkOpSpan* span = verifyOneWindingU(funName, tIndex);
3612    if (!span) {
3613        return;
3614    }
3615    if (span->fWindSum == SK_MinS32) {
3616        SkDebugf("%s uncomputed\n", __FUNCTION__);
3617    }
3618    SkASSERT(!span->fDone);
3619    span->fDone = true;
3620    fDoneSpans++;
3621}
3622
3623SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
3624    SkOpSpan& span = fTs[tIndex];
3625    if (span.fDone && !span.fSmall) {
3626        return NULL;
3627    }
3628#if DEBUG_MARK_DONE
3629    debugShowNewWinding(funName, span, winding);
3630#endif
3631    SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3632#if DEBUG_LIMIT_WIND_SUM
3633    SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3634#endif
3635    span.fWindSum = winding;
3636    return &span;
3637}
3638
3639SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
3640                                      int oppWinding) {
3641    SkOpSpan& span = fTs[tIndex];
3642    if (span.fDone && !span.fSmall) {
3643        return NULL;
3644    }
3645#if DEBUG_MARK_DONE
3646    debugShowNewWinding(funName, span, winding, oppWinding);
3647#endif
3648    SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3649#if DEBUG_LIMIT_WIND_SUM
3650    SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3651#endif
3652    span.fWindSum = winding;
3653    SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
3654#if DEBUG_LIMIT_WIND_SUM
3655    SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
3656#endif
3657    span.fOppSum = oppWinding;
3658    debugValidate();
3659    return &span;
3660}
3661
3662// from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
3663bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const {
3664    SkASSERT(fVerb != SkPath::kLine_Verb);
3665    SkPoint edge[4];
3666    subDivide(tStart, tEnd, edge);
3667    int points = SkPathOpsVerbToPoints(fVerb);
3668    double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
3669    bool sumSet = false;
3670    if (fVerb == SkPath::kCubic_Verb) {
3671        SkDCubic cubic;
3672        cubic.set(edge);
3673        double inflectionTs[2];
3674        int inflections = cubic.findInflections(inflectionTs);
3675        // FIXME: this fixes cubicOp114 and breaks cubicOp58d
3676        // the trouble is that cubics with inflections confuse whether the curve breaks towards
3677        // or away, which in turn is used to determine if it is on the far right or left.
3678        // Probably a totally different approach is in order. At one time I tried to project a
3679        // horizontal ray to determine winding, but was confused by how to map the vertically
3680        // oriented winding computation over.
3681        if (0 && inflections) {
3682            double tLo = this->span(tStart).fT;
3683            double tHi = this->span(tEnd).fT;
3684            double tLoStart = tLo;
3685            for (int index = 0; index < inflections; ++index) {
3686                if (between(tLo, inflectionTs[index], tHi)) {
3687                    tLo = inflectionTs[index];
3688                }
3689            }
3690            if (tLo != tLoStart && tLo != tHi) {
3691                SkDPoint sub[2];
3692                sub[0] = cubic.ptAtT(tLo);
3693                sub[1].set(edge[3]);
3694                SkDPoint ctrl[2];
3695                SkDCubic::SubDivide(fPts, sub[0], sub[1], tLo, tHi, ctrl);
3696                edge[0] = sub[0].asSkPoint();
3697                edge[1] = ctrl[0].asSkPoint();
3698                edge[2] = ctrl[1].asSkPoint();
3699                sum = (edge[0].fX - edge[3].fX) * (edge[0].fY + edge[3].fY);
3700            }
3701        }
3702        SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
3703        if (edge[1].fY < lesser && edge[2].fY < lesser) {
3704            SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
3705            SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
3706            if (SkIntersections::Test(tangent1, tangent2)) {
3707                SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3708                sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
3709                sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
3710                sumSet = true;
3711            }
3712        }
3713    }
3714    if (!sumSet) {
3715        for (int idx = 0; idx < points; ++idx){
3716            sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
3717        }
3718    }
3719    if (fVerb == SkPath::kCubic_Verb) {
3720        SkDCubic cubic;
3721        cubic.set(edge);
3722         *swap = sum > 0 && !cubic.monotonicInY() && !cubic.serpentine();
3723    } else {
3724        SkDQuad quad;
3725        quad.set(edge);
3726        *swap = sum > 0 && !quad.monotonicInY();
3727    }
3728    return sum <= 0;
3729}
3730
3731bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
3732    SkASSERT(fVerb != SkPath::kLine_Verb);
3733    if (fVerb == SkPath::kQuad_Verb) {
3734        SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3735        return dst.monotonicInY();
3736    }
3737    SkASSERT(fVerb == SkPath::kCubic_Verb);
3738    SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3739    return dst.monotonicInY();
3740}
3741
3742bool SkOpSegment::serpentine(int tStart, int tEnd) const {
3743    if (fVerb != SkPath::kCubic_Verb) {
3744        return false;
3745    }
3746    SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3747    return dst.serpentine();
3748}
3749
3750SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
3751    SkOpSpan& span = fTs[tIndex];
3752    if (span.fDone) {
3753        return NULL;
3754    }
3755#if DEBUG_MARK_DONE
3756    debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
3757#endif
3758// If the prior angle in the sort is unorderable, the winding sum may not be computable.
3759// To enable the assert, the 'prior is unorderable' state could be
3760// piped down to this test, but not sure it's worth it.
3761// (Once the sort order is stored in the span, this test may be feasible.)
3762//    SkASSERT(span.fWindSum != SK_MinS32);
3763//    SkASSERT(span.fOppSum != SK_MinS32);
3764    return &span;
3765}
3766
3767SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
3768    SkOpSpan& span = fTs[tIndex];
3769    if (span.fDone) {
3770        return NULL;
3771    }
3772#if DEBUG_MARK_DONE
3773    debugShowNewWinding(funName, span, span.fWindSum);
3774#endif
3775// If the prior angle in the sort is unorderable, the winding sum may not be computable.
3776// To enable the assert, the 'prior is unorderable' state could be
3777// piped down to this test, but not sure it's worth it.
3778// (Once the sort order is stored in the span, this test may be feasible.)
3779//    SkASSERT(span.fWindSum != SK_MinS32);
3780    return &span;
3781}
3782
3783void SkOpSegment::markWinding(int index, int winding) {
3784//    SkASSERT(!done());
3785    SkASSERT(winding);
3786    double referenceT = fTs[index].fT;
3787    int lesser = index;
3788    while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3789        markOneWinding(__FUNCTION__, lesser, winding);
3790    }
3791    do {
3792        markOneWinding(__FUNCTION__, index, winding);
3793   } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3794    debugValidate();
3795}
3796
3797void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
3798//    SkASSERT(!done());
3799    SkASSERT(winding || oppWinding);
3800    double referenceT = fTs[index].fT;
3801    int lesser = index;
3802    while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3803        markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3804    }
3805    do {
3806        markOneWinding(__FUNCTION__, index, winding, oppWinding);
3807   } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3808    debugValidate();
3809}
3810
3811void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
3812    int nextDoorWind = SK_MaxS32;
3813    int nextOppWind = SK_MaxS32;
3814    // prefer exact matches
3815    if (tIndex > 0) {
3816        const SkOpSpan& below = fTs[tIndex - 1];
3817        if (below.fT == t) {
3818            nextDoorWind = below.fWindValue;
3819            nextOppWind = below.fOppValue;
3820        }
3821    }
3822    if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3823        const SkOpSpan& above = fTs[tIndex + 1];
3824        if (above.fT == t) {
3825            nextDoorWind = above.fWindValue;
3826            nextOppWind = above.fOppValue;
3827        }
3828    }
3829    if (nextDoorWind == SK_MaxS32 && tIndex > 0) {
3830        const SkOpSpan& below = fTs[tIndex - 1];
3831        if (approximately_negative(t - below.fT)) {
3832            nextDoorWind = below.fWindValue;
3833            nextOppWind = below.fOppValue;
3834        }
3835    }
3836    if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3837        const SkOpSpan& above = fTs[tIndex + 1];
3838        if (approximately_negative(above.fT - t)) {
3839            nextDoorWind = above.fWindValue;
3840            nextOppWind = above.fOppValue;
3841        }
3842    }
3843    if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3844        const SkOpSpan& below = fTs[tIndex - 1];
3845        nextDoorWind = below.fWindValue;
3846        nextOppWind = below.fOppValue;
3847    }
3848    if (nextDoorWind != SK_MaxS32) {
3849        SkOpSpan& newSpan = fTs[tIndex];
3850        newSpan.fWindValue = nextDoorWind;
3851        newSpan.fOppValue = nextOppWind;
3852        if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3853            newSpan.fDone = true;
3854            ++fDoneSpans;
3855        }
3856    }
3857}
3858
3859bool SkOpSegment::nextCandidate(int* start, int* end) const {
3860    while (fTs[*end].fDone) {
3861        if (fTs[*end].fT == 1) {
3862            return false;
3863        }
3864        ++(*end);
3865    }
3866    *start = *end;
3867    *end = nextExactSpan(*start, 1);
3868    return true;
3869}
3870
3871static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) {
3872    if (last && !endSpan->fSmall) {
3873        *last = endSpan;
3874    }
3875    return NULL;
3876}
3877
3878SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, SkOpSpan** last) {
3879    int origIndex = *indexPtr;
3880    int step = *stepPtr;
3881    int end = nextExactSpan(origIndex, step);
3882    SkASSERT(end >= 0);
3883    SkOpSpan& endSpan = fTs[end];
3884    SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
3885    int foundIndex;
3886    int otherEnd;
3887    SkOpSegment* other;
3888    if (angle == NULL) {
3889        if (endSpan.fT != 0 && endSpan.fT != 1) {
3890            return NULL;
3891        }
3892        other = endSpan.fOther;
3893        foundIndex = endSpan.fOtherIndex;
3894        otherEnd = other->nextExactSpan(foundIndex, step);
3895    } else {
3896        int loopCount = angle->loopCount();
3897        if (loopCount > 2) {
3898            return set_last(last, &endSpan);
3899        }
3900        const SkOpAngle* next = angle->next();
3901        if (angle->sign() != next->sign()) {
3902#if DEBUG_WINDING
3903            SkDebugf("%s mismatched signs\n", __FUNCTION__);
3904#endif
3905        //    return set_last(last, &endSpan);
3906        }
3907        other = next->segment();
3908        foundIndex = end = next->start();
3909        otherEnd = next->end();
3910    }
3911    int foundStep = foundIndex < otherEnd ? 1 : -1;
3912    if (*stepPtr != foundStep) {
3913        return set_last(last, &endSpan);
3914    }
3915    SkASSERT(*indexPtr >= 0);
3916    SkASSERT(otherEnd >= 0);
3917#if 1
3918    int origMin = origIndex + (step < 0 ? step : 0);
3919    const SkOpSpan& orig = this->span(origMin);
3920#endif
3921    int foundMin = SkMin32(foundIndex, otherEnd);
3922#if 1
3923    const SkOpSpan& found = other->span(foundMin);
3924    if (found.fWindValue != orig.fWindValue || found.fOppValue != orig.fOppValue) {
3925          return set_last(last, &endSpan);
3926    }
3927#endif
3928    *indexPtr = foundIndex;
3929    *stepPtr = foundStep;
3930    if (minPtr) {
3931        *minPtr = foundMin;
3932    }
3933    return other;
3934}
3935
3936// This has callers for two different situations: one establishes the end
3937// of the current span, and one establishes the beginning of the next span
3938// (thus the name). When this is looking for the end of the current span,
3939// coincidence is found when the beginning Ts contain -step and the end
3940// contains step. When it is looking for the beginning of the next, the
3941// first Ts found can be ignored and the last Ts should contain -step.
3942// OPTIMIZATION: probably should split into two functions
3943int SkOpSegment::nextSpan(int from, int step) const {
3944    const SkOpSpan& fromSpan = fTs[from];
3945    int count = fTs.count();
3946    int to = from;
3947    while (step > 0 ? ++to < count : --to >= 0) {
3948        const SkOpSpan& span = fTs[to];
3949        if (approximately_zero(span.fT - fromSpan.fT)) {
3950            continue;
3951        }
3952        return to;
3953    }
3954    return -1;
3955}
3956
3957// FIXME
3958// this returns at any difference in T, vs. a preset minimum. It may be
3959// that all callers to nextSpan should use this instead.
3960int SkOpSegment::nextExactSpan(int from, int step) const {
3961    int to = from;
3962    if (step < 0) {
3963        const SkOpSpan& fromSpan = fTs[from];
3964        while (--to >= 0) {
3965            const SkOpSpan& span = fTs[to];
3966            if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
3967                continue;
3968            }
3969            return to;
3970        }
3971    } else {
3972        while (fTs[from].fTiny) {
3973            from++;
3974        }
3975        const SkOpSpan& fromSpan = fTs[from];
3976        int count = fTs.count();
3977        while (++to < count) {
3978            const SkOpSpan& span = fTs[to];
3979            if (precisely_negative(span.fT - fromSpan.fT)) {
3980                continue;
3981            }
3982            return to;
3983        }
3984    }
3985    return -1;
3986}
3987
3988void SkOpSegment::pinT(const SkPoint& pt, double* t) {
3989    if (pt == fPts[0]) {
3990        *t = 0;
3991    }
3992    int count = SkPathOpsVerbToPoints(fVerb);
3993    if (pt == fPts[count]) {
3994        *t = 1;
3995    }
3996}
3997
3998bool SkOpSegment::reversePoints(const SkPoint& p1, const SkPoint& p2) const {
3999    SkASSERT(p1 != p2);
4000    int spanCount = count();
4001    int p1IndexMin = -1;
4002    int p2IndexMax = spanCount;
4003    for (int index = 0; index < spanCount; ++index) {
4004        const SkOpSpan& span = fTs[index];
4005        if (span.fPt == p1) {
4006            if (p1IndexMin < 0) {
4007                p1IndexMin = index;
4008            }
4009        } else if (span.fPt == p2) {
4010            p2IndexMax = index;
4011        }
4012    }
4013    return p1IndexMin > p2IndexMax;
4014}
4015
4016void SkOpSegment::setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt,
4017        SkOpSegment* other) {
4018    int count = this->count();
4019    for (int index = 0; index < count; ++index) {
4020        SkOpSpan &span = fTs[index];
4021        if ((startPt == span.fPt || endPt == span.fPt) && other == span.fOther) {
4022            span.fCoincident = true;
4023        }
4024    }
4025}
4026
4027void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
4028        int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
4029    int deltaSum = spanSign(index, endIndex);
4030    int oppDeltaSum = oppSign(index, endIndex);
4031    if (operand()) {
4032        *maxWinding = *sumSuWinding;
4033        *sumWinding = *sumSuWinding -= deltaSum;
4034        *oppMaxWinding = *sumMiWinding;
4035        *oppSumWinding = *sumMiWinding -= oppDeltaSum;
4036    } else {
4037        *maxWinding = *sumMiWinding;
4038        *sumWinding = *sumMiWinding -= deltaSum;
4039        *oppMaxWinding = *sumSuWinding;
4040        *oppSumWinding = *sumSuWinding -= oppDeltaSum;
4041    }
4042#if DEBUG_LIMIT_WIND_SUM
4043    SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4044    SkASSERT(abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
4045#endif
4046}
4047
4048void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
4049        int* maxWinding, int* sumWinding) {
4050    int deltaSum = spanSign(index, endIndex);
4051    *maxWinding = *sumMiWinding;
4052    *sumWinding = *sumMiWinding -= deltaSum;
4053#if DEBUG_LIMIT_WIND_SUM
4054    SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4055#endif
4056}
4057
4058void SkOpSegment::sortAngles() {
4059    int spanCount = fTs.count();
4060    if (spanCount <= 2) {
4061        return;
4062    }
4063    int index = 0;
4064    do {
4065        SkOpAngle* fromAngle = fTs[index].fFromAngle;
4066        SkOpAngle* toAngle = fTs[index].fToAngle;
4067        if (!fromAngle && !toAngle) {
4068            index += 1;
4069            continue;
4070        }
4071        SkOpAngle* baseAngle = NULL;
4072        if (fromAngle) {
4073            baseAngle = fromAngle;
4074            if (inLoop(baseAngle, spanCount, &index)) {
4075                continue;
4076            }
4077        }
4078#if DEBUG_ANGLE
4079        bool wroteAfterHeader = false;
4080#endif
4081        if (toAngle) {
4082            if (!baseAngle) {
4083                baseAngle = toAngle;
4084                if (inLoop(baseAngle, spanCount, &index)) {
4085                    continue;
4086                }
4087            } else {
4088                SkDEBUGCODE(int newIndex = index);
4089                SkASSERT(!inLoop(baseAngle, spanCount, &newIndex) && newIndex == index);
4090#if DEBUG_ANGLE
4091                SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4092                        index);
4093                wroteAfterHeader = true;
4094#endif
4095                baseAngle->insert(toAngle);
4096            }
4097        }
4098        SkOpAngle* nextFrom, * nextTo;
4099        int firstIndex = index;
4100        do {
4101            SkOpSpan& span = fTs[index];
4102            SkOpSegment* other = span.fOther;
4103            SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
4104            SkOpAngle* oAngle = oSpan.fFromAngle;
4105            if (oAngle) {
4106#if DEBUG_ANGLE
4107                if (!wroteAfterHeader) {
4108                    SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4109                            index);
4110                    wroteAfterHeader = true;
4111                }
4112#endif
4113                if (!oAngle->loopContains(*baseAngle)) {
4114                    baseAngle->insert(oAngle);
4115                }
4116            }
4117            oAngle = oSpan.fToAngle;
4118            if (oAngle) {
4119#if DEBUG_ANGLE
4120                if (!wroteAfterHeader) {
4121                    SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4122                            index);
4123                    wroteAfterHeader = true;
4124                }
4125#endif
4126                if (!oAngle->loopContains(*baseAngle)) {
4127                    baseAngle->insert(oAngle);
4128                }
4129            }
4130            if (++index == spanCount) {
4131                break;
4132            }
4133            nextFrom = fTs[index].fFromAngle;
4134            nextTo = fTs[index].fToAngle;
4135        } while (fromAngle == nextFrom && toAngle == nextTo);
4136        if (baseAngle && baseAngle->loopCount() == 1) {
4137            index = firstIndex;
4138            do {
4139                SkOpSpan& span = fTs[index];
4140                span.fFromAngle = span.fToAngle = NULL;
4141                if (++index == spanCount) {
4142                    break;
4143                }
4144                nextFrom = fTs[index].fFromAngle;
4145                nextTo = fTs[index].fToAngle;
4146            } while (fromAngle == nextFrom && toAngle == nextTo);
4147            baseAngle = NULL;
4148        }
4149#if DEBUG_SORT
4150        SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
4151#endif
4152    } while (index < spanCount);
4153}
4154
4155// return true if midpoints were computed
4156bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
4157    SkASSERT(start != end);
4158    edge[0] = fTs[start].fPt;
4159    int points = SkPathOpsVerbToPoints(fVerb);
4160    edge[points] = fTs[end].fPt;
4161    if (fVerb == SkPath::kLine_Verb) {
4162        return false;
4163    }
4164    double startT = fTs[start].fT;
4165    double endT = fTs[end].fT;
4166    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4167        // don't compute midpoints if we already have them
4168        if (fVerb == SkPath::kQuad_Verb) {
4169            edge[1] = fPts[1];
4170            return false;
4171        }
4172        SkASSERT(fVerb == SkPath::kCubic_Verb);
4173        if (start < end) {
4174            edge[1] = fPts[1];
4175            edge[2] = fPts[2];
4176            return false;
4177        }
4178        edge[1] = fPts[2];
4179        edge[2] = fPts[1];
4180        return false;
4181    }
4182    const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
4183    if (fVerb == SkPath::kQuad_Verb) {
4184        edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
4185    } else {
4186        SkASSERT(fVerb == SkPath::kCubic_Verb);
4187        SkDPoint ctrl[2];
4188        SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
4189        edge[1] = ctrl[0].asSkPoint();
4190        edge[2] = ctrl[1].asSkPoint();
4191    }
4192    return true;
4193}
4194
4195// return true if midpoints were computed
4196bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
4197    SkASSERT(start != end);
4198    (*result)[0].set(fTs[start].fPt);
4199    int points = SkPathOpsVerbToPoints(fVerb);
4200    (*result)[points].set(fTs[end].fPt);
4201    if (fVerb == SkPath::kLine_Verb) {
4202        return false;
4203    }
4204    double startT = fTs[start].fT;
4205    double endT = fTs[end].fT;
4206    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4207        // don't compute midpoints if we already have them
4208        if (fVerb == SkPath::kQuad_Verb) {
4209            (*result)[1].set(fPts[1]);
4210            return false;
4211        }
4212        SkASSERT(fVerb == SkPath::kCubic_Verb);
4213        if (start < end) {
4214            (*result)[1].set(fPts[1]);
4215            (*result)[2].set(fPts[2]);
4216            return false;
4217        }
4218        (*result)[1].set(fPts[2]);
4219        (*result)[2].set(fPts[1]);
4220        return false;
4221    }
4222    if (fVerb == SkPath::kQuad_Verb) {
4223        (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
4224    } else {
4225        SkASSERT(fVerb == SkPath::kCubic_Verb);
4226        SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
4227    }
4228    return true;
4229}
4230
4231void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
4232    SkPoint edge[4];
4233    subDivide(start, end, edge);
4234    (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
4235}
4236
4237void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
4238        const SkPoint& startPt) {
4239    int outCount = outsidePts->count();
4240    if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
4241        outsidePts->push_back(endPt);
4242        outsidePts->push_back(startPt);
4243    }
4244}
4245
4246void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
4247    int outCount = outsidePts->count();
4248    if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
4249        outsidePts->push_back(startPt);
4250    }
4251}
4252
4253void SkOpSegment::undoneSpan(int* start, int* end) {
4254    int tCount = fTs.count();
4255    int index;
4256    for (index = 0; index < tCount; ++index) {
4257        if (!fTs[index].fDone) {
4258            break;
4259        }
4260    }
4261    SkASSERT(index < tCount - 1);
4262    *start = index;
4263    double startT = fTs[index].fT;
4264    while (approximately_negative(fTs[++index].fT - startT))
4265        SkASSERT(index < tCount);
4266    SkASSERT(index < tCount);
4267    *end = index;
4268}
4269
4270int SkOpSegment::updateOppWinding(int index, int endIndex) const {
4271    int lesser = SkMin32(index, endIndex);
4272    int oppWinding = oppSum(lesser);
4273    int oppSpanWinding = oppSign(index, endIndex);
4274    if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
4275            && oppWinding != SK_MaxS32) {
4276        oppWinding -= oppSpanWinding;
4277    }
4278    return oppWinding;
4279}
4280
4281int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
4282    int startIndex = angle->start();
4283    int endIndex = angle->end();
4284    return updateOppWinding(endIndex, startIndex);
4285}
4286
4287int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
4288    int startIndex = angle->start();
4289    int endIndex = angle->end();
4290    return updateOppWinding(startIndex, endIndex);
4291}
4292
4293int SkOpSegment::updateWinding(int index, int endIndex) const {
4294    int lesser = SkMin32(index, endIndex);
4295    int winding = windSum(lesser);
4296    if (winding == SK_MinS32) {
4297        return winding;
4298    }
4299    int spanWinding = spanSign(index, endIndex);
4300    if (winding && UseInnerWinding(winding - spanWinding, winding)
4301            && winding != SK_MaxS32) {
4302        winding -= spanWinding;
4303    }
4304    return winding;
4305}
4306
4307int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
4308    int startIndex = angle->start();
4309    int endIndex = angle->end();
4310    return updateWinding(endIndex, startIndex);
4311}
4312
4313int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
4314    int lesser = SkMin32(index, endIndex);
4315    int winding = windSum(lesser);
4316    int spanWinding = spanSign(endIndex, index);
4317    if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
4318            && winding != SK_MaxS32) {
4319        winding -= spanWinding;
4320    }
4321    return winding;
4322}
4323
4324int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
4325    int startIndex = angle->start();
4326    int endIndex = angle->end();
4327    return updateWindingReverse(endIndex, startIndex);
4328}
4329
4330// OPTIMIZATION: does the following also work, and is it any faster?
4331// return outerWinding * innerWinding > 0
4332//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
4333bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
4334    SkASSERT(outerWinding != SK_MaxS32);
4335    SkASSERT(innerWinding != SK_MaxS32);
4336    int absOut = abs(outerWinding);
4337    int absIn = abs(innerWinding);
4338    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
4339    return result;
4340}
4341
4342bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
4343    SkASSERT(outerWinding != SK_MaxS32);
4344    SkASSERT(innerWinding != SK_MaxS32);
4345    int absOut = abs(outerWinding);
4346    int absIn = abs(innerWinding);
4347    bool result = absOut == absIn ? true : absOut < absIn;
4348    return result;
4349}
4350
4351int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
4352    if (approximately_zero(tHit - t(tIndex))) {  // if we hit the end of a span, disregard
4353        return SK_MinS32;
4354    }
4355    int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
4356    SkASSERT(winding != SK_MinS32);
4357    int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
4358#if DEBUG_WINDING_AT_T
4359    SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__,
4360            debugID(), crossOpp, tHit, t(tIndex), winding, windVal);
4361#endif
4362    // see if a + change in T results in a +/- change in X (compute x'(T))
4363    *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
4364    if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
4365        *dx = fPts[2].fX - fPts[1].fX - *dx;
4366    }
4367    if (*dx == 0) {
4368#if DEBUG_WINDING_AT_T
4369        SkDebugf(" dx=0 winding=SK_MinS32\n");
4370#endif
4371        return SK_MinS32;
4372    }
4373    if (windVal < 0) {  // reverse sign if opp contour traveled in reverse
4374            *dx = -*dx;
4375    }
4376    if (winding * *dx > 0) {  // if same signs, result is negative
4377        winding += *dx > 0 ? -windVal : windVal;
4378    }
4379#if DEBUG_WINDING_AT_T
4380    SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
4381#endif
4382    return winding;
4383}
4384
4385int SkOpSegment::windSum(const SkOpAngle* angle) const {
4386    int start = angle->start();
4387    int end = angle->end();
4388    int index = SkMin32(start, end);
4389    return windSum(index);
4390}
4391
4392void SkOpSegment::zeroSpan(SkOpSpan* span) {
4393    SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
4394    span->fWindValue = 0;
4395    span->fOppValue = 0;
4396    if (span->fTiny || span->fSmall) {
4397        return;
4398    }
4399    SkASSERT(!span->fDone);
4400    span->fDone = true;
4401    ++fDoneSpans;
4402}
4403