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