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