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