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