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