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