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