Simplify.cpp revision d9f65e3df45c9b4994c70f6bf13d29985afd2f65 
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;
5064            switch (wt.segmentType()) {
5065                case Work::kHorizontalLine_Segment:
5066                    swap = true;
5067                    switch (wn.segmentType()) {
5068                        case Work::kHorizontalLine_Segment:
5069                        case Work::kVerticalLine_Segment:
5070                        case Work::kLine_Segment: {
5071                            pts = HLineIntersect(wn.pts(), wt.left(),
5072                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5073                            debugShowLineIntersection(pts, wt, wn,
5074                                    ts.fT[1], ts.fT[0]);
5075                            break;
5076                        }
5077                        case Work::kQuad_Segment: {
5078                            pts = HQuadIntersect(wn.pts(), wt.left(),
5079                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5080                            break;
5081                        }
5082                        case Work::kCubic_Segment: {
5083                            pts = HCubicIntersect(wn.pts(), wt.left(),
5084                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5085                            break;
5086                        }
5087                        default:
5088                            SkASSERT(0);
5089                    }
5090                    break;
5091                case Work::kVerticalLine_Segment:
5092                    swap = true;
5093                    switch (wn.segmentType()) {
5094                        case Work::kHorizontalLine_Segment:
5095                        case Work::kVerticalLine_Segment:
5096                        case Work::kLine_Segment: {
5097                            pts = VLineIntersect(wn.pts(), wt.top(),
5098                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5099                            debugShowLineIntersection(pts, wt, wn,
5100                                    ts.fT[1], ts.fT[0]);
5101                            break;
5102                        }
5103                        case Work::kQuad_Segment: {
5104                            pts = VQuadIntersect(wn.pts(), wt.top(),
5105                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5106                            break;
5107                        }
5108                        case Work::kCubic_Segment: {
5109                            pts = VCubicIntersect(wn.pts(), wt.top(),
5110                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5111                            break;
5112                        }
5113                        default:
5114                            SkASSERT(0);
5115                    }
5116                    break;
5117                case Work::kLine_Segment:
5118                    switch (wn.segmentType()) {
5119                        case Work::kHorizontalLine_Segment:
5120                            pts = HLineIntersect(wt.pts(), wn.left(),
5121                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5122                            debugShowLineIntersection(pts, wt, wn,
5123                                    ts.fT[1], ts.fT[0]);
5124                            break;
5125                        case Work::kVerticalLine_Segment:
5126                            pts = VLineIntersect(wt.pts(), wn.top(),
5127                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5128                            debugShowLineIntersection(pts, wt, wn,
5129                                    ts.fT[1], ts.fT[0]);
5130                            break;
5131                        case Work::kLine_Segment: {
5132                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
5133                            debugShowLineIntersection(pts, wt, wn,
5134                                    ts.fT[1], ts.fT[0]);
5135                            break;
5136                        }
5137                        case Work::kQuad_Segment: {
5138                            swap = true;
5139                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
5140                            debugShowQuadLineIntersection(pts, wn, wt,
5141                                    ts.fT[0], ts.fT[1]);
5142                            break;
5143                        }
5144                        case Work::kCubic_Segment: {
5145                            swap = true;
5146                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
5147                            break;
5148                        }
5149                        default:
5150                            SkASSERT(0);
5151                    }
5152                    break;
5153                case Work::kQuad_Segment:
5154                    switch (wn.segmentType()) {
5155                        case Work::kHorizontalLine_Segment:
5156                            pts = HQuadIntersect(wt.pts(), wn.left(),
5157                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5158                            break;
5159                        case Work::kVerticalLine_Segment:
5160                            pts = VQuadIntersect(wt.pts(), wn.top(),
5161                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5162                            break;
5163                        case Work::kLine_Segment: {
5164                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
5165                            debugShowQuadLineIntersection(pts, wt, wn,
5166                                    ts.fT[0], ts.fT[1]);
5167                            break;
5168                        }
5169                        case Work::kQuad_Segment: {
5170                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
5171                            debugShowQuadIntersection(pts, wt, wn,
5172                                    ts.fT[0], ts.fT[1]);
5173                            break;
5174                        }
5175                        case Work::kCubic_Segment: {
5176                            wt.promoteToCubic();
5177                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
5178                            break;
5179                        }
5180                        default:
5181                            SkASSERT(0);
5182                    }
5183                    break;
5184                case Work::kCubic_Segment:
5185                    switch (wn.segmentType()) {
5186                        case Work::kHorizontalLine_Segment:
5187                            pts = HCubicIntersect(wt.pts(), wn.left(),
5188                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5189                            break;
5190                        case Work::kVerticalLine_Segment:
5191                            pts = VCubicIntersect(wt.pts(), wn.top(),
5192                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5193                            break;
5194                        case Work::kLine_Segment: {
5195                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
5196                            break;
5197                        }
5198                        case Work::kQuad_Segment: {
5199                            wn.promoteToCubic();
5200                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
5201                            break;
5202                        }
5203                        case Work::kCubic_Segment: {
5204                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
5205                            break;
5206                        }
5207                        default:
5208                            SkASSERT(0);
5209                    }
5210                    break;
5211                default:
5212                    SkASSERT(0);
5213            }
5214            if (!foundCommonContour && pts > 0) {
5215                test->addCross(next);
5216                next->addCross(test);
5217                foundCommonContour = true;
5218            }
5219            // in addition to recording T values, record matching segment
5220            if (pts == 2) {
5221                if (wn.segmentType() <= Work::kLine_Segment
5222                        && wt.segmentType() <= Work::kLine_Segment) {
5223                    wt.addCoincident(wn, ts, swap);
5224                    continue;
5225                }
5226                if (wn.segmentType() == Work::kQuad_Segment
5227                        && wt.segmentType() == Work::kQuad_Segment
5228                        && ts.coincidentUsed() == 2) {
5229                    wt.addCoincident(wn, ts, swap);
5230                    continue;
5231                }
5232
5233            }
5234            for (int pt = 0; pt < pts; ++pt) {
5235                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
5236                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
5237                int testTAt = wt.addT(ts.fT[swap][pt], wn);
5238                int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
5239                wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
5240                wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
5241            }
5242        } while (wn.advance());
5243    } while (wt.advance());
5244    return true;
5245}
5246
5247// resolve any coincident pairs found while intersecting, and
5248// see if coincidence is formed by clipping non-concident segments
5249static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {
5250    int contourCount = contourList.count();
5251#if ONE_PASS_COINCIDENCE_CHECK
5252    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5253        Contour* contour = contourList[cIndex];
5254        contour->resolveCoincidence(contourList);
5255    }
5256#else
5257    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5258        Contour* contour = contourList[cIndex];
5259        contour->addCoincidentPoints();
5260    }
5261    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5262        Contour* contour = contourList[cIndex];
5263        contour->calcCoincidentWinding();
5264    }
5265#endif
5266    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5267        Contour* contour = contourList[cIndex];
5268        contour->findTooCloseToCall();
5269    }
5270}
5271
5272static int contourRangeCheckY(SkTDArray<Contour*>& contourList,  Segment*& current, int& index,
5273        int& endIndex, double& bestHit, SkScalar& bestDx, bool& tryAgain, double& mid, bool opp) {
5274    SkPoint basePt;
5275    double tAtMid = current->tAtMid(index, endIndex, mid);
5276    current->xyAtT(tAtMid, basePt);
5277    int contourCount = contourList.count();
5278    SkScalar bestY = SK_ScalarMin;
5279    Segment* bestSeg = NULL;
5280    int bestTIndex;
5281    bool bestOpp;
5282    bool hitSomething = false;
5283    for (int cTest = 0; cTest < contourCount; ++cTest) {
5284        Contour* contour = contourList[cTest];
5285        bool testOpp = contour->operand() ^ current->operand() ^ opp;
5286        if (basePt.fY < contour->bounds().fTop) {
5287            continue;
5288        }
5289        if (bestY > contour->bounds().fBottom) {
5290            continue;
5291        }
5292        int segmentCount = contour->segments().count();
5293        for (int test = 0; test < segmentCount; ++test) {
5294            Segment* testSeg = &contour->segments()[test];
5295            SkScalar testY = bestY;
5296            double testHit;
5297            int testTIndex = testSeg->crossedSpanY(basePt, testY, testHit, hitSomething, tAtMid,
5298                    testOpp, testSeg == current);
5299            if (testTIndex < 0) {
5300                if (testTIndex == SK_MinS32) {
5301                    hitSomething = true;
5302                    bestSeg = NULL;
5303                    goto abortContours; // vertical encountered, return and try different point
5304                }
5305                continue;
5306            }
5307            if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
5308                double baseT = current->t(index);
5309                double endT = current->t(endIndex);
5310                double newMid = (testHit - baseT) / (endT - baseT);
5311#if DEBUG_WINDING
5312                SkPoint midXY, newXY;
5313                double midT = current->tAtMid(index, endIndex, mid);
5314                current->xyAtT(midT, midXY);
5315                double newMidT = current->tAtMid(index, endIndex, newMid);
5316                current->xyAtT(newMidT, newXY);
5317                SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
5318                        " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
5319                        current->debugID(), mid, newMid,
5320                        baseT, current->xAtT(index), current->yAtT(index),
5321                        baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
5322                        baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
5323                        endT, current->xAtT(endIndex), current->yAtT(endIndex));
5324#endif
5325                mid = newMid * 2; // calling loop with divide by 2 before continuing
5326                return SK_MinS32;
5327            }
5328            bestSeg = testSeg;
5329            bestHit = testHit;
5330            bestOpp = testOpp;
5331            bestTIndex = testTIndex;
5332            bestY = testY;
5333        }
5334    }
5335abortContours:
5336    int result;
5337    if (!bestSeg) {
5338        result = hitSomething ? SK_MinS32 : 0;
5339    } else {
5340        if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
5341            current = bestSeg;
5342            index = bestTIndex;
5343            endIndex = bestSeg->nextSpan(bestTIndex, 1);
5344            SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
5345            tryAgain = true;
5346            return 0;
5347        }
5348        result = bestSeg->windingAtT(bestHit, bestTIndex, bestOpp, bestDx);
5349        SkASSERT(bestDx);
5350    }
5351    double baseT = current->t(index);
5352    double endT = current->t(endIndex);
5353    bestHit = baseT + mid * (endT - baseT);
5354    return result;
5355}
5356
5357static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
5358    int contourCount = contourList.count();
5359    Segment* result;
5360    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5361        Contour* contour = contourList[cIndex];
5362        result = contour->undoneSegment(start, end);
5363        if (result) {
5364            return result;
5365        }
5366    }
5367    return NULL;
5368}
5369
5370#define OLD_FIND_CHASE 1
5371
5372static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {
5373    while (chase.count()) {
5374        Span* span;
5375        chase.pop(&span);
5376        const Span& backPtr = span->fOther->span(span->fOtherIndex);
5377        Segment* segment = backPtr.fOther;
5378        tIndex = backPtr.fOtherIndex;
5379        SkTDArray<Angle> angles;
5380        int done = 0;
5381        if (segment->activeAngle(tIndex, done, angles)) {
5382            Angle* last = angles.end() - 1;
5383            tIndex = last->start();
5384            endIndex = last->end();
5385   #if TRY_ROTATE
5386            *chase.insert(0) = span;
5387   #else
5388            *chase.append() = span;
5389   #endif
5390            return last->segment();
5391        }
5392        if (done == angles.count()) {
5393            continue;
5394        }
5395        SkTDArray<Angle*> sorted;
5396        bool sortable = Segment::SortAngles(angles, sorted);
5397        int angleCount = sorted.count();
5398#if DEBUG_SORT
5399        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
5400#endif
5401        if (!sortable) {
5402            continue;
5403        }
5404        // find first angle, initialize winding to computed fWindSum
5405        int firstIndex = -1;
5406        const Angle* angle;
5407#if OLD_FIND_CHASE
5408        int winding;
5409        do {
5410            angle = sorted[++firstIndex];
5411            segment = angle->segment();
5412            winding = segment->windSum(angle);
5413        } while (winding == SK_MinS32);
5414        int spanWinding = segment->spanSign(angle->start(), angle->end());
5415    #if DEBUG_WINDING
5416        SkDebugf("%s winding=%d spanWinding=%d\n",
5417                __FUNCTION__, winding, spanWinding);
5418    #endif
5419        // turn span winding into contour winding
5420        if (spanWinding * winding < 0) {
5421            winding += spanWinding;
5422        }
5423    #if DEBUG_SORT
5424        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);
5425    #endif
5426        // we care about first sign and whether wind sum indicates this
5427        // edge is inside or outside. Maybe need to pass span winding
5428        // or first winding or something into this function?
5429        // advance to first undone angle, then return it and winding
5430        // (to set whether edges are active or not)
5431        int nextIndex = firstIndex + 1;
5432        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5433        angle = sorted[firstIndex];
5434        winding -= angle->segment()->spanSign(angle);
5435#else
5436        do {
5437            angle = sorted[++firstIndex];
5438            segment = angle->segment();
5439        } while (segment->windSum(angle) == SK_MinS32);
5440    #if DEBUG_SORT
5441        segment->debugShowSort(__FUNCTION__, sorted, firstIndex);
5442    #endif
5443        int sumWinding = segment->updateWindingReverse(angle);
5444        int nextIndex = firstIndex + 1;
5445        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5446        Segment* first = NULL;
5447#endif
5448        do {
5449            SkASSERT(nextIndex != firstIndex);
5450            if (nextIndex == angleCount) {
5451                nextIndex = 0;
5452            }
5453            angle = sorted[nextIndex];
5454            segment = angle->segment();
5455#if OLD_FIND_CHASE
5456            int maxWinding = winding;
5457            winding -= segment->spanSign(angle);
5458    #if DEBUG_SORT
5459            SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
5460                    segment->debugID(), maxWinding, winding, angle->sign());
5461    #endif
5462            tIndex = angle->start();
5463            endIndex = angle->end();
5464            int lesser = SkMin32(tIndex, endIndex);
5465            const Span& nextSpan = segment->span(lesser);
5466            if (!nextSpan.fDone) {
5467#if 1
5468            // FIXME: this be wrong? assign startWinding if edge is in
5469            // same direction. If the direction is opposite, winding to
5470            // assign is flipped sign or +/- 1?
5471                if (useInnerWinding(maxWinding, winding)) {
5472                    maxWinding = winding;
5473                }
5474                segment->markAndChaseWinding(angle, maxWinding, 0);
5475#endif
5476                break;
5477            }
5478#else
5479            int start = angle->start();
5480            int end = angle->end();
5481            int maxWinding;
5482            segment->setUpWinding(start, end, maxWinding, sumWinding);
5483            if (!segment->done(angle)) {
5484                if (!first) {
5485                    first = segment;
5486                    tIndex = start;
5487                    endIndex = end;
5488                }
5489                (void) segment->markAngle(maxWinding, sumWinding, true, angle);
5490            }
5491#endif
5492        } while (++nextIndex != lastIndex);
5493   #if TRY_ROTATE
5494        *chase.insert(0) = span;
5495   #else
5496        *chase.append() = span;
5497   #endif
5498        return segment;
5499    }
5500    return NULL;
5501}
5502
5503#if DEBUG_ACTIVE_SPANS
5504static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
5505    int index;
5506    for (index = 0; index < contourList.count(); ++ index) {
5507        contourList[index]->debugShowActiveSpans();
5508    }
5509    for (index = 0; index < contourList.count(); ++ index) {
5510        contourList[index]->validateActiveSpans();
5511    }
5512}
5513#endif
5514
5515static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
5516        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool onlySortable) {
5517    Segment* result;
5518    do {
5519        SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
5520        int contourCount = contourList.count();
5521        Segment* topStart = NULL;
5522        done = true;
5523        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5524            Contour* contour = contourList[cIndex];
5525            if (contour->done()) {
5526                continue;
5527            }
5528            const Bounds& bounds = contour->bounds();
5529            if (bounds.fBottom < topLeft.fY) {
5530                done = false;
5531                continue;
5532            }
5533            if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) {
5534                done = false;
5535                continue;
5536            }
5537            contour->topSortableSegment(topLeft, bestXY, topStart);
5538            if (!contour->done()) {
5539                done = false;
5540            }
5541        }
5542        if (!topStart) {
5543            return NULL;
5544        }
5545        topLeft = bestXY;
5546        result = topStart->findTop(index, endIndex, unsortable, onlySortable);
5547    } while (!result);
5548    return result;
5549}
5550
5551static int rightAngleWinding(SkTDArray<Contour*>& contourList,
5552        Segment*& current, int& index, int& endIndex, double& tHit, SkScalar& hitDx, bool& tryAgain,
5553        bool opp) {
5554    double test = 0.9;
5555    int contourWinding;
5556    do {
5557        contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
5558                tryAgain, test, opp);
5559        if (contourWinding != SK_MinS32 || tryAgain) {
5560            return contourWinding;
5561        }
5562        test /= 2;
5563    } while (!approximately_negative(test));
5564    SkASSERT(0); // should be OK to comment out, but interested when this hits
5565    return contourWinding;
5566}
5567
5568static void skipVertical(SkTDArray<Contour*>& contourList,
5569        Segment*& current, int& index, int& endIndex) {
5570    if (!current->isVertical(index, endIndex)) {
5571        return;
5572    }
5573    int contourCount = contourList.count();
5574    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5575        Contour* contour = contourList[cIndex];
5576        if (contour->done()) {
5577            continue;
5578        }
5579        current = contour->nonVerticalSegment(index, endIndex);
5580        if (current) {
5581            return;
5582        }
5583    }
5584}
5585
5586static Segment* findSortableTop(SkTDArray<Contour*>& contourList, bool& firstContour, int& index,
5587        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool binary) {
5588    Segment* current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, done,
5589            true);
5590    if (!current) {
5591        return NULL;
5592    }
5593    if (firstContour) {
5594        current->initWinding(index, endIndex);
5595        firstContour = false;
5596        return current;
5597    }
5598    int minIndex = SkMin32(index, endIndex);
5599    int sumWinding = current->windSum(minIndex);
5600    if (sumWinding != SK_MinS32) {
5601        return current;
5602    }
5603    sumWinding = current->computeSum(index, endIndex, binary);
5604    if (sumWinding != SK_MinS32) {
5605        return current;
5606    }
5607    int contourWinding;
5608    int oppContourWinding = 0;
5609    // the simple upward projection of the unresolved points hit unsortable angles
5610    // shoot rays at right angles to the segment to find its winding, ignoring angle cases
5611    bool tryAgain;
5612    double tHit;
5613    SkScalar hitDx = 0;
5614    SkScalar hitOppDx = 0;
5615    do {
5616        // if current is vertical, find another candidate which is not
5617        // if only remaining candidates are vertical, then they can be marked done
5618        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
5619        skipVertical(contourList, current, index, endIndex);
5620        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
5621        tryAgain = false;
5622        contourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitDx,
5623                tryAgain, false);
5624        if (tryAgain) {
5625            continue;
5626        }
5627        if (!binary) {
5628            break;
5629        }
5630        oppContourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitOppDx,
5631                tryAgain, true);
5632    } while (tryAgain);
5633
5634    current->initWinding(index, endIndex, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx);
5635    return current;
5636}
5637
5638// rewrite that abandons keeping local track of winding
5639static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
5640    bool firstContour = true;
5641    bool unsortable = false;
5642    bool topUnsortable = false;
5643    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
5644    do {
5645        int index, endIndex;
5646        bool topDone;
5647        Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft,
5648                topUnsortable, topDone, false);
5649        if (!current) {
5650            if (topUnsortable || !topDone) {
5651                topUnsortable = false;
5652                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
5653                topLeft.fX = topLeft.fY = SK_ScalarMin;
5654                continue;
5655            }
5656            break;
5657        }
5658        SkTDArray<Span*> chaseArray;
5659        do {
5660            if (current->activeWinding(index, endIndex)) {
5661                do {
5662            #if DEBUG_ACTIVE_SPANS
5663                    if (!unsortable && current->done()) {
5664                        debugShowActiveSpans(contourList);
5665                    }
5666            #endif
5667                    SkASSERT(unsortable || !current->done());
5668                    int nextStart = index;
5669                    int nextEnd = endIndex;
5670                    Segment* next = current->findNextWinding(chaseArray, nextStart, nextEnd,
5671                            unsortable);
5672                    if (!next) {
5673                        if (!unsortable && simple.hasMove()
5674                                && current->verb() != SkPath::kLine_Verb
5675                                && !simple.isClosed()) {
5676                            current->addCurveTo(index, endIndex, simple, true);
5677                            SkASSERT(simple.isClosed());
5678                        }
5679                        break;
5680                    }
5681        #if DEBUG_FLOW
5682            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
5683                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
5684                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
5685        #endif
5686                    current->addCurveTo(index, endIndex, simple, true);
5687                    current = next;
5688                    index = nextStart;
5689                    endIndex = nextEnd;
5690                } while (!simple.isClosed() && (!unsortable
5691                        || !current->done(SkMin32(index, endIndex))));
5692                if (current->activeWinding(index, endIndex) && !simple.isClosed()) {
5693                    SkASSERT(unsortable);
5694                    int min = SkMin32(index, endIndex);
5695                    if (!current->done(min)) {
5696                        current->addCurveTo(index, endIndex, simple, true);
5697                        current->markDoneUnary(min);
5698                    }
5699                }
5700                simple.close();
5701            } else {
5702                Span* last = current->markAndChaseDoneUnary(index, endIndex);
5703                if (last) {
5704                    *chaseArray.append() = last;
5705                }
5706            }
5707            current = findChase(chaseArray, index, endIndex);
5708        #if DEBUG_ACTIVE_SPANS
5709            debugShowActiveSpans(contourList);
5710        #endif
5711            if (!current) {
5712                break;
5713            }
5714        } while (true);
5715    } while (true);
5716    return simple.someAssemblyRequired();
5717}
5718
5719// returns true if all edges were processed
5720static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
5721    Segment* current;
5722    int start, end;
5723    bool unsortable = false;
5724    bool closable = true;
5725    while ((current = findUndone(contourList, start, end))) {
5726        do {
5727    #if DEBUG_ACTIVE_SPANS
5728            if (!unsortable && current->done()) {
5729                debugShowActiveSpans(contourList);
5730            }
5731    #endif
5732            SkASSERT(unsortable || !current->done());
5733            int nextStart = start;
5734            int nextEnd = end;
5735            Segment* next = current->findNextXor(nextStart, nextEnd, unsortable);
5736            if (!next) {
5737                if (!unsortable && simple.hasMove()
5738                        && current->verb() != SkPath::kLine_Verb
5739                        && !simple.isClosed()) {
5740                    current->addCurveTo(start, end, simple, true);
5741                    SkASSERT(simple.isClosed());
5742                }
5743                break;
5744            }
5745        #if DEBUG_FLOW
5746            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
5747                    current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
5748                    current->xyAtT(end).fX, current->xyAtT(end).fY);
5749        #endif
5750            current->addCurveTo(start, end, simple, true);
5751            current = next;
5752            start = nextStart;
5753            end = nextEnd;
5754        } while (!simple.isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
5755        if (!simple.isClosed()) {
5756            SkASSERT(unsortable);
5757            int min = SkMin32(start, end);
5758            if (!current->done(min)) {
5759                current->addCurveTo(start, end, simple, true);
5760                current->markDone(min, 1);
5761            }
5762            closable = false;
5763        }
5764        simple.close();
5765    #if DEBUG_ACTIVE_SPANS
5766        debugShowActiveSpans(contourList);
5767    #endif
5768    }
5769    return closable;
5770}
5771
5772static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
5773    int contourCount = contourList.count();
5774    for (int cTest = 0; cTest < contourCount; ++cTest) {
5775        Contour* contour = contourList[cTest];
5776        contour->fixOtherTIndex();
5777    }
5778}
5779
5780static void sortSegments(SkTDArray<Contour*>& contourList) {
5781    int contourCount = contourList.count();
5782    for (int cTest = 0; cTest < contourCount; ++cTest) {
5783        Contour* contour = contourList[cTest];
5784        contour->sortSegments();
5785    }
5786}
5787
5788static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& list,
5789        bool evenOdd, bool oppEvenOdd) {
5790    int count = contours.count();
5791    if (count == 0) {
5792        return;
5793    }
5794    for (int index = 0; index < count; ++index) {
5795        Contour& contour = contours[index];
5796        contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
5797        *list.append() = &contour;
5798    }
5799    QSort<Contour>(list.begin(), list.end() - 1);
5800}
5801
5802static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) {
5803    return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY);
5804}
5805
5806static bool lessThan(SkTDArray<double>& distances, const int one, const int two) {
5807    return distances[one] < distances[two];
5808}
5809    /*
5810        check start and end of each contour
5811        if not the same, record them
5812        match them up
5813        connect closest
5814        reassemble contour pieces into new path
5815    */
5816static void assemble(const PathWrapper& path, PathWrapper& simple) {
5817#if DEBUG_PATH_CONSTRUCTION
5818    SkDebugf("%s\n", __FUNCTION__);
5819#endif
5820    SkTArray<Contour> contours;
5821    EdgeBuilder builder(path, contours);
5822    builder.finish();
5823    int count = contours.count();
5824    int outer;
5825    SkTDArray<int> runs; // indices of partial contours
5826    for (outer = 0; outer < count; ++outer) {
5827        const Contour& eContour = contours[outer];
5828        const SkPoint& eStart = eContour.start();
5829        const SkPoint& eEnd = eContour.end();
5830#if DEBUG_ASSEMBLE
5831        SkDebugf("%s contour", __FUNCTION__);
5832        if (!approximatelyEqual(eStart, eEnd)) {
5833            SkDebugf("[%d]", runs.count());
5834        } else {
5835            SkDebugf("   ");
5836        }
5837        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
5838                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
5839#endif
5840        if (approximatelyEqual(eStart, eEnd)) {
5841            eContour.toPath(simple);
5842            continue;
5843        }
5844        *runs.append() = outer;
5845    }
5846    count = runs.count();
5847    if (count == 0) {
5848        return;
5849    }
5850    SkTDArray<int> sLink, eLink;
5851    sLink.setCount(count);
5852    eLink.setCount(count);
5853    int rIndex, iIndex;
5854    for (rIndex = 0; rIndex < count; ++rIndex) {
5855        sLink[rIndex] = eLink[rIndex] = INT_MAX;
5856    }
5857    SkTDArray<double> distances;
5858    const int ends = count * 2; // all starts and ends
5859    const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2
5860    distances.setCount(entries);
5861    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
5862        outer = runs[rIndex >> 1];
5863        const Contour& oContour = contours[outer];
5864        const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
5865        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
5866                * ends - rIndex - 1;
5867        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
5868            int inner = runs[iIndex >> 1];
5869            const Contour& iContour = contours[inner];
5870            const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
5871            double dx = iPt.fX - oPt.fX;
5872            double dy = iPt.fY - oPt.fY;
5873            double dist = dx * dx + dy * dy;
5874            distances[row + iIndex] = dist; // oStart distance from iStart
5875        }
5876    }
5877    SkTDArray<int> sortedDist;
5878    sortedDist.setCount(entries);
5879    for (rIndex = 0; rIndex < entries; ++rIndex) {
5880        sortedDist[rIndex] = rIndex;
5881    }
5882    QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end() - 1, lessThan);
5883    int remaining = count; // number of start/end pairs
5884    for (rIndex = 0; rIndex < entries; ++rIndex) {
5885        int pair = sortedDist[rIndex];
5886        int row = pair / ends;
5887        int col = pair - row * ends;
5888        int thingOne = row < col ? row : ends - row - 2;
5889        int ndxOne = thingOne >> 1;
5890        bool endOne = thingOne & 1;
5891        int* linkOne = endOne ? eLink.begin() : sLink.begin();
5892        if (linkOne[ndxOne] != INT_MAX) {
5893            continue;
5894        }
5895        int thingTwo = row < col ? col : ends - row + col - 1;
5896        int ndxTwo = thingTwo >> 1;
5897        bool endTwo = thingTwo & 1;
5898        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
5899        if (linkTwo[ndxTwo] != INT_MAX) {
5900            continue;
5901        }
5902        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
5903        bool flip = endOne == endTwo;
5904        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
5905        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
5906        if (!--remaining) {
5907            break;
5908        }
5909    }
5910    SkASSERT(!remaining);
5911#if DEBUG_ASSEMBLE
5912    for (rIndex = 0; rIndex < count; ++rIndex) {
5913        int s = sLink[rIndex];
5914        int e = eLink[rIndex];
5915        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
5916                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
5917    }
5918#endif
5919    rIndex = 0;
5920    do {
5921        bool forward = true;
5922        bool first = true;
5923        int sIndex = sLink[rIndex];
5924        SkASSERT(sIndex != INT_MAX);
5925        sLink[rIndex] = INT_MAX;
5926        int eIndex;
5927        if (sIndex < 0) {
5928            eIndex = sLink[~sIndex];
5929            sLink[~sIndex] = INT_MAX;
5930        } else {
5931            eIndex = eLink[sIndex];
5932            eLink[sIndex] = INT_MAX;
5933        }
5934        SkASSERT(eIndex != INT_MAX);
5935#if DEBUG_ASSEMBLE
5936        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
5937                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
5938                    eIndex < 0 ? ~eIndex : eIndex);
5939#endif
5940        do {
5941            outer = runs[rIndex];
5942            const Contour& contour = contours[outer];
5943            if (first) {
5944                first = false;
5945                const SkPoint* startPtr = &contour.start();
5946                simple.deferredMove(startPtr[0]);
5947            }
5948            if (forward) {
5949                contour.toPartialForward(simple);
5950            } else {
5951                contour.toPartialBackward(simple);
5952            }
5953#if DEBUG_ASSEMBLE
5954            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
5955                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
5956                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
5957#endif
5958            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
5959                simple.close();
5960                break;
5961            }
5962            if (forward) {
5963                eIndex = eLink[rIndex];
5964                SkASSERT(eIndex != INT_MAX);
5965                eLink[rIndex] = INT_MAX;
5966                if (eIndex >= 0) {
5967                    SkASSERT(sLink[eIndex] == rIndex);
5968                    sLink[eIndex] = INT_MAX;
5969                } else {
5970                    SkASSERT(eLink[~eIndex] == ~rIndex);
5971                    eLink[~eIndex] = INT_MAX;
5972                }
5973            } else {
5974                eIndex = sLink[rIndex];
5975                SkASSERT(eIndex != INT_MAX);
5976                sLink[rIndex] = INT_MAX;
5977                if (eIndex >= 0) {
5978                    SkASSERT(eLink[eIndex] == rIndex);
5979                    eLink[eIndex] = INT_MAX;
5980                } else {
5981                    SkASSERT(sLink[~eIndex] == ~rIndex);
5982                    sLink[~eIndex] = INT_MAX;
5983                }
5984            }
5985            rIndex = eIndex;
5986            if (rIndex < 0) {
5987                forward ^= 1;
5988                rIndex = ~rIndex;
5989            }
5990        } while (true);
5991        for (rIndex = 0; rIndex < count; ++rIndex) {
5992            if (sLink[rIndex] != INT_MAX) {
5993                break;
5994            }
5995        }
5996    } while (rIndex < count);
5997#if DEBUG_ASSEMBLE
5998    for (rIndex = 0; rIndex < count; ++rIndex) {
5999       SkASSERT(sLink[rIndex] == INT_MAX);
6000       SkASSERT(eLink[rIndex] == INT_MAX);
6001    }
6002#endif
6003}
6004
6005void simplifyx(const SkPath& path, SkPath& result) {
6006    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
6007    result.reset();
6008    result.setFillType(SkPath::kEvenOdd_FillType);
6009    PathWrapper simple(result);
6010
6011    // turn path into list of segments
6012    SkTArray<Contour> contours;
6013    // FIXME: add self-intersecting cubics' T values to segment
6014    EdgeBuilder builder(path, contours);
6015    builder.finish();
6016    SkTDArray<Contour*> contourList;
6017    makeContourList(contours, contourList, false, false);
6018    Contour** currentPtr = contourList.begin();
6019    if (!currentPtr) {
6020        return;
6021    }
6022    Contour** listEnd = contourList.end();
6023    // find all intersections between segments
6024    do {
6025        Contour** nextPtr = currentPtr;
6026        Contour* current = *currentPtr++;
6027        Contour* next;
6028        do {
6029            next = *nextPtr++;
6030        } while (addIntersectTs(current, next) && nextPtr != listEnd);
6031    } while (currentPtr != listEnd);
6032    // eat through coincident edges
6033    coincidenceCheck(contourList, 0);
6034    fixOtherTIndex(contourList);
6035    sortSegments(contourList);
6036#if DEBUG_ACTIVE_SPANS
6037    debugShowActiveSpans(contourList);
6038#endif
6039    // construct closed contours
6040    if (builder.xorMask() == kWinding_Mask ? bridgeWinding(contourList, simple)
6041                : !bridgeXor(contourList, simple))
6042    { // if some edges could not be resolved, assemble remaining fragments
6043        SkPath temp;
6044        temp.setFillType(SkPath::kEvenOdd_FillType);
6045        PathWrapper assembled(temp);
6046        assemble(simple, assembled);
6047        result = *assembled.nativePath();
6048    }
6049}
6050
6051