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