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