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