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