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