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