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