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