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