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