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