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