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