Simplify.cpp revision e7bd5f4041701cbab87f6e779eb18fbb9fe74216
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 "Simplify.h"
8
9#undef SkASSERT
10#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
11
12// Terminology:
13// A Path contains one of more Contours
14// A Contour is made up of Segment array
15// A Segment is described by a Verb and a Point array with 2, 3, or 4 points
16// A Verb is one of Line, Quad(ratic), or Cubic
17// A Segment contains a Span array
18// A Span is describes a portion of a Segment using starting and ending T
19// T values range from 0 to 1, where 0 is the first Point in the Segment
20// An Edge is a Segment generated from a Span
21
22// FIXME: remove once debugging is complete
23#ifdef SK_DEBUG
24int gDebugMaxWindSum = SK_MaxS32;
25int gDebugMaxWindValue = SK_MaxS32;
26#endif
27
28#define PIN_ADD_T 0
29#define TRY_ROTATE 1
30
31#define DEBUG_UNUSED 0 // set to expose unused functions
32#define FORCE_RELEASE 0  // set force release to 1 for multiple thread -- no debugging
33
34#if FORCE_RELEASE || defined SK_RELEASE
35
36const bool gRunTestsInOneThread = false;
37
38#define DEBUG_ACTIVE_SPANS 0
39#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
40#define DEBUG_ADD_INTERSECTING_TS 0
41#define DEBUG_ADD_T_PAIR 0
42#define DEBUG_ANGLE 0
43#define DEBUG_ASSEMBLE 0
44#define DEBUG_CONCIDENT 0
45#define DEBUG_CROSS 0
46#define DEBUG_FLOW 0
47#define DEBUG_MARK_DONE 0
48#define DEBUG_PATH_CONSTRUCTION 0
49#define DEBUG_SHOW_WINDING 0
50#define DEBUG_SORT 0
51#define DEBUG_WIND_BUMP 0
52#define DEBUG_WINDING 0
53
54#else
55
56const bool gRunTestsInOneThread = true;
57
58#define DEBUG_ACTIVE_SPANS 1
59#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
60#define DEBUG_ADD_INTERSECTING_TS 1
61#define DEBUG_ADD_T_PAIR 1
62#define DEBUG_ANGLE 1
63#define DEBUG_ASSEMBLE 1
64#define DEBUG_CONCIDENT 1
65#define DEBUG_CROSS 0
66#define DEBUG_FLOW 1
67#define DEBUG_MARK_DONE 1
68#define DEBUG_PATH_CONSTRUCTION 1
69#define DEBUG_SHOW_WINDING 0
70#define DEBUG_SORT 1
71#define DEBUG_WIND_BUMP 0
72#define DEBUG_WINDING 1
73
74#endif
75
76#define DEBUG_DUMP (DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | DEBUG_PATH_CONSTRUCTION)
77
78#if DEBUG_DUMP
79static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
80// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
81static int gContourID;
82static int gSegmentID;
83#endif
84
85#ifndef DEBUG_TEST
86#define DEBUG_TEST 0
87#endif
88
89#define MAKE_CONST_LINE(line, pts) \
90    const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}
91#define MAKE_CONST_QUAD(quad, pts) \
92    const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
93            {pts[2].fX, pts[2].fY}}
94#define MAKE_CONST_CUBIC(cubic, pts) \
95    const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
96            {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}
97
98static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
99        Intersections& intersections) {
100    MAKE_CONST_LINE(aLine, a);
101    MAKE_CONST_LINE(bLine, b);
102    return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
103}
104
105static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
106        Intersections& intersections) {
107    MAKE_CONST_QUAD(aQuad, a);
108    MAKE_CONST_LINE(bLine, b);
109    return intersect(aQuad, bLine, intersections);
110}
111
112static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],
113        Intersections& intersections) {
114    MAKE_CONST_CUBIC(aCubic, a);
115    MAKE_CONST_LINE(bLine, b);
116    return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
117}
118
119static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
120        Intersections& intersections) {
121    MAKE_CONST_QUAD(aQuad, a);
122    MAKE_CONST_QUAD(bQuad, b);
123#define TRY_QUARTIC_SOLUTION 1
124#if TRY_QUARTIC_SOLUTION
125    intersect2(aQuad, bQuad, intersections);
126#else
127    intersect(aQuad, bQuad, intersections);
128#endif
129    return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed;
130}
131
132static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
133        Intersections& intersections) {
134    MAKE_CONST_CUBIC(aCubic, a);
135    MAKE_CONST_CUBIC(bCubic, b);
136    intersect(aCubic, bCubic, intersections);
137    return intersections.fUsed;
138}
139
140static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
141        SkScalar y, bool flipped, Intersections& intersections) {
142    MAKE_CONST_LINE(aLine, a);
143    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
144}
145
146static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
147        SkScalar y, bool flipped, Intersections& intersections) {
148    MAKE_CONST_QUAD(aQuad, a);
149    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
150}
151
152static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
153        SkScalar y, bool flipped, Intersections& intersections) {
154    MAKE_CONST_CUBIC(aCubic, a);
155    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
156}
157
158static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,
159        SkScalar , SkScalar , bool , Intersections& ) = {
160    NULL,
161    HLineIntersect,
162    HQuadIntersect,
163    HCubicIntersect
164};
165
166static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
167        SkScalar x, bool flipped, Intersections& intersections) {
168    MAKE_CONST_LINE(aLine, a);
169    return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
170}
171
172static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
173        SkScalar x, bool flipped, Intersections& intersections) {
174    MAKE_CONST_QUAD(aQuad, a);
175    return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
176}
177
178static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
179        SkScalar x, bool flipped, Intersections& intersections) {
180    MAKE_CONST_CUBIC(aCubic, a);
181    return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
182}
183
184static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
185        SkScalar , SkScalar , bool , Intersections& ) = {
186    NULL,
187    VLineIntersect,
188    VQuadIntersect,
189    VCubicIntersect
190};
191
192static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
193    MAKE_CONST_LINE(line, a);
194    double x, y;
195    xy_at_t(line, t, x, y);
196    out->fX = SkDoubleToScalar(x);
197    out->fY = SkDoubleToScalar(y);
198}
199
200static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
201    MAKE_CONST_QUAD(quad, a);
202    double x, y;
203    xy_at_t(quad, t, x, y);
204    out->fX = SkDoubleToScalar(x);
205    out->fY = SkDoubleToScalar(y);
206}
207
208static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {
209    MAKE_CONST_QUAD(quad, a);
210    xy_at_t(quad, t, out->x, out->y);
211}
212
213static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
214    MAKE_CONST_CUBIC(cubic, a);
215    double x, y;
216    xy_at_t(cubic, t, x, y);
217    out->fX = SkDoubleToScalar(x);
218    out->fY = SkDoubleToScalar(y);
219}
220
221static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
222    NULL,
223    LineXYAtT,
224    QuadXYAtT,
225    CubicXYAtT
226};
227
228static SkScalar LineXAtT(const SkPoint a[2], double t) {
229    MAKE_CONST_LINE(aLine, a);
230    double x;
231    xy_at_t(aLine, t, x, *(double*) 0);
232    return SkDoubleToScalar(x);
233}
234
235static SkScalar QuadXAtT(const SkPoint a[3], double t) {
236    MAKE_CONST_QUAD(quad, a);
237    double x;
238    xy_at_t(quad, t, x, *(double*) 0);
239    return SkDoubleToScalar(x);
240}
241
242static SkScalar CubicXAtT(const SkPoint a[4], double t) {
243    MAKE_CONST_CUBIC(cubic, a);
244    double x;
245    xy_at_t(cubic, t, x, *(double*) 0);
246    return SkDoubleToScalar(x);
247}
248
249static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
250    NULL,
251    LineXAtT,
252    QuadXAtT,
253    CubicXAtT
254};
255
256static SkScalar LineYAtT(const SkPoint a[2], double t) {
257    MAKE_CONST_LINE(aLine, a);
258    double y;
259    xy_at_t(aLine, t, *(double*) 0, y);
260    return SkDoubleToScalar(y);
261}
262
263static SkScalar QuadYAtT(const SkPoint a[3], double t) {
264    MAKE_CONST_QUAD(quad, a);
265    double y;
266    xy_at_t(quad, t, *(double*) 0, y);
267    return SkDoubleToScalar(y);
268}
269
270static SkScalar CubicYAtT(const SkPoint a[4], double t) {
271    MAKE_CONST_CUBIC(cubic, a);
272    double y;
273    xy_at_t(cubic, t, *(double*) 0, y);
274    return SkDoubleToScalar(y);
275}
276
277static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
278    NULL,
279    LineYAtT,
280    QuadYAtT,
281    CubicYAtT
282};
283
284static SkScalar LineDXAtT(const SkPoint a[2], double ) {
285    return a[1].fX - a[0].fX;
286}
287
288static SkScalar QuadDXAtT(const SkPoint a[3], double t) {
289    MAKE_CONST_QUAD(quad, a);
290    double x;
291    dxdy_at_t(quad, t, x, *(double*) 0);
292    return SkDoubleToScalar(x);
293}
294
295static SkScalar CubicDXAtT(const SkPoint a[4], double t) {
296    MAKE_CONST_CUBIC(cubic, a);
297    double x;
298    dxdy_at_t(cubic, t, x, *(double*) 0);
299    return SkDoubleToScalar(x);
300}
301
302static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
303    NULL,
304    LineDXAtT,
305    QuadDXAtT,
306    CubicDXAtT
307};
308
309static SkScalar LineDYAtT(const SkPoint a[2], double ) {
310    return a[1].fY - a[0].fY;
311}
312
313static SkScalar QuadDYAtT(const SkPoint a[3], double t) {
314    MAKE_CONST_QUAD(quad, a);
315    double y;
316    dxdy_at_t(quad, t, *(double*) 0, y);
317    return SkDoubleToScalar(y);
318}
319
320static SkScalar CubicDYAtT(const SkPoint a[4], double t) {
321    MAKE_CONST_CUBIC(cubic, a);
322    double y;
323    dxdy_at_t(cubic, t, *(double*) 0, y);
324    return SkDoubleToScalar(y);
325}
326
327static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {
328    NULL,
329    LineDYAtT,
330    QuadDYAtT,
331    CubicDYAtT
332};
333
334static void LineSubDivide(const SkPoint a[2], double startT, double endT,
335        SkPoint sub[2]) {
336    MAKE_CONST_LINE(aLine, a);
337    _Line dst;
338    sub_divide(aLine, startT, endT, dst);
339    sub[0].fX = SkDoubleToScalar(dst[0].x);
340    sub[0].fY = SkDoubleToScalar(dst[0].y);
341    sub[1].fX = SkDoubleToScalar(dst[1].x);
342    sub[1].fY = SkDoubleToScalar(dst[1].y);
343}
344
345static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
346        SkPoint sub[3]) {
347    MAKE_CONST_QUAD(aQuad, a);
348    Quadratic dst;
349    sub_divide(aQuad, startT, endT, dst);
350    sub[0].fX = SkDoubleToScalar(dst[0].x);
351    sub[0].fY = SkDoubleToScalar(dst[0].y);
352    sub[1].fX = SkDoubleToScalar(dst[1].x);
353    sub[1].fY = SkDoubleToScalar(dst[1].y);
354    sub[2].fX = SkDoubleToScalar(dst[2].x);
355    sub[2].fY = SkDoubleToScalar(dst[2].y);
356}
357
358static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
359        SkPoint sub[4]) {
360    MAKE_CONST_CUBIC(aCubic, a);
361    Cubic dst;
362    sub_divide(aCubic, startT, endT, dst);
363    sub[0].fX = SkDoubleToScalar(dst[0].x);
364    sub[0].fY = SkDoubleToScalar(dst[0].y);
365    sub[1].fX = SkDoubleToScalar(dst[1].x);
366    sub[1].fY = SkDoubleToScalar(dst[1].y);
367    sub[2].fX = SkDoubleToScalar(dst[2].x);
368    sub[2].fY = SkDoubleToScalar(dst[2].y);
369    sub[3].fX = SkDoubleToScalar(dst[3].x);
370    sub[3].fY = SkDoubleToScalar(dst[3].y);
371}
372
373static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
374        SkPoint []) = {
375    NULL,
376    LineSubDivide,
377    QuadSubDivide,
378    CubicSubDivide
379};
380
381static void LineSubDivideHD(const SkPoint a[2], double startT, double endT,
382        _Line sub) {
383    MAKE_CONST_LINE(aLine, a);
384    _Line dst;
385    sub_divide(aLine, startT, endT, dst);
386    sub[0] = dst[0];
387    sub[1] = dst[1];
388}
389
390static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT,
391        Quadratic sub) {
392    MAKE_CONST_QUAD(aQuad, a);
393    Quadratic dst;
394    sub_divide(aQuad, startT, endT, dst);
395    sub[0] = dst[0];
396    sub[1] = dst[1];
397    sub[2] = dst[2];
398}
399
400static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT,
401        Cubic sub) {
402    MAKE_CONST_CUBIC(aCubic, a);
403    Cubic dst;
404    sub_divide(aCubic, startT, endT, dst);
405    sub[0] = dst[0];
406    sub[1] = dst[1];
407    sub[2] = dst[2];
408    sub[3] = dst[3];
409}
410
411#if DEBUG_UNUSED
412static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
413        SkRect& bounds) {
414    SkPoint dst[3];
415    QuadSubDivide(a, startT, endT, dst);
416    bounds.fLeft = bounds.fRight = dst[0].fX;
417    bounds.fTop = bounds.fBottom = dst[0].fY;
418    for (int index = 1; index < 3; ++index) {
419        bounds.growToInclude(dst[index].fX, dst[index].fY);
420    }
421}
422
423static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
424        SkRect& bounds) {
425    SkPoint dst[4];
426    CubicSubDivide(a, startT, endT, dst);
427    bounds.fLeft = bounds.fRight = dst[0].fX;
428    bounds.fTop = bounds.fBottom = dst[0].fY;
429    for (int index = 1; index < 4; ++index) {
430        bounds.growToInclude(dst[index].fX, dst[index].fY);
431    }
432}
433#endif
434
435static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
436        SkTDArray<SkPoint>& reducePts) {
437    MAKE_CONST_QUAD(aQuad, a);
438    Quadratic dst;
439    int order = reduceOrder(aQuad, dst);
440    if (order == 2) { // quad became line
441        for (int index = 0; index < order; ++index) {
442            SkPoint* pt = reducePts.append();
443            pt->fX = SkDoubleToScalar(dst[index].x);
444            pt->fY = SkDoubleToScalar(dst[index].y);
445        }
446    }
447    return (SkPath::Verb) (order - 1);
448}
449
450static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
451        SkTDArray<SkPoint>& reducePts) {
452    MAKE_CONST_CUBIC(aCubic, a);
453    Cubic dst;
454    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
455    if (order == 2 || order == 3) { // cubic became line or quad
456        for (int index = 0; index < order; ++index) {
457            SkPoint* pt = reducePts.append();
458            pt->fX = SkDoubleToScalar(dst[index].x);
459            pt->fY = SkDoubleToScalar(dst[index].y);
460        }
461    }
462    return (SkPath::Verb) (order - 1);
463}
464
465static bool QuadIsLinear(const SkPoint a[3]) {
466    MAKE_CONST_QUAD(aQuad, a);
467    return isLinear(aQuad, 0, 2);
468}
469
470static bool CubicIsLinear(const SkPoint a[4]) {
471    MAKE_CONST_CUBIC(aCubic, a);
472    return isLinear(aCubic, 0, 3);
473}
474
475static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
476    MAKE_CONST_LINE(aLine, a);
477    double x[2];
478    xy_at_t(aLine, startT, x[0], *(double*) 0);
479    xy_at_t(aLine, endT, x[1], *(double*) 0);
480    return SkMinScalar((float) x[0], (float) x[1]);
481}
482
483static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
484    MAKE_CONST_QUAD(aQuad, a);
485    return (float) leftMostT(aQuad, startT, endT);
486}
487
488static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
489    MAKE_CONST_CUBIC(aCubic, a);
490    return (float) leftMostT(aCubic, startT, endT);
491}
492
493static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
494    NULL,
495    LineLeftMost,
496    QuadLeftMost,
497    CubicLeftMost
498};
499
500#if 0 // currently unused
501static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
502        Intersections& intersections) {
503    MAKE_CONST_QUAD(aQuad, a);
504    MAKE_CONST_LINE(bLine, b);
505    return intersectRay(aQuad, bLine, intersections);
506}
507#endif
508
509static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine,
510        Intersections& intersections) {
511    MAKE_CONST_QUAD(aQuad, a);
512    return intersectRay(aQuad, bLine, intersections);
513}
514
515class Segment;
516
517struct Span {
518    Segment* fOther;
519    mutable SkPoint fPt; // lazily computed as needed
520    double fT;
521    double fOtherT; // value at fOther[fOtherIndex].fT
522    int fOtherIndex;  // can't be used during intersection
523    int fWindSum; // accumulated from contours surrounding this one.
524    int fOppSum; // for binary operators: the opposite winding sum
525    int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
526    int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
527    bool fDone; // if set, this span to next higher T has been processed
528    bool fUnsortableStart; // set when start is part of an unsortable pair
529    bool fUnsortableEnd; // set when end is part of an unsortable pair
530    bool fTiny; // if set, span may still be considered once for edge following
531};
532
533// sorting angles
534// given angles of {dx dy ddx ddy dddx dddy} sort them
535class Angle {
536public:
537    // FIXME: this is bogus for quads and cubics
538    // if the quads and cubics' line from end pt to ctrl pt are coincident,
539    // there's no obvious way to determine the curve ordering from the
540    // derivatives alone. In particular, if one quadratic's coincident tangent
541    // is longer than the other curve, the final control point can place the
542    // longer curve on either side of the shorter one.
543    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
544    // may provide some help, but nothing has been figured out yet.
545
546    /*(
547    for quads and cubics, set up a parameterized line (e.g. LineParameters )
548    for points [0] to [1]. See if point [2] is on that line, or on one side
549    or the other. If it both quads' end points are on the same side, choose
550    the shorter tangent. If the tangents are equal, choose the better second
551    tangent angle
552
553    maybe I could set up LineParameters lazily
554    */
555    bool operator<(const Angle& rh) const {
556        double y = dy();
557        double ry = rh.dy();
558        if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
559            return y < 0;
560        }
561        double x = dx();
562        double rx = rh.dx();
563        if (y == 0 && ry == 0 && x * rx < 0) {
564            return x < rx;
565        }
566        double x_ry = x * ry;
567        double rx_y = rx * y;
568        double cmp = x_ry - rx_y;
569        if (!approximately_zero(cmp)) {
570            return cmp < 0;
571        }
572        if (approximately_zero(x_ry) && approximately_zero(rx_y)
573                && !approximately_zero_squared(cmp)) {
574            return cmp < 0;
575        }
576        // at this point, the initial tangent line is coincident
577        if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
578                || !approximately_zero(rh.fSide))) {
579            // FIXME: running demo will trigger this assertion
580            // (don't know if commenting out will trigger further assertion or not)
581            // commenting it out allows demo to run in release, though
582     //       SkASSERT(fSide != rh.fSide);
583            return fSide < rh.fSide;
584        }
585        // see if either curve can be lengthened and try the tangent compare again
586        if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
587                && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
588            Angle longer = *this;
589            Angle rhLonger = rh;
590            if (longer.lengthen() | rhLonger.lengthen()) {
591                return longer < rhLonger;
592            }
593            // what if we extend in the other direction?
594            longer = *this;
595            rhLonger = rh;
596            if (longer.reverseLengthen() | rhLonger.reverseLengthen()) {
597                return longer < rhLonger;
598            }
599        }
600        if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
601                || (rh.fVerb == SkPath::kLine_Verb
602                && approximately_zero(rx) && approximately_zero(ry))) {
603            // See general unsortable comment below. This case can happen when
604            // one line has a non-zero change in t but no change in x and y.
605            fUnsortable = true;
606            rh.fUnsortable = true;
607            return this < &rh; // even with no solution, return a stable sort
608        }
609        if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
610                || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
611            fUnsortable = true;
612            rh.fUnsortable = true;
613            return this < &rh; // even with no solution, return a stable sort
614        }
615        SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
616        SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
617        // FIXME: until I can think of something better, project a ray from the
618        // end of the shorter tangent to midway between the end points
619        // through both curves and use the resulting angle to sort
620        // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
621        double len = fTangent1.normalSquared();
622        double rlen = rh.fTangent1.normalSquared();
623        _Line ray;
624        Intersections i, ri;
625        int roots, rroots;
626        bool flip = false;
627        do {
628            const Quadratic& q = (len < rlen) ^ flip ? fQ : rh.fQ;
629            double midX = (q[0].x + q[2].x) / 2;
630            double midY = (q[0].y + q[2].y) / 2;
631            ray[0] = q[1];
632            ray[1].x = midX;
633            ray[1].y = midY;
634            SkASSERT(ray[0] != ray[1]);
635            roots = QuadRayIntersect(fPts, ray, i);
636            rroots = QuadRayIntersect(rh.fPts, ray, ri);
637        } while ((roots == 0 || rroots == 0) && (flip ^= true));
638        if (roots == 0 || rroots == 0) {
639            // FIXME: we don't have a solution in this case. The interim solution
640            // is to mark the edges as unsortable, exclude them from this and
641            // future computations, and allow the returned path to be fragmented
642            fUnsortable = true;
643            rh.fUnsortable = true;
644            return this < &rh; // even with no solution, return a stable sort
645        }
646        _Point loc;
647        double best = SK_ScalarInfinity;
648        double dx, dy, dist;
649        int index;
650        for (index = 0; index < roots; ++index) {
651            QuadXYAtT(fPts, i.fT[0][index], &loc);
652            dx = loc.x - ray[0].x;
653            dy = loc.y - ray[0].y;
654            dist = dx * dx + dy * dy;
655            if (best > dist) {
656                best = dist;
657            }
658        }
659        for (index = 0; index < rroots; ++index) {
660            QuadXYAtT(rh.fPts, ri.fT[0][index], &loc);
661            dx = loc.x - ray[0].x;
662            dy = loc.y - ray[0].y;
663            dist = dx * dx + dy * dy;
664            if (best > dist) {
665                return fSide < 0;
666            }
667        }
668        return fSide > 0;
669    }
670
671    double dx() const {
672        return fTangent1.dx();
673    }
674
675    double dy() const {
676        return fTangent1.dy();
677    }
678
679    int end() const {
680        return fEnd;
681    }
682
683    bool isHorizontal() const {
684        return dy() == 0 && fVerb == SkPath::kLine_Verb;
685    }
686
687    bool lengthen() {
688        int newEnd = fEnd;
689        if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
690            fEnd = newEnd;
691            setSpans();
692            return true;
693        }
694        return false;
695    }
696
697    bool reverseLengthen() {
698        if (fReversed) {
699            return false;
700        }
701        int newEnd = fStart;
702        if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
703            fEnd = newEnd;
704            fReversed = true;
705            setSpans();
706            return true;
707        }
708        return false;
709    }
710
711    void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
712            int start, int end, const SkTDArray<Span>& spans) {
713        fSegment = segment;
714        fStart = start;
715        fEnd = end;
716        fPts = orig;
717        fVerb = verb;
718        fSpans = &spans;
719        fReversed = false;
720        fUnsortable = false;
721        setSpans();
722    }
723
724    void setSpans() {
725        double startT = (*fSpans)[fStart].fT;
726        double endT = (*fSpans)[fEnd].fT;
727        switch (fVerb) {
728        case SkPath::kLine_Verb:
729            _Line l;
730            LineSubDivideHD(fPts, startT, endT, l);
731            // OPTIMIZATION: for pure line compares, we never need fTangent1.c
732            fTangent1.lineEndPoints(l);
733            fUnsortable = dx() == 0 && dy() == 0;
734            fSide = 0;
735            break;
736        case SkPath::kQuad_Verb:
737            QuadSubDivideHD(fPts, startT, endT, fQ);
738            fTangent1.quadEndPoints(fQ, 0, 1);
739            fSide = -fTangent1.pointDistance(fQ[2]); // not normalized -- compare sign only
740            break;
741        case SkPath::kCubic_Verb:
742            Cubic c;
743            CubicSubDivideHD(fPts, startT, endT, c);
744            fTangent1.cubicEndPoints(c, 0, 1);
745            fSide = -fTangent1.pointDistance(c[2]); // not normalized -- compare sign only
746            break;
747        default:
748            SkASSERT(0);
749        }
750        if (fUnsortable) {
751            return;
752        }
753        SkASSERT(fStart != fEnd);
754        int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
755        for (int index = fStart; index != fEnd; index += step) {
756            if ((*fSpans)[index].fUnsortableStart) {
757                fUnsortable = true;
758                return;
759            }
760#if 0
761            if (index != fStart && (*fSpans)[index].fUnsortableEnd) {
762                SkASSERT(0);
763                fUnsortable = true;
764                return;
765            }
766#endif
767        }
768    }
769
770    Segment* segment() const {
771        return const_cast<Segment*>(fSegment);
772    }
773
774    int sign() const {
775        return SkSign32(fStart - fEnd);
776    }
777
778    const SkTDArray<Span>* spans() const {
779        return fSpans;
780    }
781
782    int start() const {
783        return fStart;
784    }
785
786    bool unsortable() const {
787        return fUnsortable;
788    }
789
790#if DEBUG_ANGLE
791    const SkPoint* pts() const {
792        return fPts;
793    }
794
795    SkPath::Verb verb() const {
796        return fVerb;
797    }
798
799    void debugShow(const SkPoint& a) const {
800        SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
801    }
802#endif
803
804private:
805    const SkPoint* fPts;
806    Quadratic fQ;
807    SkPath::Verb fVerb;
808    double fSide;
809    LineParameters fTangent1;
810    const SkTDArray<Span>* fSpans;
811    const Segment* fSegment;
812    int fStart;
813    int fEnd;
814    bool fReversed;
815    mutable bool fUnsortable; // this alone is editable by the less than operator
816};
817
818// Bounds, unlike Rect, does not consider a line to be empty.
819struct Bounds : public SkRect {
820    static bool Intersects(const Bounds& a, const Bounds& b) {
821        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
822                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
823    }
824
825    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
826        if (left < fLeft) {
827            fLeft = left;
828        }
829        if (top < fTop) {
830            fTop = top;
831        }
832        if (right > fRight) {
833            fRight = right;
834        }
835        if (bottom > fBottom) {
836            fBottom = bottom;
837        }
838    }
839
840    void add(const Bounds& toAdd) {
841        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
842    }
843
844    void add(const SkPoint& pt) {
845        if (pt.fX < fLeft) fLeft = pt.fX;
846        if (pt.fY < fTop) fTop = pt.fY;
847        if (pt.fX > fRight) fRight = pt.fX;
848        if (pt.fY > fBottom) fBottom = pt.fY;
849    }
850
851    bool isEmpty() {
852        return fLeft > fRight || fTop > fBottom
853                || (fLeft == fRight && fTop == fBottom)
854                || isnan(fLeft) || isnan(fRight)
855                || isnan(fTop) || isnan(fBottom);
856    }
857
858    void setCubicBounds(const SkPoint a[4]) {
859        _Rect dRect;
860        MAKE_CONST_CUBIC(cubic, a);
861        dRect.setBounds(cubic);
862        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
863                (float) dRect.bottom);
864    }
865
866    void setQuadBounds(const SkPoint a[3]) {
867        MAKE_CONST_QUAD(quad, a);
868        _Rect dRect;
869        dRect.setBounds(quad);
870        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
871                (float) dRect.bottom);
872    }
873
874    void setPoint(const SkPoint& pt) {
875        fLeft = fRight = pt.fX;
876        fTop = fBottom = pt.fY;
877    }
878};
879
880// OPTIMIZATION: does the following also work, and is it any faster?
881// return outerWinding * innerWinding > 0
882//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
883static bool useInnerWinding(int outerWinding, int innerWinding) {
884  //  SkASSERT(outerWinding != innerWinding);
885    int absOut = abs(outerWinding);
886    int absIn = abs(innerWinding);
887    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
888    if (outerWinding * innerWinding < 0) {
889#if DEBUG_WINDING
890        SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
891                outerWinding, innerWinding, result ? "true" : "false");
892#endif
893    }
894    return result;
895}
896
897#define F (false)      // discard the edge
898#define T (true)       // keep the edge
899
900static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {
901//                 miFrom=0                              miFrom=1
902//         miTo=0            miTo=1              miTo=0             miTo=1
903//    suFrom=0    1     suFrom=0     1      suFrom=0    1      suFrom=0    1
904//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
905    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
906    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
907    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
908    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
909};
910
911#undef F
912#undef T
913
914// wrap path to keep track of whether the contour is initialized and non-empty
915class PathWrapper {
916public:
917    PathWrapper(SkPath& path)
918        : fPathPtr(&path)
919    {
920        init();
921    }
922
923    void close() {
924        if (!fHasMove) {
925            return;
926        }
927        bool callClose = isClosed();
928        lineTo();
929        if (fEmpty) {
930            return;
931        }
932        if (callClose) {
933    #if DEBUG_PATH_CONSTRUCTION
934            SkDebugf("path.close();\n");
935    #endif
936            fPathPtr->close();
937        }
938        init();
939    }
940
941    void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
942        lineTo();
943        moveTo();
944#if DEBUG_PATH_CONSTRUCTION
945        SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
946                pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY);
947#endif
948        fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY);
949        fDefer[0] = fDefer[1] = pt3;
950        fEmpty = false;
951    }
952
953    void deferredLine(const SkPoint& pt) {
954        if (pt == fDefer[1]) {
955            return;
956        }
957        if (changedSlopes(pt)) {
958            lineTo();
959            fDefer[0] = fDefer[1];
960        }
961        fDefer[1] = pt;
962    }
963
964    void deferredMove(const SkPoint& pt) {
965        fMoved = true;
966        fHasMove = true;
967        fEmpty = true;
968        fDefer[0] = fDefer[1] = pt;
969    }
970
971    void deferredMoveLine(const SkPoint& pt) {
972        if (!fHasMove) {
973            deferredMove(pt);
974        }
975        deferredLine(pt);
976    }
977
978    bool hasMove() const {
979        return fHasMove;
980    }
981
982    void init() {
983        fEmpty = true;
984        fHasMove = false;
985        fMoved = false;
986    }
987
988    bool isClosed() const {
989        return !fEmpty && fFirstPt == fDefer[1];
990    }
991
992    void lineTo() {
993        if (fDefer[0] == fDefer[1]) {
994            return;
995        }
996        moveTo();
997        fEmpty = false;
998#if DEBUG_PATH_CONSTRUCTION
999        SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
1000#endif
1001        fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);
1002        fDefer[0] = fDefer[1];
1003    }
1004
1005    const SkPath* nativePath() const {
1006        return fPathPtr;
1007    }
1008
1009    void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
1010        lineTo();
1011        moveTo();
1012#if DEBUG_PATH_CONSTRUCTION
1013        SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
1014                pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1015#endif
1016        fPathPtr->quadTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1017        fDefer[0] = fDefer[1] = pt2;
1018        fEmpty = false;
1019    }
1020
1021protected:
1022    bool changedSlopes(const SkPoint& pt) const {
1023        if (fDefer[0] == fDefer[1]) {
1024            return false;
1025        }
1026        SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;
1027        SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;
1028        SkScalar lineDx = pt.fX - fDefer[1].fX;
1029        SkScalar lineDy = pt.fY - fDefer[1].fY;
1030        return deferDx * lineDy != deferDy * lineDx;
1031    }
1032
1033    void moveTo() {
1034        if (!fMoved) {
1035            return;
1036        }
1037        fFirstPt = fDefer[0];
1038#if DEBUG_PATH_CONSTRUCTION
1039        SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);
1040#endif
1041        fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);
1042        fMoved = false;
1043    }
1044
1045private:
1046    SkPath* fPathPtr;
1047    SkPoint fDefer[2];
1048    SkPoint fFirstPt;
1049    bool fEmpty;
1050    bool fHasMove;
1051    bool fMoved;
1052};
1053
1054class Segment {
1055public:
1056    Segment() {
1057#if DEBUG_DUMP
1058        fID = ++gSegmentID;
1059#endif
1060    }
1061
1062    bool operator<(const Segment& rh) const {
1063        return fBounds.fTop < rh.fBounds.fTop;
1064    }
1065
1066    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
1067        if (activeAngleInner(index, done, angles)) {
1068            return true;
1069        }
1070        double referenceT = fTs[index].fT;
1071        int lesser = index;
1072        while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
1073            if (activeAngleOther(lesser, done, angles)) {
1074                return true;
1075            }
1076        }
1077        do {
1078            if (activeAngleOther(index, done, angles)) {
1079                return true;
1080            }
1081        } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
1082        return false;
1083    }
1084
1085    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
1086        Span* span = &fTs[index];
1087        Segment* other = span->fOther;
1088        int oIndex = span->fOtherIndex;
1089        return other->activeAngleInner(oIndex, done, angles);
1090    }
1091
1092    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
1093        int next = nextExactSpan(index, 1);
1094        if (next > 0) {
1095            Span& upSpan = fTs[index];
1096            if (upSpan.fWindValue || upSpan.fOppValue) {
1097                addAngle(angles, index, next);
1098                if (upSpan.fDone || upSpan.fUnsortableEnd) {
1099                    done++;
1100                } else if (upSpan.fWindSum != SK_MinS32) {
1101                    return true;
1102                }
1103            } else if (!upSpan.fDone) {
1104                upSpan.fDone = true;
1105                fDoneSpans++;
1106            }
1107        }
1108        int prev = nextExactSpan(index, -1);
1109        // edge leading into junction
1110        if (prev >= 0) {
1111            Span& downSpan = fTs[prev];
1112            if (downSpan.fWindValue || downSpan.fOppValue) {
1113                addAngle(angles, index, prev);
1114                if (downSpan.fDone) {
1115                    done++;
1116                 } else if (downSpan.fWindSum != SK_MinS32) {
1117                    return true;
1118                }
1119            } else if (!downSpan.fDone) {
1120                downSpan.fDone = true;
1121                fDoneSpans++;
1122            }
1123        }
1124        return false;
1125    }
1126
1127    void activeLeftTop(SkPoint& result) const {
1128        SkASSERT(!done());
1129        int count = fTs.count();
1130        result.fY = SK_ScalarMax;
1131        bool lastDone = true;
1132        bool lastUnsortable = false;
1133        for (int index = 0; index < count; ++index) {
1134            const Span& span = fTs[index];
1135            if (span.fUnsortableStart | lastUnsortable) {
1136                goto next;
1137            }
1138            if (!span.fDone | !lastDone) {
1139                const SkPoint& xy = xyAtT(index);
1140                if (result.fY < xy.fY) {
1141                    goto next;
1142                }
1143                if (result.fY == xy.fY && result.fX < xy.fX) {
1144                    goto next;
1145                }
1146                result = xy;
1147            }
1148    next:
1149            lastDone = span.fDone;
1150            lastUnsortable = span.fUnsortableEnd;
1151        }
1152        SkASSERT(result.fY < SK_ScalarMax);
1153    }
1154
1155    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
1156        int sumMiWinding = updateWinding(endIndex, index);
1157        int sumSuWinding = updateOppWinding(endIndex, index);
1158        if (fOperand) {
1159            SkTSwap<int>(sumMiWinding, sumSuWinding);
1160        }
1161        int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1162        return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,
1163                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1164    }
1165
1166    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,
1167            int& sumMiWinding, int& sumSuWinding,
1168            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
1169        setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
1170                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1171        bool miFrom;
1172        bool miTo;
1173        bool suFrom;
1174        bool suTo;
1175        if (operand()) {
1176            miFrom = (oppMaxWinding & xorMiMask) != 0;
1177            miTo = (oppSumWinding & xorMiMask) != 0;
1178            suFrom = (maxWinding & xorSuMask) != 0;
1179            suTo = (sumWinding & xorSuMask) != 0;
1180        } else {
1181            miFrom = (maxWinding & xorMiMask) != 0;
1182            miTo = (sumWinding & xorMiMask) != 0;
1183            suFrom = (oppMaxWinding & xorSuMask) != 0;
1184            suTo = (oppSumWinding & xorSuMask) != 0;
1185        }
1186        bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
1187        SkASSERT(result != -1);
1188        return result;
1189    }
1190
1191    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
1192        SkASSERT(start != end);
1193        Angle* angle = angles.append();
1194#if DEBUG_ANGLE
1195        if (angles.count() > 1 && !fTs[start].fTiny) {
1196            SkPoint angle0Pt, newPt;
1197            (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
1198                    (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
1199            (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
1200            SkASSERT(approximately_equal(angle0Pt.fX, newPt.fX));
1201            SkASSERT(approximately_equal(angle0Pt.fY, newPt.fY));
1202        }
1203#endif
1204        angle->set(fPts, fVerb, this, start, end, fTs);
1205    }
1206
1207    void addCancelOutsides(double tStart, double oStart, Segment& other,
1208            double oEnd) {
1209        int tIndex = -1;
1210        int tCount = fTs.count();
1211        int oIndex = -1;
1212        int oCount = other.fTs.count();
1213        do {
1214            ++tIndex;
1215        } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
1216        int tIndexStart = tIndex;
1217        do {
1218            ++oIndex;
1219        } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
1220        int oIndexStart = oIndex;
1221        double nextT;
1222        do {
1223            nextT = fTs[++tIndex].fT;
1224        } while (nextT < 1 && approximately_negative(nextT - tStart));
1225        double oNextT;
1226        do {
1227            oNextT = other.fTs[++oIndex].fT;
1228        } while (oNextT < 1 && approximately_negative(oNextT - oStart));
1229        // at this point, spans before and after are at:
1230        //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1231        // if tIndexStart == 0, no prior span
1232        // if nextT == 1, no following span
1233
1234        // advance the span with zero winding
1235        // if the following span exists (not past the end, non-zero winding)
1236        // connect the two edges
1237        if (!fTs[tIndexStart].fWindValue) {
1238            if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1239    #if DEBUG_CONCIDENT
1240                SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1241                        __FUNCTION__, fID, other.fID, tIndexStart - 1,
1242                        fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
1243                        xyAtT(tIndexStart).fY);
1244    #endif
1245                addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false);
1246            }
1247            if (nextT < 1 && fTs[tIndex].fWindValue) {
1248    #if DEBUG_CONCIDENT
1249                SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1250                        __FUNCTION__, fID, other.fID, tIndex,
1251                        fTs[tIndex].fT, xyAtT(tIndex).fX,
1252                        xyAtT(tIndex).fY);
1253    #endif
1254                addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false);
1255            }
1256        } else {
1257            SkASSERT(!other.fTs[oIndexStart].fWindValue);
1258            if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
1259    #if DEBUG_CONCIDENT
1260                SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1261                        __FUNCTION__, fID, other.fID, oIndexStart - 1,
1262                        other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
1263                        other.xyAtT(oIndexStart).fY);
1264                other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1265    #endif
1266            }
1267            if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
1268    #if DEBUG_CONCIDENT
1269                SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1270                        __FUNCTION__, fID, other.fID, oIndex,
1271                        other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
1272                        other.xyAtT(oIndex).fY);
1273                other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1274    #endif
1275            }
1276        }
1277    }
1278
1279    void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
1280            double oEnd) {
1281        // walk this to outsideTs[0]
1282        // walk other to outsideTs[1]
1283        // if either is > 0, add a pointer to the other, copying adjacent winding
1284        int tIndex = -1;
1285        int oIndex = -1;
1286        double tStart = outsideTs[0];
1287        double oStart = outsideTs[1];
1288        do {
1289            ++tIndex;
1290        } while (!approximately_negative(tStart - fTs[tIndex].fT));
1291        do {
1292            ++oIndex;
1293        } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
1294        if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
1295            addTPair(tStart, other, oStart, false);
1296        }
1297        tStart = fTs[tIndex].fT;
1298        oStart = other.fTs[oIndex].fT;
1299        do {
1300            double nextT;
1301            do {
1302                nextT = fTs[++tIndex].fT;
1303            } while (approximately_negative(nextT - tStart));
1304            tStart = nextT;
1305            do {
1306                nextT = other.fTs[++oIndex].fT;
1307            } while (approximately_negative(nextT - oStart));
1308            oStart = nextT;
1309            if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
1310                break;
1311            }
1312            addTPair(tStart, other, oStart, false);
1313        } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
1314    }
1315
1316    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
1317        init(pts, SkPath::kCubic_Verb, operand, evenOdd);
1318        fBounds.setCubicBounds(pts);
1319    }
1320
1321    /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const {
1322        SkPoint edge[4];
1323        const SkPoint* ePtr;
1324        int lastT = fTs.count() - 1;
1325        if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
1326            ePtr = fPts;
1327        } else {
1328        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
1329            (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
1330            ePtr = edge;
1331        }
1332        if (active) {
1333            bool reverse = ePtr == fPts && start != 0;
1334            if (reverse) {
1335                path.deferredMoveLine(ePtr[fVerb]);
1336                switch (fVerb) {
1337                    case SkPath::kLine_Verb:
1338                        path.deferredLine(ePtr[0]);
1339                        break;
1340                    case SkPath::kQuad_Verb:
1341                        path.quadTo(ePtr[1], ePtr[0]);
1342                        break;
1343                    case SkPath::kCubic_Verb:
1344                        path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);
1345                        break;
1346                    default:
1347                        SkASSERT(0);
1348                }
1349       //         return ePtr[0];
1350           } else {
1351                path.deferredMoveLine(ePtr[0]);
1352                switch (fVerb) {
1353                    case SkPath::kLine_Verb:
1354                        path.deferredLine(ePtr[1]);
1355                        break;
1356                    case SkPath::kQuad_Verb:
1357                        path.quadTo(ePtr[1], ePtr[2]);
1358                        break;
1359                    case SkPath::kCubic_Verb:
1360                        path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);
1361                        break;
1362                    default:
1363                        SkASSERT(0);
1364                }
1365            }
1366        }
1367      //  return ePtr[fVerb];
1368    }
1369
1370    void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
1371        init(pts, SkPath::kLine_Verb, operand, evenOdd);
1372        fBounds.set(pts, 2);
1373    }
1374
1375#if 0
1376    const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {
1377        const SkPoint& pt = xyAtT(tIndex);
1378        if (active) {
1379            path.deferredMove(pt);
1380        }
1381        return pt;
1382    }
1383#endif
1384
1385    // add 2 to edge or out of range values to get T extremes
1386    void addOtherT(int index, double otherT, int otherIndex) {
1387        Span& span = fTs[index];
1388    #if PIN_ADD_T
1389        if (precisely_less_than_zero(otherT)) {
1390            otherT = 0;
1391        } else if (precisely_greater_than_one(otherT)) {
1392            otherT = 1;
1393        }
1394    #endif
1395        span.fOtherT = otherT;
1396        span.fOtherIndex = otherIndex;
1397    }
1398
1399    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
1400        init(pts, SkPath::kQuad_Verb, operand, evenOdd);
1401        fBounds.setQuadBounds(pts);
1402    }
1403
1404    // Defer all coincident edge processing until
1405    // after normal intersections have been computed
1406
1407// no need to be tricky; insert in normal T order
1408// resolve overlapping ts when considering coincidence later
1409
1410    // add non-coincident intersection. Resulting edges are sorted in T.
1411    int addT(double newT, Segment* other) {
1412        // FIXME: in the pathological case where there is a ton of intercepts,
1413        //  binary search?
1414        int insertedAt = -1;
1415        size_t tCount = fTs.count();
1416    #if PIN_ADD_T
1417        // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
1418        if (precisely_less_than_zero(newT)) {
1419            newT = 0;
1420        } else if (precisely_greater_than_one(newT)) {
1421            newT = 1;
1422        }
1423    #endif
1424        for (size_t index = 0; index < tCount; ++index) {
1425            // OPTIMIZATION: if there are three or more identical Ts, then
1426            // the fourth and following could be further insertion-sorted so
1427            // that all the edges are clockwise or counterclockwise.
1428            // This could later limit segment tests to the two adjacent
1429            // neighbors, although it doesn't help with determining which
1430            // circular direction to go in.
1431            if (newT < fTs[index].fT) {
1432                insertedAt = index;
1433                break;
1434            }
1435        }
1436        Span* span;
1437        if (insertedAt >= 0) {
1438            span = fTs.insert(insertedAt);
1439        } else {
1440            insertedAt = tCount;
1441            span = fTs.append();
1442        }
1443        span->fT = newT;
1444        span->fOther = other;
1445        span->fPt.fX = SK_ScalarNaN;
1446        span->fWindSum = SK_MinS32;
1447        span->fOppSum = SK_MinS32;
1448        span->fWindValue = 1;
1449        span->fOppValue = 0;
1450        span->fTiny = false;
1451        if ((span->fDone = newT == 1)) {
1452            ++fDoneSpans;
1453        }
1454        span->fUnsortableStart = false;
1455        span->fUnsortableEnd = false;
1456        if (span - fTs.begin() > 0 && !span[-1].fDone
1457                && !precisely_negative(newT - span[-1].fT)
1458 //               && approximately_negative(newT - span[-1].fT)
1459                && xyAtT(&span[-1]) == xyAtT(span)) {
1460            span[-1].fTiny = true;
1461            span[-1].fDone = true;
1462            if (approximately_negative(newT - span[-1].fT)) {
1463                if (approximately_greater_than_one(newT)) {
1464                    span[-1].fUnsortableStart = true;
1465                    span[-2].fUnsortableEnd = true;
1466                }
1467                if (approximately_less_than_zero(span[-1].fT)) {
1468                    span->fUnsortableStart = true;
1469                    span[-1].fUnsortableEnd = true;
1470                }
1471            }
1472            ++fDoneSpans;
1473        }
1474        if (fTs.end() - span > 1 && !span->fDone
1475                && !precisely_negative(span[1].fT - newT)
1476 //               && approximately_negative(span[1].fT - newT)
1477                && xyAtT(&span[1]) == xyAtT(span)) {
1478            span->fTiny = true;
1479            span->fDone = true;
1480            if (approximately_negative(span[1].fT - newT)) {
1481                if (approximately_greater_than_one(span[1].fT)) {
1482                    span->fUnsortableStart = true;
1483                    span[-1].fUnsortableEnd = true;
1484                }
1485                if (approximately_less_than_zero(newT)) {
1486                    span[1].fUnsortableStart = true;
1487                    span->fUnsortableEnd = true;
1488                }
1489            }
1490            ++fDoneSpans;
1491        }
1492        return insertedAt;
1493    }
1494
1495    // set spans from start to end to decrement by one
1496    // note this walks other backwards
1497    // FIMXE: there's probably an edge case that can be constructed where
1498    // two span in one segment are separated by float epsilon on one span but
1499    // not the other, if one segment is very small. For this
1500    // case the counts asserted below may or may not be enough to separate the
1501    // spans. Even if the counts work out, what if the spans aren't correctly
1502    // sorted? It feels better in such a case to match the span's other span
1503    // pointer since both coincident segments must contain the same spans.
1504    void addTCancel(double startT, double endT, Segment& other,
1505            double oStartT, double oEndT) {
1506        SkASSERT(!approximately_negative(endT - startT));
1507        SkASSERT(!approximately_negative(oEndT - oStartT));
1508        bool binary = fOperand != other.fOperand;
1509        int index = 0;
1510        while (!approximately_negative(startT - fTs[index].fT)) {
1511            ++index;
1512        }
1513        int oIndex = other.fTs.count();
1514        while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
1515            ;
1516        double tRatio = (oEndT - oStartT) / (endT - startT);
1517        Span* test = &fTs[index];
1518        Span* oTest = &other.fTs[oIndex];
1519        SkTDArray<double> outsideTs;
1520        SkTDArray<double> oOutsideTs;
1521        do {
1522            bool decrement = test->fWindValue && oTest->fWindValue && !binary;
1523            bool track = test->fWindValue || oTest->fWindValue;
1524            double testT = test->fT;
1525            double oTestT = oTest->fT;
1526            Span* span = test;
1527            do {
1528                if (decrement) {
1529                    decrementSpan(span);
1530                } else if (track && span->fT < 1 && oTestT < 1) {
1531                    TrackOutside(outsideTs, span->fT, oTestT);
1532                }
1533                span = &fTs[++index];
1534            } while (approximately_negative(span->fT - testT));
1535            Span* oSpan = oTest;
1536            double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
1537            double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
1538            SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
1539            while (approximately_negative(otherTMatchStart - oSpan->fT)
1540                    && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
1541        #ifdef SK_DEBUG
1542                SkASSERT(originalWindValue == oSpan->fWindValue);
1543        #endif
1544                if (decrement) {
1545                    other.decrementSpan(oSpan);
1546                } else if (track && oSpan->fT < 1 && testT < 1) {
1547                    TrackOutside(oOutsideTs, oSpan->fT, testT);
1548                }
1549                if (!oIndex) {
1550                    break;
1551                }
1552                oSpan = &other.fTs[--oIndex];
1553            }
1554            test = span;
1555            oTest = oSpan;
1556        } while (!approximately_negative(endT - test->fT));
1557        SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
1558        // FIXME: determine if canceled edges need outside ts added
1559        if (!done() && outsideTs.count()) {
1560            double tStart = outsideTs[0];
1561            double oStart = outsideTs[1];
1562            addCancelOutsides(tStart, oStart, other, oEndT);
1563            int count = outsideTs.count();
1564            if (count > 2) {
1565                double tStart = outsideTs[count - 2];
1566                double oStart = outsideTs[count - 1];
1567                addCancelOutsides(tStart, oStart, other, oEndT);
1568            }
1569        }
1570        if (!other.done() && oOutsideTs.count()) {
1571            double tStart = oOutsideTs[0];
1572            double oStart = oOutsideTs[1];
1573            other.addCancelOutsides(tStart, oStart, *this, endT);
1574        }
1575    }
1576
1577    int bumpCoincidentThis(const Span* oTest, bool opp, int index,
1578            SkTDArray<double>& outsideTs) {
1579        int oWindValue = oTest->fWindValue;
1580        int oOppValue = oTest->fOppValue;
1581        if (opp) {
1582            SkTSwap<int>(oWindValue, oOppValue);
1583        }
1584        Span* const test = &fTs[index];
1585        Span* end = test;
1586        const double oStartT = oTest->fT;
1587        do {
1588            if (bumpSpan(end, oWindValue, oOppValue)) {
1589                TrackOutside(outsideTs, end->fT, oStartT);
1590            }
1591            end = &fTs[++index];
1592        } while (approximately_negative(end->fT - test->fT));
1593        return index;
1594    }
1595
1596    // because of the order in which coincidences are resolved, this and other
1597    // may not have the same intermediate points. Compute the corresponding
1598    // intermediate T values (using this as the master, other as the follower)
1599    // and walk other conditionally -- hoping that it catches up in the end
1600    int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,
1601            SkTDArray<double>& oOutsideTs) {
1602        Span* const oTest = &fTs[oIndex];
1603        Span* oEnd = oTest;
1604        const double startT = test->fT;
1605        const double oStartT = oTest->fT;
1606        while (!approximately_negative(oEndT - oEnd->fT)
1607                && approximately_negative(oEnd->fT - oStartT)) {
1608            zeroSpan(oEnd);
1609            TrackOutside(oOutsideTs, oEnd->fT, startT);
1610            oEnd = &fTs[++oIndex];
1611        }
1612        return oIndex;
1613    }
1614
1615    // FIXME: need to test this case:
1616    // contourA has two segments that are coincident
1617    // contourB has two segments that are coincident in the same place
1618    // each ends up with +2/0 pairs for winding count
1619    // since logic below doesn't transfer count (only increments/decrements) can this be
1620    // resolved to +4/0 ?
1621
1622    // set spans from start to end to increment the greater by one and decrement
1623    // the lesser
1624    void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
1625        SkASSERT(!approximately_negative(endT - startT));
1626        SkASSERT(!approximately_negative(oEndT - oStartT));
1627        bool opp = fOperand ^ other.fOperand;
1628        int index = 0;
1629        while (!approximately_negative(startT - fTs[index].fT)) {
1630            ++index;
1631        }
1632        int oIndex = 0;
1633        while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
1634            ++oIndex;
1635        }
1636        Span* test = &fTs[index];
1637        Span* oTest = &other.fTs[oIndex];
1638        SkTDArray<double> outsideTs;
1639        SkTDArray<double> oOutsideTs;
1640        do {
1641            // if either span has an opposite value and the operands don't match, resolve first
1642     //       SkASSERT(!test->fDone || !oTest->fDone);
1643            if (test->fDone || oTest->fDone) {
1644                index = advanceCoincidentThis(oTest, opp, index);
1645                oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
1646            } else {
1647                index = bumpCoincidentThis(oTest, opp, index, outsideTs);
1648                oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
1649            }
1650            test = &fTs[index];
1651            oTest = &other.fTs[oIndex];
1652        } while (!approximately_negative(endT - test->fT));
1653        SkASSERT(approximately_negative(oTest->fT - oEndT));
1654        SkASSERT(approximately_negative(oEndT - oTest->fT));
1655        if (!done() && outsideTs.count()) {
1656            addCoinOutsides(outsideTs, other, oEndT);
1657        }
1658        if (!other.done() && oOutsideTs.count()) {
1659            other.addCoinOutsides(oOutsideTs, *this, endT);
1660        }
1661    }
1662
1663    // FIXME: this doesn't prevent the same span from being added twice
1664    // fix in caller, assert here?
1665    void addTPair(double t, Segment& other, double otherT, bool borrowWind) {
1666        int tCount = fTs.count();
1667        for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1668            const Span& span = fTs[tIndex];
1669            if (!approximately_negative(span.fT - t)) {
1670                break;
1671            }
1672            if (approximately_negative(span.fT - t) && span.fOther == &other
1673                    && approximately_equal(span.fOtherT, otherT)) {
1674#if DEBUG_ADD_T_PAIR
1675                SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1676                        __FUNCTION__, fID, t, other.fID, otherT);
1677#endif
1678                return;
1679            }
1680        }
1681#if DEBUG_ADD_T_PAIR
1682        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1683                __FUNCTION__, fID, t, other.fID, otherT);
1684#endif
1685        int insertedAt = addT(t, &other);
1686        int otherInsertedAt = other.addT(otherT, this);
1687        addOtherT(insertedAt, otherT, otherInsertedAt);
1688        other.addOtherT(otherInsertedAt, t, insertedAt);
1689        matchWindingValue(insertedAt, t, borrowWind);
1690        other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
1691    }
1692
1693    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
1694        // add edge leading into junction
1695        int min = SkMin32(end, start);
1696        if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
1697            addAngle(angles, end, start);
1698        }
1699        // add edge leading away from junction
1700        int step = SkSign32(end - start);
1701        int tIndex = nextExactSpan(end, step);
1702        min = SkMin32(end, tIndex);
1703        if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
1704            addAngle(angles, end, tIndex);
1705        }
1706    }
1707
1708    int advanceCoincidentThis(const Span* oTest, bool opp, int index) {
1709        Span* const test = &fTs[index];
1710        Span* end = test;
1711        do {
1712            end = &fTs[++index];
1713        } while (approximately_negative(end->fT - test->fT));
1714        return index;
1715    }
1716
1717    int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {
1718        Span* const oTest = &fTs[oIndex];
1719        Span* oEnd = oTest;
1720        const double oStartT = oTest->fT;
1721        while (!approximately_negative(oEndT - oEnd->fT)
1722                && approximately_negative(oEnd->fT - oStartT)) {
1723            oEnd = &fTs[++oIndex];
1724        }
1725        return oIndex;
1726    }
1727
1728    const Bounds& bounds() const {
1729        return fBounds;
1730    }
1731
1732    void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {
1733        double referenceT = fTs[index].fT;
1734        int lesser = index;
1735        while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
1736                && precisely_negative(referenceT - fTs[lesser].fT)) {
1737            buildAnglesInner(lesser, angles);
1738        }
1739        do {
1740            buildAnglesInner(index, angles);
1741        } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
1742                && precisely_negative(fTs[index].fT - referenceT));
1743    }
1744
1745    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
1746        Span* span = &fTs[index];
1747        Segment* other = span->fOther;
1748    // if there is only one live crossing, and no coincidence, continue
1749    // in the same direction
1750    // if there is coincidence, the only choice may be to reverse direction
1751        // find edge on either side of intersection
1752        int oIndex = span->fOtherIndex;
1753        // if done == -1, prior span has already been processed
1754        int step = 1;
1755        int next = other->nextExactSpan(oIndex, step);
1756       if (next < 0) {
1757            step = -step;
1758            next = other->nextExactSpan(oIndex, step);
1759        }
1760        // add candidate into and away from junction
1761        other->addTwoAngles(next, oIndex, angles);
1762    }
1763
1764    int computeSum(int startIndex, int endIndex, bool binary) {
1765        SkTDArray<Angle> angles;
1766        addTwoAngles(startIndex, endIndex, angles);
1767        buildAngles(endIndex, angles, false);
1768        // OPTIMIZATION: check all angles to see if any have computed wind sum
1769        // before sorting (early exit if none)
1770        SkTDArray<Angle*> sorted;
1771        bool sortable = SortAngles(angles, sorted);
1772#if DEBUG_SORT
1773        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
1774#endif
1775        if (!sortable) {
1776            return SK_MinS32;
1777        }
1778        int angleCount = angles.count();
1779        const Angle* angle;
1780        const Segment* base;
1781        int winding;
1782        int oWinding;
1783        int firstIndex = 0;
1784        do {
1785            angle = sorted[firstIndex];
1786            base = angle->segment();
1787            winding = base->windSum(angle);
1788            if (winding != SK_MinS32) {
1789                oWinding = base->oppSum(angle);
1790                break;
1791            }
1792            if (++firstIndex == angleCount) {
1793                return SK_MinS32;
1794            }
1795        } while (true);
1796        // turn winding into contourWinding
1797        int spanWinding = base->spanSign(angle);
1798        bool inner = useInnerWinding(winding + spanWinding, winding);
1799    #if DEBUG_WINDING
1800        SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
1801            spanWinding, winding, angle->sign(), inner,
1802            inner ? winding + spanWinding : winding);
1803    #endif
1804        if (inner) {
1805            winding += spanWinding;
1806        }
1807    #if DEBUG_SORT
1808        base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
1809    #endif
1810        int nextIndex = firstIndex + 1;
1811        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1812        winding -= base->spanSign(angle);
1813        oWinding -= base->oppSign(angle);
1814        do {
1815            if (nextIndex == angleCount) {
1816                nextIndex = 0;
1817            }
1818            angle = sorted[nextIndex];
1819            Segment* segment = angle->segment();
1820            bool opp = base->fOperand ^ segment->fOperand;
1821            int maxWinding, oMaxWinding;
1822            int spanSign = segment->spanSign(angle);
1823            int oppoSign = segment->oppSign(angle);
1824            if (opp) {
1825                oMaxWinding = oWinding;
1826                oWinding -= spanSign;
1827                maxWinding = winding;
1828                if (oppoSign) {
1829                    winding -= oppoSign;
1830                }
1831            } else {
1832                maxWinding = winding;
1833                winding -= spanSign;
1834                oMaxWinding = oWinding;
1835                if (oppoSign) {
1836                    oWinding -= oppoSign;
1837                }
1838            }
1839            if (segment->windSum(angle) == SK_MinS32) {
1840                if (opp) {
1841                    if (useInnerWinding(oMaxWinding, oWinding)) {
1842                        oMaxWinding = oWinding;
1843                    }
1844                    if (oppoSign && useInnerWinding(maxWinding, winding)) {
1845                        maxWinding = winding;
1846                    }
1847                    (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
1848                } else {
1849                    if (useInnerWinding(maxWinding, winding)) {
1850                        maxWinding = winding;
1851                    }
1852                    if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
1853                        oMaxWinding = oWinding;
1854                    }
1855                    (void) segment->markAndChaseWinding(angle, maxWinding,
1856                            binary ? oMaxWinding : 0);
1857                }
1858            }
1859        } while (++nextIndex != lastIndex);
1860        int minIndex = SkMin32(startIndex, endIndex);
1861        return windSum(minIndex);
1862    }
1863
1864    int crossedSpanX(const SkPoint& basePt, SkScalar& bestX, double& hitT, bool opp) const {
1865        int bestT = -1;
1866        SkScalar left = bounds().fLeft;
1867        SkScalar right = bounds().fRight;
1868        int end = 0;
1869        do {
1870            int start = end;
1871            end = nextSpan(start, 1);
1872            if ((opp ? fTs[start].fOppValue : fTs[start].fWindValue) == 0) {
1873                continue;
1874            }
1875            SkPoint edge[4];
1876            double startT = fTs[start].fT;
1877            double endT = fTs[end].fT;
1878            (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
1879            // intersect ray starting at basePt with edge
1880            Intersections intersections;
1881            // FIXME: always use original and limit results to T values within
1882            // start t and end t.
1883            // OPTIMIZE: use specialty function that intersects ray with curve,
1884            // returning t values only for curve (we don't care about t on ray)
1885            int pts = (*HSegmentIntersect[fVerb])(edge, left, right, basePt.fY,
1886                    false, intersections);
1887            if (pts == 0) {
1888                continue;
1889            }
1890            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1891            // if the intersection is edge on, wait for another one
1892                continue;
1893            }
1894            for (int index = 0; index < pts; ++index) {
1895                double foundT = intersections.fT[0][index];
1896                double testT = startT + (endT - startT) * foundT;
1897                SkScalar testX = (*SegmentXAtT[fVerb])(fPts, testT);
1898                if (bestX < testX && testX < basePt.fX) {
1899                    if (fVerb > SkPath::kLine_Verb
1900                            && !approximately_less_than_zero(foundT)
1901                            && !approximately_greater_than_one(foundT)) {
1902                        SkScalar dy = (*SegmentDYAtT[fVerb])(fPts, testT);
1903                        if (approximately_zero(dy)) {
1904                            continue;
1905                        }
1906                    }
1907                    bestX = testX;
1908                    bestT = foundT < 1 ? start : end;
1909                    hitT = testT;
1910                }
1911            }
1912        } while (fTs[end].fT != 1);
1913        return bestT;
1914    }
1915
1916    int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool opp) const {
1917        int bestT = -1;
1918        SkScalar top = bounds().fTop;
1919        SkScalar bottom = bounds().fBottom;
1920        int end = 0;
1921        do {
1922            int start = end;
1923            end = nextSpan(start, 1);
1924            if ((opp ? fTs[start].fOppValue : fTs[start].fWindValue) == 0) {
1925                continue;
1926            }
1927            SkPoint edge[4];
1928            double startT = fTs[start].fT;
1929            double endT = fTs[end].fT;
1930            (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
1931            // intersect ray starting at basePt with edge
1932            Intersections intersections;
1933            // FIXME: always use original and limit results to T values within
1934            // start t and end t.
1935            // OPTIMIZE: use specialty function that intersects ray with curve,
1936            // returning t values only for curve (we don't care about t on ray)
1937            int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
1938                    false, intersections);
1939            if (pts == 0) {
1940                continue;
1941            }
1942            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1943            // if the intersection is edge on, wait for another one
1944                continue;
1945            }
1946            for (int index = 0; index < pts; ++index) {
1947                double foundT = intersections.fT[0][index];
1948                double testT = startT + (endT - startT) * foundT;
1949                SkScalar testY = (*SegmentYAtT[fVerb])(fPts, testT);
1950                if (bestY < testY && testY < basePt.fY) {
1951                    if (fVerb > SkPath::kLine_Verb
1952                            && !approximately_less_than_zero(foundT)
1953                            && !approximately_greater_than_one(foundT)) {
1954                        SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, testT);
1955                        if (approximately_zero(dx)) {
1956                            continue;
1957                        }
1958                    }
1959                    bestY = testY;
1960                    bestT = foundT < 1 ? start : end;
1961                    hitT = testT;
1962                }
1963            }
1964        } while (fTs[end].fT != 1);
1965        return bestT;
1966    }
1967
1968    void decrementSpan(Span* span) {
1969        SkASSERT(span->fWindValue > 0);
1970        if (--(span->fWindValue) == 0) {
1971            if (!span->fOppValue && !span->fDone) {
1972                span->fDone = true;
1973                ++fDoneSpans;
1974            }
1975        }
1976    }
1977
1978    bool bumpSpan(Span* span, int windDelta, int oppDelta) {
1979        SkASSERT(!span->fDone);
1980        span->fWindValue += windDelta;
1981        SkASSERT(span->fWindValue >= 0);
1982        span->fOppValue += oppDelta;
1983        SkASSERT(span->fOppValue >= 0);
1984        if (fXor) {
1985            span->fWindValue &= 1;
1986        }
1987        if (fOppXor) {
1988            span->fOppValue &= 1;
1989        }
1990        if (!span->fWindValue && !span->fOppValue) {
1991            span->fDone = true;
1992            ++fDoneSpans;
1993            return true;
1994        }
1995        return false;
1996    }
1997
1998    // OPTIMIZE
1999    // when the edges are initially walked, they don't automatically get the prior and next
2000    // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
2001    // and would additionally remove the need for similar checks in condition edges. It would
2002    // also allow intersection code to assume end of segment intersections (maybe?)
2003    bool complete() const {
2004        int count = fTs.count();
2005        return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
2006    }
2007
2008    bool done() const {
2009        SkASSERT(fDoneSpans <= fTs.count());
2010        return fDoneSpans == fTs.count();
2011    }
2012
2013    bool done(int min) const {
2014        return fTs[min].fDone;
2015    }
2016
2017    bool done(const Angle* angle) const {
2018        return done(SkMin32(angle->start(), angle->end()));
2019    }
2020
2021    /*
2022     The M and S variable name parts stand for the operators.
2023       Mi stands for Minuend (see wiki subtraction, analogous to difference)
2024       Su stands for Subtrahend
2025     The Opp variable name part designates that the value is for the Opposite operator.
2026     Opposite values result from combining coincident spans.
2027     */
2028
2029    Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
2030            bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMask) {
2031        const int startIndex = nextStart;
2032        const int endIndex = nextEnd;
2033        SkASSERT(startIndex != endIndex);
2034        const int count = fTs.count();
2035        SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2036        const int step = SkSign32(endIndex - startIndex);
2037        const int end = nextExactSpan(startIndex, step);
2038        SkASSERT(end >= 0);
2039        Span* endSpan = &fTs[end];
2040        Segment* other;
2041        if (isSimple(end)) {
2042        // mark the smaller of startIndex, endIndex done, and all adjacent
2043        // spans with the same T value (but not 'other' spans)
2044    #if DEBUG_WINDING
2045            SkDebugf("%s simple\n", __FUNCTION__);
2046    #endif
2047            int min = SkMin32(startIndex, endIndex);
2048            if (fTs[min].fDone) {
2049                return NULL;
2050            }
2051            markDoneBinary(min);
2052            other = endSpan->fOther;
2053            nextStart = endSpan->fOtherIndex;
2054            double startT = other->fTs[nextStart].fT;
2055            nextEnd = nextStart;
2056            do {
2057                nextEnd += step;
2058            }
2059            while (precisely_zero(startT - other->fTs[nextEnd].fT));
2060            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2061            return other;
2062        }
2063        // more than one viable candidate -- measure angles to find best
2064        SkTDArray<Angle> angles;
2065        SkASSERT(startIndex - endIndex != 0);
2066        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2067        addTwoAngles(startIndex, end, angles);
2068        buildAngles(end, angles, true);
2069        SkTDArray<Angle*> sorted;
2070        bool sortable = SortAngles(angles, sorted);
2071        int angleCount = angles.count();
2072        int firstIndex = findStartingEdge(sorted, startIndex, end);
2073        SkASSERT(firstIndex >= 0);
2074    #if DEBUG_SORT
2075        debugShowSort(__FUNCTION__, sorted, firstIndex);
2076    #endif
2077        if (!sortable) {
2078            unsortable = true;
2079            return NULL;
2080        }
2081        SkASSERT(sorted[firstIndex]->segment() == this);
2082    #if DEBUG_WINDING
2083        SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
2084                sorted[firstIndex]->sign());
2085    #endif
2086        int sumMiWinding = updateWinding(endIndex, startIndex);
2087        int sumSuWinding = updateOppWinding(endIndex, startIndex);
2088        if (operand()) {
2089            SkTSwap<int>(sumMiWinding, sumSuWinding);
2090        }
2091        int nextIndex = firstIndex + 1;
2092        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2093        const Angle* foundAngle = NULL;
2094        bool foundDone = false;
2095        // iterate through the angle, and compute everyone's winding
2096        Segment* nextSegment;
2097        do {
2098            SkASSERT(nextIndex != firstIndex);
2099            if (nextIndex == angleCount) {
2100                nextIndex = 0;
2101            }
2102            const Angle* nextAngle = sorted[nextIndex];
2103            nextSegment = nextAngle->segment();
2104            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
2105            bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2106                    nextAngle->end(), op, sumMiWinding, sumSuWinding,
2107                    maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
2108            if (activeAngle && (!foundAngle || foundDone)) {
2109                foundAngle = nextAngle;
2110                foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
2111            }
2112            if (nextSegment->done()) {
2113                continue;
2114            }
2115            if (nextSegment->windSum(nextAngle) != SK_MinS32) {
2116                continue;
2117            }
2118            Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
2119                    oppSumWinding, activeAngle, nextAngle);
2120            if (last) {
2121                *chase.append() = last;
2122#if DEBUG_WINDING
2123                SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2124                        last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2125#endif
2126            }
2127        } while (++nextIndex != lastIndex);
2128        markDoneBinary(SkMin32(startIndex, endIndex));
2129        if (!foundAngle) {
2130            return NULL;
2131        }
2132        nextStart = foundAngle->start();
2133        nextEnd = foundAngle->end();
2134        nextSegment = foundAngle->segment();
2135
2136    #if DEBUG_WINDING
2137        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2138                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2139     #endif
2140        return nextSegment;
2141    }
2142
2143    // so the span needs to contain the pairing info found here
2144    // this should include the winding computed for the edge, and
2145    //  what edge it connects to, and whether it is discarded
2146    //  (maybe discarded == abs(winding) > 1) ?
2147    // only need derivatives for duration of sorting, add a new struct
2148    // for pairings, remove extra spans that have zero length and
2149    //  reference an unused other
2150    // for coincident, the last span on the other may be marked done
2151    //  (always?)
2152
2153    // if loop is exhausted, contour may be closed.
2154    // FIXME: pass in close point so we can check for closure
2155
2156    // given a segment, and a sense of where 'inside' is, return the next
2157    // segment. If this segment has an intersection, or ends in multiple
2158    // segments, find the mate that continues the outside.
2159    // note that if there are multiples, but no coincidence, we can limit
2160    // choices to connections in the correct direction
2161
2162    // mark found segments as done
2163
2164    // start is the index of the beginning T of this edge
2165    // it is guaranteed to have an end which describes a non-zero length (?)
2166    // winding -1 means ccw, 1 means cw
2167    Segment* findNextWinding(SkTDArray<Span*>& chase, bool active,
2168            int& nextStart, int& nextEnd, int& winding, int& spanWinding,
2169            bool& unsortable) {
2170        const int startIndex = nextStart;
2171        const int endIndex = nextEnd;
2172        int outerWinding = winding;
2173        int innerWinding = winding + spanWinding;
2174    #if DEBUG_WINDING
2175        SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n",
2176                __FUNCTION__, winding, spanWinding, outerWinding, innerWinding);
2177    #endif
2178        if (useInnerWinding(outerWinding, innerWinding)) {
2179            outerWinding = innerWinding;
2180        }
2181        SkASSERT(startIndex != endIndex);
2182        int count = fTs.count();
2183        SkASSERT(startIndex < endIndex ? startIndex < count - 1
2184                : startIndex > 0);
2185        int step = SkSign32(endIndex - startIndex);
2186        int end = nextExactSpan(startIndex, step);
2187        SkASSERT(end >= 0);
2188        Span* endSpan = &fTs[end];
2189        Segment* other;
2190        if (isSimple(end)) {
2191        // mark the smaller of startIndex, endIndex done, and all adjacent
2192        // spans with the same T value (but not 'other' spans)
2193    #if DEBUG_WINDING
2194            SkDebugf("%s simple\n", __FUNCTION__);
2195    #endif
2196            int min = SkMin32(startIndex, endIndex);
2197            if (fTs[min].fDone) {
2198                return NULL;
2199            }
2200            markDone(min, outerWinding);
2201            other = endSpan->fOther;
2202            nextStart = endSpan->fOtherIndex;
2203            double startT = other->fTs[nextStart].fT;
2204            nextEnd = nextStart;
2205            do {
2206                nextEnd += step;
2207            }
2208             while (precisely_zero(startT - other->fTs[nextEnd].fT));
2209            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2210            return other;
2211        }
2212        // more than one viable candidate -- measure angles to find best
2213        SkTDArray<Angle> angles;
2214        SkASSERT(startIndex - endIndex != 0);
2215        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2216        addTwoAngles(startIndex, end, angles);
2217        buildAngles(end, angles, false);
2218        SkTDArray<Angle*> sorted;
2219        bool sortable = SortAngles(angles, sorted);
2220        int angleCount = angles.count();
2221        int firstIndex = findStartingEdge(sorted, startIndex, end);
2222        SkASSERT(firstIndex >= 0);
2223    #if DEBUG_SORT
2224        debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);
2225    #endif
2226        if (!sortable) {
2227            unsortable = true;
2228            return NULL;
2229        }
2230        SkASSERT(sorted[firstIndex]->segment() == this);
2231    #if DEBUG_WINDING
2232        SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign());
2233    #endif
2234        int sumWinding = winding - spanSign(sorted[firstIndex]);
2235        int nextIndex = firstIndex + 1;
2236        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2237        const Angle* foundAngle = NULL;
2238        // FIXME: found done logic probably fails if there are more than 4
2239        // sorted angles. It should bias towards the first and last undone
2240        // edges -- but not sure that it won't choose a middle (incorrect)
2241        // edge if one is undone
2242        bool foundDone = false;
2243        bool foundDone2 = false;
2244        // iterate through the angle, and compute everyone's winding
2245        bool altFlipped = false;
2246        bool foundFlipped = false;
2247        int foundSum = SK_MinS32;
2248        Segment* nextSegment;
2249        int lastNonZeroSum = winding;
2250        do {
2251            if (nextIndex == angleCount) {
2252                nextIndex = 0;
2253            }
2254            const Angle* nextAngle = sorted[nextIndex];
2255            int maxWinding = sumWinding;
2256            if (sumWinding) {
2257                lastNonZeroSum = sumWinding;
2258            }
2259            nextSegment = nextAngle->segment();
2260            bool nextDone = nextSegment->done(nextAngle);
2261            bool nextTiny = nextSegment->tiny(nextAngle);
2262            sumWinding -= nextSegment->spanSign(nextAngle);
2263            altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
2264    #if 0 && DEBUG_WINDING
2265            SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
2266            SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
2267                    nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
2268    #endif
2269           if (!sumWinding) {
2270                if (!active) {
2271                    // FIXME: shouldn't this call mark and chase done ?
2272                    markDone(SkMin32(startIndex, endIndex), outerWinding);
2273                    // FIXME: shouldn't this call mark and chase winding ?
2274                    nextSegment->markWinding(SkMin32(nextAngle->start(),
2275                                nextAngle->end()), maxWinding);
2276    #if DEBUG_WINDING
2277                    SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex);
2278    #endif
2279                    return NULL;
2280                }
2281                if (!foundAngle || foundDone) {
2282                    foundAngle = nextAngle;
2283                    foundDone = nextDone && !nextTiny;
2284                    foundFlipped = altFlipped;
2285                }
2286                continue;
2287            }
2288
2289            if (!maxWinding && (!foundAngle || foundDone2)) {
2290        #if DEBUG_WINDING
2291                if (foundAngle && foundDone2) {
2292                    SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex);
2293                }
2294        #endif
2295                foundAngle = nextAngle;
2296                foundDone2 = nextDone && !nextTiny;
2297                foundFlipped = altFlipped;
2298                foundSum = sumWinding;
2299            }
2300            if (nextSegment->done()) {
2301                continue;
2302            }
2303            // if the winding is non-zero, nextAngle does not connect to
2304            // current chain. If we haven't done so already, mark the angle
2305            // as done, record the winding value, and mark connected unambiguous
2306            // segments as well.
2307            if (nextSegment->windSum(nextAngle) == SK_MinS32) {
2308                if (useInnerWinding(maxWinding, sumWinding)) {
2309                    maxWinding = sumWinding;
2310                }
2311                Span* last;
2312                if (foundAngle) {
2313                    last = nextSegment->markAndChaseWinding(nextAngle, maxWinding);
2314                } else {
2315                    last = nextSegment->markAndChaseDone(nextAngle, maxWinding);
2316                }
2317                if (last) {
2318                    *chase.append() = last;
2319    #if DEBUG_WINDING
2320                    SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2321                            last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2322    #endif
2323                }
2324            }
2325        } while (++nextIndex != lastIndex);
2326        markDone(SkMin32(startIndex, endIndex), outerWinding);
2327        if (!foundAngle) {
2328            return NULL;
2329        }
2330        nextStart = foundAngle->start();
2331        nextEnd = foundAngle->end();
2332        nextSegment = foundAngle->segment();
2333        int flipped = foundFlipped ? -1 : 1;
2334        spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(
2335                SkMin32(nextStart, nextEnd));
2336        if (winding) {
2337    #if DEBUG_WINDING
2338            SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding);
2339            if (foundSum == SK_MinS32) {
2340                SkDebugf("?");
2341            } else {
2342                SkDebugf("%d", foundSum);
2343            }
2344            SkDebugf("\n");
2345     #endif
2346            winding = foundSum;
2347        }
2348    #if DEBUG_WINDING
2349        SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped);
2350    #endif
2351        return nextSegment;
2352    }
2353
2354    Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) {
2355        const int startIndex = nextStart;
2356        const int endIndex = nextEnd;
2357        SkASSERT(startIndex != endIndex);
2358        int count = fTs.count();
2359        SkASSERT(startIndex < endIndex ? startIndex < count - 1
2360                : startIndex > 0);
2361        int step = SkSign32(endIndex - startIndex);
2362        int end = nextExactSpan(startIndex, step);
2363        SkASSERT(end >= 0);
2364        Span* endSpan = &fTs[end];
2365        Segment* other;
2366        if (isSimple(end)) {
2367    #if DEBUG_WINDING
2368            SkDebugf("%s simple\n", __FUNCTION__);
2369    #endif
2370            int min = SkMin32(startIndex, endIndex);
2371            if (fTs[min].fDone) {
2372                return NULL;
2373            }
2374            markDone(min, 1);
2375            other = endSpan->fOther;
2376            nextStart = endSpan->fOtherIndex;
2377            double startT = other->fTs[nextStart].fT;
2378            SkDEBUGCODE(bool firstLoop = true;)
2379            if ((approximately_less_than_zero(startT) && step < 0)
2380                    || (approximately_greater_than_one(startT) && step > 0)) {
2381                step = -step;
2382                SkDEBUGCODE(firstLoop = false;)
2383            }
2384            do {
2385                nextEnd = nextStart;
2386                do {
2387                    nextEnd += step;
2388                }
2389                 while (precisely_zero(startT - other->fTs[nextEnd].fT));
2390                if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
2391                    break;
2392                }
2393 #ifdef SK_DEBUG
2394                SkASSERT(firstLoop);
2395 #endif
2396                SkDEBUGCODE(firstLoop = false;)
2397                step = -step;
2398            } while (true);
2399            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2400            return other;
2401        }
2402        SkTDArray<Angle> angles;
2403        SkASSERT(startIndex - endIndex != 0);
2404        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2405        addTwoAngles(startIndex, end, angles);
2406        buildAngles(end, angles, false);
2407        SkTDArray<Angle*> sorted;
2408        bool sortable = SortAngles(angles, sorted);
2409        if (!sortable) {
2410            unsortable = true;
2411            return NULL;
2412        }
2413        int angleCount = angles.count();
2414        int firstIndex = findStartingEdge(sorted, startIndex, end);
2415        SkASSERT(firstIndex >= 0);
2416    #if DEBUG_SORT
2417        debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
2418    #endif
2419        SkASSERT(sorted[firstIndex]->segment() == this);
2420        int nextIndex = firstIndex + 1;
2421        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2422        const Angle* nextAngle;
2423        Segment* nextSegment;
2424        bool foundAngle = false;
2425        do {
2426            if (nextIndex == angleCount) {
2427                nextIndex = 0;
2428            }
2429            nextAngle = sorted[nextIndex];
2430            nextSegment = nextAngle->segment();
2431            if (!nextSegment->done(nextAngle) || nextSegment->tiny(nextAngle)) {
2432                foundAngle = true;
2433                break;
2434            }
2435        } while (++nextIndex != lastIndex);
2436        markDone(SkMin32(startIndex, endIndex), 1);
2437        if (!foundAngle) {
2438            nextIndex = firstIndex + 1 == angleCount ? 0 : firstIndex + 1;
2439            nextAngle = sorted[nextIndex];
2440        }
2441        nextStart = nextAngle->start();
2442        nextEnd = nextAngle->end();
2443        return nextSegment;
2444    }
2445
2446    int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
2447        int angleCount = sorted.count();
2448        int firstIndex = -1;
2449        for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2450            const Angle* angle = sorted[angleIndex];
2451            if (angle->segment() == this && angle->start() == end &&
2452                    angle->end() == start) {
2453                firstIndex = angleIndex;
2454                break;
2455            }
2456        }
2457        return firstIndex;
2458    }
2459
2460    // FIXME: this is tricky code; needs its own unit test
2461    void findTooCloseToCall() {
2462        int count = fTs.count();
2463        if (count < 3) { // require t=0, x, 1 at minimum
2464            return;
2465        }
2466        int matchIndex = 0;
2467        int moCount;
2468        Span* match;
2469        Segment* mOther;
2470        do {
2471            match = &fTs[matchIndex];
2472            mOther = match->fOther;
2473            // FIXME: allow quads, cubics to be near coincident?
2474            if (mOther->fVerb == SkPath::kLine_Verb) {
2475                moCount = mOther->fTs.count();
2476                if (moCount >= 3) {
2477                    break;
2478                }
2479            }
2480            if (++matchIndex >= count) {
2481                return;
2482            }
2483        } while (true); // require t=0, x, 1 at minimum
2484        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
2485        const SkPoint* matchPt = &xyAtT(match);
2486        // look for a pair of nearby T values that map to the same (x,y) value
2487        // if found, see if the pair of other segments share a common point. If
2488        // so, the span from here to there is coincident.
2489        for (int index = matchIndex + 1; index < count; ++index) {
2490            Span* test = &fTs[index];
2491            if (test->fDone) {
2492                continue;
2493            }
2494            Segment* tOther = test->fOther;
2495            if (tOther->fVerb != SkPath::kLine_Verb) {
2496                continue; // FIXME: allow quads, cubics to be near coincident?
2497            }
2498            int toCount = tOther->fTs.count();
2499            if (toCount < 3) { // require t=0, x, 1 at minimum
2500                continue;
2501            }
2502            const SkPoint* testPt = &xyAtT(test);
2503            if (*matchPt != *testPt) {
2504                matchIndex = index;
2505                moCount = toCount;
2506                match = test;
2507                mOther = tOther;
2508                matchPt = testPt;
2509                continue;
2510            }
2511            int moStart = -1;
2512            int moEnd = -1;
2513            double moStartT, moEndT;
2514            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
2515                Span& moSpan = mOther->fTs[moIndex];
2516                if (moSpan.fDone) {
2517                    continue;
2518                }
2519                if (moSpan.fOther == this) {
2520                    if (moSpan.fOtherT == match->fT) {
2521                        moStart = moIndex;
2522                        moStartT = moSpan.fT;
2523                    }
2524                    continue;
2525                }
2526                if (moSpan.fOther == tOther) {
2527                    if (tOther->fTs[moSpan.fOtherIndex].fWindValue == 0) {
2528                        moStart = -1;
2529                        break;
2530                    }
2531                    SkASSERT(moEnd == -1);
2532                    moEnd = moIndex;
2533                    moEndT = moSpan.fT;
2534                }
2535            }
2536            if (moStart < 0 || moEnd < 0) {
2537                continue;
2538            }
2539            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
2540            if (approximately_equal(moStartT, moEndT)) {
2541                continue;
2542            }
2543            int toStart = -1;
2544            int toEnd = -1;
2545            double toStartT, toEndT;
2546            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
2547                Span& toSpan = tOther->fTs[toIndex];
2548                if (toSpan.fDone) {
2549                    continue;
2550                }
2551                if (toSpan.fOther == this) {
2552                    if (toSpan.fOtherT == test->fT) {
2553                        toStart = toIndex;
2554                        toStartT = toSpan.fT;
2555                    }
2556                    continue;
2557                }
2558                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
2559                    if (mOther->fTs[toSpan.fOtherIndex].fWindValue == 0) {
2560                        moStart = -1;
2561                        break;
2562                    }
2563                    SkASSERT(toEnd == -1);
2564                    toEnd = toIndex;
2565                    toEndT = toSpan.fT;
2566                }
2567            }
2568            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
2569            if (toStart <= 0 || toEnd <= 0) {
2570                continue;
2571            }
2572            if (approximately_equal(toStartT, toEndT)) {
2573                continue;
2574            }
2575            // test to see if the segment between there and here is linear
2576            if (!mOther->isLinear(moStart, moEnd)
2577                    || !tOther->isLinear(toStart, toEnd)) {
2578                continue;
2579            }
2580            bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
2581            if (flipped) {
2582                mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
2583            } else {
2584                mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEndT);
2585            }
2586        }
2587    }
2588
2589 //   start here;
2590    // either:
2591    // a) mark spans with either end unsortable as done, or
2592    // b) rewrite findTop / findTopSegment / findTopContour to iterate further
2593    //    when encountering an unsortable span
2594
2595    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
2596    // and use more concise logic like the old edge walker code?
2597    // FIXME: this needs to deal with coincident edges
2598    Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable) {
2599        // iterate through T intersections and return topmost
2600        // topmost tangent from y-min to first pt is closer to horizontal
2601        SkASSERT(!done());
2602        int firstT = -1;
2603        SkPoint topPt;
2604        topPt.fY = SK_ScalarMax;
2605        int count = fTs.count();
2606        // see if either end is not done since we want smaller Y of the pair
2607        bool lastDone = true;
2608        bool lastUnsortable = false;
2609        for (int index = 0; index < count; ++index) {
2610            const Span& span = fTs[index];
2611            if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
2612                goto next;
2613            }
2614            if (!span.fDone | !lastDone) {
2615                const SkPoint& intercept = xyAtT(&span);
2616                if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
2617                        && topPt.fX > intercept.fX)) {
2618                    topPt = intercept;
2619                    firstT = index;
2620                }
2621            }
2622    next:
2623            lastDone = span.fDone;
2624            lastUnsortable = span.fUnsortableEnd;
2625        }
2626        SkASSERT(firstT >= 0);
2627        // sort the edges to find the leftmost
2628        int step = 1;
2629        int end = nextSpan(firstT, step);
2630        if (end == -1) {
2631            step = -1;
2632            end = nextSpan(firstT, step);
2633            SkASSERT(end != -1);
2634        }
2635        // if the topmost T is not on end, or is three-way or more, find left
2636        // look for left-ness from tLeft to firstT (matching y of other)
2637        SkTDArray<Angle> angles;
2638        SkASSERT(firstT - end != 0);
2639        addTwoAngles(end, firstT, angles);
2640        buildAngles(firstT, angles, true);
2641        SkTDArray<Angle*> sorted;
2642        bool sortable = SortAngles(angles, sorted);
2643    #if DEBUG_SORT
2644        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
2645    #endif
2646        if (onlySortable && !sortable) {
2647            unsortable = true;
2648            return NULL;
2649        }
2650        // skip edges that have already been processed
2651        firstT = -1;
2652        Segment* leftSegment;
2653        do {
2654            const Angle* angle = sorted[++firstT];
2655            SkASSERT(!onlySortable || !angle->unsortable());
2656            leftSegment = angle->segment();
2657            tIndex = angle->end();
2658            endIndex = angle->start();
2659        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
2660        SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
2661        return leftSegment;
2662    }
2663
2664    // FIXME: not crazy about this
2665    // when the intersections are performed, the other index is into an
2666    // incomplete array. as the array grows, the indices become incorrect
2667    // while the following fixes the indices up again, it isn't smart about
2668    // skipping segments whose indices are already correct
2669    // assuming we leave the code that wrote the index in the first place
2670    void fixOtherTIndex() {
2671        int iCount = fTs.count();
2672        for (int i = 0; i < iCount; ++i) {
2673            Span& iSpan = fTs[i];
2674            double oT = iSpan.fOtherT;
2675            Segment* other = iSpan.fOther;
2676            int oCount = other->fTs.count();
2677            for (int o = 0; o < oCount; ++o) {
2678                Span& oSpan = other->fTs[o];
2679                if (oT == oSpan.fT && this == oSpan.fOther) {
2680                    iSpan.fOtherIndex = o;
2681                    break;
2682                }
2683            }
2684        }
2685    }
2686
2687    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
2688        fDoneSpans = 0;
2689        fOperand = operand;
2690        fXor = evenOdd;
2691        fPts = pts;
2692        fVerb = verb;
2693    }
2694
2695    void initWinding(int start, int end, int winding, int oppWinding) {
2696        int local = spanSign(start, end);
2697        if (local * winding >= 0) {
2698            winding += local;
2699        }
2700        local = oppSign(start, end);
2701        if (local * oppWinding >= 0) {
2702            oppWinding += local;
2703        }
2704        (void) markAndChaseWinding(start, end, winding, oppWinding);
2705    }
2706
2707    bool intersected() const {
2708        return fTs.count() > 0;
2709    }
2710
2711    bool isConnected(int startIndex, int endIndex) const {
2712        return fTs[startIndex].fWindSum != SK_MinS32
2713                || fTs[endIndex].fWindSum != SK_MinS32;
2714    }
2715
2716    bool isHorizontal() const {
2717        return fBounds.fTop == fBounds.fBottom;
2718    }
2719
2720    bool isLinear(int start, int end) const {
2721        if (fVerb == SkPath::kLine_Verb) {
2722            return true;
2723        }
2724        if (fVerb == SkPath::kQuad_Verb) {
2725            SkPoint qPart[3];
2726            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
2727            return QuadIsLinear(qPart);
2728        } else {
2729            SkASSERT(fVerb == SkPath::kCubic_Verb);
2730            SkPoint cPart[4];
2731            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
2732            return CubicIsLinear(cPart);
2733        }
2734    }
2735
2736    // OPTIMIZE: successive calls could start were the last leaves off
2737    // or calls could specialize to walk forwards or backwards
2738    bool isMissing(double startT) const {
2739        size_t tCount = fTs.count();
2740        for (size_t index = 0; index < tCount; ++index) {
2741            if (approximately_zero(startT - fTs[index].fT)) {
2742                return false;
2743            }
2744        }
2745        return true;
2746    }
2747
2748    bool isSimple(int end) const {
2749        int count = fTs.count();
2750        if (count == 2) {
2751            return true;
2752        }
2753        double t = fTs[end].fT;
2754        if (approximately_less_than_zero(t)) {
2755            return !approximately_less_than_zero(fTs[1].fT);
2756        }
2757        if (approximately_greater_than_one(t)) {
2758            return !approximately_greater_than_one(fTs[count - 2].fT);
2759        }
2760        return false;
2761    }
2762
2763    bool isVertical() const {
2764        return fBounds.fLeft == fBounds.fRight;
2765    }
2766
2767    SkScalar leftMost(int start, int end) const {
2768        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
2769    }
2770
2771    // this span is excluded by the winding rule -- chase the ends
2772    // as long as they are unambiguous to mark connections as done
2773    // and give them the same winding value
2774    Span* markAndChaseDone(const Angle* angle, int winding) {
2775        int index = angle->start();
2776        int endIndex = angle->end();
2777        return markAndChaseDone(index, endIndex, winding);
2778    }
2779
2780    Span* markAndChaseDone(int index, int endIndex, int winding) {
2781        int step = SkSign32(endIndex - index);
2782        int min = SkMin32(index, endIndex);
2783        markDone(min, winding);
2784        Span* last;
2785        Segment* other = this;
2786        while ((other = other->nextChase(index, step, min, last))) {
2787            other->markDone(min, winding);
2788        }
2789        return last;
2790    }
2791
2792    Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding) {
2793        int index = angle->start();
2794        int endIndex = angle->end();
2795        int step = SkSign32(endIndex - index);
2796        int min = SkMin32(index, endIndex);
2797        markDoneBinary(min, winding, oppWinding);
2798        Span* last;
2799        Segment* other = this;
2800        while ((other = other->nextChase(index, step, min, last))) {
2801            other->markDoneBinary(min, winding, oppWinding);
2802        }
2803        return last;
2804    }
2805
2806    Span* markAndChaseDoneBinary(int index, int endIndex) {
2807        int step = SkSign32(endIndex - index);
2808        int min = SkMin32(index, endIndex);
2809        markDoneBinary(min);
2810        Span* last;
2811        Segment* other = this;
2812        while ((other = other->nextChase(index, step, min, last))) {
2813            if (other->done()) {
2814                return NULL;
2815            }
2816            other->markDoneBinary(min);
2817        }
2818        return last;
2819    }
2820
2821    Span* markAndChaseWinding(const Angle* angle, const int winding) {
2822        int index = angle->start();
2823        int endIndex = angle->end();
2824        int step = SkSign32(endIndex - index);
2825        int min = SkMin32(index, endIndex);
2826        markWinding(min, winding);
2827        Span* last;
2828        Segment* other = this;
2829        while ((other = other->nextChase(index, step, min, last))) {
2830            if (other->fTs[min].fWindSum != SK_MinS32) {
2831                SkASSERT(other->fTs[min].fWindSum == winding);
2832                return NULL;
2833            }
2834            other->markWinding(min, winding);
2835        }
2836        return last;
2837    }
2838
2839    Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
2840        int min = SkMin32(index, endIndex);
2841        int step = SkSign32(endIndex - index);
2842        markWinding(min, winding, oppWinding);
2843        Span* last;
2844        Segment* other = this;
2845        while ((other = other->nextChase(index, step, min, last))) {
2846            if (other->fTs[min].fWindSum != SK_MinS32) {
2847                SkASSERT(other->fTs[min].fWindSum == winding);
2848                return NULL;
2849            }
2850            other->markWinding(min, winding, oppWinding);
2851        }
2852        return last;
2853    }
2854
2855    Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) {
2856        int start = angle->start();
2857        int end = angle->end();
2858        return markAndChaseWinding(start, end, winding, oppWinding);
2859    }
2860
2861    Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
2862            bool activeAngle, const Angle* angle) {
2863        SkASSERT(angle->segment() == this);
2864        if (useInnerWinding(maxWinding, sumWinding)) {
2865            maxWinding = sumWinding;
2866        }
2867        if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, oppSumWinding)) {
2868            oppMaxWinding = oppSumWinding;
2869        }
2870        Span* last;
2871        if (activeAngle) {
2872            last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
2873        } else {
2874            last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
2875        }
2876        return last;
2877    }
2878
2879    // FIXME: this should also mark spans with equal (x,y)
2880    // This may be called when the segment is already marked done. While this
2881    // wastes time, it shouldn't do any more than spin through the T spans.
2882    // OPTIMIZATION: abort on first done found (assuming that this code is
2883    // always called to mark segments done).
2884    void markDone(int index, int winding) {
2885      //  SkASSERT(!done());
2886        SkASSERT(winding);
2887        double referenceT = fTs[index].fT;
2888        int lesser = index;
2889        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2890            markOneDone(__FUNCTION__, lesser, winding);
2891        }
2892        do {
2893            markOneDone(__FUNCTION__, index, winding);
2894        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2895    }
2896
2897    void markDoneBinary(int index, int winding, int oppWinding) {
2898      //  SkASSERT(!done());
2899        SkASSERT(winding || oppWinding);
2900        double referenceT = fTs[index].fT;
2901        int lesser = index;
2902        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2903            markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);
2904        }
2905        do {
2906            markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);
2907        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2908    }
2909
2910    void markDoneBinary(int index) {
2911        double referenceT = fTs[index].fT;
2912        int lesser = index;
2913        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2914            markOneDoneBinary(__FUNCTION__, lesser);
2915        }
2916        do {
2917            markOneDoneBinary(__FUNCTION__, index);
2918        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2919    }
2920
2921    void markOneDone(const char* funName, int tIndex, int winding) {
2922        Span* span = markOneWinding(funName, tIndex, winding);
2923        if (!span) {
2924            return;
2925        }
2926        span->fDone = true;
2927        fDoneSpans++;
2928    }
2929
2930    void markOneDoneBinary(const char* funName, int tIndex) {
2931        Span* span = verifyOneWinding(funName, tIndex);
2932        if (!span) {
2933            return;
2934        }
2935        span->fDone = true;
2936        fDoneSpans++;
2937    }
2938
2939    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) {
2940        Span* span = markOneWinding(funName, tIndex, winding, oppWinding);
2941        if (!span) {
2942            return;
2943        }
2944        span->fDone = true;
2945        fDoneSpans++;
2946    }
2947
2948    Span* markOneWinding(const char* funName, int tIndex, int winding) {
2949        Span& span = fTs[tIndex];
2950        if (span.fDone) {
2951            return NULL;
2952        }
2953    #if DEBUG_MARK_DONE
2954        debugShowNewWinding(funName, span, winding);
2955    #endif
2956        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
2957   #ifdef SK_DEBUG
2958        SkASSERT(abs(winding) <= gDebugMaxWindSum);
2959   #endif
2960        span.fWindSum = winding;
2961        return &span;
2962    }
2963
2964    Span* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding) {
2965        Span& span = fTs[tIndex];
2966        if (span.fDone) {
2967            return NULL;
2968        }
2969    #if DEBUG_MARK_DONE
2970        debugShowNewWinding(funName, span, winding, oppWinding);
2971    #endif
2972        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
2973   #ifdef SK_DEBUG
2974        SkASSERT(abs(winding) <= gDebugMaxWindSum);
2975   #endif
2976        span.fWindSum = winding;
2977        SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
2978   #ifdef SK_DEBUG
2979        SkASSERT(abs(oppWinding) <= gDebugMaxWindSum);
2980   #endif
2981        span.fOppSum = oppWinding;
2982        return &span;
2983    }
2984
2985    Span* verifyOneWinding(const char* funName, int tIndex) {
2986        Span& span = fTs[tIndex];
2987        if (span.fDone) {
2988            return NULL;
2989        }
2990    #if DEBUG_MARK_DONE
2991        debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
2992    #endif
2993        SkASSERT(span.fWindSum != SK_MinS32);
2994        SkASSERT(span.fOppSum != SK_MinS32);
2995        return &span;
2996    }
2997
2998    // note that just because a span has one end that is unsortable, that's
2999    // not enough to mark it done. The other end may be sortable, allowing the
3000    // span to be added.
3001    void markUnsortable(int start, int end) {
3002        Span* span = &fTs[start];
3003        if (start < end) {
3004            span->fUnsortableStart = true;
3005        } else {
3006            --span;
3007            span->fUnsortableEnd = true;
3008        }
3009        if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
3010            return;
3011        }
3012        span->fDone = true;
3013        fDoneSpans++;
3014    }
3015
3016    void markWinding(int index, int winding) {
3017    //    SkASSERT(!done());
3018        SkASSERT(winding);
3019        double referenceT = fTs[index].fT;
3020        int lesser = index;
3021        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3022            markOneWinding(__FUNCTION__, lesser, winding);
3023        }
3024        do {
3025            markOneWinding(__FUNCTION__, index, winding);
3026       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3027    }
3028
3029    void markWinding(int index, int winding, int oppWinding) {
3030    //    SkASSERT(!done());
3031        SkASSERT(winding || oppWinding);
3032        double referenceT = fTs[index].fT;
3033        int lesser = index;
3034        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3035            markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3036        }
3037        do {
3038            markOneWinding(__FUNCTION__, index, winding, oppWinding);
3039       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3040    }
3041
3042    void matchWindingValue(int tIndex, double t, bool borrowWind) {
3043        int nextDoorWind = SK_MaxS32;
3044        int nextOppWind = SK_MaxS32;
3045        if (tIndex > 0) {
3046            const Span& below = fTs[tIndex - 1];
3047            if (approximately_negative(t - below.fT)) {
3048                nextDoorWind = below.fWindValue;
3049                nextOppWind = below.fOppValue;
3050            }
3051        }
3052        if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3053            const Span& above = fTs[tIndex + 1];
3054            if (approximately_negative(above.fT - t)) {
3055                nextDoorWind = above.fWindValue;
3056                nextOppWind = above.fOppValue;
3057            }
3058        }
3059        if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3060            const Span& below = fTs[tIndex - 1];
3061            nextDoorWind = below.fWindValue;
3062            nextOppWind = below.fOppValue;
3063        }
3064        if (nextDoorWind != SK_MaxS32) {
3065            Span& newSpan = fTs[tIndex];
3066            newSpan.fWindValue = nextDoorWind;
3067            newSpan.fOppValue = nextOppWind;
3068            if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3069                newSpan.fDone = true;
3070                ++fDoneSpans;
3071            }
3072        }
3073    }
3074
3075    // return span if when chasing, two or more radiating spans are not done
3076    // OPTIMIZATION: ? multiple spans is detected when there is only one valid
3077    // candidate and the remaining spans have windValue == 0 (canceled by
3078    // coincidence). The coincident edges could either be removed altogether,
3079    // or this code could be more complicated in detecting this case. Worth it?
3080    bool multipleSpans(int end) const {
3081        return end > 0 && end < fTs.count() - 1;
3082    }
3083
3084    Segment* nextChase(int& index, const int step, int& min, Span*& last) const {
3085        int end = nextExactSpan(index, step);
3086        SkASSERT(end >= 0);
3087        if (multipleSpans(end)) {
3088            last = &fTs[end];
3089            return NULL;
3090        }
3091        const Span& endSpan = fTs[end];
3092        Segment* other = endSpan.fOther;
3093        index = endSpan.fOtherIndex;
3094        int otherEnd = other->nextExactSpan(index, step);
3095        min = SkMin32(index, otherEnd);
3096        return other;
3097    }
3098
3099    // This has callers for two different situations: one establishes the end
3100    // of the current span, and one establishes the beginning of the next span
3101    // (thus the name). When this is looking for the end of the current span,
3102    // coincidence is found when the beginning Ts contain -step and the end
3103    // contains step. When it is looking for the beginning of the next, the
3104    // first Ts found can be ignored and the last Ts should contain -step.
3105    // OPTIMIZATION: probably should split into two functions
3106    int nextSpan(int from, int step) const {
3107        const Span& fromSpan = fTs[from];
3108        int count = fTs.count();
3109        int to = from;
3110        while (step > 0 ? ++to < count : --to >= 0) {
3111            const Span& span = fTs[to];
3112            if (approximately_zero(span.fT - fromSpan.fT)) {
3113                continue;
3114            }
3115            return to;
3116        }
3117        return -1;
3118    }
3119
3120    // FIXME
3121    // this returns at any difference in T, vs. a preset minimum. It may be
3122    // that all callers to nextSpan should use this instead.
3123    // OPTIMIZATION splitting this into separate loops for up/down steps
3124    // would allow using precisely_negative instead of precisely_zero
3125    int nextExactSpan(int from, int step) const {
3126        const Span& fromSpan = fTs[from];
3127        int count = fTs.count();
3128        int to = from;
3129        while (step > 0 ? ++to < count : --to >= 0) {
3130            const Span& span = fTs[to];
3131            if (precisely_zero(span.fT - fromSpan.fT)) {
3132                continue;
3133            }
3134            return to;
3135        }
3136        return -1;
3137    }
3138
3139    bool operand() const {
3140        return fOperand;
3141    }
3142
3143    int oppSign(const Angle* angle) const {
3144        SkASSERT(angle->segment() == this);
3145        return oppSign(angle->start(), angle->end());
3146    }
3147
3148    int oppSign(int startIndex, int endIndex) const {
3149        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue
3150                : fTs[endIndex].fOppValue;
3151#if DEBUG_WIND_BUMP
3152        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
3153#endif
3154        return result;
3155    }
3156
3157    int oppSum(int tIndex) const {
3158        return fTs[tIndex].fOppSum;
3159    }
3160
3161    int oppSum(const Angle* angle) const {
3162        int lesser = SkMin32(angle->start(), angle->end());
3163        return fTs[lesser].fOppSum;
3164    }
3165
3166    int oppValue(int tIndex) const {
3167        return fTs[tIndex].fOppValue;
3168    }
3169
3170    int oppValue(const Angle* angle) const {
3171        int lesser = SkMin32(angle->start(), angle->end());
3172        return fTs[lesser].fOppValue;
3173    }
3174
3175    const SkPoint* pts() const {
3176        return fPts;
3177    }
3178
3179    void reset() {
3180        init(NULL, (SkPath::Verb) -1, false, false);
3181        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
3182        fTs.reset();
3183    }
3184
3185    void setOppXor(bool isOppXor) {
3186        fOppXor = isOppXor;
3187    }
3188
3189    void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding,
3190            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
3191        int deltaSum = spanSign(index, endIndex);
3192        int oppDeltaSum = oppSign(index, endIndex);
3193        if (operand()) {
3194            maxWinding = sumSuWinding;
3195            sumWinding = sumSuWinding -= deltaSum;
3196            oppMaxWinding = sumMiWinding;
3197            oppSumWinding = sumMiWinding -= oppDeltaSum;
3198        } else {
3199            maxWinding = sumMiWinding;
3200            sumWinding = sumMiWinding -= deltaSum;
3201            oppMaxWinding = sumSuWinding;
3202            oppSumWinding = sumSuWinding -= oppDeltaSum;
3203        }
3204    }
3205
3206    // This marks all spans unsortable so that this info is available for early
3207    // exclusion in find top and others. This could be optimized to only mark
3208    // adjacent spans that unsortable. However, this makes it difficult to later
3209    // determine starting points for edge detection in find top and the like.
3210    static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
3211        bool sortable = true;
3212        int angleCount = angles.count();
3213        int angleIndex;
3214        angleList.setReserve(angleCount);
3215        for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3216            Angle& angle = angles[angleIndex];
3217            *angleList.append() = &angle;
3218            sortable &= !angle.unsortable();
3219        }
3220        if (sortable) {
3221            QSort<Angle>(angleList.begin(), angleList.end() - 1);
3222            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3223                if (angles[angleIndex].unsortable()) {
3224                    sortable = false;
3225                    break;
3226                }
3227            }
3228        }
3229        if (!sortable) {
3230            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3231                Angle& angle = angles[angleIndex];
3232                angle.segment()->markUnsortable(angle.start(), angle.end());
3233            }
3234        }
3235        return sortable;
3236    }
3237
3238    // OPTIMIZATION: mark as debugging only if used solely by tests
3239    const Span& span(int tIndex) const {
3240        return fTs[tIndex];
3241    }
3242
3243    int spanSign(const Angle* angle) const {
3244        SkASSERT(angle->segment() == this);
3245        return spanSign(angle->start(), angle->end());
3246    }
3247
3248    int spanSign(int startIndex, int endIndex) const {
3249        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue
3250                : fTs[endIndex].fWindValue;
3251#if DEBUG_WIND_BUMP
3252        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
3253#endif
3254        return result;
3255    }
3256
3257    // OPTIMIZATION: mark as debugging only if used solely by tests
3258    double t(int tIndex) const {
3259        return fTs[tIndex].fT;
3260    }
3261
3262    bool tiny(const Angle* angle) const {
3263        int start = angle->start();
3264        int end = angle->end();
3265        const Span& mSpan = fTs[SkMin32(start, end)];
3266        return mSpan.fTiny;
3267    }
3268
3269    static void TrackOutside(SkTDArray<double>& outsideTs, double end,
3270            double start) {
3271        int outCount = outsideTs.count();
3272        if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) {
3273            *outsideTs.append() = end;
3274            *outsideTs.append() = start;
3275        }
3276    }
3277
3278    void undoneSpan(int& start, int& end) {
3279        size_t tCount = fTs.count();
3280        size_t index;
3281        for (index = 0; index < tCount; ++index) {
3282            if (!fTs[index].fDone) {
3283                break;
3284            }
3285        }
3286        SkASSERT(index < tCount - 1);
3287        start = index;
3288        double startT = fTs[index].fT;
3289        while (approximately_negative(fTs[++index].fT - startT))
3290            SkASSERT(index < tCount);
3291        SkASSERT(index < tCount);
3292        end = index;
3293    }
3294
3295    bool unsortable(int index) const {
3296        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
3297    }
3298
3299    void updatePts(const SkPoint pts[]) {
3300        fPts = pts;
3301    }
3302
3303    int updateOppWinding(int index, int endIndex) const {
3304        int lesser = SkMin32(index, endIndex);
3305        int oppWinding = oppSum(lesser);
3306        int oppSpanWinding = oppSign(index, endIndex);
3307        if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWinding)) {
3308            oppWinding -= oppSpanWinding;
3309        }
3310        return oppWinding;
3311    }
3312
3313    int updateOppWinding(const Angle* angle) const {
3314        int startIndex = angle->start();
3315        int endIndex = angle->end();
3316        return updateOppWinding(endIndex, startIndex);
3317    }
3318
3319    int updateOppWindingReverse(const Angle* angle) const {
3320        int startIndex = angle->start();
3321        int endIndex = angle->end();
3322        return updateOppWinding(startIndex, endIndex);
3323    }
3324
3325    int updateWinding(int index, int endIndex) const {
3326        int lesser = SkMin32(index, endIndex);
3327        int winding = windSum(lesser);
3328        int spanWinding = spanSign(index, endIndex);
3329        if (winding && useInnerWinding(winding - spanWinding, winding)) {
3330            winding -= spanWinding;
3331        }
3332        return winding;
3333    }
3334
3335    int updateWinding(const Angle* angle) const {
3336        int startIndex = angle->start();
3337        int endIndex = angle->end();
3338        return updateWinding(endIndex, startIndex);
3339    }
3340
3341    int updateWindingReverse(const Angle* angle) const {
3342        int startIndex = angle->start();
3343        int endIndex = angle->end();
3344        return updateWinding(startIndex, endIndex);
3345    }
3346
3347    SkPath::Verb verb() const {
3348        return fVerb;
3349    }
3350
3351    int windSum(int tIndex) const {
3352        return fTs[tIndex].fWindSum;
3353    }
3354
3355    int windSum(const Angle* angle) const {
3356        int start = angle->start();
3357        int end = angle->end();
3358        int index = SkMin32(start, end);
3359        return windSum(index);
3360    }
3361
3362    int windValue(int tIndex) const {
3363        return fTs[tIndex].fWindValue;
3364    }
3365
3366    int windValue(const Angle* angle) const {
3367        int start = angle->start();
3368        int end = angle->end();
3369        int index = SkMin32(start, end);
3370        return windValue(index);
3371    }
3372
3373    SkScalar xAtT(const Span* span) const {
3374        return xyAtT(span).fX;
3375    }
3376
3377    const SkPoint& xyAtT(int index) const {
3378        return xyAtT(&fTs[index]);
3379    }
3380
3381    const SkPoint& xyAtT(const Span* span) const {
3382        if (SkScalarIsNaN(span->fPt.fX)) {
3383            if (span->fT == 0) {
3384                span->fPt = fPts[0];
3385            } else if (span->fT == 1) {
3386                span->fPt = fPts[fVerb];
3387            } else {
3388                (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt);
3389            }
3390        }
3391        return span->fPt;
3392    }
3393
3394    SkScalar yAtT(int index) const {
3395        return yAtT(&fTs[index]);
3396    }
3397
3398    SkScalar yAtT(const Span* span) const {
3399        return xyAtT(span).fY;
3400    }
3401
3402    void zeroCoincidentOpp(Span* oTest, int index) {
3403        Span* const test = &fTs[index];
3404        Span* end = test;
3405        do {
3406            end->fOppValue = 0;
3407            end = &fTs[++index];
3408        } while (approximately_negative(end->fT - test->fT));
3409    }
3410
3411    void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT, int oIndex) {
3412        Span* const oTest = &fTs[oIndex];
3413        Span* oEnd = oTest;
3414        const double startT = test->fT;
3415        const double oStartT = oTest->fT;
3416        double otherTMatch = (test->fT - startT) * tRatio + oStartT;
3417        while (!approximately_negative(oEndT - oEnd->fT)
3418                && approximately_negative(oEnd->fT - otherTMatch)) {
3419            oEnd->fOppValue = 0;
3420            oEnd = &fTs[++oIndex];
3421        }
3422    }
3423
3424    void zeroSpan(Span* span) {
3425        SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
3426        span->fWindValue = 0;
3427        span->fOppValue = 0;
3428        SkASSERT(!span->fDone);
3429        span->fDone = true;
3430        ++fDoneSpans;
3431    }
3432
3433#if DEBUG_DUMP
3434    void dump() const {
3435        const char className[] = "Segment";
3436        const int tab = 4;
3437        for (int i = 0; i < fTs.count(); ++i) {
3438            SkPoint out;
3439            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
3440            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
3441                    " otherT=%1.9g windSum=%d\n",
3442                    tab + sizeof(className), className, fID,
3443                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
3444                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
3445        }
3446        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
3447                tab + sizeof(className), className, fID,
3448                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
3449    }
3450#endif
3451
3452#if DEBUG_CONCIDENT
3453    // assert if pair has not already been added
3454     void debugAddTPair(double t, const Segment& other, double otherT) const {
3455        for (int i = 0; i < fTs.count(); ++i) {
3456            if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
3457                return;
3458            }
3459        }
3460        SkASSERT(0);
3461     }
3462#endif
3463
3464#if DEBUG_DUMP
3465    int debugID() const {
3466        return fID;
3467    }
3468#endif
3469
3470#if DEBUG_WINDING
3471    void debugShowSums() const {
3472        SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,
3473            fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);
3474        for (int i = 0; i < fTs.count(); ++i) {
3475            const Span& span = fTs[i];
3476            SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span));
3477            if (span.fWindSum == SK_MinS32) {
3478                SkDebugf("?");
3479            } else {
3480                SkDebugf("%d", span.fWindSum);
3481            }
3482            SkDebugf("]");
3483        }
3484        SkDebugf("\n");
3485    }
3486#endif
3487
3488#if DEBUG_CONCIDENT
3489    void debugShowTs() const {
3490        SkDebugf("%s id=%d", __FUNCTION__, fID);
3491        int lastWind = -1;
3492        int lastOpp = -1;
3493        double lastT = -1;
3494        int i;
3495        for (i = 0; i < fTs.count(); ++i) {
3496            bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
3497                    || lastOpp != fTs[i].fOppValue;
3498            if (change && lastWind >= 0) {
3499                SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
3500                        lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
3501            }
3502            if (change) {
3503                SkDebugf(" [o=%d", fTs[i].fOther->fID);
3504                lastWind = fTs[i].fWindValue;
3505                lastOpp = fTs[i].fOppValue;
3506                lastT = fTs[i].fT;
3507            } else {
3508                SkDebugf(",%d", fTs[i].fOther->fID);
3509            }
3510        }
3511        if (i <= 0) {
3512            return;
3513        }
3514        SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
3515                lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
3516        if (fOperand) {
3517            SkDebugf(" operand");
3518        }
3519        if (done()) {
3520            SkDebugf(" done");
3521        }
3522        SkDebugf("\n");
3523    }
3524#endif
3525
3526#if DEBUG_ACTIVE_SPANS
3527    void debugShowActiveSpans() const {
3528        if (done()) {
3529            return;
3530        }
3531#if DEBUG_ACTIVE_SPANS_SHORT_FORM
3532        int lastId = -1;
3533        double lastT = -1;
3534#endif
3535        for (int i = 0; i < fTs.count(); ++i) {
3536            if (fTs[i].fDone) {
3537                continue;
3538            }
3539#if DEBUG_ACTIVE_SPANS_SHORT_FORM
3540            if (lastId == fID && lastT == fTs[i].fT) {
3541                continue;
3542            }
3543            lastId = fID;
3544            lastT = fTs[i].fT;
3545#endif
3546            SkDebugf("%s id=%d", __FUNCTION__, fID);
3547            SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3548            for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3549                SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3550            }
3551            const Span* span = &fTs[i];
3552            SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,
3553                     xAtT(span), yAtT(span));
3554            const Segment* other = fTs[i].fOther;
3555            SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
3556                    other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
3557            if (fTs[i].fWindSum == SK_MinS32) {
3558                SkDebugf("?");
3559            } else {
3560                SkDebugf("%d", fTs[i].fWindSum);
3561            }
3562            SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
3563        }
3564    }
3565
3566    // This isn't useful yet -- but leaving it in for now in case i think of something
3567    // to use it for
3568    void validateActiveSpans() const {
3569        if (done()) {
3570            return;
3571        }
3572        int tCount = fTs.count();
3573        for (int index = 0; index < tCount; ++index) {
3574            if (fTs[index].fDone) {
3575                continue;
3576            }
3577            // count number of connections which are not done
3578            int first = index;
3579            double baseT = fTs[index].fT;
3580            while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) {
3581                --first;
3582            }
3583            int last = index;
3584            while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) {
3585                ++last;
3586            }
3587            int connections = 0;
3588            connections += first > 0 && !fTs[first - 1].fDone;
3589            for (int test = first; test <= last; ++test) {
3590                connections += !fTs[test].fDone;
3591                const Segment* other = fTs[test].fOther;
3592                int oIndex = fTs[test].fOtherIndex;
3593                connections += !other->fTs[oIndex].fDone;
3594                connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone;
3595            }
3596      //      SkASSERT(!(connections & 1));
3597        }
3598    }
3599#endif
3600
3601#if DEBUG_MARK_DONE
3602    void debugShowNewWinding(const char* fun, const Span& span, int winding) {
3603        const SkPoint& pt = xyAtT(&span);
3604        SkDebugf("%s id=%d", fun, fID);
3605        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3606        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3607            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3608        }
3609        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3610                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3611        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=",
3612                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding);
3613        if (span.fWindSum == SK_MinS32) {
3614            SkDebugf("?");
3615        } else {
3616            SkDebugf("%d", span.fWindSum);
3617        }
3618        SkDebugf(" windValue=%d\n", span.fWindValue);
3619    }
3620
3621    void debugShowNewWinding(const char* fun, const Span& span, int winding, int oppWinding) {
3622        const SkPoint& pt = xyAtT(&span);
3623        SkDebugf("%s id=%d", fun, fID);
3624        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3625        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3626            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3627        }
3628        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3629                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3630        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d newOppSum=%d oppSum=",
3631                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
3632                winding, oppWinding);
3633        if (span.fOppSum == SK_MinS32) {
3634            SkDebugf("?");
3635        } else {
3636            SkDebugf("%d", span.fOppSum);
3637        }
3638        SkDebugf(" windSum=");
3639        if (span.fWindSum == SK_MinS32) {
3640            SkDebugf("?");
3641        } else {
3642            SkDebugf("%d", span.fWindSum);
3643        }
3644        SkDebugf(" windValue=%d\n", span.fWindValue);
3645    }
3646#endif
3647
3648#if DEBUG_SORT
3649    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first,
3650            const int contourWinding, const int oppContourWinding) const {
3651        SkASSERT(angles[first]->segment() == this);
3652        SkASSERT(angles.count() > 1);
3653        int lastSum = contourWinding;
3654        int oppLastSum = oppContourWinding;
3655        const Angle* firstAngle = angles[first];
3656        int windSum = lastSum - spanSign(firstAngle);
3657        int oppoSign = oppSign(firstAngle);
3658        int oppWindSum = oppLastSum - oppoSign;
3659        SkDebugf("%s %s contourWinding=%d oppContourWinding=%d sign=%d\n", fun, __FUNCTION__,
3660                contourWinding, oppContourWinding, spanSign(angles[first]));
3661        int index = first;
3662        bool firstTime = true;
3663        do {
3664            const Angle& angle = *angles[index];
3665            const Segment& segment = *angle.segment();
3666            int start = angle.start();
3667            int end = angle.end();
3668            const Span& sSpan = segment.fTs[start];
3669            const Span& eSpan = segment.fTs[end];
3670            const Span& mSpan = segment.fTs[SkMin32(start, end)];
3671            bool opp = segment.fOperand ^ fOperand;
3672            if (!firstTime) {
3673                oppoSign = segment.oppSign(&angle);
3674                if (opp) {
3675                    oppLastSum = oppWindSum;
3676                    oppWindSum -= segment.spanSign(&angle);
3677                    if (oppoSign) {
3678                        lastSum = windSum;
3679                        windSum -= oppoSign;
3680                    }
3681                } else {
3682                    lastSum = windSum;
3683                    windSum -= segment.spanSign(&angle);
3684                    if (oppoSign) {
3685                        oppLastSum = oppWindSum;
3686                        oppWindSum -= oppoSign;
3687                    }
3688                }
3689            }
3690            SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
3691                    " sign=%d windValue=%d windSum=",
3692                    __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "",
3693                    segment.fID, kLVerbStr[segment.fVerb],
3694                    start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
3695                    segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(),
3696                    mSpan.fWindValue);
3697            if (mSpan.fWindSum == SK_MinS32) {
3698                SkDebugf("?");
3699            } else {
3700                SkDebugf("%d", mSpan.fWindSum);
3701            }
3702            int last, wind;
3703            if (opp) {
3704                last = oppLastSum;
3705                wind = oppWindSum;
3706            } else {
3707                last = lastSum;
3708                wind = windSum;
3709            }
3710            if (!oppoSign) {
3711                SkDebugf(" %d->%d (max=%d)", last, wind,
3712                        useInnerWinding(last, wind) ? wind : last);
3713            } else {
3714                SkDebugf(" %d->%d (%d->%d)", last, wind, opp ? lastSum : oppLastSum,
3715                        opp ? windSum : oppWindSum);
3716            }
3717            SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp);
3718#if false && DEBUG_ANGLE
3719            angle.debugShow(segment.xyAtT(&sSpan));
3720#endif
3721            ++index;
3722            if (index == angles.count()) {
3723                index = 0;
3724            }
3725            if (firstTime) {
3726                firstTime = false;
3727            }
3728        } while (index != first);
3729    }
3730
3731    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first) {
3732        const Angle* firstAngle = angles[first];
3733        const Segment* segment = firstAngle->segment();
3734        int winding = segment->updateWinding(firstAngle);
3735        int oppWinding = segment->updateOppWinding(firstAngle);
3736        debugShowSort(fun, angles, first, winding, oppWinding);
3737    }
3738
3739#endif
3740
3741#if DEBUG_WINDING
3742    static char as_digit(int value) {
3743        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
3744    }
3745#endif
3746
3747#if DEBUG_SHOW_WINDING
3748    int debugShowWindingValues(int slotCount, int ofInterest) const {
3749        if (!(1 << fID & ofInterest)) {
3750            return 0;
3751        }
3752        int sum = 0;
3753        SkTDArray<char> slots;
3754        slots.setCount(slotCount * 2);
3755        memset(slots.begin(), ' ', slotCount * 2);
3756        for (int i = 0; i < fTs.count(); ++i) {
3757       //     if (!(1 << fTs[i].fOther->fID & ofInterest)) {
3758       //         continue;
3759       //     }
3760            sum += fTs[i].fWindValue;
3761            slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
3762            sum += fTs[i].fOppValue;
3763            slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
3764        }
3765        SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
3766                slots.begin() + slotCount);
3767        return sum;
3768    }
3769#endif
3770
3771private:
3772    const SkPoint* fPts;
3773    Bounds fBounds;
3774    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
3775    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
3776    int fDoneSpans; // quick check that segment is finished
3777    // OPTIMIZATION: force the following to be byte-sized
3778    SkPath::Verb fVerb;
3779    bool fOperand;
3780    bool fXor; // set if original contour had even-odd fill
3781    bool fOppXor; // set if opposite operand had even-odd fill
3782#if DEBUG_DUMP
3783    int fID;
3784#endif
3785};
3786
3787class Contour;
3788
3789struct Coincidence {
3790    Contour* fContours[2];
3791    int fSegments[2];
3792    double fTs[2][2];
3793};
3794
3795class Contour {
3796public:
3797    Contour() {
3798        reset();
3799#if DEBUG_DUMP
3800        fID = ++gContourID;
3801#endif
3802    }
3803
3804    bool operator<(const Contour& rh) const {
3805        return fBounds.fTop == rh.fBounds.fTop
3806                ? fBounds.fLeft < rh.fBounds.fLeft
3807                : fBounds.fTop < rh.fBounds.fTop;
3808    }
3809
3810    void addCoincident(int index, Contour* other, int otherIndex,
3811            const Intersections& ts, bool swap) {
3812        Coincidence& coincidence = *fCoincidences.append();
3813        coincidence.fContours[0] = this; // FIXME: no need to store
3814        coincidence.fContours[1] = other;
3815        coincidence.fSegments[0] = index;
3816        coincidence.fSegments[1] = otherIndex;
3817        if (fSegments[index].verb() == SkPath::kLine_Verb &&
3818                other->fSegments[otherIndex].verb() == SkPath::kLine_Verb) {
3819            // FIXME: coincident lines use legacy Ts instead of coincident Ts
3820            coincidence.fTs[swap][0] = ts.fT[0][0];
3821            coincidence.fTs[swap][1] = ts.fT[0][1];
3822            coincidence.fTs[!swap][0] = ts.fT[1][0];
3823            coincidence.fTs[!swap][1] = ts.fT[1][1];
3824        } else if (fSegments[index].verb() == SkPath::kQuad_Verb &&
3825                other->fSegments[otherIndex].verb() == SkPath::kQuad_Verb) {
3826            coincidence.fTs[swap][0] = ts.fCoincidentT[0][0];
3827            coincidence.fTs[swap][1] = ts.fCoincidentT[0][1];
3828            coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0];
3829            coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1];
3830        }
3831    }
3832
3833    void addCross(const Contour* crosser) {
3834#ifdef DEBUG_CROSS
3835        for (int index = 0; index < fCrosses.count(); ++index) {
3836            SkASSERT(fCrosses[index] != crosser);
3837        }
3838#endif
3839        *fCrosses.append() = crosser;
3840    }
3841
3842    void addCubic(const SkPoint pts[4]) {
3843        fSegments.push_back().addCubic(pts, fOperand, fXor);
3844        fContainsCurves = true;
3845    }
3846
3847    int addLine(const SkPoint pts[2]) {
3848        fSegments.push_back().addLine(pts, fOperand, fXor);
3849        return fSegments.count();
3850    }
3851
3852    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
3853        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
3854    }
3855
3856    int addQuad(const SkPoint pts[3]) {
3857        fSegments.push_back().addQuad(pts, fOperand, fXor);
3858        fContainsCurves = true;
3859        return fSegments.count();
3860    }
3861
3862    int addT(int segIndex, double newT, Contour* other, int otherIndex) {
3863        containsIntercepts();
3864        return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
3865    }
3866
3867    const Bounds& bounds() const {
3868        return fBounds;
3869    }
3870
3871    void complete() {
3872        setBounds();
3873        fContainsIntercepts = false;
3874    }
3875
3876    void containsIntercepts() {
3877        fContainsIntercepts = true;
3878    }
3879
3880    const Segment* crossedSegmentX(const SkPoint& basePt, SkScalar& bestX,
3881            int &tIndex, double& hitT, bool opp) {
3882        int segmentCount = fSegments.count();
3883        const Segment* bestSegment = NULL;
3884        for (int test = 0; test < segmentCount; ++test) {
3885            Segment* testSegment = &fSegments[test];
3886            const SkRect& bounds = testSegment->bounds();
3887            if (bounds.fRight <= bestX) {
3888                continue;
3889            }
3890            if (bounds.fLeft >= basePt.fX) {
3891                continue;
3892            }
3893            if (bounds.fTop > basePt.fY) {
3894                continue;
3895            }
3896            if (bounds.fBottom < basePt.fY) {
3897                continue;
3898            }
3899            if (bounds.fTop == bounds.fBottom) {
3900                continue;
3901            }
3902            double testHitT;
3903            int testT = testSegment->crossedSpanX(basePt, bestX, testHitT, opp);
3904            if (testT >= 0) {
3905                bestSegment = testSegment;
3906                tIndex = testT;
3907                hitT = testHitT;
3908            }
3909        }
3910        return bestSegment;
3911    }
3912
3913    const Segment* crossedSegmentY(const SkPoint& basePt, SkScalar& bestY,
3914            int &tIndex, double& hitT, bool opp) {
3915        int segmentCount = fSegments.count();
3916        const Segment* bestSegment = NULL;
3917        for (int test = 0; test < segmentCount; ++test) {
3918            Segment* testSegment = &fSegments[test];
3919            const SkRect& bounds = testSegment->bounds();
3920            if (bounds.fBottom <= bestY) {
3921                continue;
3922            }
3923            if (bounds.fTop >= basePt.fY) {
3924                continue;
3925            }
3926            if (bounds.fLeft > basePt.fX) {
3927                continue;
3928            }
3929            if (bounds.fRight < basePt.fX) {
3930                continue;
3931            }
3932            if (bounds.fLeft == bounds.fRight) {
3933                continue;
3934            }
3935            double testHitT;
3936            int testT = testSegment->crossedSpanY(basePt, bestY, testHitT, opp);
3937            if (testT >= 0) {
3938                bestSegment = testSegment;
3939                tIndex = testT;
3940                hitT = testHitT;
3941            }
3942        }
3943        return bestSegment;
3944    }
3945
3946    bool crosses(const Contour* crosser) const {
3947        for (int index = 0; index < fCrosses.count(); ++index) {
3948            if (fCrosses[index] == crosser) {
3949                return true;
3950            }
3951        }
3952        return false;
3953    }
3954
3955    const SkPoint& end() const {
3956        const Segment& segment = fSegments.back();
3957        return segment.pts()[segment.verb()];
3958    }
3959
3960    void findTooCloseToCall() {
3961        int segmentCount = fSegments.count();
3962        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
3963            fSegments[sIndex].findTooCloseToCall();
3964        }
3965    }
3966
3967    void fixOtherTIndex() {
3968        int segmentCount = fSegments.count();
3969        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
3970            fSegments[sIndex].fixOtherTIndex();
3971        }
3972    }
3973
3974    bool operand() const {
3975        return fOperand;
3976    }
3977
3978    void reset() {
3979        fSegments.reset();
3980        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
3981        fContainsCurves = fContainsIntercepts = false;
3982    }
3983
3984    void resolveCoincidence(SkTDArray<Contour*>& contourList) {
3985        int count = fCoincidences.count();
3986        for (int index = 0; index < count; ++index) {
3987            Coincidence& coincidence = fCoincidences[index];
3988            SkASSERT(coincidence.fContours[0] == this);
3989            int thisIndex = coincidence.fSegments[0];
3990            Segment& thisOne = fSegments[thisIndex];
3991            Contour* otherContour = coincidence.fContours[1];
3992            int otherIndex = coincidence.fSegments[1];
3993            Segment& other = otherContour->fSegments[otherIndex];
3994            if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
3995                continue;
3996            }
3997        #if DEBUG_CONCIDENT
3998            thisOne.debugShowTs();
3999            other.debugShowTs();
4000        #endif
4001            double startT = coincidence.fTs[0][0];
4002            double endT = coincidence.fTs[0][1];
4003            bool cancelers = false;
4004            if (startT > endT) {
4005                SkTSwap<double>(startT, endT);
4006                cancelers ^= true; // FIXME: just assign true
4007            }
4008            SkASSERT(!approximately_negative(endT - startT));
4009            double oStartT = coincidence.fTs[1][0];
4010            double oEndT = coincidence.fTs[1][1];
4011            if (oStartT > oEndT) {
4012                SkTSwap<double>(oStartT, oEndT);
4013                cancelers ^= true;
4014            }
4015            SkASSERT(!approximately_negative(oEndT - oStartT));
4016            bool opp = fOperand ^ otherContour->fOperand;
4017            if (cancelers && !opp) {
4018                // make sure startT and endT have t entries
4019                if (startT > 0 || oEndT < 1
4020                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
4021                    thisOne.addTPair(startT, other, oEndT, true);
4022                }
4023                if (oStartT > 0 || endT < 1
4024                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
4025                    other.addTPair(oStartT, thisOne, endT, true);
4026                }
4027                if (!thisOne.done() && !other.done()) {
4028                    thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
4029                }
4030            } else {
4031                if (startT > 0 || oStartT > 0
4032                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
4033                    thisOne.addTPair(startT, other, oStartT, true);
4034                }
4035                if (endT < 1 || oEndT < 1
4036                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
4037                    other.addTPair(oEndT, thisOne, endT, true);
4038                }
4039                if (!thisOne.done() && !other.done()) {
4040                    thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
4041                }
4042            }
4043        #if DEBUG_CONCIDENT
4044            thisOne.debugShowTs();
4045            other.debugShowTs();
4046        #endif
4047        #if DEBUG_SHOW_WINDING
4048            debugShowWindingValues(contourList);
4049        #endif
4050        }
4051    }
4052
4053    const SkTArray<Segment>& segments() {
4054        return fSegments;
4055    }
4056
4057    void setOperand(bool isOp) {
4058        fOperand = isOp;
4059    }
4060
4061    void setOppXor(bool isOppXor) {
4062        fOppXor = isOppXor;
4063        int segmentCount = fSegments.count();
4064        for (int test = 0; test < segmentCount; ++test) {
4065            fSegments[test].setOppXor(isOppXor);
4066        }
4067    }
4068
4069    void setXor(bool isXor) {
4070        fXor = isXor;
4071    }
4072
4073    void sortSegments() {
4074        int segmentCount = fSegments.count();
4075        fSortedSegments.setReserve(segmentCount);
4076        for (int test = 0; test < segmentCount; ++test) {
4077            *fSortedSegments.append() = &fSegments[test];
4078        }
4079        QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
4080        fFirstSorted = 0;
4081    }
4082
4083    const SkPoint& start() const {
4084        return fSegments.front().pts()[0];
4085    }
4086
4087    void toPath(PathWrapper& path) const {
4088        int segmentCount = fSegments.count();
4089        const SkPoint& pt = fSegments.front().pts()[0];
4090        path.deferredMove(pt);
4091        for (int test = 0; test < segmentCount; ++test) {
4092            fSegments[test].addCurveTo(0, 1, path, true);
4093        }
4094        path.close();
4095    }
4096
4097    void toPartialBackward(PathWrapper& path) const {
4098        int segmentCount = fSegments.count();
4099        for (int test = segmentCount - 1; test >= 0; --test) {
4100            fSegments[test].addCurveTo(1, 0, path, true);
4101        }
4102    }
4103
4104    void toPartialForward(PathWrapper& path) const {
4105        int segmentCount = fSegments.count();
4106        for (int test = 0; test < segmentCount; ++test) {
4107            fSegments[test].addCurveTo(0, 1, path, true);
4108        }
4109    }
4110
4111#if 0 // FIXME: obsolete, remove
4112    // OPTIMIZATION: feel pretty uneasy about this. It seems like once again
4113    // we need to sort and walk edges in y, but that on the surface opens the
4114    // same can of worms as before. But then, this is a rough sort based on
4115    // segments' top, and not a true sort, so it could be ameniable to regular
4116    // sorting instead of linear searching. Still feel like I'm missing something
4117    Segment* topSegment(SkScalar& bestY) {
4118        int segmentCount = fSegments.count();
4119        SkASSERT(segmentCount > 0);
4120        int best = -1;
4121        Segment* bestSegment = NULL;
4122        while (++best < segmentCount) {
4123            Segment* testSegment = &fSegments[best];
4124            if (testSegment->done()) {
4125                continue;
4126            }
4127            bestSegment = testSegment;
4128            break;
4129        }
4130        if (!bestSegment) {
4131            return NULL;
4132        }
4133        SkScalar bestTop = bestSegment->activeTop();
4134        for (int test = best + 1; test < segmentCount; ++test) {
4135            Segment* testSegment = &fSegments[test];
4136            if (testSegment->done()) {
4137                continue;
4138            }
4139            if (testSegment->bounds().fTop > bestTop) {
4140                continue;
4141            }
4142            SkScalar testTop = testSegment->activeTop();
4143            if (bestTop > testTop) {
4144                bestTop = testTop;
4145                bestSegment = testSegment;
4146            }
4147        }
4148        bestY = bestTop;
4149        return bestSegment;
4150    }
4151#endif
4152
4153    // FIXME: get rid of allowTies logic if we don't need it
4154    Segment* topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, bool allowTies) {
4155        int segmentCount = fSortedSegments.count();
4156        SkASSERT(segmentCount > 0);
4157        Segment* bestSegment = NULL;
4158        int sortedIndex = fFirstSorted;
4159        for ( ; sortedIndex < segmentCount; ++sortedIndex) {
4160            Segment* testSegment = fSortedSegments[sortedIndex];
4161            if (testSegment->done()) {
4162                if (sortedIndex == fFirstSorted) {
4163                    ++fFirstSorted;
4164                }
4165                continue;
4166            }
4167            SkPoint testXY;
4168            testSegment->activeLeftTop(testXY);
4169            if (testXY.fY < topLeft.fY) {
4170                continue;
4171            }
4172            if (testXY.fY == topLeft.fY && ( /* allowTies ? testXY.fX < topLeft.fX : */
4173                    testXY.fX <= topLeft.fX)) {
4174                continue;
4175            }
4176            if (bestXY.fY < testXY.fY) {
4177                continue;
4178            }
4179            if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) {
4180                continue;
4181            }
4182            bestSegment = testSegment;
4183            bestXY = testXY;
4184        }
4185        return bestSegment;
4186    }
4187
4188    Segment* undoneSegment(int& start, int& end) {
4189        int segmentCount = fSegments.count();
4190        for (int test = 0; test < segmentCount; ++test) {
4191            Segment* testSegment = &fSegments[test];
4192            if (testSegment->done()) {
4193                continue;
4194            }
4195            testSegment->undoneSpan(start, end);
4196            return testSegment;
4197        }
4198        return NULL;
4199    }
4200
4201    int updateSegment(int index, const SkPoint* pts) {
4202        Segment& segment = fSegments[index];
4203        segment.updatePts(pts);
4204        return segment.verb() + 1;
4205    }
4206
4207#if DEBUG_TEST
4208    SkTArray<Segment>& debugSegments() {
4209        return fSegments;
4210    }
4211#endif
4212
4213#if DEBUG_DUMP
4214    void dump() {
4215        int i;
4216        const char className[] = "Contour";
4217        const int tab = 4;
4218        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
4219        for (i = 0; i < fSegments.count(); ++i) {
4220            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
4221                    className, i);
4222            fSegments[i].dump();
4223        }
4224        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
4225                tab + sizeof(className), className,
4226                fBounds.fLeft, fBounds.fTop,
4227                fBounds.fRight, fBounds.fBottom);
4228        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
4229                className, fContainsIntercepts);
4230        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
4231                className, fContainsCurves);
4232    }
4233#endif
4234
4235#if DEBUG_ACTIVE_SPANS
4236    void debugShowActiveSpans() {
4237        for (int index = 0; index < fSegments.count(); ++index) {
4238            fSegments[index].debugShowActiveSpans();
4239        }
4240    }
4241
4242    void validateActiveSpans() {
4243        for (int index = 0; index < fSegments.count(); ++index) {
4244            fSegments[index].validateActiveSpans();
4245        }
4246    }
4247#endif
4248
4249#if DEBUG_SHOW_WINDING
4250    int debugShowWindingValues(int totalSegments, int ofInterest) {
4251        int count = fSegments.count();
4252        int sum = 0;
4253        for (int index = 0; index < count; ++index) {
4254            sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
4255        }
4256  //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
4257        return sum;
4258    }
4259
4260    static void debugShowWindingValues(SkTDArray<Contour*>& contourList) {
4261   //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
4262    //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
4263        int ofInterest = 1 << 5 | 1 << 8;
4264        int total = 0;
4265        int index;
4266        for (index = 0; index < contourList.count(); ++index) {
4267            total += contourList[index]->segments().count();
4268        }
4269        int sum = 0;
4270        for (index = 0; index < contourList.count(); ++index) {
4271            sum += contourList[index]->debugShowWindingValues(total, ofInterest);
4272        }
4273 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
4274    }
4275#endif
4276
4277protected:
4278    void setBounds() {
4279        int count = fSegments.count();
4280        if (count == 0) {
4281            SkDebugf("%s empty contour\n", __FUNCTION__);
4282            SkASSERT(0);
4283            // FIXME: delete empty contour?
4284            return;
4285        }
4286        fBounds = fSegments.front().bounds();
4287        for (int index = 1; index < count; ++index) {
4288            fBounds.add(fSegments[index].bounds());
4289        }
4290    }
4291
4292private:
4293    SkTArray<Segment> fSegments;
4294    SkTDArray<Segment*> fSortedSegments;
4295    int fFirstSorted;
4296    SkTDArray<Coincidence> fCoincidences;
4297    SkTDArray<const Contour*> fCrosses;
4298    Bounds fBounds;
4299    bool fContainsIntercepts;
4300    bool fContainsCurves;
4301    bool fOperand; // true for the second argument to a binary operator
4302    bool fXor;
4303    bool fOppXor;
4304#if DEBUG_DUMP
4305    int fID;
4306#endif
4307};
4308
4309class EdgeBuilder {
4310public:
4311
4312EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours)
4313    : fPath(path.nativePath())
4314    , fContours(contours)
4315{
4316    init();
4317}
4318
4319EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
4320    : fPath(&path)
4321    , fContours(contours)
4322{
4323    init();
4324}
4325
4326void init() {
4327    fCurrentContour = NULL;
4328    fOperand = false;
4329    fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
4330#if DEBUG_DUMP
4331    gContourID = 0;
4332    gSegmentID = 0;
4333#endif
4334    fSecondHalf = preFetch();
4335}
4336
4337void addOperand(const SkPath& path) {
4338    SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
4339    fPathVerbs.pop();
4340    fPath = &path;
4341    fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
4342    preFetch();
4343}
4344
4345void finish() {
4346    walk();
4347    complete();
4348    if (fCurrentContour && !fCurrentContour->segments().count()) {
4349        fContours.pop_back();
4350    }
4351    // correct pointers in contours since fReducePts may have moved as it grew
4352    int cIndex = 0;
4353    int extraCount = fExtra.count();
4354    SkASSERT(extraCount == 0 || fExtra[0] == -1);
4355    int eIndex = 0;
4356    int rIndex = 0;
4357    while (++eIndex < extraCount) {
4358        int offset = fExtra[eIndex];
4359        if (offset < 0) {
4360            ++cIndex;
4361            continue;
4362        }
4363        fCurrentContour = &fContours[cIndex];
4364        rIndex += fCurrentContour->updateSegment(offset - 1,
4365                &fReducePts[rIndex]);
4366    }
4367    fExtra.reset(); // we're done with this
4368}
4369
4370ShapeOpMask xorMask() const {
4371    return fXorMask[fOperand];
4372}
4373
4374protected:
4375
4376void complete() {
4377    if (fCurrentContour && fCurrentContour->segments().count()) {
4378        fCurrentContour->complete();
4379        fCurrentContour = NULL;
4380    }
4381}
4382
4383// FIXME:remove once we can access path pts directly
4384int preFetch() {
4385    SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed
4386    SkPoint pts[4];
4387    SkPath::Verb verb;
4388    do {
4389        verb = iter.next(pts);
4390        *fPathVerbs.append() = verb;
4391        if (verb == SkPath::kMove_Verb) {
4392            *fPathPts.append() = pts[0];
4393        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
4394            fPathPts.append(verb, &pts[1]);
4395        }
4396    } while (verb != SkPath::kDone_Verb);
4397    return fPathVerbs.count() - 1;
4398}
4399
4400void walk() {
4401    SkPath::Verb reducedVerb;
4402    uint8_t* verbPtr = fPathVerbs.begin();
4403    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
4404    const SkPoint* pointsPtr = fPathPts.begin();
4405    const SkPoint* finalCurveStart = NULL;
4406    const SkPoint* finalCurveEnd = NULL;
4407    SkPath::Verb verb;
4408    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
4409        switch (verb) {
4410            case SkPath::kMove_Verb:
4411                complete();
4412                if (!fCurrentContour) {
4413                    fCurrentContour = fContours.push_back_n(1);
4414                    fCurrentContour->setOperand(fOperand);
4415                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_Mask);
4416                    *fExtra.append() = -1; // start new contour
4417                }
4418                finalCurveEnd = pointsPtr++;
4419                goto nextVerb;
4420            case SkPath::kLine_Verb:
4421                // skip degenerate points
4422                if (pointsPtr[-1].fX != pointsPtr[0].fX
4423                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
4424                    fCurrentContour->addLine(&pointsPtr[-1]);
4425                }
4426                break;
4427            case SkPath::kQuad_Verb:
4428
4429                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
4430                if (reducedVerb == 0) {
4431                    break; // skip degenerate points
4432                }
4433                if (reducedVerb == 1) {
4434                    *fExtra.append() =
4435                            fCurrentContour->addLine(fReducePts.end() - 2);
4436                    break;
4437                }
4438                fCurrentContour->addQuad(&pointsPtr[-1]);
4439                break;
4440            case SkPath::kCubic_Verb:
4441                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
4442                if (reducedVerb == 0) {
4443                    break; // skip degenerate points
4444                }
4445                if (reducedVerb == 1) {
4446                    *fExtra.append() =
4447                            fCurrentContour->addLine(fReducePts.end() - 2);
4448                    break;
4449                }
4450                if (reducedVerb == 2) {
4451                    *fExtra.append() =
4452                            fCurrentContour->addQuad(fReducePts.end() - 3);
4453                    break;
4454                }
4455                fCurrentContour->addCubic(&pointsPtr[-1]);
4456                break;
4457            case SkPath::kClose_Verb:
4458                SkASSERT(fCurrentContour);
4459                if (finalCurveStart && finalCurveEnd
4460                        && *finalCurveStart != *finalCurveEnd) {
4461                    *fReducePts.append() = *finalCurveStart;
4462                    *fReducePts.append() = *finalCurveEnd;
4463                    *fExtra.append() =
4464                            fCurrentContour->addLine(fReducePts.end() - 2);
4465                }
4466                complete();
4467                goto nextVerb;
4468            default:
4469                SkDEBUGFAIL("bad verb");
4470                return;
4471        }
4472        finalCurveStart = &pointsPtr[verb - 1];
4473        pointsPtr += verb;
4474        SkASSERT(fCurrentContour);
4475    nextVerb:
4476        if (verbPtr == endOfFirstHalf) {
4477            fOperand = true;
4478        }
4479    }
4480}
4481
4482private:
4483    const SkPath* fPath;
4484    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
4485    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
4486    Contour* fCurrentContour;
4487    SkTArray<Contour>& fContours;
4488    SkTDArray<SkPoint> fReducePts; // segments created on the fly
4489    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
4490    ShapeOpMask fXorMask[2];
4491    int fSecondHalf;
4492    bool fOperand;
4493};
4494
4495class Work {
4496public:
4497    enum SegmentType {
4498        kHorizontalLine_Segment = -1,
4499        kVerticalLine_Segment = 0,
4500        kLine_Segment = SkPath::kLine_Verb,
4501        kQuad_Segment = SkPath::kQuad_Verb,
4502        kCubic_Segment = SkPath::kCubic_Verb,
4503    };
4504
4505    void addCoincident(Work& other, const Intersections& ts, bool swap) {
4506        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
4507    }
4508
4509    // FIXME: does it make sense to write otherIndex now if we're going to
4510    // fix it up later?
4511    void addOtherT(int index, double otherT, int otherIndex) {
4512        fContour->addOtherT(fIndex, index, otherT, otherIndex);
4513    }
4514
4515    // Avoid collapsing t values that are close to the same since
4516    // we walk ts to describe consecutive intersections. Since a pair of ts can
4517    // be nearly equal, any problems caused by this should be taken care
4518    // of later.
4519    // On the edge or out of range values are negative; add 2 to get end
4520    int addT(double newT, const Work& other) {
4521        return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
4522    }
4523
4524    bool advance() {
4525        return ++fIndex < fLast;
4526    }
4527
4528    SkScalar bottom() const {
4529        return bounds().fBottom;
4530    }
4531
4532    const Bounds& bounds() const {
4533        return fContour->segments()[fIndex].bounds();
4534    }
4535
4536    const SkPoint* cubic() const {
4537        return fCubic;
4538    }
4539
4540    void init(Contour* contour) {
4541        fContour = contour;
4542        fIndex = 0;
4543        fLast = contour->segments().count();
4544    }
4545
4546    bool isAdjacent(const Work& next) {
4547        return fContour == next.fContour && fIndex + 1 == next.fIndex;
4548    }
4549
4550    bool isFirstLast(const Work& next) {
4551        return fContour == next.fContour && fIndex == 0
4552                && next.fIndex == fLast - 1;
4553    }
4554
4555    SkScalar left() const {
4556        return bounds().fLeft;
4557    }
4558
4559    void promoteToCubic() {
4560        fCubic[0] = pts()[0];
4561        fCubic[2] = pts()[1];
4562        fCubic[3] = pts()[2];
4563        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
4564        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
4565        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
4566        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
4567    }
4568
4569    const SkPoint* pts() const {
4570        return fContour->segments()[fIndex].pts();
4571    }
4572
4573    SkScalar right() const {
4574        return bounds().fRight;
4575    }
4576
4577    ptrdiff_t segmentIndex() const {
4578        return fIndex;
4579    }
4580
4581    SegmentType segmentType() const {
4582        const Segment& segment = fContour->segments()[fIndex];
4583        SegmentType type = (SegmentType) segment.verb();
4584        if (type != kLine_Segment) {
4585            return type;
4586        }
4587        if (segment.isHorizontal()) {
4588            return kHorizontalLine_Segment;
4589        }
4590        if (segment.isVertical()) {
4591            return kVerticalLine_Segment;
4592        }
4593        return kLine_Segment;
4594    }
4595
4596    bool startAfter(const Work& after) {
4597        fIndex = after.fIndex;
4598        return advance();
4599    }
4600
4601    SkScalar top() const {
4602        return bounds().fTop;
4603    }
4604
4605    SkPath::Verb verb() const {
4606        return fContour->segments()[fIndex].verb();
4607    }
4608
4609    SkScalar x() const {
4610        return bounds().fLeft;
4611    }
4612
4613    bool xFlipped() const {
4614        return x() != pts()[0].fX;
4615    }
4616
4617    SkScalar y() const {
4618        return bounds().fTop;
4619    }
4620
4621    bool yFlipped() const {
4622        return y() != pts()[0].fY;
4623    }
4624
4625protected:
4626    Contour* fContour;
4627    SkPoint fCubic[4];
4628    int fIndex;
4629    int fLast;
4630};
4631
4632#if DEBUG_ADD_INTERSECTING_TS
4633static void debugShowLineIntersection(int pts, const Work& wt,
4634        const Work& wn, const double wtTs[2], const double wnTs[2]) {
4635    return;
4636    if (!pts) {
4637        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
4638                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
4639                wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY,
4640                wn.pts()[1].fX, wn.pts()[1].fY);
4641        return;
4642    }
4643    SkPoint wtOutPt, wnOutPt;
4644    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
4645    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
4646    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4647            __FUNCTION__,
4648            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
4649            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
4650    if (pts == 2) {
4651        SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
4652    }
4653    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4654            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
4655            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
4656    if (pts == 2) {
4657        SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
4658    }
4659    SkDebugf("\n");
4660}
4661
4662static void debugShowQuadLineIntersection(int pts, const Work& wt,
4663        const Work& wn, const double wtTs[2], const double wnTs[2]) {
4664    if (!pts) {
4665        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
4666                " (%1.9g,%1.9g %1.9g,%1.9g)\n",
4667                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
4668                wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
4669                wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY);
4670        return;
4671    }
4672    SkPoint wtOutPt, wnOutPt;
4673    QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
4674    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
4675    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4676            __FUNCTION__,
4677            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
4678            wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
4679            wtOutPt.fX, wtOutPt.fY);
4680    if (pts == 2) {
4681        QuadXYAtT(wt.pts(), wtTs[1], &wtOutPt);
4682        SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY);
4683    }
4684    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4685            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
4686            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
4687    if (pts == 2) {
4688        LineXYAtT(wn.pts(), wnTs[1], &wnOutPt);
4689        SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY);
4690    }
4691    SkDebugf("\n");
4692}
4693
4694static void debugShowQuadIntersection(int pts, const Work& wt,
4695        const Work& wn, const double wtTs[2], const double wnTs[2]) {
4696    if (!pts) {
4697        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
4698                " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
4699                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
4700                wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
4701                wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
4702                wn.pts()[2].fX, wn.pts()[2].fY );
4703        return;
4704    }
4705    SkPoint wtOutPt, wnOutPt;
4706    QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
4707    QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt);
4708    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4709            __FUNCTION__,
4710            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
4711            wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
4712            wtOutPt.fX, wtOutPt.fY);
4713    if (pts == 2) {
4714        SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
4715    }
4716    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
4717            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
4718            wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY,
4719            wnOutPt.fX, wnOutPt.fY);
4720    if (pts == 2) {
4721        SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
4722    }
4723    SkDebugf("\n");
4724}
4725#else
4726static void debugShowLineIntersection(int , const Work& ,
4727        const Work& , const double [2], const double [2]) {
4728}
4729
4730static void debugShowQuadLineIntersection(int , const Work& ,
4731        const Work& , const double [2], const double [2]) {
4732}
4733
4734static void debugShowQuadIntersection(int , const Work& ,
4735        const Work& , const double [2], const double [2]) {
4736}
4737#endif
4738
4739static bool addIntersectTs(Contour* test, Contour* next) {
4740
4741    if (test != next) {
4742        if (test->bounds().fBottom < next->bounds().fTop) {
4743            return false;
4744        }
4745        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
4746            return true;
4747        }
4748    }
4749    Work wt;
4750    wt.init(test);
4751    bool foundCommonContour = test == next;
4752    do {
4753        Work wn;
4754        wn.init(next);
4755        if (test == next && !wn.startAfter(wt)) {
4756            continue;
4757        }
4758        do {
4759            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
4760                continue;
4761            }
4762            int pts;
4763            Intersections ts;
4764            bool swap = false;
4765            switch (wt.segmentType()) {
4766                case Work::kHorizontalLine_Segment:
4767                    swap = true;
4768                    switch (wn.segmentType()) {
4769                        case Work::kHorizontalLine_Segment:
4770                        case Work::kVerticalLine_Segment:
4771                        case Work::kLine_Segment: {
4772                            pts = HLineIntersect(wn.pts(), wt.left(),
4773                                    wt.right(), wt.y(), wt.xFlipped(), ts);
4774                            debugShowLineIntersection(pts, wt, wn,
4775                                    ts.fT[1], ts.fT[0]);
4776                            break;
4777                        }
4778                        case Work::kQuad_Segment: {
4779                            pts = HQuadIntersect(wn.pts(), wt.left(),
4780                                    wt.right(), wt.y(), wt.xFlipped(), ts);
4781                            break;
4782                        }
4783                        case Work::kCubic_Segment: {
4784                            pts = HCubicIntersect(wn.pts(), wt.left(),
4785                                    wt.right(), wt.y(), wt.xFlipped(), ts);
4786                            break;
4787                        }
4788                        default:
4789                            SkASSERT(0);
4790                    }
4791                    break;
4792                case Work::kVerticalLine_Segment:
4793                    swap = true;
4794                    switch (wn.segmentType()) {
4795                        case Work::kHorizontalLine_Segment:
4796                        case Work::kVerticalLine_Segment:
4797                        case Work::kLine_Segment: {
4798                            pts = VLineIntersect(wn.pts(), wt.top(),
4799                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
4800                            debugShowLineIntersection(pts, wt, wn,
4801                                    ts.fT[1], ts.fT[0]);
4802                            break;
4803                        }
4804                        case Work::kQuad_Segment: {
4805                            pts = VQuadIntersect(wn.pts(), wt.top(),
4806                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
4807                            break;
4808                        }
4809                        case Work::kCubic_Segment: {
4810                            pts = VCubicIntersect(wn.pts(), wt.top(),
4811                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
4812                            break;
4813                        }
4814                        default:
4815                            SkASSERT(0);
4816                    }
4817                    break;
4818                case Work::kLine_Segment:
4819                    switch (wn.segmentType()) {
4820                        case Work::kHorizontalLine_Segment:
4821                            pts = HLineIntersect(wt.pts(), wn.left(),
4822                                    wn.right(), wn.y(), wn.xFlipped(), ts);
4823                            debugShowLineIntersection(pts, wt, wn,
4824                                    ts.fT[1], ts.fT[0]);
4825                            break;
4826                        case Work::kVerticalLine_Segment:
4827                            pts = VLineIntersect(wt.pts(), wn.top(),
4828                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
4829                            debugShowLineIntersection(pts, wt, wn,
4830                                    ts.fT[1], ts.fT[0]);
4831                            break;
4832                        case Work::kLine_Segment: {
4833                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
4834                            debugShowLineIntersection(pts, wt, wn,
4835                                    ts.fT[1], ts.fT[0]);
4836                            break;
4837                        }
4838                        case Work::kQuad_Segment: {
4839                            swap = true;
4840                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
4841                            debugShowQuadLineIntersection(pts, wn, wt,
4842                                    ts.fT[0], ts.fT[1]);
4843                            break;
4844                        }
4845                        case Work::kCubic_Segment: {
4846                            swap = true;
4847                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
4848                            break;
4849                        }
4850                        default:
4851                            SkASSERT(0);
4852                    }
4853                    break;
4854                case Work::kQuad_Segment:
4855                    switch (wn.segmentType()) {
4856                        case Work::kHorizontalLine_Segment:
4857                            pts = HQuadIntersect(wt.pts(), wn.left(),
4858                                    wn.right(), wn.y(), wn.xFlipped(), ts);
4859                            break;
4860                        case Work::kVerticalLine_Segment:
4861                            pts = VQuadIntersect(wt.pts(), wn.top(),
4862                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
4863                            break;
4864                        case Work::kLine_Segment: {
4865                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
4866                            debugShowQuadLineIntersection(pts, wt, wn,
4867                                    ts.fT[0], ts.fT[1]);
4868                            break;
4869                        }
4870                        case Work::kQuad_Segment: {
4871                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
4872                            debugShowQuadIntersection(pts, wt, wn,
4873                                    ts.fT[0], ts.fT[1]);
4874                            break;
4875                        }
4876                        case Work::kCubic_Segment: {
4877                            wt.promoteToCubic();
4878                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
4879                            break;
4880                        }
4881                        default:
4882                            SkASSERT(0);
4883                    }
4884                    break;
4885                case Work::kCubic_Segment:
4886                    switch (wn.segmentType()) {
4887                        case Work::kHorizontalLine_Segment:
4888                            pts = HCubicIntersect(wt.pts(), wn.left(),
4889                                    wn.right(), wn.y(), wn.xFlipped(), ts);
4890                            break;
4891                        case Work::kVerticalLine_Segment:
4892                            pts = VCubicIntersect(wt.pts(), wn.top(),
4893                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
4894                            break;
4895                        case Work::kLine_Segment: {
4896                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
4897                            break;
4898                        }
4899                        case Work::kQuad_Segment: {
4900                            wn.promoteToCubic();
4901                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
4902                            break;
4903                        }
4904                        case Work::kCubic_Segment: {
4905                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
4906                            break;
4907                        }
4908                        default:
4909                            SkASSERT(0);
4910                    }
4911                    break;
4912                default:
4913                    SkASSERT(0);
4914            }
4915            if (!foundCommonContour && pts > 0) {
4916                test->addCross(next);
4917                next->addCross(test);
4918                foundCommonContour = true;
4919            }
4920            // in addition to recording T values, record matching segment
4921            if (pts == 2) {
4922                if (wn.segmentType() <= Work::kLine_Segment
4923                        && wt.segmentType() <= Work::kLine_Segment) {
4924                    wt.addCoincident(wn, ts, swap);
4925                    continue;
4926                }
4927                if (wn.segmentType() == Work::kQuad_Segment
4928                        && wt.segmentType() == Work::kQuad_Segment
4929                        && ts.coincidentUsed() == 2) {
4930                    wt.addCoincident(wn, ts, swap);
4931                    continue;
4932                }
4933
4934            }
4935            for (int pt = 0; pt < pts; ++pt) {
4936                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
4937                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
4938                int testTAt = wt.addT(ts.fT[swap][pt], wn);
4939                int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
4940                wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
4941                wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
4942            }
4943        } while (wn.advance());
4944    } while (wt.advance());
4945    return true;
4946}
4947
4948// resolve any coincident pairs found while intersecting, and
4949// see if coincidence is formed by clipping non-concident segments
4950static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {
4951    int contourCount = contourList.count();
4952    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
4953        Contour* contour = contourList[cIndex];
4954        contour->resolveCoincidence(contourList);
4955    }
4956    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
4957        Contour* contour = contourList[cIndex];
4958        contour->findTooCloseToCall();
4959    }
4960}
4961
4962static int contourRangeCheckX(SkTDArray<Contour*>& contourList, double mid,
4963        const Segment* current, int index, int endIndex, bool opp) {
4964    const SkPoint& basePt = current->xyAtT(endIndex);
4965    int contourCount = contourList.count();
4966    SkScalar bestX = SK_ScalarMin;
4967    const Segment* test = NULL;
4968    int tIndex;
4969    double tHit;
4970    bool crossOpp;
4971    for (int cTest = 0; cTest < contourCount; ++cTest) {
4972        Contour* contour = contourList[cTest];
4973        bool testOpp = contour->operand() ^ current->operand() ^ opp;
4974        if (basePt.fX < contour->bounds().fLeft) {
4975            continue;
4976        }
4977        if (bestX > contour->bounds().fRight) {
4978            continue;
4979        }
4980        const Segment* next = contour->crossedSegmentX(basePt, bestX, tIndex, tHit, testOpp);
4981        if (next) {
4982            test = next;
4983            crossOpp = testOpp;
4984        }
4985    }
4986    if (!test) {
4987        return 0;
4988    }
4989    if (approximately_zero(tHit - test->t(tIndex))) { // if we hit the end of a span, disregard
4990        return SK_MinS32;
4991    }
4992    int winding = crossOpp ? test->oppSum(tIndex) : test->windSum(tIndex);
4993    SkASSERT(winding != SK_MinS32);
4994    int windValue = crossOpp ? test->oppValue(tIndex) : test->windValue(tIndex);
4995#if DEBUG_WINDING
4996    SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
4997            windValue);
4998#endif
4999    // see if a + change in T results in a +/- change in X (compute x'(T))
5000    SkScalar dy = (*SegmentDYAtT[test->verb()])(test->pts(), tHit);
5001    if (test->verb() > SkPath::kLine_Verb && approximately_zero(dy)) {
5002        const SkPoint* pts = test->pts();
5003        dy = pts[2].fY - pts[1].fY - dy;
5004    }
5005#if DEBUG_WINDING
5006    SkDebugf("%s dy=%1.9g\n", __FUNCTION__, dy);
5007#endif
5008    SkASSERT(dy != 0);
5009    if (winding * dy > 0) { // if same signs, result is negative
5010        winding += dy > 0 ? -windValue : windValue;
5011#if DEBUG_WINDING
5012        SkDebugf("%s final winding=%d\n", __FUNCTION__, winding);
5013#endif
5014    }
5015    return winding;
5016}
5017
5018static int contourRangeCheckY(SkTDArray<Contour*>& contourList, double mid,
5019        const Segment* current, int index, int endIndex, bool opp) {
5020    const SkPoint& basePt = current->xyAtT(endIndex);
5021    int contourCount = contourList.count();
5022    SkScalar bestY = SK_ScalarMin;
5023    const Segment* test = NULL;
5024    int tIndex;
5025    double tHit;
5026    bool crossOpp;
5027    for (int cTest = 0; cTest < contourCount; ++cTest) {
5028        Contour* contour = contourList[cTest];
5029        bool testOpp = contour->operand() ^ current->operand() ^ opp;
5030        if (basePt.fY < contour->bounds().fTop) {
5031            continue;
5032        }
5033        if (bestY > contour->bounds().fBottom) {
5034            continue;
5035        }
5036        const Segment* next = contour->crossedSegmentY(basePt, bestY, tIndex, tHit, testOpp);
5037        if (next) {
5038            test = next;
5039            crossOpp = testOpp;
5040        }
5041    }
5042    if (!test) {
5043        return 0;
5044    }
5045    if (approximately_zero(tHit - test->t(tIndex))) { // if we hit the end of a span, disregard
5046        return SK_MinS32;