Simplify.cpp revision 055c7c299cb47eebd360b809ad58a0006e2e55f7
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 HIGH_DEF_ANGLES 1
29
30#if HIGH_DEF_ANGLES
31typedef double AngleValue;
32#else
33typedef SkScalar AngleValue;
34#endif
35
36#define DEBUG_UNUSED 0 // set to expose unused functions
37
38#if 1 // set to 1 for multiple thread -- no debugging
39
40const bool gRunTestsInOneThread = false;
41
42#define DEBUG_ACTIVE_SPANS 0
43#define DEBUG_ADD_INTERSECTING_TS 0
44#define DEBUG_ADD_T_PAIR 0
45#define DEBUG_ANGLE 0
46#define DEBUG_CONCIDENT 0
47#define DEBUG_CROSS 0
48#define DEBUG_DUMP 0
49#define DEBUG_MARK_DONE 0
50#define DEBUG_PATH_CONSTRUCTION 0
51#define DEBUG_SORT 0
52#define DEBUG_WIND_BUMP 0
53#define DEBUG_WINDING 0
54
55#else
56
57const bool gRunTestsInOneThread = true;
58
59#define DEBUG_ACTIVE_SPANS 1
60#define DEBUG_ADD_INTERSECTING_TS 0
61#define DEBUG_ADD_T_PAIR 0
62#define DEBUG_ANGLE 1
63#define DEBUG_CONCIDENT 1
64#define DEBUG_CROSS 0
65#define DEBUG_DUMP 1
66#define DEBUG_MARK_DONE 1
67#define DEBUG_PATH_CONSTRUCTION 1
68#define DEBUG_SORT 1
69#define DEBUG_WIND_BUMP 0
70#define DEBUG_WINDING 1
71
72#endif
73
74#if (DEBUG_ACTIVE_SPANS || DEBUG_CONCIDENT || DEBUG_SORT) && !DEBUG_DUMP
75#undef DEBUG_DUMP
76#define DEBUG_DUMP 1
77#endif
78
79#if DEBUG_DUMP
80static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
81// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
82static int gContourID;
83static int gSegmentID;
84#endif
85
86#ifndef DEBUG_TEST
87#define DEBUG_TEST 0
88#endif
89
90#define MAKE_CONST_LINE(line, pts) \
91    const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}
92#define MAKE_CONST_QUAD(quad, pts) \
93    const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
94            {pts[2].fX, pts[2].fY}}
95#define MAKE_CONST_CUBIC(cubic, pts) \
96    const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
97            {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}
98
99static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
100        Intersections& intersections) {
101    MAKE_CONST_LINE(aLine, a);
102    MAKE_CONST_LINE(bLine, b);
103    return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
104}
105
106static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
107        Intersections& intersections) {
108    MAKE_CONST_QUAD(aQuad, a);
109    MAKE_CONST_LINE(bLine, b);
110    return intersect(aQuad, bLine, intersections);
111}
112
113static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],
114        Intersections& intersections) {
115    MAKE_CONST_CUBIC(aCubic, a);
116    MAKE_CONST_LINE(bLine, b);
117    return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
118}
119
120static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
121        Intersections& intersections) {
122    MAKE_CONST_QUAD(aQuad, a);
123    MAKE_CONST_QUAD(bQuad, b);
124#define TRY_QUARTIC_SOLUTION 1
125#if TRY_QUARTIC_SOLUTION
126    intersect2(aQuad, bQuad, intersections);
127#else
128    intersect(aQuad, bQuad, intersections);
129#endif
130    return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed;
131}
132
133static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
134        Intersections& intersections) {
135    MAKE_CONST_CUBIC(aCubic, a);
136    MAKE_CONST_CUBIC(bCubic, b);
137    intersect(aCubic, bCubic, intersections);
138    return intersections.fUsed;
139}
140
141static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
142        SkScalar y, bool flipped, Intersections& intersections) {
143    MAKE_CONST_LINE(aLine, a);
144    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
145}
146
147static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
148        SkScalar y, bool flipped, Intersections& intersections) {
149    MAKE_CONST_QUAD(aQuad, a);
150    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
151}
152
153static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
154        SkScalar y, bool flipped, Intersections& intersections) {
155    MAKE_CONST_CUBIC(aCubic, a);
156    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
157}
158
159static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
160        SkScalar x, bool flipped, Intersections& intersections) {
161    MAKE_CONST_LINE(aLine, a);
162    return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
163}
164
165static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
166        SkScalar x, bool flipped, Intersections& intersections) {
167    MAKE_CONST_QUAD(aQuad, a);
168    return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
169}
170
171static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
172        SkScalar x, bool flipped, Intersections& intersections) {
173    MAKE_CONST_CUBIC(aCubic, a);
174    return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
175}
176
177static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
178        SkScalar , SkScalar , bool , Intersections& ) = {
179    NULL,
180    VLineIntersect,
181    VQuadIntersect,
182    VCubicIntersect
183};
184
185static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
186    MAKE_CONST_LINE(line, a);
187    double x, y;
188    xy_at_t(line, t, x, y);
189    out->fX = SkDoubleToScalar(x);
190    out->fY = SkDoubleToScalar(y);
191}
192
193static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
194    MAKE_CONST_QUAD(quad, a);
195    double x, y;
196    xy_at_t(quad, t, x, y);
197    out->fX = SkDoubleToScalar(x);
198    out->fY = SkDoubleToScalar(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
463static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
464        Intersections& intersections) {
465    MAKE_CONST_QUAD(aQuad, a);
466    MAKE_CONST_LINE(bLine, b);
467    return intersectRay(aQuad, bLine, intersections);
468}
469
470class Segment;
471
472// sorting angles
473// given angles of {dx dy ddx ddy dddx dddy} sort them
474class Angle {
475public:
476    // FIXME: this is bogus for quads and cubics
477    // if the quads and cubics' line from end pt to ctrl pt are coincident,
478    // there's no obvious way to determine the curve ordering from the
479    // derivatives alone. In particular, if one quadratic's coincident tangent
480    // is longer than the other curve, the final control point can place the
481    // longer curve on either side of the shorter one.
482    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
483    // may provide some help, but nothing has been figured out yet.
484
485 //   start here
486    /*(
487    for quads and cubics, set up a parameterized line (e.g. LineParameters )
488    for points [0] to [1]. See if point [2] is on that line, or on one side
489    or the other. If it both quads' end points are on the same side, choose
490    the shorter tangent. If the tangents are equal, choose the better second
491    tangent angle
492
493    maybe I set up LineParameters lazily
494    */
495    bool operator<(const Angle& rh) const {
496        double y = dy();
497        double ry = rh.dy();
498        if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
499            return y < 0;
500        }
501        double x = dx();
502        double rx = rh.dx();
503        if (y == 0 && ry == 0 && x * rx < 0) {
504            return x < rx;
505        }
506        AngleValue cmp = x * ry - rx * y;
507        if (!approximately_zero(cmp)) {
508            return cmp < 0;
509        }
510        // at this point, the initial tangent line is coincident
511    #if !HIGH_DEF_ANGLES // old way
512        AngleValue dy = approximately_pin(fDy + fDDy);
513        AngleValue rdy = approximately_pin(rh.fDy + rh.fDDy);
514        if (dy * rdy < 0) {
515            return dy < 0;
516        }
517        AngleValue dx = approximately_pin(fDx + fDDx);
518        AngleValue rdx = approximately_pin(rh.fDx + rh.fDDx);
519        if (dy == 0 && rdy == 0 && dx * rdx < 0) {
520            return dx < rdx;
521        }
522        cmp = dx * rdy - rdx * dy;
523        if (!approximately_zero(cmp)) {
524            return cmp < 0;
525        }
526        dy = approximately_pin(dy + fDDDy);
527        rdy = approximately_pin(rdy + rh.fDDDy);
528        if (dy * rdy < 0) {
529            return dy < 0;
530        }
531        dx = approximately_pin(dx + fDDDx);
532        rdx = approximately_pin(rdx + rh.fDDDx);
533        if (dy == 0 && rdy == 0 && dx * rdx < 0) {
534            return dx < rdx;
535        }
536        return dx * rdy < rdx * dy;
537    #else // new way
538        if (fSide * rh.fSide <= 0) {
539            SkASSERT(fSide != rh.fSide);
540            return fSide < rh.fSide;
541        }
542    #if 0 // the following code is a bust. In particular, tangent length doesn't provide a sort
543        if (y != ry) {
544            return (fabs(y) < fabs(ry)) ^ (fSide > 0);
545        }
546        if (x != rx) {
547            return (fabs(x) < fabs(rx)) ^ (fSide > 0);
548        }
549        // sort by second tangent angle
550        cmp = fD2x * rh.fD2y - rh.fD2x * fD2y;
551        if (!approximately_zero(cmp)) {
552            return cmp < 0;
553        }
554        SkASSERT(0); // add code for cubic case
555    #else
556        SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
557        SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
558        // FIXME: until I can think of something better, project a ray perpendicular from the
559        // end of the shorter tangent through both curves and use the resulting angle to sort
560        // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
561        double len = fTangent1.normalSquared();
562        double rlen = rh.fTangent1.normalSquared();
563        SkPoint ray[2];
564        const Quadratic& q = len < rlen ? fQ : rh.fQ;
565        ray[0].fX = SkDoubleToScalar(q[1].x);
566        ray[0].fY = SkDoubleToScalar(q[1].y);
567        ray[1].fX = SkDoubleToScalar((q[0].x + q[2].x) / 2);
568        ray[1].fY = SkDoubleToScalar((q[0].y + q[2].y) / 2);
569        Intersections i, ri;
570        int roots = QuadRayIntersect(fPts, ray, i);
571        SkASSERT(roots > 0);
572        int rroots = QuadRayIntersect(rh.fPts, ray, ri);
573        SkASSERT(rroots > 0);
574        SkPoint loc;
575        SkScalar best = SK_ScalarInfinity;
576        SkScalar dx, dy, dist;
577        int index;
578        for (index = 0; index < roots; ++index) {
579            QuadXYAtT(fPts, i.fT[0][index], &loc);
580            dx = loc.fX - ray[0].fX;
581            dy = loc.fY - ray[0].fY;
582            dist = dx * dx + dy * dy;
583            if (best > dist) {
584                best = dist;
585            }
586        }
587        for (index = 0; index < rroots; ++index) {
588            QuadXYAtT(rh.fPts, ri.fT[0][index], &loc);
589            dx = loc.fX - ray[0].fX;
590            dy = loc.fY - ray[0].fY;
591            dist = dx * dx + dy * dy;
592            if (best > dist) {
593                return fSide < 0;
594            }
595        }
596        return fSide > 0;
597    #endif
598    #endif
599    }
600
601    double dx() const {
602#if HIGH_DEF_ANGLES
603        return fTangent1.dx();
604#else
605        return fDx;
606#endif
607    }
608
609    double dy() const {
610#if HIGH_DEF_ANGLES
611        return fTangent1.dy();
612#else
613        return fDy;
614#endif
615    }
616
617    int end() const {
618        return fEnd;
619    }
620
621    bool isHorizontal() const {
622#if HIGH_DEF_ANGLES
623        return dy() == 0 && fVerb == SkPath::kLine_Verb;
624#else
625        return fDy == 0 && fDDy == 0 && fDDDy == 0;
626#endif
627    }
628
629    // high precision version
630#if HIGH_DEF_ANGLES
631    void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
632            int start, int end, double startT, double endT) {
633        fSegment = segment;
634        fStart = start;
635        fEnd = end;
636        fPts = orig;
637        fVerb = verb;
638        switch (verb) {
639        case SkPath::kLine_Verb:
640            _Line l;
641            LineSubDivideHD(orig, startT, endT, l);
642            // OPTIMIZATION: for pure line compares, we never need fTangent1.c
643            fTangent1.lineEndPoints(l);
644            fSide = 0;
645            break;
646        case SkPath::kQuad_Verb:
647            QuadSubDivideHD(orig, startT, endT, fQ);
648            fTangent1.quadEndPoints(fQ, 0, 1);
649            fSide = -fTangent1.pointDistance(fQ[2]); // not normalized -- compare sign only
650            break;
651        case SkPath::kCubic_Verb:
652            Cubic c;
653            CubicSubDivideHD(orig, startT, endT, c);
654            fTangent1.cubicEndPoints(c, 0, 1);
655            fSide = -fTangent1.pointDistance(c[2]); // not normalized -- compare sign only
656            break;
657        default:
658            SkASSERT(0);
659        }
660        // OPTIMIZATION: don't need these, access fTangent1 directly
661    }
662
663#else
664    // since all angles share a point, this needs to know which point
665    // is the common origin, i.e., whether the center is at pts[0] or pts[verb]
666    // practically, this should only be called by addAngle
667    void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment,
668            int start, int end) {
669        SkASSERT(start != end);
670        fSegment = segment;
671        fStart = start;
672        fEnd = end;
673        fDx = approximately_pin(pts[1].fX - pts[0].fX); // b - a
674        fDy = approximately_pin(pts[1].fY - pts[0].fY);
675        if (verb == SkPath::kLine_Verb) {
676            fDDx = fDDy = fDDDx = fDDDy = 0;
677            return;
678        }
679        fDDx = approximately_pin(pts[2].fX - pts[1].fX - fDx); // a - 2b + c
680        fDDy = approximately_pin(pts[2].fY - pts[1].fY - fDy);
681        if (verb == SkPath::kQuad_Verb) {
682            fDDDx = fDDDy = 0;
683            return;
684        }
685        fDDDx = approximately_pin(pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX);
686        fDDDy = approximately_pin(pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY);
687    }
688
689    // noncoincident quads/cubics may have the same initial angle
690    // as lines, so must sort by derivatives as well
691    // if flatness turns out to be a reasonable way to sort, use the below:
692    void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
693            int start, int end) {
694        fSegment = segment;
695        fStart = start;
696        fEnd = end;
697        fDx = pts[1].fX - pts[0].fX; // b - a
698        fDy = pts[1].fY - pts[0].fY;
699        if (verb == SkPath::kLine_Verb) {
700            fDDx = fDDy = fDDDx = fDDDy = 0;
701            return;
702        }
703        if (verb == SkPath::kQuad_Verb) {
704            int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx);
705            int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy);
706            int larger = std::max(abs(uplsX), abs(uplsY));
707            int shift = 0;
708            double flatT;
709            SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point)
710            LineParameters implicitLine;
711            MAKE_CONST_LINE(tangent, pts);
712            implicitLine.lineEndPoints(tangent);
713            implicitLine.normalize();
714            while (larger > UlpsEpsilon * 1024) {
715                larger >>= 2;
716                ++shift;
717                flatT = 0.5 / (1 << shift);
718                QuadXYAtT(pts, flatT, &ddPt);
719                _Point _pt = {ddPt.fX, ddPt.fY};
720                double distance = implicitLine.pointDistance(_pt);
721                if (approximately_zero(distance)) {
722                    SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance);
723                    break;
724                }
725            }
726            flatT = 0.5 / (1 << shift);
727            QuadXYAtT(pts, flatT, &ddPt);
728            fDDx = ddPt.fX - pts[0].fX;
729            fDDy = ddPt.fY - pts[0].fY;
730            SkASSERT(fDDx != 0 || fDDy != 0);
731            fDDDx = fDDDy = 0;
732            return;
733        }
734        SkASSERT(0); // FIXME: add cubic case
735    }
736#endif
737
738    Segment* segment() const {
739        return const_cast<Segment*>(fSegment);
740    }
741
742    int sign() const {
743        return SkSign32(fStart - fEnd);
744    }
745
746    int start() const {
747        return fStart;
748    }
749
750#if DEBUG_ANGLE
751    void debugShow(const SkPoint& a) const {
752#if HIGH_DEF_ANGLES
753        SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n",
754                dx(), dy(), fSide);
755#else
756        SkDebugf("    d=(%1.9g,%1.9g) dd=(%1.9g,%1.9g) ddd=(%1.9g,%1.9g)\n",
757                fDx, fDy, fDDx, fDDy, fDDDx, fDDDy);
758        AngleValue ax = (AngleValue) a.fX;
759        AngleValue ay = (AngleValue) a.fY;
760        AngleValue bx, by, cx, cy, dx, dy;
761        bx = ax + fDx; // add b - a
762        by = ay + fDy;
763        cx = ax + 2 * fDx + fDDx; // add a + 2(b - a) to a - 2b + c
764        cy = ay + 2 * fDy + fDDy;
765        if (fDDDx == 0 && fDDDy == 0) {
766            if (fDDx == 0 && fDDy == 0) {
767                SkDebugf(
768"    {SkPath::kLine_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}        }},\n",
769                        ax, ay, bx, by);
770            } else {
771                SkDebugf(
772"    {SkPath::kQuad_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
773                        ax, ay, bx, by, cx, cy);
774            }
775        } else {
776            dx = fDDDx - ax - 3 * (cx - bx);
777            dy = fDDDy - ay - 3 * (cy - by);
778            SkDebugf(
779"    {SkPath::kCubic_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
780                    ax, ay, bx, by, cx, cy, dx, dy);
781        }
782#endif
783    }
784#endif
785
786private:
787#if HIGH_DEF_ANGLES
788    const SkPoint* fPts;
789    Quadratic fQ;
790    SkPath::Verb fVerb;
791    double fSide;
792    LineParameters fTangent1;
793#else
794    AngleValue fDx;
795    AngleValue fDy;
796    AngleValue fDDx;
797    AngleValue fDDy;
798    AngleValue fDDDx;
799    AngleValue fDDDy;
800#endif
801    const Segment* fSegment;
802    int fStart;
803    int fEnd;
804};
805
806static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
807    int angleCount = angles.count();
808    int angleIndex;
809    angleList.setReserve(angleCount);
810    for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
811        *angleList.append() = &angles[angleIndex];
812    }
813    QSort<Angle>(angleList.begin(), angleList.end() - 1);
814}
815
816// Bounds, unlike Rect, does not consider a line to be empty.
817struct Bounds : public SkRect {
818    static bool Intersects(const Bounds& a, const Bounds& b) {
819        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
820                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
821    }
822
823    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
824        if (left < fLeft) {
825            fLeft = left;
826        }
827        if (top < fTop) {
828            fTop = top;
829        }
830        if (right > fRight) {
831            fRight = right;
832        }
833        if (bottom > fBottom) {
834            fBottom = bottom;
835        }
836    }
837
838    void add(const Bounds& toAdd) {
839        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
840    }
841
842    bool isEmpty() {
843        return fLeft > fRight || fTop > fBottom
844                || (fLeft == fRight && fTop == fBottom)
845                || isnan(fLeft) || isnan(fRight)
846                || isnan(fTop) || isnan(fBottom);
847    }
848
849    void setCubicBounds(const SkPoint a[4]) {
850        _Rect dRect;
851        MAKE_CONST_CUBIC(cubic, a);
852        dRect.setBounds(cubic);
853        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
854                (float) dRect.bottom);
855    }
856
857    void setQuadBounds(const SkPoint a[3]) {
858        MAKE_CONST_QUAD(quad, a);
859        _Rect dRect;
860        dRect.setBounds(quad);
861        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
862                (float) dRect.bottom);
863    }
864};
865
866static bool useInnerWinding(int outerWinding, int innerWinding) {
867    SkASSERT(outerWinding != innerWinding);
868    int absOut = abs(outerWinding);
869    int absIn = abs(innerWinding);
870    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
871    if (outerWinding * innerWinding < 0) {
872#if DEBUG_WINDING
873        SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
874                outerWinding, innerWinding, result ? "true" : "false");
875#endif
876    }
877    return result;
878}
879
880struct Span {
881    Segment* fOther;
882    mutable SkPoint fPt; // lazily computed as needed
883    double fT;
884    double fOtherT; // value at fOther[fOtherIndex].fT
885    int fOtherIndex;  // can't be used during intersection
886    int fWindSum; // accumulated from contours surrounding this one
887    int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
888    int fWindValueOpp; // opposite value, if any (for binary ops with coincidence)
889    bool fDone; // if set, this span to next higher T has been processed
890};
891
892static const bool opLookup[][2][2] = {
893    //     ==0             !=0
894    //  b      a        b      a
895    {{true , false}, {false, true }}, // a - b
896    {{false, false}, {true , true }}, // a & b
897    {{true , true }, {false, false}}, // a | b
898    {{true , true }, {true , true }}, // a ^ b
899};
900
901static bool activeOp(bool angleIsOp, int otherNonZero, ShapeOp op) {
902    return opLookup[op][otherNonZero][angleIsOp];
903}
904
905class Segment {
906public:
907    Segment() {
908#if DEBUG_DUMP
909        fID = ++gSegmentID;
910#endif
911    }
912
913    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const {
914        if (activeAngleInner(index, done, angles)) {
915            return true;
916        }
917        double referenceT = fTs[index].fT;
918        int lesser = index;
919        while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
920            if (activeAngleOther(lesser, done, angles)) {
921                return true;
922            }
923        }
924        do {
925            if (activeAngleOther(index, done, angles)) {
926                return true;
927            }
928        } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
929        return false;
930    }
931
932    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const {
933        Span* span = &fTs[index];
934        Segment* other = span->fOther;
935        int oIndex = span->fOtherIndex;
936        return other->activeAngleInner(oIndex, done, angles);
937    }
938
939    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const {
940        int next = nextSpan(index, 1);
941        if (next > 0) {
942            const Span& upSpan = fTs[index];
943            if (upSpan.fWindValue) {
944                addAngle(angles, index, next);
945                if (upSpan.fDone) {
946                    done++;
947                } else if (upSpan.fWindSum != SK_MinS32) {
948                    return true;
949                }
950            }
951        }
952        int prev = nextSpan(index, -1);
953        // edge leading into junction
954        if (prev >= 0) {
955            const Span& downSpan = fTs[prev];
956            if (downSpan.fWindValue) {
957                addAngle(angles, index, prev);
958                if (downSpan.fDone) {
959                    done++;
960                 } else if (downSpan.fWindSum != SK_MinS32) {
961                    return true;
962                }
963            }
964        }
965        return false;
966    }
967
968    SkScalar activeTop() const {
969        SkASSERT(!done());
970        int count = fTs.count();
971        SkScalar result = SK_ScalarMax;
972        bool lastDone = true;
973        for (int index = 0; index < count; ++index) {
974            bool done = fTs[index].fDone;
975            if (!done || !lastDone) {
976                SkScalar y = yAtT(index);
977                if (result > y) {
978                    result = y;
979                }
980            }
981            lastDone = done;
982        }
983        SkASSERT(result < SK_ScalarMax);
984        return result;
985    }
986
987    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
988        SkASSERT(start != end);
989        Angle* angle = angles.append();
990#if HIGH_DEF_ANGLES==0 // old way
991        SkPoint edge[4];
992        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
993        angle->set(edge, fVerb, this, start, end);
994#else // new way : compute temp edge in higher precision
995        angle->set(fPts, fVerb, this, start, end, fTs[start].fT, fTs[end].fT);
996#endif
997    }
998
999    void addCancelOutsides(double tStart, double oStart, Segment& other,
1000            double oEnd) {
1001        int tIndex = -1;
1002        int tCount = fTs.count();
1003        int oIndex = -1;
1004        int oCount = other.fTs.count();
1005        do {
1006            ++tIndex;
1007        } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
1008        int tIndexStart = tIndex;
1009        do {
1010            ++oIndex;
1011        } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
1012        int oIndexStart = oIndex;
1013        double nextT;
1014        do {
1015            nextT = fTs[++tIndex].fT;
1016        } while (nextT < 1 && approximately_negative(nextT - tStart));
1017        double oNextT;
1018        do {
1019            oNextT = other.fTs[++oIndex].fT;
1020        } while (oNextT < 1 && approximately_negative(oNextT - oStart));
1021        // at this point, spans before and after are at:
1022        //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1023        // if tIndexStart == 0, no prior span
1024        // if nextT == 1, no following span
1025
1026        // advance the span with zero winding
1027        // if the following span exists (not past the end, non-zero winding)
1028        // connect the two edges
1029        if (!fTs[tIndexStart].fWindValue) {
1030            if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1031    #if DEBUG_CONCIDENT
1032                SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1033                        __FUNCTION__, fID, other.fID, tIndexStart - 1,
1034                        fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
1035                        xyAtT(tIndexStart).fY);
1036    #endif
1037                addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false);
1038            }
1039            if (nextT < 1 && fTs[tIndex].fWindValue) {
1040    #if DEBUG_CONCIDENT
1041                SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1042                        __FUNCTION__, fID, other.fID, tIndex,
1043                        fTs[tIndex].fT, xyAtT(tIndex).fX,
1044                        xyAtT(tIndex).fY);
1045    #endif
1046                addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false);
1047            }
1048        } else {
1049            SkASSERT(!other.fTs[oIndexStart].fWindValue);
1050            if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
1051    #if DEBUG_CONCIDENT
1052                SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1053                        __FUNCTION__, fID, other.fID, oIndexStart - 1,
1054                        other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
1055                        other.xyAtT(oIndexStart).fY);
1056                other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1057    #endif
1058            }
1059            if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
1060    #if DEBUG_CONCIDENT
1061                SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1062                        __FUNCTION__, fID, other.fID, oIndex,
1063                        other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
1064                        other.xyAtT(oIndex).fY);
1065                other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1066    #endif
1067            }
1068        }
1069    }
1070
1071    void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
1072            double oEnd) {
1073        // walk this to outsideTs[0]
1074        // walk other to outsideTs[1]
1075        // if either is > 0, add a pointer to the other, copying adjacent winding
1076        int tIndex = -1;
1077        int oIndex = -1;
1078        double tStart = outsideTs[0];
1079        double oStart = outsideTs[1];
1080        do {
1081            ++tIndex;
1082        } while (!approximately_negative(tStart - fTs[tIndex].fT));
1083        do {
1084            ++oIndex;
1085        } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
1086        if (tIndex > 0 || oIndex > 0) {
1087            addTPair(tStart, other, oStart, false);
1088        }
1089        tStart = fTs[tIndex].fT;
1090        oStart = other.fTs[oIndex].fT;
1091        do {
1092            double nextT;
1093            do {
1094                nextT = fTs[++tIndex].fT;
1095            } while (approximately_negative(nextT - tStart));
1096            tStart = nextT;
1097            do {
1098                nextT = other.fTs[++oIndex].fT;
1099            } while (approximately_negative(nextT - oStart));
1100            oStart = nextT;
1101            if (tStart == 1 && oStart == 1) {
1102                break;
1103            }
1104            addTPair(tStart, other, oStart, false);
1105        } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
1106    }
1107
1108    void addCubic(const SkPoint pts[4], bool operand) {
1109        init(pts, SkPath::kCubic_Verb, operand);
1110        fBounds.setCubicBounds(pts);
1111    }
1112
1113    // FIXME: this needs to defer add for aligned consecutive line segments
1114    SkPoint addCurveTo(int start, int end, SkPath& path, bool active) {
1115        SkPoint edge[4];
1116        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
1117        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
1118        if (active) {
1119    #if DEBUG_PATH_CONSTRUCTION
1120            SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
1121                    kLVerbStr[fVerb], edge[1].fX, edge[1].fY);
1122            if (fVerb > 1) {
1123                SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY);
1124            }
1125            if (fVerb > 2) {
1126                SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY);
1127            }
1128            SkDebugf("\n");
1129    #endif
1130            switch (fVerb) {
1131                case SkPath::kLine_Verb:
1132                    path.lineTo(edge[1].fX, edge[1].fY);
1133                    break;
1134                case SkPath::kQuad_Verb:
1135                    path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY);
1136                    break;
1137                case SkPath::kCubic_Verb:
1138                    path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY,
1139                            edge[3].fX, edge[3].fY);
1140                    break;
1141                default:
1142                    SkASSERT(0);
1143            }
1144        }
1145        return edge[fVerb];
1146    }
1147
1148    void addLine(const SkPoint pts[2], bool operand) {
1149        init(pts, SkPath::kLine_Verb, operand);
1150        fBounds.set(pts, 2);
1151    }
1152
1153    const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) {
1154        const SkPoint& pt = xyAtT(tIndex);
1155        if (active) {
1156    #if DEBUG_PATH_CONSTRUCTION
1157            SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
1158    #endif
1159            path.moveTo(pt.fX, pt.fY);
1160        }
1161        return pt;
1162    }
1163
1164    // add 2 to edge or out of range values to get T extremes
1165    void addOtherT(int index, double otherT, int otherIndex) {
1166        Span& span = fTs[index];
1167        span.fOtherT = otherT;
1168        span.fOtherIndex = otherIndex;
1169    }
1170
1171    void addQuad(const SkPoint pts[3], bool operand) {
1172        init(pts, SkPath::kQuad_Verb, operand);
1173        fBounds.setQuadBounds(pts);
1174    }
1175
1176    // Defer all coincident edge processing until
1177    // after normal intersections have been computed
1178
1179// no need to be tricky; insert in normal T order
1180// resolve overlapping ts when considering coincidence later
1181
1182    // add non-coincident intersection. Resulting edges are sorted in T.
1183    int addT(double newT, Segment* other) {
1184        // FIXME: in the pathological case where there is a ton of intercepts,
1185        //  binary search?
1186        int insertedAt = -1;
1187        size_t tCount = fTs.count();
1188        // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
1189        if (approximately_less_than_zero(newT)) {
1190            newT = 0;
1191        }
1192        if (approximately_greater_than_one(newT)) {
1193            newT = 1;
1194        }
1195        for (size_t index = 0; index < tCount; ++index) {
1196            // OPTIMIZATION: if there are three or more identical Ts, then
1197            // the fourth and following could be further insertion-sorted so
1198            // that all the edges are clockwise or counterclockwise.
1199            // This could later limit segment tests to the two adjacent
1200            // neighbors, although it doesn't help with determining which
1201            // circular direction to go in.
1202            if (newT < fTs[index].fT) {
1203                insertedAt = index;
1204                break;
1205            }
1206        }
1207        Span* span;
1208        if (insertedAt >= 0) {
1209            span = fTs.insert(insertedAt);
1210        } else {
1211            insertedAt = tCount;
1212            span = fTs.append();
1213        }
1214        span->fT = newT;
1215        span->fOther = other;
1216        span->fPt.fX = SK_ScalarNaN;
1217        span->fWindSum = SK_MinS32;
1218        span->fWindValue = 1;
1219        span->fWindValueOpp = 0;
1220        if ((span->fDone = newT == 1)) {
1221            ++fDoneSpans;
1222        }
1223        return insertedAt;
1224    }
1225
1226    // set spans from start to end to decrement by one
1227    // note this walks other backwards
1228    // FIMXE: there's probably an edge case that can be constructed where
1229    // two span in one segment are separated by float epsilon on one span but
1230    // not the other, if one segment is very small. For this
1231    // case the counts asserted below may or may not be enough to separate the
1232    // spans. Even if the counts work out, what if the spans aren't correctly
1233    // sorted? It feels better in such a case to match the span's other span
1234    // pointer since both coincident segments must contain the same spans.
1235    void addTCancel(double startT, double endT, Segment& other,
1236            double oStartT, double oEndT) {
1237        SkASSERT(!approximately_negative(endT - startT));
1238        SkASSERT(!approximately_negative(oEndT - oStartT));
1239        bool binary = fOperand != other.fOperand;
1240        int index = 0;
1241        while (!approximately_negative(startT - fTs[index].fT)) {
1242            ++index;
1243        }
1244        int oIndex = other.fTs.count();
1245        while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
1246            ;
1247        double tRatio = (oEndT - oStartT) / (endT - startT);
1248        Span* test = &fTs[index];
1249        Span* oTest = &other.fTs[oIndex];
1250        SkTDArray<double> outsideTs;
1251        SkTDArray<double> oOutsideTs;
1252        do {
1253            bool decrement = test->fWindValue && oTest->fWindValue;
1254            bool track = test->fWindValue || oTest->fWindValue;
1255            double testT = test->fT;
1256            double oTestT = oTest->fT;
1257            Span* span = test;
1258            do {
1259                if (decrement) {
1260                    if (binary) {
1261                        --(span->fWindValueOpp);
1262                    } else {
1263                        decrementSpan(span);
1264                    }
1265                } else if (track && span->fT < 1 && oTestT < 1) {
1266                    TrackOutside(outsideTs, span->fT, oTestT);
1267                }
1268                span = &fTs[++index];
1269            } while (approximately_negative(span->fT - testT));
1270            Span* oSpan = oTest;
1271            double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
1272            double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
1273            SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
1274            while (approximately_negative(otherTMatchStart - oSpan->fT)
1275                    && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
1276        #ifdef SK_DEBUG
1277                SkASSERT(originalWindValue == oSpan->fWindValue);
1278        #endif
1279                if (decrement) {
1280                    other.decrementSpan(oSpan);
1281                } else if (track && oSpan->fT < 1 && testT < 1) {
1282                    TrackOutside(oOutsideTs, oSpan->fT, testT);
1283                }
1284                if (!oIndex) {
1285                    break;
1286                }
1287                oSpan = &other.fTs[--oIndex];
1288            }
1289            test = span;
1290            oTest = oSpan;
1291        } while (!approximately_negative(endT - test->fT));
1292        SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
1293        // FIXME: determine if canceled edges need outside ts added
1294        if (!done() && outsideTs.count()) {
1295            double tStart = outsideTs[0];
1296            double oStart = outsideTs[1];
1297            addCancelOutsides(tStart, oStart, other, oEndT);
1298            int count = outsideTs.count();
1299            if (count > 2) {
1300                double tStart = outsideTs[count - 2];
1301                double oStart = outsideTs[count - 1];
1302                addCancelOutsides(tStart, oStart, other, oEndT);
1303            }
1304        }
1305        if (!other.done() && oOutsideTs.count()) {
1306            double tStart = oOutsideTs[0];
1307            double oStart = oOutsideTs[1];
1308            other.addCancelOutsides(tStart, oStart, *this, endT);
1309        }
1310    }
1311
1312    // set spans from start to end to increment the greater by one and decrement
1313    // the lesser
1314    void addTCoincident(const bool isXor, double startT, double endT,
1315            Segment& other, double oStartT, double oEndT) {
1316        SkASSERT(!approximately_negative(endT - startT));
1317        SkASSERT(!approximately_negative(oEndT - oStartT));
1318        bool binary = fOperand != other.fOperand;
1319        int index = 0;
1320        while (!approximately_negative(startT - fTs[index].fT)) {
1321            ++index;
1322        }
1323        int oIndex = 0;
1324        while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
1325            ++oIndex;
1326        }
1327        double tRatio = (oEndT - oStartT) / (endT - startT);
1328        Span* test = &fTs[index];
1329        Span* oTest = &other.fTs[oIndex];
1330        SkTDArray<double> outsideTs;
1331        SkTDArray<double> xOutsideTs;
1332        SkTDArray<double> oOutsideTs;
1333        SkTDArray<double> oxOutsideTs;
1334        do {
1335            bool transfer = test->fWindValue && oTest->fWindValue;
1336            bool decrementThis = (test->fWindValue < oTest->fWindValue) & !isXor;
1337            bool decrementOther = (test->fWindValue >= oTest->fWindValue) & !isXor;
1338            Span* end = test;
1339            double startT = end->fT;
1340            int startIndex = index;
1341            double oStartT = oTest->fT;
1342            int oStartIndex = oIndex;
1343            do {
1344                if (transfer) {
1345                    if (decrementOther) {
1346                #ifdef SK_DEBUG
1347                        SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue);
1348                #endif
1349                        if (binary) {
1350                            ++(end->fWindValueOpp);
1351                        } else {
1352                            ++(end->fWindValue);
1353                        }
1354                    } else if (decrementSpan(end)) {
1355                        TrackOutside(outsideTs, end->fT, oStartT);
1356                    }
1357                } else if (oTest->fWindValue) {
1358                    SkASSERT(!decrementOther);
1359                    if (startIndex > 0 && fTs[startIndex - 1].fWindValue) {
1360                        TrackOutside(xOutsideTs, end->fT, oStartT);
1361                    }
1362                }
1363                end = &fTs[++index];
1364            } while (approximately_negative(end->fT - test->fT));
1365        // because of the order in which coincidences are resolved, this and other
1366        // may not have the same intermediate points. Compute the corresponding
1367        // intermediate T values (using this as the master, other as the follower)
1368        // and walk other conditionally -- hoping that it catches up in the end
1369            double otherTMatch = (test->fT - startT) * tRatio + oStartT;
1370            Span* oEnd = oTest;
1371            while (!approximately_negative(oEndT - oEnd->fT) && approximately_negative(oEnd->fT - otherTMatch)) {
1372                if (transfer) {
1373                    if (decrementThis) {
1374                 #ifdef SK_DEBUG
1375                       SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
1376                #endif
1377                        if (binary) {
1378                            ++(oEnd->fWindValueOpp);
1379                        } else {
1380                            ++(oEnd->fWindValue);
1381                        }
1382                    } else if (other.decrementSpan(oEnd)) {
1383                        TrackOutside(oOutsideTs, oEnd->fT, startT);
1384                    }
1385                } else if (test->fWindValue) {
1386                    SkASSERT(!decrementOther);
1387                    if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) {
1388                        SkASSERT(0); // track for later?
1389                    }
1390                }
1391                oEnd = &other.fTs[++oIndex];
1392            }
1393            test = end;
1394            oTest = oEnd;
1395        } while (!approximately_negative(endT - test->fT));
1396        SkASSERT(approximately_negative(oTest->fT - oEndT));
1397        SkASSERT(approximately_negative(oEndT - oTest->fT));
1398        if (!done()) {
1399            if (outsideTs.count()) {
1400                addCoinOutsides(outsideTs, other, oEndT);
1401            }
1402            if (xOutsideTs.count()) {
1403                addCoinOutsides(xOutsideTs, other, oEndT);
1404            }
1405        }
1406        if (!other.done() && oOutsideTs.count()) {
1407            other.addCoinOutsides(oOutsideTs, *this, endT);
1408        }
1409    }
1410
1411    // FIXME: this doesn't prevent the same span from being added twice
1412    // fix in caller, assert here?
1413    void addTPair(double t, Segment& other, double otherT, bool borrowWind) {
1414        int tCount = fTs.count();
1415        for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1416            const Span& span = fTs[tIndex];
1417            if (!approximately_negative(span.fT - t)) {
1418                break;
1419            }
1420            if (approximately_negative(span.fT - t) && span.fOther == &other && span.fOtherT == otherT) {
1421#if DEBUG_ADD_T_PAIR
1422                SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1423                        __FUNCTION__, fID, t, other.fID, otherT);
1424#endif
1425                return;
1426            }
1427        }
1428#if DEBUG_ADD_T_PAIR
1429        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1430                __FUNCTION__, fID, t, other.fID, otherT);
1431#endif
1432        int insertedAt = addT(t, &other);
1433        int otherInsertedAt = other.addT(otherT, this);
1434        addOtherT(insertedAt, otherT, otherInsertedAt);
1435        other.addOtherT(otherInsertedAt, t, insertedAt);
1436        matchWindingValue(insertedAt, t, borrowWind);
1437        other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
1438    }
1439
1440    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
1441        // add edge leading into junction
1442        if (fTs[SkMin32(end, start)].fWindValue > 0) {
1443            addAngle(angles, end, start);
1444        }
1445        // add edge leading away from junction
1446        int step = SkSign32(end - start);
1447        int tIndex = nextSpan(end, step);
1448        if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) {
1449            addAngle(angles, end, tIndex);
1450        }
1451    }
1452
1453    const Bounds& bounds() const {
1454        return fBounds;
1455    }
1456
1457    void buildAngles(int index, SkTDArray<Angle>& angles) const {
1458        double referenceT = fTs[index].fT;
1459        int lesser = index;
1460        while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
1461            buildAnglesInner(lesser, angles);
1462        }
1463        do {
1464            buildAnglesInner(index, angles);
1465        } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
1466    }
1467
1468    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
1469        Span* span = &fTs[index];
1470        Segment* other = span->fOther;
1471    // if there is only one live crossing, and no coincidence, continue
1472    // in the same direction
1473    // if there is coincidence, the only choice may be to reverse direction
1474        // find edge on either side of intersection
1475        int oIndex = span->fOtherIndex;
1476        // if done == -1, prior span has already been processed
1477        int step = 1;
1478        int next = other->nextSpan(oIndex, step);
1479        if (next < 0) {
1480            step = -step;
1481            next = other->nextSpan(oIndex, step);
1482        }
1483        // add candidate into and away from junction
1484        other->addTwoAngles(next, oIndex, angles);
1485    }
1486
1487    // figure out if the segment's ascending T goes clockwise or not
1488    // not enough context to write this as shown
1489    // instead, add all segments meeting at the top
1490    // sort them using buildAngleList
1491    // find the first in the sort
1492    // see if ascendingT goes to top
1493    bool clockwise(int /* tIndex */) const {
1494        SkASSERT(0); // incomplete
1495        return false;
1496    }
1497
1498    int computeSum(int startIndex, int endIndex) {
1499        SkTDArray<Angle> angles;
1500        addTwoAngles(startIndex, endIndex, angles);
1501        buildAngles(endIndex, angles);
1502        SkTDArray<Angle*> sorted;
1503        sortAngles(angles, sorted);
1504#if DEBUG_SORT
1505        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0);
1506#endif
1507        int angleCount = angles.count();
1508        const Angle* angle;
1509        const Segment* base;
1510        int winding;
1511        int firstIndex = 0;
1512        do {
1513            angle = sorted[firstIndex];
1514            base = angle->segment();
1515            winding = base->windSum(angle);
1516            if (winding != SK_MinS32) {
1517                break;
1518            }
1519            if (++firstIndex == angleCount) {
1520                return SK_MinS32;
1521            }
1522        } while (true);
1523        // turn winding into contourWinding
1524        int spanWinding = base->spanSign(angle);
1525        bool inner = useInnerWinding(winding + spanWinding, winding);
1526    #if DEBUG_WINDING
1527        SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
1528            spanWinding, winding, angle->sign(), inner,
1529            inner ? winding + spanWinding : winding);
1530    #endif
1531        if (inner) {
1532            winding += spanWinding;
1533        }
1534    #if DEBUG_SORT
1535        base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding);
1536    #endif
1537        int nextIndex = firstIndex + 1;
1538        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1539        winding -= base->spanSign(angle);
1540        do {
1541            if (nextIndex == angleCount) {
1542                nextIndex = 0;
1543            }
1544            angle = sorted[nextIndex];
1545            Segment* segment = angle->segment();
1546            int maxWinding = winding;
1547            winding -= segment->spanSign(angle);
1548            if (segment->windSum(angle) == SK_MinS32) {
1549                if (useInnerWinding(maxWinding, winding)) {
1550                    maxWinding = winding;
1551                }
1552                segment->markAndChaseWinding(angle, maxWinding);
1553            }
1554        } while (++nextIndex != lastIndex);
1555        return windSum(SkMin32(startIndex, endIndex));
1556    }
1557
1558    int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const {
1559        int bestT = -1;
1560        SkScalar top = bounds().fTop;
1561        SkScalar bottom = bounds().fBottom;
1562        int end = 0;
1563        do {
1564            int start = end;
1565            end = nextSpan(start, 1);
1566            if (fTs[start].fWindValue == 0) {
1567                continue;
1568            }
1569            SkPoint edge[4];
1570            // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can
1571            // work with the original data directly
1572            double startT = fTs[start].fT;
1573            double endT = fTs[end].fT;
1574            (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
1575            // intersect ray starting at basePt with edge
1576            Intersections intersections;
1577            int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
1578                    false, intersections);
1579            if (pts == 0) {
1580                continue;
1581            }
1582            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1583            // if the intersection is edge on, wait for another one
1584                continue;
1585            }
1586            for (int index = 0; index < pts; ++index) {
1587                SkPoint pt;
1588                double foundT = intersections.fT[0][index];
1589                double testT = startT + (endT - startT) * foundT;
1590                (*SegmentXYAtT[fVerb])(fPts, testT, &pt);
1591                if (bestY < pt.fY && pt.fY < basePt.fY) {
1592                    bestY = pt.fY;
1593                    bestT = foundT < 1 ? start : end;
1594                    hitT = testT;
1595                }
1596            }
1597        } while (fTs[end].fT != 1);
1598        return bestT;
1599    }
1600
1601    bool crossedSpanHalves(const SkPoint& basePt, bool leftHalf, bool rightHalf) {
1602        // if a segment is connected to this one, consider it crossing
1603        int tIndex;
1604        if (fPts[0].fX == basePt.fX) {
1605            tIndex = 0;
1606            do {
1607                const Span& sSpan = fTs[tIndex];
1608                const Segment* sOther = sSpan.fOther;
1609                if (!sOther->fTs[sSpan.fOtherIndex].fWindValue) {
1610                    continue;
1611                }
1612                if (leftHalf ? sOther->fBounds.fLeft < basePt.fX
1613                        : sOther->fBounds.fRight > basePt.fX) {
1614                    return true;
1615                }
1616            } while (fTs[++tIndex].fT == 0);
1617        }
1618        if (fPts[fVerb].fX == basePt.fX) {
1619            tIndex = fTs.count() - 1;
1620            do {
1621                const Span& eSpan = fTs[tIndex];
1622                const Segment* eOther = eSpan.fOther;
1623                if (!eOther->fTs[eSpan.fOtherIndex].fWindValue) {
1624                    continue;
1625                }
1626                if (leftHalf ? eOther->fBounds.fLeft < basePt.fX
1627                        : eOther->fBounds.fRight > basePt.fX) {
1628                    return true;
1629                }
1630            } while (fTs[--tIndex].fT == 1);
1631        }
1632        return false;
1633    }
1634
1635    bool decrementSpan(Span* span) {
1636        SkASSERT(span->fWindValue > 0);
1637        if (--(span->fWindValue) == 0) {
1638            span->fDone = true;
1639            ++fDoneSpans;
1640            return true;
1641        }
1642        return false;
1643    }
1644
1645    bool done() const {
1646        SkASSERT(fDoneSpans <= fTs.count());
1647        return fDoneSpans == fTs.count();
1648    }
1649
1650    bool done(const Angle& angle) const {
1651        int start = angle.start();
1652        int end = angle.end();
1653        const Span& mSpan = fTs[SkMin32(start, end)];
1654        return mSpan.fDone;
1655    }
1656
1657    Segment* findNextOp(SkTDArray<Span*>& chase, bool active,
1658            int& nextStart, int& nextEnd, int& winding, int& spanWinding, ShapeOp op,
1659            const int aXorMask, const int bXorMask) {
1660        const int startIndex = nextStart;
1661        const int endIndex = nextEnd;
1662        int outerWinding = winding;
1663        int innerWinding = winding + spanWinding;
1664    #if DEBUG_WINDING
1665        SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n",
1666                __FUNCTION__, winding, spanWinding, outerWinding, innerWinding);
1667    #endif
1668        if (useInnerWinding(outerWinding, innerWinding)) {
1669            outerWinding = innerWinding;
1670        }
1671        SkASSERT(startIndex != endIndex);
1672        int count = fTs.count();
1673        SkASSERT(startIndex < endIndex ? startIndex < count - 1
1674                : startIndex > 0);
1675        int step = SkSign32(endIndex - startIndex);
1676        int end = nextSpan(startIndex, step);
1677        SkASSERT(end >= 0);
1678        Span* endSpan = &fTs[end];
1679        Segment* other;
1680        if (isSimple(end)) {
1681        // mark the smaller of startIndex, endIndex done, and all adjacent
1682        // spans with the same T value (but not 'other' spans)
1683    #if DEBUG_WINDING
1684            SkDebugf("%s simple\n", __FUNCTION__);
1685    #endif
1686            markDone(SkMin32(startIndex, endIndex), outerWinding);
1687            other = endSpan->fOther;
1688            nextStart = endSpan->fOtherIndex;
1689            double startT = other->fTs[nextStart].fT;
1690            nextEnd = nextStart;
1691            do {
1692                nextEnd += step;
1693            } while (approximately_zero(startT - other->fTs[nextEnd].fT));
1694            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
1695            return other;
1696        }
1697        // more than one viable candidate -- measure angles to find best
1698        SkTDArray<Angle> angles;
1699        SkASSERT(startIndex - endIndex != 0);
1700        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1701        addTwoAngles(startIndex, end, angles);
1702        buildAngles(end, angles);
1703        SkTDArray<Angle*> sorted;
1704        sortAngles(angles, sorted);
1705        int angleCount = angles.count();
1706        int firstIndex = findStartingEdge(sorted, startIndex, end);
1707        SkASSERT(firstIndex >= 0);
1708    #if DEBUG_SORT
1709        debugShowSort(__FUNCTION__, sorted, firstIndex, winding);
1710    #endif
1711        SkASSERT(sorted[firstIndex]->segment() == this);
1712    #if DEBUG_WINDING
1713        SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign());
1714    #endif
1715        int aSumWinding = winding;
1716        int bSumWinding = winding;
1717        bool angleIsOp = sorted[firstIndex]->segment()->operand();
1718        int angleSpan = spanSign(sorted[firstIndex]);
1719        if (angleIsOp) {
1720            bSumWinding -= angleSpan;
1721        } else {
1722            aSumWinding -= angleSpan;
1723        }
1724        int nextIndex = firstIndex + 1;
1725        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1726        const Angle* foundAngle = NULL;
1727        // FIXME: found done logic probably fails if there are more than 4
1728        // sorted angles. It should bias towards the first and last undone
1729        // edges -- but not sure that it won't choose a middle (incorrect)
1730        // edge if one is undone
1731        bool foundDone = false;
1732        bool foundDone2 = false;
1733        // iterate through the angle, and compute everyone's winding
1734        bool altFlipped = false;
1735        bool foundFlipped = false;
1736        int foundMax = SK_MinS32;
1737        int foundSum = SK_MinS32;
1738        Segment* nextSegment;
1739        int lastNonZeroSum = winding;
1740        do {
1741            if (nextIndex == angleCount) {
1742                nextIndex = 0;
1743            }
1744            const Angle* nextAngle = sorted[nextIndex];
1745            nextSegment = nextAngle->segment();
1746            angleIsOp = nextSegment->operand();
1747            int sumWinding = angleIsOp ? bSumWinding : aSumWinding;
1748            int maxWinding = sumWinding;
1749            if (sumWinding) {
1750                lastNonZeroSum = sumWinding;
1751            }
1752            sumWinding -= nextSegment->spanSign(nextAngle);
1753            int xorMask = nextSegment->operand() ? bXorMask : aXorMask;
1754            bool otherNonZero;
1755            if (angleIsOp) {
1756                bSumWinding = sumWinding;
1757                otherNonZero = aSumWinding & aXorMask;
1758            } else {
1759                aSumWinding = sumWinding;
1760                otherNonZero = bSumWinding & bXorMask;
1761            }
1762            altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
1763    #if DEBUG_WINDING
1764            SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
1765            SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
1766                    nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
1767    #endif
1768
1769            if (!(sumWinding & xorMask) && activeOp(angleIsOp, otherNonZero, op)) {
1770                if (!active) {
1771                    markDone(SkMin32(startIndex, endIndex), outerWinding);
1772                    // FIXME: seems like a bug that this isn't calling userInnerWinding
1773                    nextSegment->markWinding(SkMin32(nextAngle->start(),
1774                                nextAngle->end()), maxWinding);
1775    #if DEBUG_WINDING
1776                    SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex);
1777    #endif
1778                    return NULL;
1779                }
1780                if (!foundAngle || foundDone) {
1781                    foundAngle = nextAngle;
1782                    foundDone = nextSegment->done(*nextAngle);
1783                    foundFlipped = altFlipped;
1784                    foundMax = maxWinding;
1785                }
1786                continue;
1787            }
1788            if (!(maxWinding & xorMask) && (!foundAngle || foundDone2)
1789                    && activeOp(angleIsOp, otherNonZero, op)) {
1790        #if DEBUG_WINDING
1791                if (foundAngle && foundDone2) {
1792                    SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex);
1793                }
1794        #endif
1795                foundAngle = nextAngle;
1796                foundDone2 = nextSegment->done(*nextAngle);
1797                foundFlipped = altFlipped;
1798                foundSum = sumWinding;
1799            }
1800            if (nextSegment->done()) {
1801                continue;
1802            }
1803            // if the winding is non-zero, nextAngle does not connect to
1804            // current chain. If we haven't done so already, mark the angle
1805            // as done, record the winding value, and mark connected unambiguous
1806            // segments as well.
1807            if (nextSegment->windSum(nextAngle) == SK_MinS32) {
1808                if (useInnerWinding(maxWinding, sumWinding)) {
1809                    maxWinding = sumWinding;
1810                }
1811                Span* last;
1812                if (foundAngle) {
1813                    last = nextSegment->markAndChaseWinding(nextAngle, maxWinding);
1814                } else {
1815                    last = nextSegment->markAndChaseDone(nextAngle, maxWinding);
1816                }
1817                if (last) {
1818                    *chase.append() = last;
1819                }
1820            }
1821        } while (++nextIndex != lastIndex);
1822        markDone(SkMin32(startIndex, endIndex), outerWinding);
1823        if (!foundAngle) {
1824            return NULL;
1825        }
1826        nextStart = foundAngle->start();
1827        nextEnd = foundAngle->end();
1828        nextSegment = foundAngle->segment();
1829        int flipped = foundFlipped ? -1 : 1;
1830        spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(
1831                SkMin32(nextStart, nextEnd));
1832        if (winding) {
1833    #if DEBUG_WINDING
1834            SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding);
1835            if (foundSum == SK_MinS32) {
1836                SkDebugf("?");
1837            } else {
1838                SkDebugf("%d", foundSum);
1839            }
1840            SkDebugf(" foundMax=");
1841            if (foundMax == SK_MinS32) {
1842                SkDebugf("?");
1843            } else {
1844                SkDebugf("%d", foundMax);
1845            }
1846            SkDebugf("\n");
1847     #endif
1848            winding = foundSum;
1849        }
1850    #if DEBUG_WINDING
1851        SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped);
1852    #endif
1853        return nextSegment;
1854    }
1855
1856    // so the span needs to contain the pairing info found here
1857    // this should include the winding computed for the edge, and
1858    //  what edge it connects to, and whether it is discarded
1859    //  (maybe discarded == abs(winding) > 1) ?
1860    // only need derivatives for duration of sorting, add a new struct
1861    // for pairings, remove extra spans that have zero length and
1862    //  reference an unused other
1863    // for coincident, the last span on the other may be marked done
1864    //  (always?)
1865
1866    // if loop is exhausted, contour may be closed.
1867    // FIXME: pass in close point so we can check for closure
1868
1869    // given a segment, and a sense of where 'inside' is, return the next
1870    // segment. If this segment has an intersection, or ends in multiple
1871    // segments, find the mate that continues the outside.
1872    // note that if there are multiples, but no coincidence, we can limit
1873    // choices to connections in the correct direction
1874
1875    // mark found segments as done
1876
1877    // start is the index of the beginning T of this edge
1878    // it is guaranteed to have an end which describes a non-zero length (?)
1879    // winding -1 means ccw, 1 means cw
1880    Segment* findNextWinding(SkTDArray<Span*>& chase, bool active,
1881            int& nextStart, int& nextEnd, int& winding, int& spanWinding) {
1882        const int startIndex = nextStart;
1883        const int endIndex = nextEnd;
1884        int outerWinding = winding;
1885        int innerWinding = winding + spanWinding;
1886    #if DEBUG_WINDING
1887        SkDebugf("%s winding=%d spanWinding=%d outerWinding=%d innerWinding=%d\n",
1888                __FUNCTION__, winding, spanWinding, outerWinding, innerWinding);
1889    #endif
1890        if (useInnerWinding(outerWinding, innerWinding)) {
1891            outerWinding = innerWinding;
1892        }
1893        SkASSERT(startIndex != endIndex);
1894        int count = fTs.count();
1895        SkASSERT(startIndex < endIndex ? startIndex < count - 1
1896                : startIndex > 0);
1897        int step = SkSign32(endIndex - startIndex);
1898        int end = nextSpan(startIndex, step);
1899        SkASSERT(end >= 0);
1900        Span* endSpan = &fTs[end];
1901        Segment* other;
1902        if (isSimple(end)) {
1903        // mark the smaller of startIndex, endIndex done, and all adjacent
1904        // spans with the same T value (but not 'other' spans)
1905    #if DEBUG_WINDING
1906            SkDebugf("%s simple\n", __FUNCTION__);
1907    #endif
1908            markDone(SkMin32(startIndex, endIndex), outerWinding);
1909            other = endSpan->fOther;
1910            nextStart = endSpan->fOtherIndex;
1911            double startT = other->fTs[nextStart].fT;
1912            nextEnd = nextStart;
1913            do {
1914                nextEnd += step;
1915            } while (approximately_zero(startT - other->fTs[nextEnd].fT));
1916            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
1917            return other;
1918        }
1919        // more than one viable candidate -- measure angles to find best
1920        SkTDArray<Angle> angles;
1921        SkASSERT(startIndex - endIndex != 0);
1922        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1923        addTwoAngles(startIndex, end, angles);
1924        buildAngles(end, angles);
1925        SkTDArray<Angle*> sorted;
1926        sortAngles(angles, sorted);
1927        int angleCount = angles.count();
1928        int firstIndex = findStartingEdge(sorted, startIndex, end);
1929        SkASSERT(firstIndex >= 0);
1930    #if DEBUG_SORT
1931        debugShowSort(__FUNCTION__, sorted, firstIndex, winding);
1932    #endif
1933        SkASSERT(sorted[firstIndex]->segment() == this);
1934    #if DEBUG_WINDING
1935        SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign());
1936    #endif
1937        int sumWinding = winding - spanSign(sorted[firstIndex]);
1938        int nextIndex = firstIndex + 1;
1939        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1940        const Angle* foundAngle = NULL;
1941        // FIXME: found done logic probably fails if there are more than 4
1942        // sorted angles. It should bias towards the first and last undone
1943        // edges -- but not sure that it won't choose a middle (incorrect)
1944        // edge if one is undone
1945        bool foundDone = false;
1946        bool foundDone2 = false;
1947        // iterate through the angle, and compute everyone's winding
1948        bool altFlipped = false;
1949        bool foundFlipped = false;
1950        int foundMax = SK_MinS32;
1951        int foundSum = SK_MinS32;
1952        Segment* nextSegment;
1953        int lastNonZeroSum = winding;
1954        do {
1955            if (nextIndex == angleCount) {
1956                nextIndex = 0;
1957            }
1958            const Angle* nextAngle = sorted[nextIndex];
1959            int maxWinding = sumWinding;
1960            if (sumWinding) {
1961                lastNonZeroSum = sumWinding;
1962            }
1963            nextSegment = nextAngle->segment();
1964            sumWinding -= nextSegment->spanSign(nextAngle);
1965            altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
1966    #if DEBUG_WINDING
1967            SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
1968            SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
1969                    nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
1970    #endif
1971           if (!sumWinding) {
1972                if (!active) {
1973                    markDone(SkMin32(startIndex, endIndex), outerWinding);
1974                    // FIXME: seems like a bug that this isn't calling userInnerWinding
1975                    nextSegment->markWinding(SkMin32(nextAngle->start(),
1976                                nextAngle->end()), maxWinding);
1977    #if DEBUG_WINDING
1978                    SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex);
1979    #endif
1980                    return NULL;
1981                }
1982                if (!foundAngle || foundDone) {
1983                    foundAngle = nextAngle;
1984                    foundDone = nextSegment->done(*nextAngle);
1985                    foundFlipped = altFlipped;
1986                    foundMax = maxWinding;
1987                }
1988                continue;
1989            }
1990            if (!maxWinding && (!foundAngle || foundDone2)) {
1991        #if DEBUG_WINDING
1992                if (foundAngle && foundDone2) {
1993                    SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex);
1994                }
1995        #endif
1996                foundAngle = nextAngle;
1997                foundDone2 = nextSegment->done(*nextAngle);
1998                foundFlipped = altFlipped;
1999                foundSum = sumWinding;
2000            }
2001            if (nextSegment->done()) {
2002                continue;
2003            }
2004            // if the winding is non-zero, nextAngle does not connect to
2005            // current chain. If we haven't done so already, mark the angle
2006            // as done, record the winding value, and mark connected unambiguous
2007            // segments as well.
2008            if (nextSegment->windSum(nextAngle) == SK_MinS32) {
2009                if (useInnerWinding(maxWinding, sumWinding)) {
2010                    maxWinding = sumWinding;
2011                }
2012                Span* last;
2013                if (foundAngle) {
2014                    last = nextSegment->markAndChaseWinding(nextAngle, maxWinding);
2015                } else {
2016                    last = nextSegment->markAndChaseDone(nextAngle, maxWinding);
2017                }
2018                if (last) {
2019                    *chase.append() = last;
2020                }
2021            }
2022        } while (++nextIndex != lastIndex);
2023        markDone(SkMin32(startIndex, endIndex), outerWinding);
2024        if (!foundAngle) {
2025            return NULL;
2026        }
2027        nextStart = foundAngle->start();
2028        nextEnd = foundAngle->end();
2029        nextSegment = foundAngle->segment();
2030        int flipped = foundFlipped ? -1 : 1;
2031        spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(
2032                SkMin32(nextStart, nextEnd));
2033        if (winding) {
2034    #if DEBUG_WINDING
2035            SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding);
2036            if (foundSum == SK_MinS32) {
2037                SkDebugf("?");
2038            } else {
2039                SkDebugf("%d", foundSum);
2040            }
2041            SkDebugf(" foundMax=");
2042            if (foundMax == SK_MinS32) {
2043                SkDebugf("?");
2044            } else {
2045                SkDebugf("%d", foundMax);
2046            }
2047            SkDebugf("\n");
2048     #endif
2049            winding = foundSum;
2050        }
2051    #if DEBUG_WINDING
2052        SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped);
2053    #endif
2054        return nextSegment;
2055    }
2056
2057    Segment* findNextXor(int& nextStart, int& nextEnd) {
2058        const int startIndex = nextStart;
2059        const int endIndex = nextEnd;
2060        SkASSERT(startIndex != endIndex);
2061        int count = fTs.count();
2062        SkASSERT(startIndex < endIndex ? startIndex < count - 1
2063                : startIndex > 0);
2064        int step = SkSign32(endIndex - startIndex);
2065        int end = nextSpan(startIndex, step);
2066        SkASSERT(end >= 0);
2067        Span* endSpan = &fTs[end];
2068        Segment* other;
2069        markDone(SkMin32(startIndex, endIndex), 1);
2070        if (isSimple(end)) {
2071    #if DEBUG_WINDING
2072            SkDebugf("%s simple\n", __FUNCTION__);
2073    #endif
2074            other = endSpan->fOther;
2075            nextStart = endSpan->fOtherIndex;
2076            double startT = other->fTs[nextStart].fT;
2077            SkDEBUGCODE(bool firstLoop = true;)
2078            if ((approximately_less_than_zero(startT) && step < 0)
2079                    || (approximately_greater_than_one(startT) && step > 0)) {
2080                step = -step;
2081                SkDEBUGCODE(firstLoop = false;)
2082            }
2083            do {
2084                nextEnd = nextStart;
2085                do {
2086                    nextEnd += step;
2087                } while (approximately_zero(startT - other->fTs[nextEnd].fT));
2088                if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
2089                    break;
2090                }
2091 #ifdef SK_DEBUG
2092                SkASSERT(firstLoop);
2093 #endif
2094                SkDEBUGCODE(firstLoop = false;)
2095                step = -step;
2096            } while (true);
2097            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2098            return other;
2099        }
2100        SkTDArray<Angle> angles;
2101        SkASSERT(startIndex - endIndex != 0);
2102        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2103        addTwoAngles(startIndex, end, angles);
2104        buildAngles(end, angles);
2105        SkTDArray<Angle*> sorted;
2106        sortAngles(angles, sorted);
2107        int angleCount = angles.count();
2108        int firstIndex = findStartingEdge(sorted, startIndex, end);
2109        SkASSERT(firstIndex >= 0);
2110    #if DEBUG_SORT
2111        debugShowSort(__FUNCTION__, sorted, firstIndex, 0);
2112    #endif
2113        SkASSERT(sorted[firstIndex]->segment() == this);
2114        int nextIndex = firstIndex + 1;
2115        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2116        const Angle* nextAngle;
2117        Segment* nextSegment;
2118        do {
2119            if (nextIndex == angleCount) {
2120                nextIndex = 0;
2121            }
2122            nextAngle = sorted[nextIndex];
2123            nextSegment = nextAngle->segment();
2124            if (!nextSegment->done(*nextAngle)) {
2125                break;
2126            }
2127            if (++nextIndex == lastIndex) {
2128                return NULL;
2129            }
2130        } while (true);
2131        nextStart = nextAngle->start();
2132        nextEnd = nextAngle->end();
2133        return nextSegment;
2134    }
2135
2136    int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
2137        int angleCount = sorted.count();
2138        int firstIndex = -1;
2139        for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2140            const Angle* angle = sorted[angleIndex];
2141            if (angle->segment() == this && angle->start() == end &&
2142                    angle->end() == start) {
2143                firstIndex = angleIndex;
2144                break;
2145            }
2146        }
2147        return firstIndex;
2148    }
2149
2150    // FIXME: this is tricky code; needs its own unit test
2151    void findTooCloseToCall(bool isXor) {
2152        int count = fTs.count();
2153        if (count < 3) { // require t=0, x, 1 at minimum
2154            return;
2155        }
2156        int matchIndex = 0;
2157        int moCount;
2158        Span* match;
2159        Segment* mOther;
2160        do {
2161            match = &fTs[matchIndex];
2162            mOther = match->fOther;
2163            // FIXME: allow quads, cubics to be near coincident?
2164            if (mOther->fVerb == SkPath::kLine_Verb) {
2165                moCount = mOther->fTs.count();
2166                if (moCount >= 3) {
2167                    break;
2168                }
2169            }
2170            if (++matchIndex >= count) {
2171                return;
2172            }
2173        } while (true); // require t=0, x, 1 at minimum
2174        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
2175        const SkPoint* matchPt = &xyAtT(match);
2176        // look for a pair of nearby T values that map to the same (x,y) value
2177        // if found, see if the pair of other segments share a common point. If
2178        // so, the span from here to there is coincident.
2179        for (int index = matchIndex + 1; index < count; ++index) {
2180            Span* test = &fTs[index];
2181            if (test->fDone) {
2182                continue;
2183            }
2184            Segment* tOther = test->fOther;
2185            if (tOther->fVerb != SkPath::kLine_Verb) {
2186                continue; // FIXME: allow quads, cubics to be near coincident?
2187            }
2188            int toCount = tOther->fTs.count();
2189            if (toCount < 3) { // require t=0, x, 1 at minimum
2190                continue;
2191            }
2192            const SkPoint* testPt = &xyAtT(test);
2193            if (*matchPt != *testPt) {
2194                matchIndex = index;
2195                moCount = toCount;
2196                match = test;
2197                mOther = tOther;
2198                matchPt = testPt;
2199                continue;
2200            }
2201            int moStart = -1;
2202            int moEnd = -1;
2203            double moStartT, moEndT;
2204            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
2205                Span& moSpan = mOther->fTs[moIndex];
2206                if (moSpan.fDone) {
2207                    continue;
2208                }
2209                if (moSpan.fOther == this) {
2210                    if (moSpan.fOtherT == match->fT) {
2211                        moStart = moIndex;
2212                        moStartT = moSpan.fT;
2213                    }
2214                    continue;
2215                }
2216                if (moSpan.fOther == tOther) {
2217                    if (tOther->fTs[moSpan.fOtherIndex].fWindValue == 0) {
2218                        moStart = -1;
2219                        break;
2220                    }
2221                    SkASSERT(moEnd == -1);
2222                    moEnd = moIndex;
2223                    moEndT = moSpan.fT;
2224                }
2225            }
2226            if (moStart < 0 || moEnd < 0) {
2227                continue;
2228            }
2229            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
2230            if (approximately_equal(moStartT, moEndT)) {
2231                continue;
2232            }
2233            int toStart = -1;
2234            int toEnd = -1;
2235            double toStartT, toEndT;
2236            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
2237                Span& toSpan = tOther->fTs[toIndex];
2238                if (toSpan.fDone) {
2239                    continue;
2240                }
2241                if (toSpan.fOther == this) {
2242                    if (toSpan.fOtherT == test->fT) {
2243                        toStart = toIndex;
2244                        toStartT = toSpan.fT;
2245                    }
2246                    continue;
2247                }
2248                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
2249                    if (mOther->fTs[toSpan.fOtherIndex].fWindValue == 0) {
2250                        moStart = -1;
2251                        break;
2252                    }
2253                    SkASSERT(toEnd == -1);
2254                    toEnd = toIndex;
2255                    toEndT = toSpan.fT;
2256                }
2257            }
2258            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
2259            if (toStart <= 0 || toEnd <= 0) {
2260                continue;
2261            }
2262            if (approximately_equal(toStartT, toEndT)) {
2263                continue;
2264            }
2265            // test to see if the segment between there and here is linear
2266            if (!mOther->isLinear(moStart, moEnd)
2267                    || !tOther->isLinear(toStart, toEnd)) {
2268                continue;
2269            }
2270            bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
2271            if (flipped) {
2272                mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
2273            } else {
2274                // FIXME: this is bogus for multiple ops
2275                // the xorMask needs to be accumulated from the union of the two
2276                // edges -- which means that the segment must have its own copy of the mask
2277                mOther->addTCoincident(isXor, moStartT, moEndT, *tOther, toStartT, toEndT);
2278            }
2279        }
2280    }
2281
2282    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
2283    // and use more concise logic like the old edge walker code?
2284    // FIXME: this needs to deal with coincident edges
2285    Segment* findTop(int& tIndex, int& endIndex) {
2286        // iterate through T intersections and return topmost
2287        // topmost tangent from y-min to first pt is closer to horizontal
2288        SkASSERT(!done());
2289        int firstT;
2290        int lastT;
2291        SkPoint topPt;
2292        topPt.fY = SK_ScalarMax;
2293        int count = fTs.count();
2294        // see if either end is not done since we want smaller Y of the pair
2295        bool lastDone = true;
2296        for (int index = 0; index < count; ++index) {
2297            const Span& span = fTs[index];
2298            if (!span.fDone || !lastDone) {
2299                const SkPoint& intercept = xyAtT(&span);
2300                if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
2301                        && topPt.fX > intercept.fX)) {
2302                    topPt = intercept;
2303                    firstT = lastT = index;
2304                } else if (topPt == intercept) {
2305                    lastT = index;
2306                }
2307            }
2308            lastDone = span.fDone;
2309        }
2310        // sort the edges to find the leftmost
2311        int step = 1;
2312        int end = nextSpan(firstT, step);
2313        if (end == -1) {
2314            step = -1;
2315            end = nextSpan(firstT, step);
2316            SkASSERT(end != -1);
2317        }
2318        // if the topmost T is not on end, or is three-way or more, find left
2319        // look for left-ness from tLeft to firstT (matching y of other)
2320        SkTDArray<Angle> angles;
2321        SkASSERT(firstT - end != 0);
2322        addTwoAngles(end, firstT, angles);
2323        buildAngles(firstT, angles);
2324        SkTDArray<Angle*> sorted;
2325        sortAngles(angles, sorted);
2326    #if DEBUG_SORT
2327        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0);
2328    #endif
2329        // skip edges that have already been processed
2330        firstT = -1;
2331        Segment* leftSegment;
2332        do {
2333            const Angle* angle = sorted[++firstT];
2334            leftSegment = angle->segment();
2335            tIndex = angle->end();
2336            endIndex = angle->start();
2337        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
2338        return leftSegment;
2339    }
2340
2341    // FIXME: not crazy about this
2342    // when the intersections are performed, the other index is into an
2343    // incomplete array. as the array grows, the indices become incorrect
2344    // while the following fixes the indices up again, it isn't smart about
2345    // skipping segments whose indices are already correct
2346    // assuming we leave the code that wrote the index in the first place
2347    void fixOtherTIndex() {
2348        int iCount = fTs.count();
2349        for (int i = 0; i < iCount; ++i) {
2350            Span& iSpan = fTs[i];
2351            double oT = iSpan.fOtherT;
2352            Segment* other = iSpan.fOther;
2353            int oCount = other->fTs.count();
2354            for (int o = 0; o < oCount; ++o) {
2355                Span& oSpan = other->fTs[o];
2356                if (oT == oSpan.fT && this == oSpan.fOther) {
2357                    iSpan.fOtherIndex = o;
2358                    break;
2359                }
2360            }
2361        }
2362    }
2363
2364    // OPTIMIZATION: uses tail recursion. Unwise?
2365    Span* innerChaseDone(int index, int step, int winding) {
2366        int end = nextSpan(index, step);
2367        SkASSERT(end >= 0);
2368        if (multipleSpans(end)) {
2369            return &fTs[end];
2370        }
2371        const Span& endSpan = fTs[end];
2372        Segment* other = endSpan.fOther;
2373        index = endSpan.fOtherIndex;
2374        int otherEnd = other->nextSpan(index, step);
2375        Span* last = other->innerChaseDone(index, step, winding);
2376        other->markDone(SkMin32(index, otherEnd), winding);
2377        return last;
2378    }
2379
2380    Span* innerChaseWinding(int index, int step, int winding) {
2381        int end = nextSpan(index, step);
2382        SkASSERT(end >= 0);
2383        if (multipleSpans(end)) {
2384            return &fTs[end];
2385        }
2386        const Span& endSpan = fTs[end];
2387        Segment* other = endSpan.fOther;
2388        index = endSpan.fOtherIndex;
2389        int otherEnd = other->nextSpan(index, step);
2390        int min = SkMin32(index, otherEnd);
2391        if (other->fTs[min].fWindSum != SK_MinS32) {
2392            SkASSERT(other->fTs[min].fWindSum == winding);
2393            return NULL;
2394        }
2395        Span* last = other->innerChaseWinding(index, step, winding);
2396        other->markWinding(min, winding);
2397        return last;
2398    }
2399
2400    void init(const SkPoint pts[], SkPath::Verb verb, bool operand) {
2401        fDoneSpans = 0;
2402        fOperand = operand;
2403        fPts = pts;
2404        fVerb = verb;
2405    }
2406
2407    bool intersected() const {
2408        return fTs.count() > 0;
2409    }
2410
2411    bool isConnected(int startIndex, int endIndex) const {
2412        return fTs[startIndex].fWindSum != SK_MinS32
2413                || fTs[endIndex].fWindSum != SK_MinS32;
2414    }
2415
2416    bool isHorizontal() const {
2417        return fBounds.fTop == fBounds.fBottom;
2418    }
2419
2420    bool isLinear(int start, int end) const {
2421        if (fVerb == SkPath::kLine_Verb) {
2422            return true;
2423        }
2424        if (fVerb == SkPath::kQuad_Verb) {
2425            SkPoint qPart[3];
2426            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
2427            return QuadIsLinear(qPart);
2428        } else {
2429            SkASSERT(fVerb == SkPath::kCubic_Verb);
2430            SkPoint cPart[4];
2431            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
2432            return CubicIsLinear(cPart);
2433        }
2434    }
2435
2436    // OPTIMIZE: successive calls could start were the last leaves off
2437    // or calls could specialize to walk forwards or backwards
2438    bool isMissing(double startT) const {
2439        size_t tCount = fTs.count();
2440        for (size_t index = 0; index < tCount; ++index) {
2441            if (approximately_zero(startT - fTs[index].fT)) {
2442                return false;
2443            }
2444        }
2445        return true;
2446    }
2447
2448    bool isSimple(int end) const {
2449        int count = fTs.count();
2450        if (count == 2) {
2451            return true;
2452        }
2453        double t = fTs[end].fT;
2454        if (approximately_less_than_zero(t)) {
2455            return !approximately_less_than_zero(fTs[1].fT);
2456        }
2457        if (approximately_greater_than_one(t)) {
2458            return !approximately_greater_than_one(fTs[count - 2].fT);
2459        }
2460        return false;
2461    }
2462
2463    bool isVertical() const {
2464        return fBounds.fLeft == fBounds.fRight;
2465    }
2466
2467    SkScalar leftMost(int start, int end) const {
2468        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
2469    }
2470
2471    // this span is excluded by the winding rule -- chase the ends
2472    // as long as they are unambiguous to mark connections as done
2473    // and give them the same winding value
2474    Span* markAndChaseDone(const Angle* angle, int winding) {
2475        int index = angle->start();
2476        int endIndex = angle->end();
2477        int step = SkSign32(endIndex - index);
2478        Span* last = innerChaseDone(index, step, winding);
2479        markDone(SkMin32(index, endIndex), winding);
2480        return last;
2481    }
2482
2483    Span* markAndChaseWinding(const Angle* angle, int winding) {
2484        int index = angle->start();
2485        int endIndex = angle->end();
2486        int min = SkMin32(index, endIndex);
2487        int step = SkSign32(endIndex - index);
2488        Span* last = innerChaseWinding(index, step, winding);
2489        markWinding(min, winding);
2490        return last;
2491    }
2492
2493    // FIXME: this should also mark spans with equal (x,y)
2494    // This may be called when the segment is already marked done. While this
2495    // wastes time, it shouldn't do any more than spin through the T spans.
2496    // OPTIMIZATION: abort on first done found (assuming that this code is
2497    // always called to mark segments done).
2498    void markDone(int index, int winding) {
2499      //  SkASSERT(!done());
2500        SkASSERT(winding);
2501        double referenceT = fTs[index].fT;
2502        int lesser = index;
2503        while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
2504            markOneDone(__FUNCTION__, lesser, winding);
2505        }
2506        do {
2507            markOneDone(__FUNCTION__, index, winding);
2508        } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
2509    }
2510
2511    void markOneDone(const char* funName, int tIndex, int winding) {
2512        Span* span = markOneWinding(funName, tIndex, winding);
2513        if (!span) {
2514            return;
2515        }
2516        span->fDone = true;
2517        fDoneSpans++;
2518    }
2519
2520    Span* markOneWinding(const char* funName, int tIndex, int winding) {
2521        Span& span = fTs[tIndex];
2522        if (span.fDone) {
2523            return NULL;
2524        }
2525    #if DEBUG_MARK_DONE
2526        debugShowNewWinding(funName, span, winding);
2527    #endif
2528        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
2529   #ifdef SK_DEBUG
2530        SkASSERT(abs(winding) <= gDebugMaxWindSum);
2531   #endif
2532        span.fWindSum = winding;
2533        return &span;
2534    }
2535
2536    void markWinding(int index, int winding) {
2537    //    SkASSERT(!done());
2538        SkASSERT(winding);
2539        double referenceT = fTs[index].fT;
2540        int lesser = index;
2541        while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
2542            markOneWinding(__FUNCTION__, lesser, winding);
2543        }
2544        do {
2545            markOneWinding(__FUNCTION__, index, winding);
2546       } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
2547    }
2548
2549    void matchWindingValue(int tIndex, double t, bool borrowWind) {
2550        int nextDoorWind = SK_MaxS32;
2551        if (tIndex > 0) {
2552            const Span& below = fTs[tIndex - 1];
2553            if (approximately_negative(t - below.fT)) {
2554                nextDoorWind = below.fWindValue;
2555            }
2556        }
2557        if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
2558            const Span& above = fTs[tIndex + 1];
2559            if (approximately_negative(above.fT - t)) {
2560                nextDoorWind = above.fWindValue;
2561            }
2562        }
2563        if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
2564            const Span& below = fTs[tIndex - 1];
2565            nextDoorWind = below.fWindValue;
2566        }
2567        if (nextDoorWind != SK_MaxS32) {
2568            Span& newSpan = fTs[tIndex];
2569            newSpan.fWindValue = nextDoorWind;
2570            if (!nextDoorWind) {
2571                newSpan.fDone = true;
2572                ++fDoneSpans;
2573            }
2574        }
2575    }
2576
2577    // return span if when chasing, two or more radiating spans are not done
2578    // OPTIMIZATION: ? multiple spans is detected when there is only one valid
2579    // candidate and the remaining spans have windValue == 0 (canceled by
2580    // coincidence). The coincident edges could either be removed altogether,
2581    // or this code could be more complicated in detecting this case. Worth it?
2582    bool multipleSpans(int end) const {
2583        return end > 0 && end < fTs.count() - 1;
2584    }
2585
2586    // This has callers for two different situations: one establishes the end
2587    // of the current span, and one establishes the beginning of the next span
2588    // (thus the name). When this is looking for the end of the current span,
2589    // coincidence is found when the beginning Ts contain -step and the end
2590    // contains step. When it is looking for the beginning of the next, the
2591    // first Ts found can be ignored and the last Ts should contain -step.
2592    // OPTIMIZATION: probably should split into two functions
2593    int nextSpan(int from, int step) const {
2594        const Span& fromSpan = fTs[from];
2595        int count = fTs.count();
2596        int to = from;
2597        while (step > 0 ? ++to < count : --to >= 0) {
2598            const Span& span = fTs[to];
2599            if (approximately_zero(span.fT - fromSpan.fT)) {
2600                continue;
2601            }
2602            return to;
2603        }
2604        return -1;
2605    }
2606
2607    bool operand() const {
2608        return fOperand;
2609    }
2610
2611    int oppSign(int startIndex, int endIndex) const {
2612        int result = startIndex < endIndex ? -fTs[startIndex].fWindValueOpp :
2613                fTs[endIndex].fWindValueOpp;
2614#if DEBUG_WIND_BUMP
2615        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
2616#endif
2617        return result;
2618    }
2619
2620    const SkPoint* pts() const {
2621        return fPts;
2622    }
2623
2624    void reset() {
2625        init(NULL, (SkPath::Verb) -1, false);
2626        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
2627        fTs.reset();
2628    }
2629
2630    // OPTIMIZATION: mark as debugging only if used solely by tests
2631    const Span& span(int tIndex) const {
2632        return fTs[tIndex];
2633    }
2634
2635    int spanSign(const Angle* angle) const {
2636        SkASSERT(angle->segment() == this);
2637        return spanSign(angle->start(), angle->end());
2638    }
2639
2640    int spanSign(int startIndex, int endIndex) const {
2641        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue :
2642                fTs[endIndex].fWindValue;
2643#if DEBUG_WIND_BUMP
2644        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
2645#endif
2646        return result;
2647    }
2648
2649    // OPTIMIZATION: mark as debugging only if used solely by tests
2650    double t(int tIndex) const {
2651        return fTs[tIndex].fT;
2652    }
2653
2654    static void TrackOutside(SkTDArray<double>& outsideTs, double end,
2655            double start) {
2656        int outCount = outsideTs.count();
2657        if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) {
2658            *outsideTs.append() = end;
2659            *outsideTs.append() = start;
2660        }
2661    }
2662
2663    void undoneSpan(int& start, int& end) {
2664        size_t tCount = fTs.count();
2665        size_t index;
2666        for (index = 0; index < tCount; ++index) {
2667            if (!fTs[index].fDone) {
2668                break;
2669            }
2670        }
2671        SkASSERT(index < tCount - 1);
2672        start = index;
2673        double startT = fTs[index].fT;
2674        while (approximately_negative(fTs[++index].fT - startT))
2675            SkASSERT(index < tCount);
2676        SkASSERT(index < tCount);
2677        end = index;
2678    }
2679
2680    void updatePts(const SkPoint pts[]) {
2681        fPts = pts;
2682    }
2683
2684    SkPath::Verb verb() const {
2685        return fVerb;
2686    }
2687
2688    int windSum(int tIndex) const {
2689        return fTs[tIndex].fWindSum;
2690    }
2691
2692    int windSum(const Angle* angle) const {
2693        int start = angle->start();
2694        int end = angle->end();
2695        int index = SkMin32(start, end);
2696        return windSum(index);
2697    }
2698
2699    int windValue(int tIndex) const {
2700        return fTs[tIndex].fWindValue;
2701    }
2702
2703    int windValue(const Angle* angle) const {
2704        int start = angle->start();
2705        int end = angle->end();
2706        int index = SkMin32(start, end);
2707        return windValue(index);
2708    }
2709
2710    SkScalar xAtT(const Span* span) const {
2711        return xyAtT(span).fX;
2712    }
2713
2714    const SkPoint& xyAtT(int index) const {
2715        return xyAtT(&fTs[index]);
2716    }
2717
2718    const SkPoint& xyAtT(const Span* span) const {
2719        if (SkScalarIsNaN(span->fPt.fX)) {
2720            if (span->fT == 0) {
2721                span->fPt = fPts[0];
2722            } else if (span->fT == 1) {
2723                span->fPt = fPts[fVerb];
2724            } else {
2725                (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt);
2726            }
2727        }
2728        return span->fPt;
2729    }
2730
2731    SkScalar yAtT(int index) const {
2732        return yAtT(&fTs[index]);
2733    }
2734
2735    SkScalar yAtT(const Span* span) const {
2736        return xyAtT(span).fY;
2737    }
2738
2739#if DEBUG_DUMP
2740    void dump() const {
2741        const char className[] = "Segment";
2742        const int tab = 4;
2743        for (int i = 0; i < fTs.count(); ++i) {
2744            SkPoint out;
2745            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
2746            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
2747                    " otherT=%1.9g windSum=%d\n",
2748                    tab + sizeof(className), className, fID,
2749                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
2750                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
2751        }
2752        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
2753                tab + sizeof(className), className, fID,
2754                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
2755    }
2756#endif
2757
2758#if DEBUG_CONCIDENT
2759    // assert if pair has not already been added
2760     void debugAddTPair(double t, const Segment& other, double otherT) const {
2761        for (int i = 0; i < fTs.count(); ++i) {
2762            if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
2763                return;
2764            }
2765        }
2766        SkASSERT(0);
2767     }
2768#endif
2769
2770#if DEBUG_DUMP
2771    int debugID() const {
2772        return fID;
2773    }
2774#endif
2775
2776#if DEBUG_WINDING
2777    void debugShowSums() const {
2778        SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,
2779            fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);
2780        for (int i = 0; i < fTs.count(); ++i) {
2781            const Span& span = fTs[i];
2782            SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span));
2783            if (span.fWindSum == SK_MinS32) {
2784                SkDebugf("?");
2785            } else {
2786                SkDebugf("%d", span.fWindSum);
2787            }
2788            SkDebugf("]");
2789        }
2790        SkDebugf("\n");
2791    }
2792#endif
2793
2794#if DEBUG_CONCIDENT
2795    void debugShowTs() const {
2796        SkDebugf("%s id=%d", __FUNCTION__, fID);
2797        for (int i = 0; i < fTs.count(); ++i) {
2798            SkDebugf(" [o=%d t=%1.3g %1.9g,%1.9g w=%d]", fTs[i].fOther->fID,
2799                    fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue);
2800        }
2801        SkDebugf("\n");
2802    }
2803#endif
2804
2805#if DEBUG_ACTIVE_SPANS
2806    void debugShowActiveSpans() const {
2807        if (done()) {
2808            return;
2809        }
2810        for (int i = 0; i < fTs.count(); ++i) {
2811            if (fTs[i].fDone) {
2812                continue;
2813            }
2814            SkDebugf("%s id=%d", __FUNCTION__, fID);
2815            SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
2816            for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
2817                SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
2818            }
2819            const Span* span = &fTs[i];
2820            SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,
2821                     xAtT(span), yAtT(span));
2822            const Segment* other = fTs[i].fOther;
2823            SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
2824                    other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
2825            if (fTs[i].fWindSum == SK_MinS32) {
2826                SkDebugf("?");
2827            } else {
2828                SkDebugf("%d", fTs[i].fWindSum);
2829            }
2830            SkDebugf(" windValue=%d\n", fTs[i].fWindValue);
2831        }
2832    }
2833#endif
2834
2835#if DEBUG_MARK_DONE
2836    void debugShowNewWinding(const char* fun, const Span& span, int winding) {
2837        const SkPoint& pt = xyAtT(&span);
2838        SkDebugf("%s id=%d", fun, fID);
2839        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
2840        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
2841            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
2842        }
2843        SkDebugf(") t=%1.9g (%1.9g,%1.9g) newWindSum=%d windSum=",
2844                span.fT, pt.fX, pt.fY, winding);
2845        if (span.fWindSum == SK_MinS32) {
2846            SkDebugf("?");
2847        } else {
2848            SkDebugf("%d", span.fWindSum);
2849        }
2850        SkDebugf(" windValue=%d\n", span.fWindValue);
2851    }
2852#endif
2853
2854#if DEBUG_SORT
2855    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first,
2856            const int contourWinding) const {
2857        SkASSERT(angles[first]->segment() == this);
2858        SkASSERT(angles.count() > 1);
2859        int lastSum = contourWinding;
2860        int windSum = lastSum - spanSign(angles[first]);
2861        SkDebugf("%s %s contourWinding=%d sign=%d\n", fun, __FUNCTION__,
2862                contourWinding, spanSign(angles[first]));
2863        int index = first;
2864        bool firstTime = true;
2865        do {
2866            const Angle& angle = *angles[index];
2867            const Segment& segment = *angle.segment();
2868            int start = angle.start();
2869            int end = angle.end();
2870            const Span& sSpan = segment.fTs[start];
2871            const Span& eSpan = segment.fTs[end];
2872            const Span& mSpan = segment.fTs[SkMin32(start, end)];
2873            if (!firstTime) {
2874                lastSum = windSum;
2875                windSum -= segment.spanSign(&angle);
2876            }
2877            SkDebugf("%s [%d] id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
2878                    " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n",
2879                    __FUNCTION__, index, segment.fID, kLVerbStr[segment.fVerb],
2880                    start, segment.xAtT(&sSpan),
2881                    segment.yAtT(&sSpan), end, segment.xAtT(&eSpan),
2882                    segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue,
2883                    lastSum, windSum, useInnerWinding(lastSum, windSum)
2884                    ? windSum : lastSum, mSpan.fDone);
2885#if DEBUG_ANGLE
2886            angle.debugShow(segment.xyAtT(&sSpan));
2887#endif
2888            ++index;
2889            if (index == angles.count()) {
2890                index = 0;
2891            }
2892            if (firstTime) {
2893                firstTime = false;
2894            }
2895        } while (index != first);
2896    }
2897#endif
2898
2899#if DEBUG_WINDING
2900    bool debugVerifyWinding(int start, int end, int winding) const {
2901        const Span& span = fTs[SkMin32(start, end)];
2902        int spanWinding = span.fWindSum;
2903        if (spanWinding == SK_MinS32) {
2904            return true;
2905        }
2906        int spanSign = SkSign32(start - end);
2907        int signedVal = spanSign * span.fWindValue;
2908        if (signedVal < 0) {
2909            spanWinding -= signedVal;
2910        }
2911        return span.fWindSum == winding;
2912    }
2913#endif
2914
2915private:
2916    const SkPoint* fPts;
2917    SkPath::Verb fVerb;
2918    Bounds fBounds;
2919    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
2920    int fDoneSpans; // quick check that segment is finished
2921    bool fOperand;
2922#if DEBUG_DUMP
2923    int fID;
2924#endif
2925};
2926
2927class Contour;
2928
2929struct Coincidence {
2930    Contour* fContours[2];
2931    int fSegments[2];
2932    double fTs[2][2];
2933    bool fXor;
2934};
2935
2936class Contour {
2937public:
2938    Contour() {
2939        reset();
2940#if DEBUG_DUMP
2941        fID = ++gContourID;
2942#endif
2943    }
2944
2945    bool operator<(const Contour& rh) const {
2946        return fBounds.fTop == rh.fBounds.fTop
2947                ? fBounds.fLeft < rh.fBounds.fLeft
2948                : fBounds.fTop < rh.fBounds.fTop;
2949    }
2950
2951    void addCoincident(int index, Contour* other, int otherIndex,
2952            const Intersections& ts, bool swap) {
2953        Coincidence& coincidence = *fCoincidences.append();
2954        coincidence.fContours[0] = this;
2955        coincidence.fContours[1] = other;
2956        coincidence.fSegments[0] = index;
2957        coincidence.fSegments[1] = otherIndex;
2958        if (fSegments[index].verb() == SkPath::kLine_Verb &&
2959                other->fSegments[otherIndex].verb() == SkPath::kLine_Verb) {
2960            // FIXME: coincident lines use legacy Ts instead of coincident Ts
2961            coincidence.fTs[swap][0] = ts.fT[0][0];
2962            coincidence.fTs[swap][1] = ts.fT[0][1];
2963            coincidence.fTs[!swap][0] = ts.fT[1][0];
2964            coincidence.fTs[!swap][1] = ts.fT[1][1];
2965        } else if (fSegments[index].verb() == SkPath::kQuad_Verb &&
2966                other->fSegments[otherIndex].verb() == SkPath::kQuad_Verb) {
2967            coincidence.fTs[swap][0] = ts.fCoincidentT[0][0];
2968            coincidence.fTs[swap][1] = ts.fCoincidentT[0][1];
2969            coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0];
2970            coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1];
2971        }
2972        coincidence.fXor = fOperand == other->fOperand ? fXor : true;
2973    }
2974
2975    void addCross(const Contour* crosser) {
2976#ifdef DEBUG_CROSS
2977        for (int index = 0; index < fCrosses.count(); ++index) {
2978            SkASSERT(fCrosses[index] != crosser);
2979        }
2980#endif
2981        *fCrosses.append() = crosser;
2982    }
2983
2984    void addCubic(const SkPoint pts[4]) {
2985        fSegments.push_back().addCubic(pts, fOperand);
2986        fContainsCurves = true;
2987    }
2988
2989    int addLine(const SkPoint pts[2]) {
2990        fSegments.push_back().addLine(pts, fOperand);
2991        return fSegments.count();
2992    }
2993
2994    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
2995        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
2996    }
2997
2998    int addQuad(const SkPoint pts[3]) {
2999        fSegments.push_back().addQuad(pts, fOperand);
3000        fContainsCurves = true;
3001        return fSegments.count();
3002    }
3003
3004    int addT(int segIndex, double newT, Contour* other, int otherIndex) {
3005        containsIntercepts();
3006        return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
3007    }
3008
3009    const Bounds& bounds() const {
3010        return fBounds;
3011    }
3012
3013    void complete() {
3014        setBounds();
3015        fContainsIntercepts = false;
3016    }
3017
3018    void containsIntercepts() {
3019        fContainsIntercepts = true;
3020    }
3021
3022    const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY,
3023            int &tIndex, double& hitT) {
3024        int segmentCount = fSegments.count();
3025        const Segment* bestSegment = NULL;
3026        for (int test = 0; test < segmentCount; ++test) {
3027            Segment* testSegment = &fSegments[test];
3028            const SkRect& bounds = testSegment->bounds();
3029            if (bounds.fBottom <= bestY) {
3030                continue;
3031            }
3032            if (bounds.fTop >= basePt.fY) {
3033                continue;
3034            }
3035            if (bounds.fLeft > basePt.fX) {
3036                continue;
3037            }
3038            if (bounds.fRight < basePt.fX) {
3039                continue;
3040            }
3041            if (bounds.fLeft == bounds.fRight) {
3042                continue;
3043            }
3044     #if 0
3045            bool leftHalf = bounds.fLeft == basePt.fX;
3046            bool rightHalf = bounds.fRight == basePt.fX;
3047            if ((leftHalf || rightHalf) && !testSegment->crossedSpanHalves(
3048                    basePt, leftHalf, rightHalf)) {
3049                continue;
3050            }
3051     #endif
3052            double testHitT;
3053            int testT = testSegment->crossedSpan(basePt, bestY, testHitT);
3054            if (testT >= 0) {
3055                bestSegment = testSegment;
3056                tIndex = testT;
3057                hitT = testHitT;
3058            }
3059        }
3060        return bestSegment;
3061    }
3062
3063    bool crosses(const Contour* crosser) const {
3064        for (int index = 0; index < fCrosses.count(); ++index) {
3065            if (fCrosses[index] == crosser) {
3066                return true;
3067            }
3068        }
3069        return false;
3070    }
3071
3072    void findTooCloseToCall() {
3073        int segmentCount = fSegments.count();
3074        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
3075            fSegments[sIndex].findTooCloseToCall(fXor);
3076        }
3077    }
3078
3079    void fixOtherTIndex() {
3080        int segmentCount = fSegments.count();
3081        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
3082            fSegments[sIndex].fixOtherTIndex();
3083        }
3084    }
3085
3086    void reset() {
3087        fSegments.reset();
3088        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
3089        fContainsCurves = fContainsIntercepts = false;
3090    }
3091
3092    // FIXME: for binary ops, need to keep both ops winding contributions separately
3093    // in edge array
3094    void resolveCoincidence() {
3095        int count = fCoincidences.count();
3096        for (int index = 0; index < count; ++index) {
3097            Coincidence& coincidence = fCoincidences[index];
3098            Contour* thisContour = coincidence.fContours[0];
3099            Contour* otherContour = coincidence.fContours[1];
3100            int thisIndex = coincidence.fSegments[0];
3101            int otherIndex = coincidence.fSegments[1];
3102            Segment& thisOne = thisContour->fSegments[thisIndex];
3103            Segment& other = otherContour->fSegments[otherIndex];
3104        #if DEBUG_CONCIDENT
3105            thisOne.debugShowTs();
3106            other.debugShowTs();
3107        #endif
3108            double startT = coincidence.fTs[0][0];
3109            double endT = coincidence.fTs[0][1];
3110            bool opposite = false;
3111            if (startT > endT) {
3112                SkTSwap<double>(startT, endT);
3113                opposite ^= true;
3114            }
3115            SkASSERT(!approximately_negative(endT - startT));
3116            double oStartT = coincidence.fTs[1][0];
3117            double oEndT = coincidence.fTs[1][1];
3118            if (oStartT > oEndT) {
3119                SkTSwap<double>(oStartT, oEndT);
3120                opposite ^= true;
3121            }
3122            SkASSERT(!approximately_negative(oEndT - oStartT));
3123            if (opposite) {
3124                        // make sure startT and endT have t entries
3125                SkASSERT(opposite);
3126                if (startT > 0 || oEndT < 1
3127                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
3128                    thisOne.addTPair(startT, other, oEndT, true);
3129                }
3130                if (oStartT > 0 || endT < 1
3131                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
3132                    other.addTPair(oStartT, thisOne, endT, true);
3133                }
3134                thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
3135            } else {
3136                if (startT > 0 || oStartT > 0
3137                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
3138                    thisOne.addTPair(startT, other, oStartT, true);
3139                }
3140                if (endT < 1 || oEndT < 1
3141                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
3142                    other.addTPair(oEndT, thisOne, endT, true);
3143                }
3144                thisOne.addTCoincident(coincidence.fXor, startT, endT, other, oStartT, oEndT);
3145            }
3146        #if DEBUG_CONCIDENT
3147            thisOne.debugShowTs();
3148            other.debugShowTs();
3149        #endif
3150        }
3151    }
3152
3153    const SkTArray<Segment>& segments() {
3154        return fSegments;
3155    }
3156
3157    void setOperand(bool isOp) {
3158        fOperand = isOp;
3159    }
3160
3161    void setXor(bool isXor) {
3162        fXor = isXor;
3163    }
3164
3165    // OPTIMIZATION: feel pretty uneasy about this. It seems like once again
3166    // we need to sort and walk edges in y, but that on the surface opens the
3167    // same can of worms as before. But then, this is a rough sort based on
3168    // segments' top, and not a true sort, so it could be ameniable to regular
3169    // sorting instead of linear searching. Still feel like I'm missing something
3170    Segment* topSegment(SkScalar& bestY) {
3171        int segmentCount = fSegments.count();
3172        SkASSERT(segmentCount > 0);
3173        int best = -1;
3174        Segment* bestSegment = NULL;
3175        while (++best < segmentCount) {
3176            Segment* testSegment = &fSegments[best];
3177            if (testSegment->done()) {
3178                continue;
3179            }
3180            bestSegment = testSegment;
3181            break;
3182        }
3183        if (!bestSegment) {
3184            return NULL;
3185        }
3186        SkScalar bestTop = bestSegment->activeTop();
3187        for (int test = best + 1; test < segmentCount; ++test) {
3188            Segment* testSegment = &fSegments[test];
3189            if (testSegment->done()) {
3190                continue;
3191            }
3192            if (testSegment->bounds().fTop > bestTop) {
3193                continue;
3194            }
3195            SkScalar testTop = testSegment->activeTop();
3196            if (bestTop > testTop) {
3197                bestTop = testTop;
3198                bestSegment = testSegment;
3199            }
3200        }
3201        bestY = bestTop;
3202        return bestSegment;
3203    }
3204
3205    Segment* undoneSegment(int& start, int& end) {
3206        int segmentCount = fSegments.count();
3207        for (int test = 0; test < segmentCount; ++test) {
3208            Segment* testSegment = &fSegments[test];
3209            if (testSegment->done()) {
3210                continue;
3211            }
3212            testSegment->undoneSpan(start, end);
3213            return testSegment;
3214        }
3215        return NULL;
3216    }
3217
3218    int updateSegment(int index, const SkPoint* pts) {
3219        Segment& segment = fSegments[index];
3220        segment.updatePts(pts);
3221        return segment.verb() + 1;
3222    }
3223
3224#if DEBUG_TEST
3225    SkTArray<Segment>& debugSegments() {
3226        return fSegments;
3227    }
3228#endif
3229
3230#if DEBUG_DUMP
3231    void dump() {
3232        int i;
3233        const char className[] = "Contour";
3234        const int tab = 4;
3235        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
3236        for (i = 0; i < fSegments.count(); ++i) {
3237            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
3238                    className, i);
3239            fSegments[i].dump();
3240        }
3241        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
3242                tab + sizeof(className), className,
3243                fBounds.fLeft, fBounds.fTop,
3244                fBounds.fRight, fBounds.fBottom);
3245        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
3246                className, fContainsIntercepts);
3247        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
3248                className, fContainsCurves);
3249    }
3250#endif
3251
3252#if DEBUG_ACTIVE_SPANS
3253    void debugShowActiveSpans() {
3254        for (int index = 0; index < fSegments.count(); ++index) {
3255            fSegments[index].debugShowActiveSpans();
3256        }
3257    }
3258#endif
3259
3260protected:
3261    void setBounds() {
3262        int count = fSegments.count();
3263        if (count == 0) {
3264            SkDebugf("%s empty contour\n", __FUNCTION__);
3265            SkASSERT(0);
3266            // FIXME: delete empty contour?
3267            return;
3268        }
3269        fBounds = fSegments.front().bounds();
3270        for (int index = 1; index < count; ++index) {
3271            fBounds.add(fSegments[index].bounds());
3272        }
3273    }
3274
3275private:
3276    SkTArray<Segment> fSegments;
3277    SkTDArray<Coincidence> fCoincidences;
3278    SkTDArray<const Contour*> fCrosses;
3279    Bounds fBounds;
3280    bool fContainsIntercepts;
3281    bool fContainsCurves;
3282    bool fOperand; // true for the second argument to a binary operator
3283    bool fXor;
3284#if DEBUG_DUMP
3285    int fID;
3286#endif
3287};
3288
3289class EdgeBuilder {
3290public:
3291
3292EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
3293    : fPath(&path)
3294    , fContours(contours)
3295    , fCurrentContour(NULL)
3296    , fOperand(false)
3297{
3298    fXorMask = (path.getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
3299#if DEBUG_DUMP
3300    gContourID = 0;
3301    gSegmentID = 0;
3302#endif
3303    fSecondHalf = preFetch();
3304}
3305
3306void addOperand(const SkPath& path) {
3307    fPath = &path;
3308    fXorMask = (path.getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
3309    preFetch();
3310}
3311
3312void finish() {
3313    walk();
3314    complete();
3315    if (fCurrentContour && !fCurrentContour->segments().count()) {
3316        fContours.pop_back();
3317    }
3318    // correct pointers in contours since fReducePts may have moved as it grew
3319    int cIndex = 0;
3320    int extraCount = fExtra.count();
3321    SkASSERT(extraCount == 0 || fExtra[0] == -1);
3322    int eIndex = 0;
3323    int rIndex = 0;
3324    while (++eIndex < extraCount) {
3325        int offset = fExtra[eIndex];
3326        if (offset < 0) {
3327            ++cIndex;
3328            continue;
3329        }
3330        fCurrentContour = &fContours[cIndex];
3331        rIndex += fCurrentContour->updateSegment(offset - 1,
3332                &fReducePts[rIndex]);
3333    }
3334    fExtra.reset(); // we're done with this
3335}
3336
3337ShapeOpMask xorMask() const {
3338    return fXorMask;
3339}
3340
3341protected:
3342
3343void complete() {
3344    if (fCurrentContour && fCurrentContour->segments().count()) {
3345        fCurrentContour->complete();
3346        fCurrentContour = NULL;
3347    }
3348}
3349
3350// FIXME:remove once we can access path pts directly
3351int preFetch() {
3352    SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed
3353    SkPoint pts[4];
3354    SkPath::Verb verb;
3355    do {
3356        verb = iter.next(pts);
3357        *fPathVerbs.append() = verb;
3358        if (verb == SkPath::kMove_Verb) {
3359            *fPathPts.append() = pts[0];
3360        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
3361            fPathPts.append(verb, &pts[1]);
3362        }
3363    } while (verb != SkPath::kDone_Verb);
3364    return fPathVerbs.count();
3365}
3366
3367void walk() {
3368    SkPath::Verb reducedVerb;
3369    uint8_t* verbPtr = fPathVerbs.begin();
3370    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
3371    const SkPoint* pointsPtr = fPathPts.begin();
3372    const SkPoint* finalCurveStart = NULL;
3373    const SkPoint* finalCurveEnd = NULL;
3374    SkPath::Verb verb;
3375    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
3376        switch (verb) {
3377            case SkPath::kMove_Verb:
3378                complete();
3379                if (!fCurrentContour) {
3380                    fCurrentContour = fContours.push_back_n(1);
3381                    fCurrentContour->setOperand(fOperand);
3382                    fCurrentContour->setXor(fXorMask == kEvenOdd_Mask);
3383                    *fExtra.append() = -1; // start new contour
3384                }
3385                finalCurveEnd = pointsPtr++;
3386                continue;
3387            case SkPath::kLine_Verb:
3388                // skip degenerate points
3389                if (pointsPtr[-1].fX != pointsPtr[0].fX
3390                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
3391                    fCurrentContour->addLine(&pointsPtr[-1]);
3392                }
3393                break;
3394            case SkPath::kQuad_Verb:
3395
3396                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
3397                if (reducedVerb == 0) {
3398                    break; // skip degenerate points
3399                }
3400                if (reducedVerb == 1) {
3401                    *fExtra.append() =
3402                            fCurrentContour->addLine(fReducePts.end() - 2);
3403                    break;
3404                }
3405                fCurrentContour->addQuad(&pointsPtr[-1]);
3406                break;
3407            case SkPath::kCubic_Verb:
3408                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
3409                if (reducedVerb == 0) {
3410                    break; // skip degenerate points
3411                }
3412                if (reducedVerb == 1) {
3413                    *fExtra.append() =
3414                            fCurrentContour->addLine(fReducePts.end() - 2);
3415                    break;
3416                }
3417                if (reducedVerb == 2) {
3418                    *fExtra.append() =
3419                            fCurrentContour->addQuad(fReducePts.end() - 3);
3420                    break;
3421                }
3422                fCurrentContour->addCubic(&pointsPtr[-1]);
3423                break;
3424            case SkPath::kClose_Verb:
3425                SkASSERT(fCurrentContour);
3426                if (finalCurveStart && finalCurveEnd
3427                        && *finalCurveStart != *finalCurveEnd) {
3428                    *fReducePts.append() = *finalCurveStart;
3429                    *fReducePts.append() = *finalCurveEnd;
3430                    *fExtra.append() =
3431                            fCurrentContour->addLine(fReducePts.end() - 2);
3432                }
3433                complete();
3434                continue;
3435            default:
3436                SkDEBUGFAIL("bad verb");
3437                return;
3438        }
3439        finalCurveStart = &pointsPtr[verb - 1];
3440        pointsPtr += verb;
3441        SkASSERT(fCurrentContour);
3442        if (verbPtr == endOfFirstHalf) {
3443            fOperand = true;
3444        }
3445    }
3446}
3447
3448private:
3449    const SkPath* fPath;
3450    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
3451    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
3452    Contour* fCurrentContour;
3453    SkTArray<Contour>& fContours;
3454    SkTDArray<SkPoint> fReducePts; // segments created on the fly
3455    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
3456    ShapeOpMask fXorMask;
3457    int fSecondHalf;
3458    bool fOperand;
3459};
3460
3461class Work {
3462public:
3463    enum SegmentType {
3464        kHorizontalLine_Segment = -1,
3465        kVerticalLine_Segment = 0,
3466        kLine_Segment = SkPath::kLine_Verb,
3467        kQuad_Segment = SkPath::kQuad_Verb,
3468        kCubic_Segment = SkPath::kCubic_Verb,
3469    };
3470
3471    void addCoincident(Work& other, const Intersections& ts, bool swap) {
3472        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
3473    }
3474
3475    // FIXME: does it make sense to write otherIndex now if we're going to
3476    // fix it up later?
3477    void addOtherT(int index, double otherT, int otherIndex) {
3478        fContour->addOtherT(fIndex, index, otherT, otherIndex);
3479    }
3480
3481    // Avoid collapsing t values that are close to the same since
3482    // we walk ts to describe consecutive intersections. Since a pair of ts can
3483    // be nearly equal, any problems caused by this should be taken care
3484    // of later.
3485    // On the edge or out of range values are negative; add 2 to get end
3486    int addT(double newT, const Work& other) {
3487        return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
3488    }
3489
3490    bool advance() {
3491        return ++fIndex < fLast;
3492    }
3493
3494    SkScalar bottom() const {
3495        return bounds().fBottom;
3496    }
3497
3498    const Bounds& bounds() const {
3499        return fContour->segments()[fIndex].bounds();
3500    }
3501
3502    const SkPoint* cubic() const {
3503        return fCubic;
3504    }
3505
3506    void init(Contour* contour) {
3507        fContour = contour;
3508        fIndex = 0;
3509        fLast = contour->segments().count();
3510    }
3511
3512    bool isAdjacent(const Work& next) {
3513        return fContour == next.fContour && fIndex + 1 == next.fIndex;
3514    }
3515
3516    bool isFirstLast(const Work& next) {
3517        return fContour == next.fContour && fIndex == 0
3518                && next.fIndex == fLast - 1;
3519    }
3520
3521    SkScalar left() const {
3522        return bounds().fLeft;
3523    }
3524
3525    void promoteToCubic() {
3526        fCubic[0] = pts()[0];
3527        fCubic[2] = pts()[1];
3528        fCubic[3] = pts()[2];
3529        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
3530        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
3531        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
3532        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
3533    }
3534
3535    const SkPoint* pts() const {
3536        return fContour->segments()[fIndex].pts();
3537    }
3538
3539    SkScalar right() const {
3540        return bounds().fRight;
3541    }
3542
3543    ptrdiff_t segmentIndex() const {
3544        return fIndex;
3545    }
3546
3547    SegmentType segmentType() const {
3548        const Segment& segment = fContour->segments()[fIndex];
3549        SegmentType type = (SegmentType) segment.verb();
3550        if (type != kLine_Segment) {
3551            return type;
3552        }
3553        if (segment.isHorizontal()) {
3554            return kHorizontalLine_Segment;
3555        }
3556        if (segment.isVertical()) {
3557            return kVerticalLine_Segment;
3558        }
3559        return kLine_Segment;
3560    }
3561
3562    bool startAfter(const Work& after) {
3563        fIndex = after.fIndex;
3564        return advance();
3565    }
3566
3567    SkScalar top() const {
3568        return bounds().fTop;
3569    }
3570
3571    SkPath::Verb verb() const {
3572        return fContour->segments()[fIndex].verb();
3573    }
3574
3575    SkScalar x() const {
3576        return bounds().fLeft;
3577    }
3578
3579    bool xFlipped() const {
3580        return x() != pts()[0].fX;
3581    }
3582
3583    SkScalar y() const {
3584        return bounds().fTop;
3585    }
3586
3587    bool yFlipped() const {
3588        return y() != pts()[0].fY;
3589    }
3590
3591protected:
3592    Contour* fContour;
3593    SkPoint fCubic[4];
3594    int fIndex;
3595    int fLast;
3596};
3597
3598#if DEBUG_ADD_INTERSECTING_TS
3599static void debugShowLineIntersection(int pts, const Work& wt,
3600        const Work& wn, const double wtTs[2], const double wnTs[2]) {
3601    if (!pts) {
3602        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
3603                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
3604                wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY,
3605                wn.pts()[1].fX, wn.pts()[1].fY);
3606        return;
3607    }
3608    SkPoint wtOutPt, wnOutPt;
3609    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
3610    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
3611    SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
3612            __FUNCTION__,
3613            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
3614            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
3615    if (pts == 2) {
3616        SkDebugf(" wtTs[1]=%g", wtTs[1]);
3617    }
3618    SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
3619            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
3620            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
3621    if (pts == 2) {
3622        SkDebugf(" wnTs[1]=%g", wnTs[1]);
3623    }
3624    SkDebugf("\n");
3625}
3626#else
3627static void debugShowLineIntersection(int , const Work& ,
3628        const Work& , const double [2], const double [2]) {
3629}
3630#endif
3631
3632static bool addIntersectTs(Contour* test, Contour* next) {
3633
3634    if (test != next) {
3635        if (test->bounds().fBottom < next->bounds().fTop) {
3636            return false;
3637        }
3638        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
3639            return true;
3640        }
3641    }
3642    Work wt;
3643    wt.init(test);
3644    bool foundCommonContour = test == next;
3645    do {
3646        Work wn;
3647        wn.init(next);
3648        if (test == next && !wn.startAfter(wt)) {
3649            continue;
3650        }
3651        do {
3652            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
3653                continue;
3654            }
3655            int pts;
3656            Intersections ts;
3657            bool swap = false;
3658            switch (wt.segmentType()) {
3659                case Work::kHorizontalLine_Segment:
3660                    swap = true;
3661                    switch (wn.segmentType()) {
3662                        case Work::kHorizontalLine_Segment:
3663                        case Work::kVerticalLine_Segment:
3664                        case Work::kLine_Segment: {
3665                            pts = HLineIntersect(wn.pts(), wt.left(),
3666                                    wt.right(), wt.y(), wt.xFlipped(), ts);
3667                            debugShowLineIntersection(pts, wt, wn,
3668                                    ts.fT[1], ts.fT[0]);
3669                            break;
3670                        }
3671                        case Work::kQuad_Segment: {
3672                            pts = HQuadIntersect(wn.pts(), wt.left(),
3673                                    wt.right(), wt.y(), wt.xFlipped(), ts);
3674                            break;
3675                        }
3676                        case Work::kCubic_Segment: {
3677                            pts = HCubicIntersect(wn.pts(), wt.left(),
3678                                    wt.right(), wt.y(), wt.xFlipped(), ts);
3679                            break;
3680                        }
3681                        default:
3682                            SkASSERT(0);
3683                    }
3684                    break;
3685                case Work::kVerticalLine_Segment:
3686                    swap = true;
3687                    switch (wn.segmentType()) {
3688                        case Work::kHorizontalLine_Segment:
3689                        case Work::kVerticalLine_Segment:
3690                        case Work::kLine_Segment: {
3691                            pts = VLineIntersect(wn.pts(), wt.top(),
3692                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
3693                            debugShowLineIntersection(pts, wt, wn,
3694                                    ts.fT[1], ts.fT[0]);
3695                            break;
3696                        }
3697                        case Work::kQuad_Segment: {
3698                            pts = VQuadIntersect(wn.pts(), wt.top(),
3699                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
3700                            break;
3701                        }
3702                        case Work::kCubic_Segment: {
3703                            pts = VCubicIntersect(wn.pts(), wt.top(),
3704                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
3705                            break;
3706                        }
3707                        default:
3708                            SkASSERT(0);
3709                    }
3710                    break;
3711                case Work::kLine_Segment:
3712                    switch (wn.segmentType()) {
3713                        case Work::kHorizontalLine_Segment:
3714                            pts = HLineIntersect(wt.pts(), wn.left(),
3715                                    wn.right(), wn.y(), wn.xFlipped(), ts);
3716                            debugShowLineIntersection(pts, wt, wn,
3717                                    ts.fT[1], ts.fT[0]);
3718                            break;
3719                        case Work::kVerticalLine_Segment:
3720                            pts = VLineIntersect(wt.pts(), wn.top(),
3721                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
3722                            debugShowLineIntersection(pts, wt, wn,
3723                                    ts.fT[1], ts.fT[0]);
3724                            break;
3725                        case Work::kLine_Segment: {
3726                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
3727                            debugShowLineIntersection(pts, wt, wn,
3728                                    ts.fT[1], ts.fT[0]);
3729                            break;
3730                        }
3731                        case Work::kQuad_Segment: {
3732                            swap = true;
3733                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
3734                            break;
3735                        }
3736                        case Work::kCubic_Segment: {
3737                            swap = true;
3738                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
3739                            break;
3740                        }
3741                        default:
3742                            SkASSERT(0);
3743                    }
3744                    break;
3745                case Work::kQuad_Segment:
3746                    switch (wn.segmentType()) {
3747                        case Work::kHorizontalLine_Segment:
3748                            pts = HQuadIntersect(wt.pts(), wn.left(),
3749                                    wn.right(), wn.y(), wn.xFlipped(), ts);
3750                            break;
3751                        case Work::kVerticalLine_Segment:
3752                            pts = VQuadIntersect(wt.pts(), wn.top(),
3753                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
3754                            break;
3755                        case Work::kLine_Segment: {
3756                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
3757                            break;
3758                        }
3759                        case Work::kQuad_Segment: {
3760                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
3761                            break;
3762                        }
3763                        case Work::kCubic_Segment: {
3764                            wt.promoteToCubic();
3765                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
3766                            break;
3767                        }
3768                        default:
3769                            SkASSERT(0);
3770                    }
3771                    break;
3772                case Work::kCubic_Segment:
3773                    switch (wn.segmentType()) {
3774                        case Work::kHorizontalLine_Segment:
3775                            pts = HCubicIntersect(wt.pts(), wn.left(),
3776                                    wn.right(), wn.y(), wn.xFlipped(), ts);
3777                            break;
3778                        case Work::kVerticalLine_Segment:
3779                            pts = VCubicIntersect(wt.pts(), wn.top(),
3780                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
3781                            break;
3782                        case Work::kLine_Segment: {
3783                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
3784                            break;
3785                        }
3786                        case Work::kQuad_Segment: {
3787                            wn.promoteToCubic();
3788                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
3789                            break;
3790                        }
3791                        case Work::kCubic_Segment: {
3792                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
3793                            break;
3794                        }
3795                        default:
3796                            SkASSERT(0);
3797                    }
3798                    break;
3799                default:
3800                    SkASSERT(0);
3801            }
3802            if (!foundCommonContour && pts > 0) {
3803                test->addCross(next);
3804                next->addCross(test);
3805                foundCommonContour = true;
3806            }
3807            // in addition to recording T values, record matching segment
3808            if (pts == 2) {
3809                if (wn.segmentType() <= Work::kLine_Segment
3810                        && wt.segmentType() <= Work::kLine_Segment) {
3811                    wt.addCoincident(wn, ts, swap);
3812                    continue;
3813                }
3814                if (wn.segmentType() == Work::kQuad_Segment
3815                        && wt.segmentType() == Work::kQuad_Segment
3816                        && ts.coincidentUsed() == 2) {
3817                    wt.addCoincident(wn, ts, swap);
3818                    continue;
3819                }
3820
3821            }
3822            for (int pt = 0; pt < pts; ++pt) {
3823                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
3824                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
3825                int testTAt = wt.addT(ts.fT[swap][pt], wn);
3826                int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
3827                wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt);
3828                wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt);
3829            }
3830        } while (wn.advance());
3831    } while (wt.advance());
3832    return true;
3833}
3834
3835// resolve any coincident pairs found while intersecting, and
3836// see if coincidence is formed by clipping non-concident segments
3837static void coincidenceCheck(SkTDArray<Contour*>& contourList) {
3838    int contourCount = contourList.count();
3839    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
3840        Contour* contour = contourList[cIndex];
3841        contour->resolveCoincidence();
3842    }
3843    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
3844        Contour* contour = contourList[cIndex];
3845        contour->findTooCloseToCall();
3846    }
3847}
3848
3849// project a ray from the top of the contour up and see if it hits anything
3850// note: when we compute line intersections, we keep track of whether
3851// two contours touch, so we need only look at contours not touching this one.
3852// OPTIMIZATION: sort contourList vertically to avoid linear walk
3853static int innerContourCheck(SkTDArray<Contour*>& contourList,
3854        const Segment* current, int index, int endIndex) {
3855    const SkPoint& basePt = current->xyAtT(endIndex);
3856    int contourCount = contourList.count();
3857    SkScalar bestY = SK_ScalarMin;
3858    const Segment* test = NULL;
3859    int tIndex;
3860    double tHit;
3861 //   bool checkCrosses = true;
3862    for (int cTest = 0; cTest < contourCount; ++cTest) {
3863        Contour* contour = contourList[cTest];
3864        if (basePt.fY < contour->bounds().fTop) {
3865            continue;
3866        }
3867        if (bestY > contour->bounds().fBottom) {
3868            continue;
3869        }
3870#if 0
3871        // even though the contours crossed, if spans cancel through concidence,
3872        // the contours may be not have any span links to chase, and the current
3873        // segment may be isolated. Detect this by seeing if current has
3874        // uninitialized wind sums. If so, project a ray instead of relying on
3875        // previously found intersections.
3876        if (baseContour == contour) {
3877            continue;
3878        }
3879        if (checkCrosses && baseContour->crosses(contour)) {
3880            if (current->isConnected(index, endIndex)) {
3881                continue;
3882            }
3883            checkCrosses = false;
3884        }
3885#endif
3886        const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit);
3887        if (next) {
3888            test = next;
3889        }
3890    }
3891    if (!test) {
3892        return 0;
3893    }
3894    int winding, windValue;
3895    // If the ray hit the end of a span, we need to construct the wheel of
3896    // angles to find the span closest to the ray -- even if there are just
3897    // two spokes on the wheel.
3898    const Angle* angle = NULL;
3899    if (approximately_zero(tHit - test->t(tIndex))) {
3900        SkTDArray<Angle> angles;
3901        int end = test->nextSpan(tIndex, 1);
3902        if (end < 0) {
3903            end = test->nextSpan(tIndex, -1);
3904        }
3905        test->addTwoAngles(end, tIndex, angles);
3906        SkASSERT(angles.count() > 0);
3907        if (angles[0].segment()->yAtT(angles[0].start()) >= basePt.fY) {
3908#if DEBUG_SORT
3909            SkDebugf("%s early return\n", __FUNCTION__);
3910#endif
3911            return 0;
3912        }
3913        test->buildAngles(tIndex, angles);
3914        SkTDArray<Angle*> sorted;
3915        // OPTIMIZATION: call a sort that, if base point is the leftmost,
3916        // returns the first counterclockwise hour before 6 o'clock,
3917        // or if the base point is rightmost, returns the first clockwise
3918        // hour after 6 o'clock
3919        sortAngles(angles, sorted);
3920#if DEBUG_SORT
3921        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0);
3922#endif
3923        // walk the sorted angle fan to find the lowest angle
3924        // above the base point. Currently, the first angle in the sorted array
3925        // is 12 noon or an earlier hour (the next counterclockwise)
3926        int count = sorted.count();
3927        int left = -1;
3928        int mid = -1;
3929        int right = -1;
3930        bool baseMatches = test->yAtT(tIndex) == basePt.fY;
3931        for (int index = 0; index < count; ++index) {
3932            angle = sorted[index];
3933            if (baseMatches && angle->isHorizontal()) {
3934                continue;
3935            }
3936            double indexDx = angle->dx();
3937            if (indexDx < 0) {
3938                left = index;
3939            } else if (indexDx > 0) {
3940                right = index;
3941                int previous = index - 1;
3942                if (previous < 0) {
3943                    previous = count - 1;
3944                }
3945                const Angle* prev = sorted[previous];
3946                if (prev->dy() >= 0 && prev->dx() > 0 && angle->dy() < 0) {
3947#if DEBUG_SORT
3948                    SkDebugf("%s use prev\n", __FUNCTION__);
3949#endif
3950                    right = previous;
3951                }
3952                break;
3953            } else {
3954                mid = index;
3955            }
3956        }
3957        if (left < 0 && right < 0) {
3958            left = mid;
3959        }
3960        SkASSERT(left >= 0 || right >= 0);
3961        if (left < 0) {
3962            left = right;
3963        } else if (left >= 0 && mid >= 0 && right >= 0
3964                && sorted[mid]->sign() == sorted[right]->sign()) {
3965            left = right;
3966        }
3967        angle = sorted[left];
3968        test = angle->segment();
3969        winding = test->windSum(angle);
3970        SkASSERT(winding != SK_MinS32);
3971        windValue = test->windValue(angle);
3972#if DEBUG_WINDING
3973        SkDebugf("%s angle winding=%d windValue=%d sign=%d\n", __FUNCTION__, winding,
3974                windValue, angle->sign());
3975#endif
3976    } else {
3977        winding = test->windSum(tIndex);
3978        SkASSERT(winding != SK_MinS32);
3979        windValue = test->windValue(tIndex);
3980#if DEBUG_WINDING
3981        SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
3982                windValue);
3983#endif
3984    }
3985    // see if a + change in T results in a +/- change in X (compute x'(T))
3986    SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit);
3987#if DEBUG_WINDING
3988    SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx);
3989#endif
3990    SkASSERT(dx != 0);
3991    if (winding * dx > 0) { // if same signs, result is negative
3992        winding += dx > 0 ? -windValue : windValue;
3993#if DEBUG_WINDING
3994        SkDebugf("%s final winding=%d\n", __FUNCTION__, winding);
3995#endif
3996    }
3997    return winding;
3998}
3999
4000// OPTIMIZATION: not crazy about linear search here to find top active y.
4001// seems like we should break down and do the sort, or maybe sort each
4002// contours' segments?
4003// Once the segment array is built, there's no reason I can think of not to
4004// sort it in Y. hmmm
4005// FIXME: return the contour found to pass to inner contour check
4006static Segment* findTopContour(SkTDArray<Contour*>& contourList) {
4007    int contourCount = contourList.count();
4008    int cIndex = 0;
4009    Segment* topStart;
4010    SkScalar bestY = SK_ScalarMax;
4011    Contour* contour;
4012    do {
4013        contour = contourList[cIndex];
4014        topStart = contour->topSegment(bestY);
4015    } while (!topStart && ++cIndex < contourCount);
4016    if (!topStart) {
4017        return NULL;
4018    }
4019    while (++cIndex < contourCount) {
4020        contour = contourList[cIndex];
4021        if (bestY < contour->bounds().fTop) {
4022            continue;
4023        }
4024        SkScalar testY = SK_ScalarMax;
4025        Segment* test = contour->topSegment(testY);
4026        if (!test || bestY <= testY) {
4027            continue;
4028        }
4029        topStart = test;
4030        bestY = testY;
4031    }
4032    return topStart;
4033}
4034
4035static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
4036    int contourCount = contourList.count();
4037    Segment* result;
4038    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
4039        Contour* contour = contourList[cIndex];
4040        result = contour->undoneSegment(start, end);
4041        if (result) {
4042            return result;
4043        }
4044    }
4045    return NULL;
4046}
4047
4048
4049
4050static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex,
4051        int contourWinding) {
4052    while (chase.count()) {
4053        Span* span = chase[chase.count() - 1];
4054        const Span& backPtr = span->fOther->span(span->fOtherIndex);
4055        Segment* segment = backPtr.fOther;
4056        tIndex = backPtr.fOtherIndex;
4057        SkTDArray<Angle> angles;
4058        int done = 0;
4059        if (segment->activeAngle(tIndex, done, angles)) {
4060            Angle* last = angles.end() - 1;
4061            tIndex = last->start();
4062            endIndex = last->end();
4063            return last->segment();
4064        }
4065        if (done == angles.count()) {
4066            chase.pop(&span);
4067            continue;
4068        }
4069        SkTDArray<Angle*> sorted;
4070        sortAngles(angles, sorted);
4071#if DEBUG_SORT
4072        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0);
4073#endif
4074        // find first angle, initialize winding to computed fWindSum
4075        int firstIndex = -1;
4076        const Angle* angle;
4077        int winding;
4078        do {
4079            angle = sorted[++firstIndex];
4080            segment = angle->segment();
4081            winding = segment->windSum(angle);
4082        } while (winding == SK_MinS32);
4083        int spanWinding = segment->spanSign(angle->start(), angle->end());
4084    #if DEBUG_WINDING
4085        SkDebugf("%s winding=%d spanWinding=%d contourWinding=%d\n",
4086                __FUNCTION__, winding, spanWinding, contourWinding);
4087    #endif
4088        // turn swinding into contourWinding
4089        if (spanWinding * winding < 0) {
4090            winding += spanWinding;
4091        }
4092    #if DEBUG_SORT
4093        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding);
4094    #endif
4095        // we care about first sign and whether wind sum indicates this
4096        // edge is inside or outside. Maybe need to pass span winding
4097        // or first winding or something into this function?
4098        // advance to first undone angle, then return it and winding
4099        // (to set whether edges are active or not)
4100        int nextIndex = firstIndex + 1;
4101        int angleCount = sorted.count();
4102        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
4103        angle = sorted[firstIndex];
4104        winding -= angle->segment()->spanSign(angle);
4105        do {
4106            SkASSERT(nextIndex != firstIndex);
4107            if (nextIndex == angleCount) {
4108                nextIndex = 0;
4109            }
4110            angle = sorted[nextIndex];
4111            segment = angle->segment();
4112            int maxWinding = winding;
4113            winding -= segment->spanSign(angle);
4114    #if DEBUG_SORT
4115            SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
4116                    segment->debugID(), maxWinding, winding, angle->sign());
4117    #endif
4118            tIndex = angle->start();
4119            endIndex = angle->end();
4120            int lesser = SkMin32(tIndex, endIndex);
4121            const Span& nextSpan = segment->span(lesser);
4122            if (!nextSpan.fDone) {
4123#if 1
4124            // FIXME: this be wrong. assign startWinding if edge is in
4125            // same direction. If the direction is opposite, winding to
4126            // assign is flipped sign or +/- 1?
4127                if (useInnerWinding(maxWinding, winding)) {
4128                    maxWinding = winding;
4129                }
4130                segment->markWinding(lesser, maxWinding);
4131#endif
4132                break;
4133            }
4134        } while (++nextIndex != lastIndex);
4135        return segment;
4136    }
4137    return NULL;
4138}
4139
4140#if DEBUG_ACTIVE_SPANS
4141static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
4142    for (int index = 0; index < contourList.count(); ++ index) {
4143        contourList[index]->debugShowActiveSpans();
4144    }
4145}
4146#endif
4147
4148static bool windingIsActive(int winding, int spanWinding) {
4149    return winding * spanWinding <= 0 && abs(winding) <= abs(spanWinding)
4150            && (!winding || !spanWinding || winding == -spanWinding);
4151}
4152
4153// Each segment may have an inside or an outside. Segments contained within
4154// winding may have insides on either side, and form a contour that should be
4155// ignored. Segments that are coincident with opposing direction segments may
4156// have outsides on either side, and should also disappear.
4157// 'Normal' segments will have one inside and one outside. Subsequent connections
4158// when winding should follow the intersection direction. If more than one edge
4159// is an option, choose first edge that continues the inside.
4160    // since we start with leftmost top edge, we'll traverse through a
4161    // smaller angle counterclockwise to get to the next edge.
4162static void bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) {
4163    bool firstContour = true;
4164    do {
4165        Segment* topStart = findTopContour(contourList);
4166        if (!topStart) {
4167            break;
4168        }
4169        // Start at the top. Above the top is outside, below is inside.
4170        // follow edges to intersection by changing the index by direction.
4171        int index, endIndex;
4172        Segment* current = topStart->findTop(index, endIndex);
4173        int contourWinding;
4174        if (firstContour) {
4175            contourWinding = 0;
4176            firstContour = false;
4177        } else {
4178            int sumWinding = current->windSum(SkMin32(index, endIndex));
4179            // FIXME: don't I have to adjust windSum to get contourWinding?
4180            if (sumWinding == SK_MinS32) {
4181                sumWinding = current->computeSum(index, endIndex);
4182            }
4183            if (sumWinding == SK_MinS32) {
4184                contourWinding = innerContourCheck(contourList, current,
4185                        index, endIndex);
4186            } else {
4187                contourWinding = sumWinding;
4188                int spanWinding = current->spanSign(index, endIndex);
4189                bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding);
4190                if (inner) {
4191                    contourWinding -= spanWinding;
4192                }
4193#if DEBUG_WINDING
4194                SkDebugf("%s sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
4195                        sumWinding, spanWinding, SkSign32(index - endIndex),
4196                        inner, contourWinding);
4197#endif
4198            }
4199#if DEBUG_WINDING
4200         //   SkASSERT(current->debugVerifyWinding(index, endIndex, contourWinding));
4201            SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
4202#endif
4203        }
4204        SkPoint lastPt;
4205        int winding = contourWinding;
4206        int spanWinding = current->spanSign(index, endIndex);
4207        // FIXME: needs work. While it works in limited situations, it does
4208        // not always compute winding correctly. Active should be removed and instead
4209        // the initial winding should be correctly passed in so that if the
4210        // inner contour is wound the same way, it never finds an accumulated
4211        // winding of zero. Inside 'find next', we need to look for transitions
4212        // other than zero when resolving sorted angles.
4213        bool active = windingIsActive(winding, spanWinding);
4214        SkTDArray<Span*> chaseArray;
4215        do {
4216        #if DEBUG_WINDING
4217            SkDebugf("%s active=%s winding=%d spanWinding=%d\n",
4218                    __FUNCTION__, active ? "true" : "false",
4219                    winding, spanWinding);
4220        #endif
4221            const SkPoint* firstPt = NULL;
4222            do {
4223                SkASSERT(!current->done());
4224                int nextStart = index;
4225                int nextEnd = endIndex;
4226                Segment* next = current->findNextWinding(chaseArray, active,
4227                        nextStart, nextEnd, winding, spanWinding);
4228                if (!next) {
4229                    if (active && firstPt && current->verb() != SkPath::kLine_Verb && *firstPt != lastPt) {
4230                        lastPt = current->addCurveTo(index, endIndex, simple, true);
4231                        SkASSERT(*firstPt == lastPt);
4232                    }
4233                    break;
4234                }
4235                if (!firstPt) {
4236                    firstPt = &current->addMoveTo(index, simple, active);
4237                }
4238                lastPt = current->addCurveTo(index, endIndex, simple, active);
4239                current = next;
4240                index = nextStart;
4241                endIndex = nextEnd;
4242            } while (*firstPt != lastPt && (active || !current->done()));
4243            if (firstPt && active) {
4244        #if DEBUG_PATH_CONSTRUCTION
4245                SkDebugf("%s close\n", __FUNCTION__);
4246        #endif
4247                simple.close();
4248            }
4249            current = findChase(chaseArray, index, endIndex, contourWinding);
4250        #if DEBUG_ACTIVE_SPANS
4251            debugShowActiveSpans(contourList);
4252        #endif
4253            if (!current) {
4254                break;
4255            }
4256            int lesser = SkMin32(index, endIndex);
4257            spanWinding = current->spanSign(index, endIndex);
4258            winding = current->windSum(lesser);
4259            bool inner = useInnerWinding(winding - spanWinding, winding);
4260        #if DEBUG_WINDING
4261            SkDebugf("%s id=%d t=%1.9g spanWinding=%d winding=%d sign=%d"
4262                    " inner=%d result=%d\n",
4263                    __FUNCTION__, current->debugID(), current->t(lesser),
4264                    spanWinding, winding, SkSign32(index - endIndex),
4265                    useInnerWinding(winding - spanWinding, winding),
4266                    inner ? winding - spanWinding : winding);
4267        #endif
4268            if (inner) {
4269                winding -= spanWinding;
4270            }
4271            active = windingIsActive(winding, spanWinding);
4272        } while (true);
4273    } while (true);
4274}
4275
4276static void bridgeXor(SkTDArray<Contour*>& contourList, SkPath& simple) {
4277    Segment* current;
4278    int start, end;
4279    while ((current = findUndone(contourList, start, end))) {
4280        const SkPoint* firstPt = NULL;
4281        SkPoint lastPt;
4282        do {
4283            SkASSERT(!current->done());
4284            int nextStart = start;
4285            int nextEnd = end;
4286            Segment* next = current->findNextXor(nextStart, nextEnd);
4287            if (!next) {
4288                if (firstPt && current->verb() != SkPath::kLine_Verb && *firstPt != lastPt) {
4289                    lastPt = current->addCurveTo(start, end, simple, true);
4290                    SkASSERT(*firstPt == lastPt);
4291                }
4292                break;
4293            }
4294            if (!firstPt) {
4295                firstPt = &current->addMoveTo(start, simple, true);
4296            }
4297            lastPt = current->addCurveTo(start, end, simple, true);
4298            current = next;
4299            start = nextStart;
4300            end = nextEnd;
4301        } while (*firstPt != lastPt);
4302        if (firstPt) {
4303    #if DEBUG_PATH_CONSTRUCTION
4304            SkDebugf("%s close\n", __FUNCTION__);
4305    #endif
4306            simple.close();
4307        }
4308    }
4309}
4310
4311static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
4312    int contourCount = contourList.count();
4313    for (int cTest = 0; cTest < contourCount; ++cTest) {
4314        Contour* contour = contourList[cTest];
4315        contour->fixOtherTIndex();
4316    }
4317}
4318
4319static void makeContourList(SkTArray<Contour>& contours,
4320        SkTDArray<Contour*>& list) {
4321    int count = contours.count();
4322    if (count == 0) {
4323        return;
4324    }
4325    for (int index = 0; index < count; ++index) {
4326        *list.append() = &contours[index];
4327    }
4328    QSort<Contour>(list.begin(), list.end() - 1);
4329}
4330
4331void simplifyx(const SkPath& path, SkPath& simple) {
4332    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
4333    simple.reset();
4334    simple.setFillType(SkPath::kEvenOdd_FillType);
4335
4336    // turn path into list of segments
4337    SkTArray<Contour> contours;
4338    // FIXME: add self-intersecting cubics' T values to segment
4339    EdgeBuilder builder(path, contours);
4340    builder.finish();
4341    SkTDArray<Contour*> contourList;
4342    makeContourList(contours, contourList);
4343    Contour** currentPtr = contourList.begin();
4344    if (!currentPtr) {
4345        return;
4346    }
4347    Contour** listEnd = contourList.end();
4348    // find all intersections between segments
4349    do {
4350        Contour** nextPtr = currentPtr;
4351        Contour* current = *currentPtr++;
4352        Contour* next;
4353        do {
4354            next = *nextPtr++;
4355        } while (addIntersectTs(current, next) && nextPtr != listEnd);
4356    } while (currentPtr != listEnd);
4357    // eat through coincident edges
4358    coincidenceCheck(contourList);
4359    fixOtherTIndex(contourList);
4360    // construct closed contours
4361    if (builder.xorMask() == kWinding_Mask) {
4362        bridgeWinding(contourList, simple);
4363    } else {
4364        bridgeXor(contourList, simple);
4365    }
4366}
4367
4368