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