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