Simplify.cpp revision e21cb18c52fe82de3412b10fc078799ac35ca94b
1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "Simplify.h"
8
9#undef SkASSERT
10#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
11
12// Terminology:
13// A Path contains one of more Contours
14// A Contour is made up of Segment array
15// A Segment is described by a Verb and a Point array with 2, 3, or 4 points
16// A Verb is one of Line, Quad(ratic), or Cubic
17// A Segment contains a Span array
18// A Span is describes a portion of a Segment using starting and ending T
19// T values range from 0 to 1, where 0 is the first Point in the Segment
20// An Edge is a Segment generated from a Span
21
22// FIXME: remove once debugging is complete
23#ifdef SK_DEBUG
24int gDebugMaxWindSum = SK_MaxS32;
25int gDebugMaxWindValue = SK_MaxS32;
26#endif
27
28#define DEBUG_UNUSED 0 // set to expose unused functions
29
30#if 0 // set to 1 for multiple thread -- no debugging
31
32const bool gRunTestsInOneThread = false;
33
34#define DEBUG_ACTIVE_SPANS 0
35#define DEBUG_ADD_INTERSECTING_TS 0
36#define DEBUG_ADD_T_PAIR 0
37#define DEBUG_CONCIDENT 0
38#define DEBUG_CROSS 0
39#define DEBUG_DUMP 0
40#define DEBUG_MARK_DONE 0
41#define DEBUG_PATH_CONSTRUCTION 0
42#define DEBUG_SORT 0
43#define DEBUG_WINDING 0
44
45#else
46
47const bool gRunTestsInOneThread = true;
48
49#define DEBUG_ACTIVE_SPANS 0
50#define DEBUG_ADD_INTERSECTING_TS 0
51#define DEBUG_ADD_T_PAIR 0
52#define DEBUG_CONCIDENT 0
53#define DEBUG_CROSS 1
54#define DEBUG_DUMP 1
55#define DEBUG_MARK_DONE 1
56#define DEBUG_PATH_CONSTRUCTION 1
57#define DEBUG_SORT 1
58#define DEBUG_WINDING 1
59
60#endif
61
62#if (DEBUG_ACTIVE_SPANS || DEBUG_CONCIDENT) && !DEBUG_DUMP
63#undef DEBUG_DUMP
64#define DEBUG_DUMP 1
65#endif
66
67#if DEBUG_DUMP
68static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
69// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
70static int gContourID;
71static int gSegmentID;
72#endif
73
74#ifndef DEBUG_TEST
75#define DEBUG_TEST 0
76#endif
77
78static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
79        Intersections& intersections) {
80    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
81    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
82    return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
83}
84
85static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
86        Intersections& intersections) {
87    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
88    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
89    intersect(aQuad, bLine, intersections);
90    return intersections.fUsed;
91}
92
93static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
94        Intersections& intersections) {
95    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
96            {a[3].fX, a[3].fY}};
97    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
98    return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
99}
100
101static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
102        Intersections& intersections) {
103    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
104    const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
105    intersect(aQuad, bQuad, intersections);
106    return intersections.fUsed;
107}
108
109static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
110        Intersections& intersections) {
111    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
112            {a[3].fX, a[3].fY}};
113    const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
114            {b[3].fX, b[3].fY}};
115    intersect(aCubic, bCubic, intersections);
116    return intersections.fUsed;
117}
118
119static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
120        SkScalar y, bool flipped, Intersections& intersections) {
121    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
122    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
123}
124
125static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
126        SkScalar y, bool flipped, Intersections& intersections) {
127    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
128    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
129}
130
131static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
132        SkScalar y, bool flipped, Intersections& intersections) {
133    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
134            {a[3].fX, a[3].fY}};
135    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
136}
137
138static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
139        SkScalar x, bool flipped, Intersections& intersections) {
140    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
141    return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
142}
143
144static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
145        SkScalar x, bool flipped, Intersections& intersections) {
146    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
147    return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
148}
149
150static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
151        SkScalar x, bool flipped, Intersections& intersections) {
152    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
153            {a[3].fX, a[3].fY}};
154    return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
155}
156
157static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
158        SkScalar , SkScalar , bool , Intersections& ) = {
159    NULL,
160    VLineIntersect,
161    VQuadIntersect,
162    VCubicIntersect
163};
164
165static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
166    const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
167    double x, y;
168    xy_at_t(line, t, x, y);
169    out->fX = SkDoubleToScalar(x);
170    out->fY = SkDoubleToScalar(y);
171}
172
173static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
174    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
175    double x, y;
176    xy_at_t(quad, t, x, y);
177    out->fX = SkDoubleToScalar(x);
178    out->fY = SkDoubleToScalar(y);
179}
180
181static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
182    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
183            {a[3].fX, a[3].fY}};
184    double x, y;
185    xy_at_t(cubic, t, x, y);
186    out->fX = SkDoubleToScalar(x);
187    out->fY = SkDoubleToScalar(y);
188}
189
190static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
191    NULL,
192    LineXYAtT,
193    QuadXYAtT,
194    CubicXYAtT
195};
196
197static SkScalar LineXAtT(const SkPoint a[2], double t) {
198    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
199    double x;
200    xy_at_t(aLine, t, x, *(double*) 0);
201    return SkDoubleToScalar(x);
202}
203
204static SkScalar QuadXAtT(const SkPoint a[3], double t) {
205    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
206    double x;
207    xy_at_t(quad, t, x, *(double*) 0);
208    return SkDoubleToScalar(x);
209}
210
211static SkScalar CubicXAtT(const SkPoint a[4], double t) {
212    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
213            {a[3].fX, a[3].fY}};
214    double x;
215    xy_at_t(cubic, t, x, *(double*) 0);
216    return SkDoubleToScalar(x);
217}
218
219static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
220    NULL,
221    LineXAtT,
222    QuadXAtT,
223    CubicXAtT
224};
225
226static SkScalar LineYAtT(const SkPoint a[2], double t) {
227    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
228    double y;
229    xy_at_t(aLine, t, *(double*) 0, y);
230    return SkDoubleToScalar(y);
231}
232
233static SkScalar QuadYAtT(const SkPoint a[3], double t) {
234    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
235    double y;
236    xy_at_t(quad, t, *(double*) 0, y);
237    return SkDoubleToScalar(y);
238}
239
240static SkScalar CubicYAtT(const SkPoint a[4], double t) {
241    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
242            {a[3].fX, a[3].fY}};
243    double y;
244    xy_at_t(cubic, t, *(double*) 0, y);
245    return SkDoubleToScalar(y);
246}
247
248static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
249    NULL,
250    LineYAtT,
251    QuadYAtT,
252    CubicYAtT
253};
254
255static SkScalar LineDXAtT(const SkPoint a[2], double ) {
256    return a[1].fX - a[0].fX;
257}
258
259static SkScalar QuadDXAtT(const SkPoint a[3], double t) {
260    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
261    double x;
262    dxdy_at_t(quad, t, x, *(double*) 0);
263    return SkDoubleToScalar(x);
264}
265
266static SkScalar CubicDXAtT(const SkPoint a[4], double t) {
267    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
268            {a[3].fX, a[3].fY}};
269    double x;
270    dxdy_at_t(cubic, t, x, *(double*) 0);
271    return SkDoubleToScalar(x);
272}
273
274static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
275    NULL,
276    LineDXAtT,
277    QuadDXAtT,
278    CubicDXAtT
279};
280
281static void LineSubDivide(const SkPoint a[2], double startT, double endT,
282        SkPoint sub[2]) {
283    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
284    _Line dst;
285    sub_divide(aLine, startT, endT, dst);
286    sub[0].fX = SkDoubleToScalar(dst[0].x);
287    sub[0].fY = SkDoubleToScalar(dst[0].y);
288    sub[1].fX = SkDoubleToScalar(dst[1].x);
289    sub[1].fY = SkDoubleToScalar(dst[1].y);
290}
291
292static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
293        SkPoint sub[3]) {
294    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
295            {a[2].fX, a[2].fY}};
296    Quadratic dst;
297    sub_divide(aQuad, startT, endT, dst);
298    sub[0].fX = SkDoubleToScalar(dst[0].x);
299    sub[0].fY = SkDoubleToScalar(dst[0].y);
300    sub[1].fX = SkDoubleToScalar(dst[1].x);
301    sub[1].fY = SkDoubleToScalar(dst[1].y);
302    sub[2].fX = SkDoubleToScalar(dst[2].x);
303    sub[2].fY = SkDoubleToScalar(dst[2].y);
304}
305
306static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
307        SkPoint sub[4]) {
308    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
309            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
310    Cubic dst;
311    sub_divide(aCubic, startT, endT, dst);
312    sub[0].fX = SkDoubleToScalar(dst[0].x);
313    sub[0].fY = SkDoubleToScalar(dst[0].y);
314    sub[1].fX = SkDoubleToScalar(dst[1].x);
315    sub[1].fY = SkDoubleToScalar(dst[1].y);
316    sub[2].fX = SkDoubleToScalar(dst[2].x);
317    sub[2].fY = SkDoubleToScalar(dst[2].y);
318    sub[3].fX = SkDoubleToScalar(dst[3].x);
319    sub[3].fY = SkDoubleToScalar(dst[3].y);
320}
321
322static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
323        SkPoint []) = {
324    NULL,
325    LineSubDivide,
326    QuadSubDivide,
327    CubicSubDivide
328};
329
330#if DEBUG_UNUSED
331static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
332        SkRect& bounds) {
333    SkPoint dst[3];
334    QuadSubDivide(a, startT, endT, dst);
335    bounds.fLeft = bounds.fRight = dst[0].fX;
336    bounds.fTop = bounds.fBottom = dst[0].fY;
337    for (int index = 1; index < 3; ++index) {
338        bounds.growToInclude(dst[index].fX, dst[index].fY);
339    }
340}
341
342static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
343        SkRect& bounds) {
344    SkPoint dst[4];
345    CubicSubDivide(a, startT, endT, dst);
346    bounds.fLeft = bounds.fRight = dst[0].fX;
347    bounds.fTop = bounds.fBottom = dst[0].fY;
348    for (int index = 1; index < 4; ++index) {
349        bounds.growToInclude(dst[index].fX, dst[index].fY);
350    }
351}
352#endif
353
354static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
355        SkTDArray<SkPoint>& reducePts) {
356    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
357            {a[2].fX, a[2].fY}};
358    Quadratic dst;
359    int order = reduceOrder(aQuad, dst);
360    if (order == 3) {
361        return SkPath::kQuad_Verb;
362    }
363    for (int index = 0; index < order; ++index) {
364        SkPoint* pt = reducePts.append();
365        pt->fX = SkDoubleToScalar(dst[index].x);
366        pt->fY = SkDoubleToScalar(dst[index].y);
367    }
368    return (SkPath::Verb) (order - 1);
369}
370
371static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
372        SkTDArray<SkPoint>& reducePts) {
373    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
374            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
375    Cubic dst;
376    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
377    if (order == 4) {
378        return SkPath::kCubic_Verb;
379    }
380    for (int index = 0; index < order; ++index) {
381        SkPoint* pt = reducePts.append();
382        pt->fX = SkDoubleToScalar(dst[index].x);
383        pt->fY = SkDoubleToScalar(dst[index].y);
384    }
385    return (SkPath::Verb) (order - 1);
386}
387
388static bool QuadIsLinear(const SkPoint a[3]) {
389    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
390            {a[2].fX, a[2].fY}};
391    return isLinear(aQuad, 0, 2);
392}
393
394static bool CubicIsLinear(const SkPoint a[4]) {
395    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
396            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
397    return isLinear(aCubic, 0, 3);
398}
399
400static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
401    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
402    double x[2];
403    xy_at_t(aLine, startT, x[0], *(double*) 0);
404    xy_at_t(aLine, endT, x[1], *(double*) 0);
405    return SkMinScalar((float) x[0], (float) x[1]);
406}
407
408static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
409    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
410            {a[2].fX, a[2].fY}};
411    return (float) leftMostT(aQuad, startT, endT);
412}
413
414static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
415    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
416            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
417    return (float) leftMostT(aCubic, startT, endT);
418}
419
420static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
421    NULL,
422    LineLeftMost,
423    QuadLeftMost,
424    CubicLeftMost
425};
426
427#if DEBUG_UNUSED
428static bool IsCoincident(const SkPoint a[2], const SkPoint& above,
429        const SkPoint& below) {
430    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
431    const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
432    return implicit_matches_ulps(aLine, bLine, 32);
433}
434#endif
435
436class Segment;
437
438// sorting angles
439// given angles of {dx dy ddx ddy dddx dddy} sort them
440class Angle {
441public:
442    // FIXME: this is bogus for quads and cubics
443    // if the quads and cubics' line from end pt to ctrl pt are coincident,
444    // there's no obvious way to determine the curve ordering from the
445    // derivatives alone. In particular, if one quadratic's coincident tangent
446    // is longer than the other curve, the final control point can place the
447    // longer curve on either side of the shorter one.
448    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
449    // may provide some help, but nothing has been figured out yet.
450    bool operator<(const Angle& rh) const {
451        if ((fDy < 0) ^ (rh.fDy < 0)) {
452            return fDy < 0;
453        }
454        if (fDy == 0 && rh.fDy == 0 && fDx != rh.fDx) {
455            return fDx < rh.fDx;
456        }
457        SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy;
458        if (cmp) {
459            return cmp < 0;
460        }
461        if ((fDDy < 0) ^ (rh.fDDy < 0)) {
462            return fDDy < 0;
463        }
464        if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) {
465            return fDDx < rh.fDDx;
466        }
467        cmp = fDDx * rh.fDDy - rh.fDDx * fDDy;
468        if (cmp) {
469            return cmp < 0;
470        }
471        if ((fDDDy < 0) ^ (rh.fDDDy < 0)) {
472            return fDDDy < 0;
473        }
474        if (fDDDy == 0 && rh.fDDDy == 0) {
475            return fDDDx < rh.fDDDx;
476        }
477        return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy;
478    }
479
480    double dx() const {
481        return fDx;
482    }
483
484    int end() const {
485        return fEnd;
486    }
487
488    bool isHorizontal() const {
489        return fDy == 0 && fDDy == 0 && fDDDy == 0;
490    }
491
492    // since all angles share a point, this needs to know which point
493    // is the common origin, i.e., whether the center is at pts[0] or pts[verb]
494    // practically, this should only be called by addAngle
495    void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment,
496            int start, int end) {
497        SkASSERT(start != end);
498        fSegment = segment;
499        fStart = start;
500        fEnd = end;
501        fDx = pts[1].fX - pts[0].fX; // b - a
502        fDy = pts[1].fY - pts[0].fY;
503        if (verb == SkPath::kLine_Verb) {
504            fDDx = fDDy = fDDDx = fDDDy = 0;
505            return;
506        }
507        fDDx = pts[2].fX - pts[1].fX - fDx; // a - 2b + c
508        fDDy = pts[2].fY - pts[1].fY - fDy;
509        if (verb == SkPath::kQuad_Verb) {
510            fDDDx = fDDDy = 0;
511            return;
512        }
513        fDDDx = pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX;
514        fDDDy = pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY;
515    }
516
517    // noncoincident quads/cubics may have the same initial angle
518    // as lines, so must sort by derivatives as well
519    // if flatness turns out to be a reasonable way to sort, use the below:
520    void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
521            int start, int end) {
522        fSegment = segment;
523        fStart = start;
524        fEnd = end;
525        fDx = pts[1].fX - pts[0].fX; // b - a
526        fDy = pts[1].fY - pts[0].fY;
527        if (verb == SkPath::kLine_Verb) {
528            fDDx = fDDy = fDDDx = fDDDy = 0;
529            return;
530        }
531        if (verb == SkPath::kQuad_Verb) {
532            int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx);
533            int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy);
534            int larger = std::max(abs(uplsX), abs(uplsY));
535            int shift = 0;
536            double flatT;
537            SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point)
538            LineParameters implicitLine;
539            _Line tangent = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}};
540            implicitLine.lineEndPoints(tangent);
541            implicitLine.normalize();
542            while (larger > UlpsEpsilon * 1024) {
543                larger >>= 2;
544                ++shift;
545                flatT = 0.5 / (1 << shift);
546                QuadXYAtT(pts, flatT, &ddPt);
547                _Point _pt = {ddPt.fX, ddPt.fY};
548                double distance = implicitLine.pointDistance(_pt);
549                if (approximately_zero(distance)) {
550                    SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance);
551                    break;
552                }
553            }
554            flatT = 0.5 / (1 << shift);
555            QuadXYAtT(pts, flatT, &ddPt);
556            fDDx = ddPt.fX - pts[0].fX;
557            fDDy = ddPt.fY - pts[0].fY;
558            SkASSERT(fDDx != 0 || fDDy != 0);
559            fDDDx = fDDDy = 0;
560            return;
561        }
562        SkASSERT(0); // FIXME: add cubic case
563    }
564
565    Segment* segment() const {
566        return const_cast<Segment*>(fSegment);
567    }
568
569    int sign() const {
570        return SkSign32(fStart - fEnd);
571    }
572
573    int start() const {
574        return fStart;
575    }
576
577private:
578    SkScalar fDx;
579    SkScalar fDy;
580    SkScalar fDDx;
581    SkScalar fDDy;
582    SkScalar fDDDx;
583    SkScalar fDDDy;
584    const Segment* fSegment;
585    int fStart;
586    int fEnd;
587};
588
589static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
590    int angleCount = angles.count();
591    int angleIndex;
592    angleList.setReserve(angleCount);
593    for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
594        *angleList.append() = &angles[angleIndex];
595    }
596    QSort<Angle>(angleList.begin(), angleList.end() - 1);
597}
598
599// Bounds, unlike Rect, does not consider a line to be empty.
600struct Bounds : public SkRect {
601    static bool Intersects(const Bounds& a, const Bounds& b) {
602        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
603                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
604    }
605
606    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
607        if (left < fLeft) {
608            fLeft = left;
609        }
610        if (top < fTop) {
611            fTop = top;
612        }
613        if (right > fRight) {
614            fRight = right;
615        }
616        if (bottom > fBottom) {
617            fBottom = bottom;
618        }
619    }
620
621    void add(const Bounds& toAdd) {
622        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
623    }
624
625    bool isEmpty() {
626        return fLeft > fRight || fTop > fBottom
627                || fLeft == fRight && fTop == fBottom
628                || isnan(fLeft) || isnan(fRight)
629                || isnan(fTop) || isnan(fBottom);
630    }
631
632    void setCubicBounds(const SkPoint a[4]) {
633        _Rect dRect;
634        Cubic cubic  = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
635            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
636        dRect.setBounds(cubic);
637        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
638                (float) dRect.bottom);
639    }
640
641    void setQuadBounds(const SkPoint a[3]) {
642        const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
643                {a[2].fX, a[2].fY}};
644        _Rect dRect;
645        dRect.setBounds(quad);
646        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
647                (float) dRect.bottom);
648    }
649};
650
651struct Span {
652    Segment* fOther;
653    mutable SkPoint const* fPt; // lazily computed as needed
654    double fT;
655    double fOtherT; // value at fOther[fOtherIndex].fT
656    int fOtherIndex;  // can't be used during intersection
657    int fWindSum; // accumulated from contours surrounding this one
658    int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
659    bool fDone; // if set, this span to next higher T has been processed
660};
661
662class Segment {
663public:
664    Segment() {
665#if DEBUG_DUMP
666        fID = ++gSegmentID;
667#endif
668    }
669
670    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const {
671        if (activeAngleInner(index, done, angles)) {
672            return true;
673        }
674        double referenceT = fTs[index].fT;
675        int lesser = index;
676        while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
677            if (activeAngleOther(lesser, done, angles)) {
678                return true;
679            }
680        }
681        do {
682            if (activeAngleOther(index, done, angles)) {
683                return true;
684            }
685        } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
686        return false;
687    }
688
689    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const {
690        Span* span = &fTs[index];
691        Segment* other = span->fOther;
692        int oIndex = span->fOtherIndex;
693        return other->activeAngleInner(oIndex, done, angles);
694    }
695
696    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const {
697        int next = nextSpan(index, 1);
698        if (next > 0) {
699            const Span& upSpan = fTs[index];
700            if (upSpan.fWindValue) {
701                addAngle(angles, index, next);
702                if (upSpan.fDone) {
703                    done++;
704                } else if (upSpan.fWindSum != SK_MinS32) {
705                    return true;
706                }
707            }
708        }
709        int prev = nextSpan(index, -1);
710        // edge leading into junction
711        if (prev >= 0) {
712            const Span& downSpan = fTs[prev];
713            if (downSpan.fWindValue) {
714                addAngle(angles, index, prev);
715                if (downSpan.fDone) {
716                    done++;
717                 } else if (downSpan.fWindSum != SK_MinS32) {
718                    return true;
719                }
720            }
721        }
722        return false;
723    }
724
725    SkScalar activeTop() const {
726        SkASSERT(!done());
727        int count = fTs.count();
728        SkScalar result = SK_ScalarMax;
729        bool lastDone = true;
730        for (int index = 0; index < count; ++index) {
731            bool done = fTs[index].fDone;
732            if (!done || !lastDone) {
733                SkScalar y = yAtT(index);
734                if (result > y) {
735                    result = y;
736                }
737            }
738            lastDone = done;
739        }
740        SkASSERT(result < SK_ScalarMax);
741        return result;
742    }
743
744    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
745        SkASSERT(start != end);
746        SkPoint edge[4];
747        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
748        Angle* angle = angles.append();
749        angle->set(edge, fVerb, this, start, end);
750    }
751
752    void addCubic(const SkPoint pts[4]) {
753        init(pts, SkPath::kCubic_Verb);
754        fBounds.setCubicBounds(pts);
755    }
756
757    // FIXME: this needs to defer add for aligned consecutive line segments
758    SkPoint addCurveTo(int start, int end, SkPath& path, bool active) {
759        SkPoint edge[4];
760        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
761        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
762        if (active) {
763    #if DEBUG_PATH_CONSTRUCTION
764            SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
765                    kLVerbStr[fVerb], edge[1].fX, edge[1].fY);
766            if (fVerb > 1) {
767                SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY);
768            }
769            if (fVerb > 2) {
770                SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY);
771            }
772            SkDebugf("\n");
773    #endif
774            switch (fVerb) {
775                case SkPath::kLine_Verb:
776                    path.lineTo(edge[1].fX, edge[1].fY);
777                    break;
778                case SkPath::kQuad_Verb:
779                    path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY);
780                    break;
781                case SkPath::kCubic_Verb:
782                    path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY,
783                            edge[3].fX, edge[3].fY);
784                    break;
785            }
786        }
787        return edge[fVerb];
788    }
789
790    void addLine(const SkPoint pts[2]) {
791        init(pts, SkPath::kLine_Verb);
792        fBounds.set(pts, 2);
793    }
794
795    const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) {
796        const SkPoint& pt = xyAtT(tIndex);
797        if (active) {
798    #if DEBUG_PATH_CONSTRUCTION
799            SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
800    #endif
801            path.moveTo(pt.fX, pt.fY);
802        }
803        return pt;
804    }
805
806    // add 2 to edge or out of range values to get T extremes
807    void addOtherT(int index, double otherT, int otherIndex) {
808        Span& span = fTs[index];
809        span.fOtherT = otherT;
810        span.fOtherIndex = otherIndex;
811    }
812
813    void addQuad(const SkPoint pts[3]) {
814        init(pts, SkPath::kQuad_Verb);
815        fBounds.setQuadBounds(pts);
816    }
817
818    // Defer all coincident edge processing until
819    // after normal intersections have been computed
820
821// no need to be tricky; insert in normal T order
822// resolve overlapping ts when considering coincidence later
823
824    // add non-coincident intersection. Resulting edges are sorted in T.
825    int addT(double newT, Segment* other) {
826        // FIXME: in the pathological case where there is a ton of intercepts,
827        //  binary search?
828        int insertedAt = -1;
829        size_t tCount = fTs.count();
830        for (size_t index = 0; index < tCount; ++index) {
831            // OPTIMIZATION: if there are three or more identical Ts, then
832            // the fourth and following could be further insertion-sorted so
833            // that all the edges are clockwise or counterclockwise.
834            // This could later limit segment tests to the two adjacent
835            // neighbors, although it doesn't help with determining which
836            // circular direction to go in.
837            if (newT < fTs[index].fT) {
838                insertedAt = index;
839                break;
840            }
841        }
842        Span* span;
843        if (insertedAt >= 0) {
844            span = fTs.insert(insertedAt);
845        } else {
846            insertedAt = tCount;
847            span = fTs.append();
848        }
849        span->fT = newT;
850        span->fOther = other;
851        span->fPt = NULL;
852        span->fWindSum = SK_MinS32;
853        span->fWindValue = 1;
854        if ((span->fDone = newT == 1)) {
855            ++fDoneSpans;
856        }
857        return insertedAt;
858    }
859
860    // set spans from start to end to decrement by one
861    // note this walks other backwards
862    // FIMXE: there's probably an edge case that can be constructed where
863    // two span in one segment are separated by float epsilon on one span but
864    // not the other, if one segment is very small. For this
865    // case the counts asserted below may or may not be enough to separate the
866    // spans. Even if the counts work out, what if the spanw aren't correctly
867    // sorted? It feels better in such a case to match the span's other span
868    // pointer since both coincident segments must contain the same spans.
869    void addTCancel(double startT, double endT, Segment& other,
870            double oStartT, double oEndT) {
871        SkASSERT(endT - startT >= FLT_EPSILON);
872        SkASSERT(oEndT - oStartT >= FLT_EPSILON);
873        int index = 0;
874        while (startT - fTs[index].fT >= FLT_EPSILON) {
875            ++index;
876        }
877        int oIndex = other.fTs.count();
878        while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON)
879            ;
880        Span* test = &fTs[index];
881        Span* oTest = &other.fTs[oIndex];
882        do {
883            bool decrement = test->fWindValue && oTest->fWindValue;
884            Span* end = test;
885            do {
886                if (decrement) {
887                    SkASSERT(end->fWindValue > 0);
888                    if (--(end->fWindValue) == 0) {
889                        end->fDone = true;
890                        ++fDoneSpans;
891                    }
892                }
893                end = &fTs[++index];
894            } while (end->fT - test->fT < FLT_EPSILON);
895            Span* oTestStart = oTest;
896            do {
897                if (decrement) {
898                    SkASSERT(oTestStart->fWindValue > 0);
899                    if (--(oTestStart->fWindValue) == 0) {
900                        oTestStart->fDone = true;
901                        ++other.fDoneSpans;
902                    }
903                }
904                if (!oIndex) {
905                    break;
906                }
907                oTestStart = &other.fTs[--oIndex];
908            } while (oTest->fT - oTestStart->fT < FLT_EPSILON);
909            test = end;
910            oTest = oTestStart;
911        } while (test->fT < endT - FLT_EPSILON);
912        SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON);
913    }
914
915    // set spans from start to end to increment the greater by one and decrement
916    // the lesser
917    void addTCoincident(double startT, double endT, Segment& other,
918            double oStartT, double oEndT) {
919        SkASSERT(endT - startT >= FLT_EPSILON);
920        SkASSERT(oEndT - oStartT >= FLT_EPSILON);
921        int index = 0;
922        while (startT - fTs[index].fT >= FLT_EPSILON) {
923            ++index;
924        }
925        int oIndex = 0;
926        while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) {
927            ++oIndex;
928        }
929        Span* test = &fTs[index];
930        Span* oTest = &other.fTs[oIndex];
931        SkTDArray<double> outsideTs;
932        SkTDArray<double> oOutsideTs;
933        do {
934            bool transfer = test->fWindValue && oTest->fWindValue;
935            bool decrementOther = test->fWindValue >= oTest->fWindValue;
936            Span* end = test;
937            double startT = end->fT;
938            double oStartT = oTest->fT;
939            do {
940                if (transfer) {
941                    if (decrementOther) {
942                        SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue);
943                        ++(end->fWindValue);
944                    } else {
945                        SkASSERT(end->fWindValue > 0);
946                        if (--(end->fWindValue) == 0) {
947                            end->fDone = true;
948                            ++fDoneSpans;
949                            int outCount = outsideTs.count();
950                            if (outCount == 0 || end->fT - outsideTs[outCount - 2]
951                                    >= FLT_EPSILON) {
952                                *outsideTs.append() = end->fT;
953                                *outsideTs.append() = oStartT;
954                            }
955                        }
956                    }
957                }
958                end = &fTs[++index];
959            } while (end->fT - test->fT < FLT_EPSILON);
960            Span* oEnd = oTest;
961            do {
962                if (transfer) {
963                    if (decrementOther) {
964                        SkASSERT(oEnd->fWindValue > 0);
965                        if (--(oEnd->fWindValue) == 0) {
966                            oEnd->fDone = true;
967                            ++other.fDoneSpans;
968                            int oOutCount = oOutsideTs.count();
969                            if (oOutCount == 0 || oEnd->fT
970                                    - oOutsideTs[oOutCount - 2] >= FLT_EPSILON) {
971                                *oOutsideTs.append() = oEnd->fT;
972                                *oOutsideTs.append() = startT;
973                            }
974                        }
975                    } else {
976                        SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
977                        ++(oEnd->fWindValue);
978                    }
979                }
980                oEnd = &other.fTs[++oIndex];
981            } while (oEnd->fT - oTest->fT < FLT_EPSILON);
982            test = end;
983            oTest = oEnd;
984        } while (test->fT < endT - FLT_EPSILON);
985        SkASSERT(oTest->fT < oEndT + FLT_EPSILON);
986        SkASSERT(oTest->fT > oEndT - FLT_EPSILON);
987        if (!done() && outsideTs.count()) {
988            addTOutsides(outsideTs, other, oEndT);
989        }
990        if (!other.done() && oOutsideTs.count()) {
991            other.addTOutsides(oOutsideTs, *this, endT);
992        }
993    }
994
995    void addTOutsides(const SkTDArray<double>& outsideTs, Segment& other,
996            double oEnd) {
997        // walk this to outsideTs[0]
998        // walk other to outsideTs[1]
999        // if either is > 0, add a pointer to the other, copying adjacent winding
1000        int tIndex = -1;
1001        int tCount = fTs.count();
1002        int oIndex = -1;
1003        int oCount = other.fTs.count();
1004        double tStart = outsideTs[0];
1005        double oStart = outsideTs[1];
1006        Span* tSpan;
1007        Span* oSpan;
1008        do {
1009            tSpan = &fTs[++tIndex];
1010            if (tStart - tSpan->fT < FLT_EPSILON) {
1011                break;
1012            }
1013        } while (tIndex < tCount);
1014        do {
1015            oSpan = &other.fTs[++oIndex];
1016            if (oStart - oSpan->fT < FLT_EPSILON) {
1017                break;
1018            }
1019        } while (oIndex < oCount);
1020        if (tIndex > 0 || oIndex > 0) {
1021            addTPair(tStart, other, oStart);
1022            // note: counts for fT, other.fT are one greater
1023        } else {
1024            --tCount;
1025            --oCount;
1026        }
1027        tStart = fTs[tIndex].fT;
1028        oStart = other.fTs[oIndex].fT;
1029        do {
1030            do {
1031                tSpan = &fTs[++tIndex];
1032            } while (tSpan->fT - tStart < FLT_EPSILON && tIndex < tCount);
1033            tStart = fTs[tIndex].fT;
1034            do {
1035                oSpan = &other.fTs[++oIndex];
1036            } while (oSpan->fT - oStart < FLT_EPSILON && oIndex < oCount);
1037            oStart = other.fTs[oIndex].fT;
1038            if (tStart == 1 && oStart == 1) {
1039                break;
1040            }
1041            addTPair(tStart, other, oStart);
1042            ++tCount;
1043            ++oCount;
1044        } while (tStart < 1 && oStart < 1 && oEnd - oSpan->fT >= FLT_EPSILON);
1045    }
1046
1047    void addTPair(double t, Segment& other, double otherT) {
1048#if DEBUG_ADD_T_PAIR
1049        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1050                __FUNCTION__, fID, t, other.fID, otherT);
1051#endif
1052        int insertedAt = addT(t, &other);
1053        int otherInsertedAt = other.addT(otherT, this);
1054        addOtherT(insertedAt, otherT, otherInsertedAt);
1055        other.addOtherT(otherInsertedAt, t, insertedAt);
1056        Span& newSpan = fTs[insertedAt];
1057        if (insertedAt > 0) {
1058            const Span& lastSpan = fTs[insertedAt - 1];
1059            if (t - lastSpan.fT < FLT_EPSILON) {
1060                int tWind = lastSpan.fWindValue;
1061                newSpan.fWindValue = tWind;
1062                if (!tWind) {
1063                    newSpan.fDone = true;
1064                    ++fDoneSpans;
1065                }
1066            }
1067        }
1068        int oIndex = newSpan.fOtherIndex;
1069        if (oIndex > 0) {
1070            const Span& lastOther = other.fTs[oIndex - 1];
1071            if (otherT - lastOther.fT < FLT_EPSILON) {
1072                int oWind = lastOther.fWindValue;
1073                Span& otherSpan = other.fTs[oIndex];
1074                otherSpan.fWindValue = oWind;
1075                if (!oWind) {
1076                    otherSpan.fDone = true;
1077                    ++(other.fDoneSpans);
1078                }
1079            }
1080        }
1081    }
1082
1083    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
1084        // add edge leading into junction
1085        if (fTs[SkMin32(end, start)].fWindValue > 0) {
1086            addAngle(angles, end, start);
1087        }
1088        // add edge leading away from junction
1089        int step = SkSign32(end - start);
1090        int tIndex = nextSpan(end, step);
1091        if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) {
1092            addAngle(angles, end, tIndex);
1093        }
1094    }
1095
1096    const Bounds& bounds() const {
1097        return fBounds;
1098    }
1099
1100    void buildAngles(int index, SkTDArray<Angle>& angles) const {
1101        double referenceT = fTs[index].fT;
1102        int lesser = index;
1103        while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
1104            buildAnglesInner(lesser, angles);
1105        }
1106        do {
1107            buildAnglesInner(index, angles);
1108        } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
1109    }
1110
1111    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
1112        Span* span = &fTs[index];
1113        Segment* other = span->fOther;
1114    // if there is only one live crossing, and no coincidence, continue
1115    // in the same direction
1116    // if there is coincidence, the only choice may be to reverse direction
1117        // find edge on either side of intersection
1118        int oIndex = span->fOtherIndex;
1119        // if done == -1, prior span has already been processed
1120        int step = 1;
1121        int next = other->nextSpan(oIndex, step);
1122        if (next < 0) {
1123            step = -step;
1124            next = other->nextSpan(oIndex, step);
1125        }
1126        // add candidate into and away from junction
1127        other->addTwoAngles(next, oIndex, angles);
1128    }
1129
1130    bool cancels(const Segment& other) const {
1131        SkASSERT(fVerb == SkPath::kLine_Verb);
1132        SkASSERT(other.fVerb == SkPath::kLine_Verb);
1133        SkPoint dxy = fPts[0] - fPts[1];
1134        SkPoint odxy = other.fPts[0] - other.fPts[1];
1135        return dxy.fX * odxy.fX < 0 || dxy.fY * odxy.fY < 0;
1136    }
1137
1138    // figure out if the segment's ascending T goes clockwise or not
1139    // not enough context to write this as shown
1140    // instead, add all segments meeting at the top
1141    // sort them using buildAngleList
1142    // find the first in the sort
1143    // see if ascendingT goes to top
1144    bool clockwise(int /* tIndex */) const {
1145        SkASSERT(0); // incomplete
1146        return false;
1147    }
1148
1149    int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const {
1150        int bestT = -1;
1151        SkScalar top = bounds().fTop;
1152        SkScalar bottom = bounds().fBottom;
1153        int end = 0;
1154        do {
1155            int start = end;
1156            end = nextSpan(start, 1);
1157            if (fTs[start].fWindValue == 0) {
1158                continue;
1159            }
1160            SkPoint edge[4];
1161            // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can
1162            // work with the original data directly
1163            (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
1164            // intersect ray starting at basePt with edge
1165            Intersections intersections;
1166            int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
1167                    false, intersections);
1168            if (pts == 0) {
1169                continue;
1170            }
1171            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1172            // if the intersection is edge on, wait for another one
1173                continue;
1174            }
1175            SkASSERT(pts == 1); // FIXME: more code required to disambiguate
1176            SkPoint pt;
1177            double foundT = intersections.fT[0][0];
1178            (*SegmentXYAtT[fVerb])(fPts, foundT, &pt);
1179            if (bestY < pt.fY) {
1180                bestY = pt.fY;
1181                bestT = foundT < 1 ? start : end;
1182                hitT = fTs[start].fT + (fTs[end].fT - fTs[start].fT) * foundT;
1183            }
1184        } while (fTs[end].fT != 1);
1185        return bestT;
1186    }
1187
1188    bool done() const {
1189        SkASSERT(fDoneSpans <= fTs.count());
1190        return fDoneSpans == fTs.count();
1191    }
1192
1193    bool done(const Angle& angle) const {
1194        int start = angle.start();
1195        int end = angle.end();
1196        const Span& mSpan = fTs[SkMin32(start, end)];
1197        return mSpan.fDone;
1198    }
1199
1200    // so the span needs to contain the pairing info found here
1201    // this should include the winding computed for the edge, and
1202    //  what edge it connects to, and whether it is discarded
1203    //  (maybe discarded == abs(winding) > 1) ?
1204    // only need derivatives for duration of sorting, add a new struct
1205    // for pairings, remove extra spans that have zero length and
1206    //  reference an unused other
1207    // for coincident, the last span on the other may be marked done
1208    //  (always?)
1209
1210    // if loop is exhausted, contour may be closed.
1211    // FIXME: pass in close point so we can check for closure
1212
1213    // given a segment, and a sense of where 'inside' is, return the next
1214    // segment. If this segment has an intersection, or ends in multiple
1215    // segments, find the mate that continues the outside.
1216    // note that if there are multiples, but no coincidence, we can limit
1217    // choices to connections in the correct direction
1218
1219    // mark found segments as done
1220
1221    // start is the index of the beginning T of this edge
1222    // it is guaranteed to have an end which describes a non-zero length (?)
1223    // winding -1 means ccw, 1 means cw
1224    // firstFind allows coincident edges to be treated differently
1225    Segment* findNext(SkTDArray<Span*>& chase, int winding,
1226            int contourWinding, int spanWinding,
1227            const int startIndex, const int endIndex, int& nextStart,
1228            int& nextEnd, int& flipped, bool firstFind, bool active) {
1229        int sumWinding = winding + spanWinding;
1230        if (sumWinding == 0) {
1231            sumWinding = spanWinding;
1232        }
1233    #if DEBUG_WINDING
1234        SkDebugf("%s winding=%d contourWinding=%d spanWinding=%d sumWinding=%d\n",
1235                __FUNCTION__, winding, contourWinding, spanWinding, sumWinding);
1236    #endif
1237        SkASSERT(startIndex != endIndex);
1238        int count = fTs.count();
1239        SkASSERT(startIndex < endIndex ? startIndex < count - 1
1240                : startIndex > 0);
1241        int step = SkSign32(endIndex - startIndex);
1242        int end = nextSpan(startIndex, step);
1243        SkASSERT(end >= 0);
1244        Span* endSpan = &fTs[end];
1245        Segment* other;
1246        if (isSimple(end)) {
1247        // mark the smaller of startIndex, endIndex done, and all adjacent
1248        // spans with the same T value (but not 'other' spans)
1249            markDone(SkMin32(startIndex, endIndex), sumWinding);
1250            other = endSpan->fOther;
1251            nextStart = endSpan->fOtherIndex;
1252            nextEnd = nextStart + step;
1253            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
1254            return other;
1255        }
1256        // more than one viable candidate -- measure angles to find best
1257        SkTDArray<Angle> angles;
1258        SkASSERT(startIndex - endIndex != 0);
1259        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1260        addTwoAngles(startIndex, end, angles);
1261        buildAngles(end, angles);
1262        SkTDArray<Angle*> sorted;
1263        sortAngles(angles, sorted);
1264        int angleCount = angles.count();
1265        int firstIndex = findStartingEdge(sorted, startIndex, end);
1266        SkASSERT(firstIndex >= 0);
1267    #if DEBUG_SORT
1268        debugShowSort(sorted, firstIndex, contourWinding, sumWinding);
1269    #endif
1270    #if DEBUG_WINDING
1271        SkDebugf("%s sumWinding=%d sign=%d (%srewind)\n", __FUNCTION__,
1272                sumWinding, sorted[firstIndex]->sign(),
1273                sorted[firstIndex]->sign() * sumWinding > 0 ? "" : "no ");
1274    #endif
1275        bool innerSwap = false;
1276        int startWinding = sumWinding;
1277   //     SkASSERT(SkSign32(sumWinding) == SkSign32(winding) || winding == 0);
1278        if (sorted[firstIndex]->sign() * sumWinding > 0) {
1279            int prior = rewind(sorted[firstIndex]);
1280            SkDebugf("%s prior=%d\n", __FUNCTION__, prior);
1281            if (0 && winding && contourWinding) {
1282                sumWinding += prior;
1283            } else {
1284                sumWinding -= prior;
1285            }
1286            if (active) {
1287                innerSwap = true;
1288            }
1289        }
1290        int nextIndex = firstIndex + 1;
1291        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1292        const Angle* foundAngle = NULL;
1293        bool foundDone = false;
1294        // iterate through the angle, and compute everyone's winding
1295        bool firstEdge = true;
1296        do {
1297            if (nextIndex == angleCount) {
1298                nextIndex = 0;
1299            }
1300            const Angle* nextAngle = sorted[nextIndex];
1301            int maxWinding = sumWinding;
1302            Segment* nextSegment = nextAngle->segment();
1303            int windValue = nextSegment->windValue(nextAngle);
1304            SkASSERT(windValue > 0);
1305            sumWinding -= nextAngle->sign() * windValue;
1306            SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
1307    #if DEBUG_WINDING
1308            SkDebugf("%s maxWinding=%d sumWinding=%d sign=%d\n", __FUNCTION__,
1309                    maxWinding, sumWinding, nextAngle->sign());
1310    #endif
1311            if (maxWinding * sumWinding < 0) {
1312                flipped = -flipped;
1313    #if DEBUG_WINDING
1314                SkDebugf("flipped sign %d %d\n", maxWinding, sumWinding);
1315    #endif
1316            }
1317            firstEdge = false;
1318            if (!sumWinding) {
1319                if (!active) {
1320                    markDone(SkMin32(startIndex, endIndex), startWinding);
1321                    nextSegment->markWinding(SkMin32(nextAngle->start(),
1322                                nextAngle->end()), maxWinding);
1323    #if DEBUG_WINDING
1324                    SkDebugf("%s inactive\n", __FUNCTION__);
1325    #endif
1326                    return NULL;
1327                }
1328                if (!foundAngle || foundDone) {
1329                    foundAngle = nextAngle;
1330                    foundDone = nextSegment->done(*nextAngle);
1331                    if (flipped > 0 && maxWinding * startWinding < 0) {
1332                        flipped = -flipped;
1333            #if DEBUG_WINDING
1334                        SkDebugf("flopped sign %d %d\n", maxWinding, startWinding);
1335            #endif
1336                    }
1337                }
1338                continue;
1339            }
1340            if (!maxWinding && innerSwap && !foundAngle) {
1341                foundAngle = nextAngle;
1342            }
1343            if (nextSegment->done()) {
1344                continue;
1345            }
1346            // if the winding is non-zero, nextAngle does not connect to
1347            // current chain. If we haven't done so already, mark the angle
1348            // as done, record the winding value, and mark connected unambiguous
1349            // segments as well.
1350            if (nextSegment->windSum(nextAngle) == SK_MinS32) {
1351                if (abs(maxWinding) < abs(sumWinding)) {
1352                    maxWinding = sumWinding;
1353                }
1354                Span* last;
1355                if (foundAngle || innerSwap) {
1356                    last = nextSegment->markAndChaseWinding(nextAngle, maxWinding);
1357                } else {
1358                    last = nextSegment->markAndChaseDone(nextAngle, maxWinding);
1359                }
1360                if (last) {
1361                    *chase.append() = last;
1362                }
1363            }
1364        } while (++nextIndex != lastIndex);
1365        SkASSERT(sorted[firstIndex]->segment() == this);
1366        markDone(SkMin32(startIndex, endIndex), startWinding);
1367        if (!foundAngle) {
1368            return NULL;
1369        }
1370        nextStart = foundAngle->start();
1371        nextEnd = foundAngle->end();
1372        return foundAngle->segment();
1373    }
1374
1375    int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
1376        int angleCount = sorted.count();
1377        int firstIndex = -1;
1378        for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1379            const Angle* angle = sorted[angleIndex];
1380            if (angle->segment() == this && angle->start() == end &&
1381                    angle->end() == start) {
1382                firstIndex = angleIndex;
1383                break;
1384            }
1385        }
1386        return firstIndex;
1387    }
1388
1389    // FIXME: this is tricky code; needs its own unit test
1390    void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered
1391        int count = fTs.count();
1392        if (count < 3) { // require t=0, x, 1 at minimum
1393            return;
1394        }
1395        int matchIndex = 0;
1396        int moCount;
1397        Span* match;
1398        Segment* mOther;
1399        do {
1400            match = &fTs[matchIndex];
1401            mOther = match->fOther;
1402            moCount = mOther->fTs.count();
1403            if (moCount >= 3) {
1404                break;
1405            }
1406            if (++matchIndex >= count) {
1407                return;
1408            }
1409        } while (true); // require t=0, x, 1 at minimum
1410        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
1411        const SkPoint* matchPt = &xyAtT(match);
1412        // look for a pair of nearby T values that map to the same (x,y) value
1413        // if found, see if the pair of other segments share a common point. If
1414        // so, the span from here to there is coincident.
1415        for (int index = matchIndex + 1; index < count; ++index) {
1416            Span* test = &fTs[index];
1417            if (test->fDone) {
1418                continue;
1419            }
1420            Segment* tOther = test->fOther;
1421            int toCount = tOther->fTs.count();
1422            if (toCount < 3) { // require t=0, x, 1 at minimum
1423                continue;
1424            }
1425            const SkPoint* testPt = &xyAtT(test);
1426            if (*matchPt != *testPt) {
1427                matchIndex = index;
1428                moCount = toCount;
1429                match = test;
1430                mOther = tOther;
1431                matchPt = testPt;
1432                continue;
1433            }
1434            int moStart = -1;
1435            int moEnd = -1;
1436            double moStartT, moEndT;
1437            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
1438                Span& moSpan = mOther->fTs[moIndex];
1439                if (moSpan.fDone) {
1440                    continue;
1441                }
1442                if (moSpan.fOther == this) {
1443                    if (moSpan.fOtherT == match->fT) {
1444                        moStart = moIndex;
1445                        moStartT = moSpan.fT;
1446                    }
1447                    continue;
1448                }
1449                if (moSpan.fOther == tOther) {
1450                    SkASSERT(moEnd == -1);
1451                    moEnd = moIndex;
1452                    moEndT = moSpan.fT;
1453                }
1454            }
1455            if (moStart < 0 || moEnd < 0) {
1456                continue;
1457            }
1458            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
1459            if (moStartT == moEndT) {
1460                continue;
1461            }
1462            int toStart = -1;
1463            int toEnd = -1;
1464            double toStartT, toEndT;
1465            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
1466                Span& toSpan = tOther->fTs[toIndex];
1467                if (toSpan.fOther == this) {
1468                    if (toSpan.fOtherT == test->fT) {
1469                        toStart = toIndex;
1470                        toStartT = toSpan.fT;
1471                    }
1472                    continue;
1473                }
1474                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
1475                    SkASSERT(toEnd == -1);
1476                    toEnd = toIndex;
1477                    toEndT = toSpan.fT;
1478                }
1479            }
1480            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
1481            if (toStart <= 0 || toEnd <= 0) {
1482                continue;
1483            }
1484            if (toStartT == toEndT) {
1485                continue;
1486            }
1487            // test to see if the segment between there and here is linear
1488            if (!mOther->isLinear(moStart, moEnd)
1489                    || !tOther->isLinear(toStart, toEnd)) {
1490                continue;
1491            }
1492            // FIXME: defer implementation until the rest works
1493            // this may share code with regular coincident detection
1494            SkASSERT(0);
1495        #if 0
1496            if (flipped) {
1497                mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd);
1498            } else {
1499                mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd);
1500            }
1501        #endif
1502        }
1503    }
1504
1505    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
1506    // and use more concise logic like the old edge walker code?
1507    // FIXME: this needs to deal with coincident edges
1508    Segment* findTop(int& tIndex, int& endIndex) {
1509        // iterate through T intersections and return topmost
1510        // topmost tangent from y-min to first pt is closer to horizontal
1511        SkASSERT(!done());
1512        int firstT;
1513        int lastT;
1514        SkPoint topPt;
1515        topPt.fY = SK_ScalarMax;
1516        int count = fTs.count();
1517        // see if either end is not done since we want smaller Y of the pair
1518        bool lastDone = true;
1519        for (int index = 0; index < count; ++index) {
1520            const Span& span = fTs[index];
1521            if (!span.fDone || !lastDone) {
1522                const SkPoint& intercept = xyAtT(&span);
1523                if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
1524                        && topPt.fX > intercept.fX)) {
1525                    topPt = intercept;
1526                    firstT = lastT = index;
1527                } else if (topPt == intercept) {
1528                    lastT = index;
1529                }
1530            }
1531            lastDone = span.fDone;
1532        }
1533        // sort the edges to find the leftmost
1534        int step = 1;
1535        int end = nextSpan(firstT, step);
1536        if (end == -1) {
1537            step = -1;
1538            end = nextSpan(firstT, step);
1539            SkASSERT(end != -1);
1540        }
1541        // if the topmost T is not on end, or is three-way or more, find left
1542        // look for left-ness from tLeft to firstT (matching y of other)
1543        SkTDArray<Angle> angles;
1544        SkASSERT(firstT - end != 0);
1545        addTwoAngles(end, firstT, angles);
1546        buildAngles(firstT, angles);
1547        SkTDArray<Angle*> sorted;
1548        sortAngles(angles, sorted);
1549        // skip edges that have already been processed
1550        firstT = -1;
1551        Segment* leftSegment;
1552        do {
1553            const Angle* angle = sorted[++firstT];
1554            leftSegment = angle->segment();
1555            tIndex = angle->end();
1556            endIndex = angle->start();
1557        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
1558        return leftSegment;
1559    }
1560
1561    // FIXME: not crazy about this
1562    // when the intersections are performed, the other index is into an
1563    // incomplete array. as the array grows, the indices become incorrect
1564    // while the following fixes the indices up again, it isn't smart about
1565    // skipping segments whose indices are already correct
1566    // assuming we leave the code that wrote the index in the first place
1567    void fixOtherTIndex() {
1568        int iCount = fTs.count();
1569        for (int i = 0; i < iCount; ++i) {
1570            Span& iSpan = fTs[i];
1571            double oT = iSpan.fOtherT;
1572            Segment* other = iSpan.fOther;
1573            int oCount = other->fTs.count();
1574            for (int o = 0; o < oCount; ++o) {
1575                Span& oSpan = other->fTs[o];
1576                if (oT == oSpan.fT && this == oSpan.fOther) {
1577                    iSpan.fOtherIndex = o;
1578                    break;
1579                }
1580            }
1581        }
1582    }
1583
1584    // OPTIMIZATION: uses tail recursion. Unwise?
1585    Span* innerChaseDone(int index, int step, int winding) {
1586        int end = nextSpan(index, step);
1587        SkASSERT(end >= 0);
1588        if (multipleSpans(end)) {
1589            return &fTs[end];
1590        }
1591        const Span& endSpan = fTs[end];
1592        Segment* other = endSpan.fOther;
1593        index = endSpan.fOtherIndex;
1594        int otherEnd = other->nextSpan(index, step);
1595        Span* last = other->innerChaseDone(index, step, winding);
1596        other->markDone(SkMin32(index, otherEnd), winding);
1597        return last;
1598    }
1599
1600    Span* innerChaseWinding(int index, int step, int winding) {
1601        int end = nextSpan(index, step);
1602        SkASSERT(end >= 0);
1603        if (multipleSpans(end)) {
1604            return &fTs[end];
1605        }
1606        const Span& endSpan = fTs[end];
1607        Segment* other = endSpan.fOther;
1608        index = endSpan.fOtherIndex;
1609        int otherEnd = other->nextSpan(index, step);
1610        int min = SkMin32(index, otherEnd);
1611        if (other->fTs[min].fWindSum != SK_MinS32) {
1612            SkASSERT(other->fTs[min].fWindSum == winding);
1613            return NULL;
1614        }
1615        Span* last = other->innerChaseWinding(index, step, winding);
1616        other->markWinding(min, winding);
1617        return last;
1618    }
1619
1620    void init(const SkPoint pts[], SkPath::Verb verb) {
1621        fPts = pts;
1622        fVerb = verb;
1623        fDoneSpans = 0;
1624    }
1625
1626    bool intersected() const {
1627        return fTs.count() > 0;
1628    }
1629
1630    bool isLinear(int start, int end) const {
1631        if (fVerb == SkPath::kLine_Verb) {
1632            return true;
1633        }
1634        if (fVerb == SkPath::kQuad_Verb) {
1635            SkPoint qPart[3];
1636            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
1637            return QuadIsLinear(qPart);
1638        } else {
1639            SkASSERT(fVerb == SkPath::kCubic_Verb);
1640            SkPoint cPart[4];
1641            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
1642            return CubicIsLinear(cPart);
1643        }
1644    }
1645
1646    // OPTIMIZE: successive calls could start were the last leaves off
1647    // or calls could specialize to walk forwards or backwards
1648    bool isMissing(double startT) const {
1649        size_t tCount = fTs.count();
1650        for (size_t index = 0; index < tCount; ++index) {
1651            if (fabs(startT - fTs[index].fT) < FLT_EPSILON) {
1652                return false;
1653            }
1654        }
1655        return true;
1656    }
1657
1658    bool isSimple(int end) const {
1659        int count = fTs.count();
1660        if (count == 2) {
1661            return true;
1662        }
1663        double t = fTs[end].fT;
1664        if (t < FLT_EPSILON) {
1665            return fTs[1].fT >= FLT_EPSILON;
1666        }
1667        if (t > 1 - FLT_EPSILON) {
1668            return fTs[count - 2].fT <= 1 - FLT_EPSILON;
1669        }
1670        return false;
1671    }
1672
1673    bool isHorizontal() const {
1674        return fBounds.fTop == fBounds.fBottom;
1675    }
1676
1677    bool isVertical() const {
1678        return fBounds.fLeft == fBounds.fRight;
1679    }
1680
1681    SkScalar leftMost(int start, int end) const {
1682        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
1683    }
1684
1685    // this span is excluded by the winding rule -- chase the ends
1686    // as long as they are unambiguous to mark connections as done
1687    // and give them the same winding value
1688    Span* markAndChaseDone(const Angle* angle, int winding) {
1689        int index = angle->start();
1690        int endIndex = angle->end();
1691        int step = SkSign32(endIndex - index);
1692        Span* last = innerChaseDone(index, step, winding);
1693        markDone(SkMin32(index, endIndex), winding);
1694        return last;
1695    }
1696
1697    Span* markAndChaseWinding(const Angle* angle, int winding) {
1698        int index = angle->start();
1699        int endIndex = angle->end();
1700        int min = SkMin32(index, endIndex);
1701        int step = SkSign32(endIndex - index);
1702        Span* last = innerChaseWinding(index, step, winding);
1703        markWinding(min, winding);
1704        return last;
1705    }
1706
1707    // FIXME: this should also mark spans with equal (x,y)
1708    // This may be called when the segment is already marked done. While this
1709    // wastes time, it shouldn't do any more than spin through the T spans.
1710    // OPTIMIZATION: abort on first done found (assuming that this code is
1711    // always called to mark segments done).
1712    void markDone(int index, int winding) {
1713      //  SkASSERT(!done());
1714        double referenceT = fTs[index].fT;
1715        int lesser = index;
1716        while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
1717            Span& span = fTs[lesser];
1718            if (span.fDone) {
1719                continue;
1720            }
1721        #if DEBUG_MARK_DONE
1722            const SkPoint& pt = xyAtT(&span);
1723            SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
1724                    __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding);
1725        #endif
1726            span.fDone = true;
1727            SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1728            SkASSERT(abs(winding) <= gDebugMaxWindSum);
1729            span.fWindSum = winding;
1730            fDoneSpans++;
1731        }
1732        do {
1733            Span& span = fTs[index];
1734     //       SkASSERT(!span.fDone);
1735            if (span.fDone) {
1736                continue;
1737            }
1738        #if DEBUG_MARK_DONE
1739            const SkPoint& pt = xyAtT(&span);
1740            SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
1741                    __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding);
1742        #endif
1743            span.fDone = true;
1744            SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1745            SkASSERT(abs(winding) <= gDebugMaxWindSum);
1746            span.fWindSum = winding;
1747            fDoneSpans++;
1748        } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
1749    }
1750
1751    void markWinding(int index, int winding) {
1752        SkASSERT(!done());
1753        double referenceT = fTs[index].fT;
1754        int lesser = index;
1755        while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
1756            Span& span = fTs[lesser];
1757            if (span.fDone) {
1758                continue;
1759            }
1760      //      SkASSERT(span.fWindValue == 1 || winding == 0);
1761            SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1762        #if DEBUG_MARK_DONE
1763            const SkPoint& pt = xyAtT(&span);
1764            SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
1765                    __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding);
1766        #endif
1767            SkASSERT(abs(winding) <= gDebugMaxWindSum);
1768            span.fWindSum = winding;
1769        }
1770        do {
1771            Span& span = fTs[index];
1772     //       SkASSERT(!span.fDone || span.fCoincident);
1773            if (span.fDone) {
1774                continue;
1775            }
1776     //       SkASSERT(span.fWindValue == 1 || winding == 0);
1777            SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
1778        #if DEBUG_MARK_DONE
1779            const SkPoint& pt = xyAtT(&span);
1780            SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
1781                    __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding);
1782        #endif
1783            SkASSERT(abs(winding) <= gDebugMaxWindSum);
1784            span.fWindSum = winding;
1785        } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
1786    }
1787
1788    // return span if when chasing, two or more radiating spans are not done
1789    // OPTIMIZATION: ? multiple spans is detected when there is only one valid
1790    // candidate and the remaining spans have windValue == 0 (canceled by
1791    // coincidence). The coincident edges could either be removed altogether,
1792    // or this code could be more complicated in detecting this case. Worth it?
1793    bool multipleSpans(int end) const {
1794        return end > 0 && end < fTs.count() - 1;
1795    }
1796
1797    // This has callers for two different situations: one establishes the end
1798    // of the current span, and one establishes the beginning of the next span
1799    // (thus the name). When this is looking for the end of the current span,
1800    // coincidence is found when the beginning Ts contain -step and the end
1801    // contains step. When it is looking for the beginning of the next, the
1802    // first Ts found can be ignored and the last Ts should contain -step.
1803    // OPTIMIZATION: probably should split into two functions
1804    int nextSpan(int from, int step) const {
1805        const Span& fromSpan = fTs[from];
1806        int count = fTs.count();
1807        int to = from;
1808        while (step > 0 ? ++to < count : --to >= 0) {
1809            const Span& span = fTs[to];
1810            if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) {
1811                continue;
1812            }
1813            return to;
1814        }
1815        return -1;
1816    }
1817
1818    const SkPoint* pts() const {
1819        return fPts;
1820    }
1821
1822    void reset() {
1823        init(NULL, (SkPath::Verb) -1);
1824        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1825        fTs.reset();
1826    }
1827
1828    int rewind(const Angle* angle) {
1829        SkASSERT(angle->segment() == this);
1830        const Span& span = fTs[SkMin32(angle->start(), angle->end())];
1831#if DEBUG_SORT
1832        SkDebugf("%s offset=%d\n", __FUNCTION__, angle->sign() * span.fWindValue);
1833#endif
1834        return angle->sign() * span.fWindValue;
1835    }
1836
1837    // OPTIMIZATION: mark as debugging only if used solely by tests
1838    const Span& span(int tIndex) const {
1839        return fTs[tIndex];
1840    }
1841
1842    int spanSign(int startIndex, int endIndex) const {
1843        return startIndex < endIndex ? -fTs[startIndex].fWindValue :
1844                fTs[endIndex].fWindValue;
1845    }
1846
1847    // OPTIMIZATION: mark as debugging only if used solely by tests
1848    double t(int tIndex) const {
1849        return fTs[tIndex].fT;
1850    }
1851
1852    void updatePts(const SkPoint pts[]) {
1853        fPts = pts;
1854    }
1855
1856    SkPath::Verb verb() const {
1857        return fVerb;
1858    }
1859
1860    int windSum(int tIndex) const {
1861        return fTs[tIndex].fWindSum;
1862    }
1863
1864    int windSum(const Angle* angle) const {
1865        int start = angle->start();
1866        int end = angle->end();
1867        int index = SkMin32(start, end);
1868        return windSum(index);
1869    }
1870
1871    int windValue(int tIndex) const {
1872        return fTs[tIndex].fWindValue;
1873    }
1874
1875    int windValue(const Angle* angle) const {
1876        int start = angle->start();
1877        int end = angle->end();
1878        int index = SkMin32(start, end);
1879        return windValue(index);
1880    }
1881
1882    SkScalar xAtT(const Span* span) const {
1883        return xyAtT(span).fX;
1884    }
1885
1886    const SkPoint& xyAtT(int index) const {
1887        return xyAtT(&fTs[index]);
1888    }
1889
1890    const SkPoint& xyAtT(const Span* span) const {
1891        if (!span->fPt) {
1892            if (span->fT == 0) {
1893                span->fPt = &fPts[0];
1894            } else if (span->fT == 1) {
1895                span->fPt = &fPts[fVerb];
1896            } else {
1897                SkPoint* pt = fIntersections.append();
1898                (*SegmentXYAtT[fVerb])(fPts, span->fT, pt);
1899                span->fPt = pt;
1900            }
1901        }
1902        return *span->fPt;
1903    }
1904
1905    SkScalar yAtT(int index) const {
1906        return yAtT(&fTs[index]);
1907    }
1908
1909    SkScalar yAtT(const Span* span) const {
1910        return xyAtT(span).fY;
1911    }
1912
1913#if DEBUG_DUMP
1914    void dump() const {
1915        const char className[] = "Segment";
1916        const int tab = 4;
1917        for (int i = 0; i < fTs.count(); ++i) {
1918            SkPoint out;
1919            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
1920            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
1921                    " otherT=%1.9g windSum=%d\n",
1922                    tab + sizeof(className), className, fID,
1923                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
1924                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
1925        }
1926        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
1927                tab + sizeof(className), className, fID,
1928                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
1929    }
1930#endif
1931
1932#if DEBUG_CONCIDENT
1933    void debugShowTs() {
1934        SkDebugf("%s %d", __FUNCTION__, fID);
1935        for (int i = 0; i < fTs.count(); ++i) {
1936            SkDebugf(" [o=%d %1.9g (%1.9g,%1.9g) w=%d]", fTs[i].fOther->fID,
1937                    fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue);
1938        }
1939        SkDebugf("\n");
1940    }
1941#endif
1942
1943#if DEBUG_ACTIVE_SPANS
1944    void debugShowActiveSpans(int contourID, int segmentIndex) {
1945        if (done()) {
1946            return;
1947        }
1948        for (int i = 0; i < fTs.count(); ++i) {
1949            if (fTs[i].fDone) {
1950                continue;
1951            }
1952            SkDebugf("%s contour=%d segment=%d (%d)", __FUNCTION__, contourID,
1953                     segmentIndex, fID);
1954            SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1955            for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
1956                SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1957            }
1958            const Span* span = &fTs[i];
1959            SkDebugf(") fT=%d (%1.9g) (%1.9g,%1.9g)", i, fTs[i].fT,
1960                     xAtT(span), yAtT(i));
1961            const Segment* other = fTs[i].fOther;
1962            SkDebugf(" other=%d otherT=%1.9g otherIndex=%d", other->fID,
1963                     fTs[i].fOtherT, fTs[i].fOtherIndex);
1964            SkDebugf(" windSum=%d windValue=%d\n", fTs[i].fWindSum,
1965                     fTs[i].fWindValue);
1966        }
1967    }
1968#endif
1969
1970#if DEBUG_SORT
1971    void debugShowSort(const SkTDArray<Angle*>& angles, int first,
1972            int contourWinding, int sumWinding) {
1973        int index = first;
1974        int windSum = sumWinding;
1975        const Angle& fAngle = *angles[first];
1976        const Segment& fSegment = *fAngle.segment();
1977        SkASSERT(&fSegment == this);
1978        const Span& fSpan = fSegment.fTs[SkMin32(fAngle.start(), fAngle.end())];
1979        if (fAngle.sign() * sumWinding < 0) {
1980            windSum += fAngle.sign() * fSpan.fWindValue;
1981        }
1982        do {
1983            const Angle& angle = *angles[index];
1984            const Segment& segment = *angle.segment();
1985            int start = angle.start();
1986            int end = angle.end();
1987            const Span& sSpan = segment.fTs[start];
1988            const Span& eSpan = segment.fTs[end];
1989            const Span& mSpan = segment.fTs[SkMin32(start, end)];
1990            int lastSum = windSum;
1991            windSum -= angle.sign() * mSpan.fWindValue;
1992            SkDebugf("%s [%d] id=%d start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
1993                     " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n",
1994                     __FUNCTION__, index, segment.fID, start, segment.xAtT(&sSpan),
1995                     segment.yAtT(&sSpan), end, segment.xAtT(&eSpan),
1996                     segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue,
1997                     lastSum, windSum, abs(lastSum) > abs(windSum) ? lastSum :
1998                     windSum, mSpan.fDone);
1999            ++index;
2000            if (index == angles.count()) {
2001                index = 0;
2002            }
2003        } while (index != first);
2004    }
2005#endif
2006
2007private:
2008    const SkPoint* fPts;
2009    SkPath::Verb fVerb;
2010    Bounds fBounds;
2011    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
2012    // OPTIMIZATION:if intersections array is a pointer, the it could only
2013    // be allocated as needed instead of always initialized -- though maybe
2014    // the initialization is lightweight enough that it hardly matters
2015    mutable SkTDArray<SkPoint> fIntersections;
2016    int fDoneSpans; // used for quick check that segment is finished
2017#if DEBUG_DUMP
2018    int fID;
2019#endif
2020};
2021
2022class Contour;
2023
2024struct Coincidence {
2025    Contour* fContours[2];
2026    int fSegments[2];
2027    double fTs[2][2];
2028};
2029
2030class Contour {
2031public:
2032    Contour() {
2033        reset();
2034#if DEBUG_DUMP
2035        fID = ++gContourID;
2036#endif
2037    }
2038
2039    bool operator<(const Contour& rh) const {
2040        return fBounds.fTop == rh.fBounds.fTop
2041                ? fBounds.fLeft < rh.fBounds.fLeft
2042                : fBounds.fTop < rh.fBounds.fTop;
2043    }
2044
2045    void addCoincident(int index, Contour* other, int otherIndex,
2046            const Intersections& ts, bool swap) {
2047        Coincidence& coincidence = *fCoincidences.append();
2048        coincidence.fContours[0] = this;
2049        coincidence.fContours[1] = other;
2050        coincidence.fSegments[0] = index;
2051        coincidence.fSegments[1] = otherIndex;
2052        coincidence.fTs[swap][0] = ts.fT[0][0];
2053        coincidence.fTs[swap][1] = ts.fT[0][1];
2054        coincidence.fTs[!swap][0] = ts.fT[1][0];
2055        coincidence.fTs[!swap][1] = ts.fT[1][1];
2056    }
2057
2058    void addCross(const Contour* crosser) {
2059#ifdef DEBUG_CROSS
2060        for (int index = 0; index < fCrosses.count(); ++index) {
2061            SkASSERT(fCrosses[index] != crosser);
2062        }
2063#endif
2064        *fCrosses.append() = crosser;
2065    }
2066
2067    void addCubic(const SkPoint pts[4]) {
2068        fSegments.push_back().addCubic(pts);
2069        fContainsCurves = true;
2070    }
2071
2072    int addLine(const SkPoint pts[2]) {
2073        fSegments.push_back().addLine(pts);
2074        return fSegments.count();
2075    }
2076
2077    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
2078        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
2079    }
2080
2081    int addQuad(const SkPoint pts[3]) {
2082        fSegments.push_back().addQuad(pts);
2083        fContainsCurves = true;
2084        return fSegments.count();
2085    }
2086
2087    int addT(int segIndex, double newT, Contour* other, int otherIndex) {
2088        containsIntercepts();
2089        return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
2090    }
2091
2092    const Bounds& bounds() const {
2093        return fBounds;
2094    }
2095
2096    void complete() {
2097        setBounds();
2098        fContainsIntercepts = false;
2099    }
2100
2101    void containsIntercepts() {
2102        fContainsIntercepts = true;
2103    }
2104
2105    const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY,
2106            int &tIndex, double& hitT) {
2107        int segmentCount = fSegments.count();
2108        const Segment* bestSegment = NULL;
2109        for (int test = 0; test < segmentCount; ++test) {
2110            Segment* testSegment = &fSegments[test];
2111            const SkRect& bounds = testSegment->bounds();
2112            if (bounds.fTop < bestY) {
2113                continue;
2114            }
2115            if (bounds.fTop > basePt.fY) {
2116                continue;
2117            }
2118            if (bounds.fLeft > basePt.fX) {
2119                continue;
2120            }
2121            if (bounds.fRight < basePt.fX) {
2122                continue;
2123            }
2124            double testHitT;
2125            int testT = testSegment->crossedSpan(basePt, bestY, testHitT);
2126            if (testT >= 0) {
2127                bestSegment = testSegment;
2128                tIndex = testT;
2129                hitT = testHitT;
2130            }
2131        }
2132        return bestSegment;
2133    }
2134
2135    bool crosses(const Contour* crosser) const {
2136        if (this == crosser) {
2137            return true;
2138        }
2139        for (int index = 0; index < fCrosses.count(); ++index) {
2140            if (fCrosses[index] == crosser) {
2141                return true;
2142            }
2143        }
2144        return false;
2145    }
2146
2147    void findTooCloseToCall(int winding) {
2148        int segmentCount = fSegments.count();
2149        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
2150            fSegments[sIndex].findTooCloseToCall(winding);
2151        }
2152    }
2153
2154    void fixOtherTIndex() {
2155        int segmentCount = fSegments.count();
2156        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
2157            fSegments[sIndex].fixOtherTIndex();
2158        }
2159    }
2160
2161    void reset() {
2162        fSegments.reset();
2163        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
2164        fContainsCurves = fContainsIntercepts = false;
2165        fWindingSum = SK_MinS32;
2166    }
2167
2168    void resolveCoincidence(int winding) {
2169        int count = fCoincidences.count();
2170        for (int index = 0; index < count; ++index) {
2171            Coincidence& coincidence = fCoincidences[index];
2172            Contour* thisContour = coincidence.fContours[0];
2173            Contour* otherContour = coincidence.fContours[1];
2174            int thisIndex = coincidence.fSegments[0];
2175            int otherIndex = coincidence.fSegments[1];
2176            Segment& thisOne = thisContour->fSegments[thisIndex];
2177            Segment& other = otherContour->fSegments[otherIndex];
2178        #if DEBUG_CONCIDENT
2179            thisOne.debugShowTs();
2180            other.debugShowTs();
2181        #endif
2182            double startT = coincidence.fTs[0][0];
2183            double endT = coincidence.fTs[0][1];
2184            if (startT > endT) {
2185                SkTSwap<double>(startT, endT);
2186            }
2187            SkASSERT(endT - startT >= FLT_EPSILON);
2188            double oStartT = coincidence.fTs[1][0];
2189            double oEndT = coincidence.fTs[1][1];
2190            if (oStartT > oEndT) {
2191                SkTSwap<double>(oStartT, oEndT);
2192            }
2193            SkASSERT(oEndT - oStartT >= FLT_EPSILON);
2194            if (winding > 0 || thisOne.cancels(other)) {
2195                        // make sure startT and endT have t entries
2196                if (thisOne.isMissing(startT) || other.isMissing(oEndT)) {
2197                    thisOne.addTPair(startT, other, oEndT);
2198                }
2199                if (thisOne.isMissing(endT) || other.isMissing(oStartT)) {
2200                    other.addTPair(oStartT, thisOne, endT);
2201                }
2202                thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
2203            } else {
2204                if (thisOne.isMissing(startT) || other.isMissing(oStartT)) {
2205                    thisOne.addTPair(startT, other, oStartT);
2206                }
2207                if (thisOne.isMissing(endT) || other.isMissing(oEndT)) {
2208                    other.addTPair(oEndT, thisOne, endT);
2209                }
2210                thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
2211            }
2212        #if DEBUG_CONCIDENT
2213            thisOne.debugShowTs();
2214            other.debugShowTs();
2215        #endif
2216        }
2217    }
2218
2219    const SkTArray<Segment>& segments() {
2220        return fSegments;
2221    }
2222
2223    void setWinding(int winding) {
2224        SkASSERT(fWindingSum < 0 || fWindingSum == winding);
2225        fWindingSum = winding;
2226    }
2227
2228    // OPTIMIZATION: feel pretty uneasy about this. It seems like once again
2229    // we need to sort and walk edges in y, but that on the surface opens the
2230    // same can of worms as before. But then, this is a rough sort based on
2231    // segments' top, and not a true sort, so it could be ameniable to regular
2232    // sorting instead of linear searching. Still feel like I'm missing something
2233    Segment* topSegment(SkScalar& bestY) {
2234        int segmentCount = fSegments.count();
2235        SkASSERT(segmentCount > 0);
2236        int best = -1;
2237        Segment* bestSegment = NULL;
2238        while (++best < segmentCount) {
2239            Segment* testSegment = &fSegments[best];
2240            if (testSegment->done()) {
2241                continue;
2242            }
2243            bestSegment = testSegment;
2244            break;
2245        }
2246        if (!bestSegment) {
2247            return NULL;
2248        }
2249        SkScalar bestTop = bestSegment->activeTop();
2250        for (int test = best + 1; test < segmentCount; ++test) {
2251            Segment* testSegment = &fSegments[test];
2252            if (testSegment->done()) {
2253                continue;
2254            }
2255            if (testSegment->bounds().fTop > bestTop) {
2256                continue;
2257            }
2258            SkScalar testTop = testSegment->activeTop();
2259            if (bestTop > testTop) {
2260                bestTop = testTop;
2261                bestSegment = testSegment;
2262            }
2263        }
2264        bestY = bestTop;
2265        return bestSegment;
2266    }
2267
2268    int updateSegment(int index, const SkPoint* pts) {
2269        Segment& segment = fSegments[index];
2270        segment.updatePts(pts);
2271        return segment.verb() + 1;
2272    }
2273
2274    int windSum() {
2275        if (fWindingSum >= 0) {
2276            return fWindingSum;
2277        }
2278        // check peers
2279        int count = fCrosses.count();
2280        for (int index = 0; index < count; ++index) {
2281            const Contour* crosser = fCrosses[index];
2282            if (0 <= crosser->fWindingSum) {
2283                fWindingSum = crosser->fWindingSum;
2284                break;
2285            }
2286        }
2287        return fWindingSum;
2288    }
2289
2290#if DEBUG_TEST
2291    SkTArray<Segment>& debugSegments() {
2292        return fSegments;
2293    }
2294#endif
2295
2296#if DEBUG_DUMP
2297    void dump() {
2298        int i;
2299        const char className[] = "Contour";
2300        const int tab = 4;
2301        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
2302        for (i = 0; i < fSegments.count(); ++i) {
2303            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
2304                    className, i);
2305            fSegments[i].dump();
2306        }
2307        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
2308                tab + sizeof(className), className,
2309                fBounds.fLeft, fBounds.fTop,
2310                fBounds.fRight, fBounds.fBottom);
2311        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
2312                className, fContainsIntercepts);
2313        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
2314                className, fContainsCurves);
2315    }
2316#endif
2317
2318#if DEBUG_ACTIVE_SPANS
2319    void debugShowActiveSpans() {
2320        for (int index = 0; index < fSegments.count(); ++index) {
2321            fSegments[index].debugShowActiveSpans(fID, index);
2322        }
2323    }
2324#endif
2325
2326protected:
2327    void setBounds() {
2328        int count = fSegments.count();
2329        if (count == 0) {
2330            SkDebugf("%s empty contour\n", __FUNCTION__);
2331            SkASSERT(0);
2332            // FIXME: delete empty contour?
2333            return;
2334        }
2335        fBounds = fSegments.front().bounds();
2336        for (int index = 1; index < count; ++index) {
2337            fBounds.add(fSegments[index].bounds());
2338        }
2339    }
2340
2341private:
2342    SkTArray<Segment> fSegments;
2343    SkTDArray<Coincidence> fCoincidences;
2344    SkTDArray<const Contour*> fCrosses;
2345    Bounds fBounds;
2346    bool fContainsIntercepts;
2347    bool fContainsCurves;
2348    int fWindingSum; // initial winding number outside
2349#if DEBUG_DUMP
2350    int fID;
2351#endif
2352};
2353
2354class EdgeBuilder {
2355public:
2356
2357EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
2358    : fPath(path)
2359    , fCurrentContour(NULL)
2360    , fContours(contours)
2361{
2362#if DEBUG_DUMP
2363    gContourID = 0;
2364    gSegmentID = 0;
2365#endif
2366    walk();
2367}
2368
2369protected:
2370
2371void complete() {
2372    if (fCurrentContour && fCurrentContour->segments().count()) {
2373        fCurrentContour->complete();
2374        fCurrentContour = NULL;
2375    }
2376}
2377
2378void walk() {
2379    // FIXME:remove once we can access path pts directly
2380    SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed
2381    SkPoint pts[4];
2382    SkPath::Verb verb;
2383    do {
2384        verb = iter.next(pts);
2385        *fPathVerbs.append() = verb;
2386        if (verb == SkPath::kMove_Verb) {
2387            *fPathPts.append() = pts[0];
2388        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
2389            fPathPts.append(verb, &pts[1]);
2390        }
2391    } while (verb != SkPath::kDone_Verb);
2392    // FIXME: end of section to remove once path pts are accessed directly
2393
2394    SkPath::Verb reducedVerb;
2395    uint8_t* verbPtr = fPathVerbs.begin();
2396    const SkPoint* pointsPtr = fPathPts.begin();
2397    const SkPoint* finalCurveStart = NULL;
2398    const SkPoint* finalCurveEnd = NULL;
2399    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
2400        switch (verb) {
2401            case SkPath::kMove_Verb:
2402                complete();
2403                if (!fCurrentContour) {
2404                    fCurrentContour = fContours.push_back_n(1);
2405                    finalCurveEnd = pointsPtr++;
2406                    *fExtra.append() = -1; // start new contour
2407                }
2408                continue;
2409            case SkPath::kLine_Verb:
2410                // skip degenerate points
2411                if (pointsPtr[-1].fX != pointsPtr[0].fX
2412                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
2413                    fCurrentContour->addLine(&pointsPtr[-1]);
2414                }
2415                break;
2416            case SkPath::kQuad_Verb:
2417
2418                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
2419                if (reducedVerb == 0) {
2420                    break; // skip degenerate points
2421                }
2422                if (reducedVerb == 1) {
2423                    *fExtra.append() =
2424                            fCurrentContour->addLine(fReducePts.end() - 2);
2425                    break;
2426                }
2427                fCurrentContour->addQuad(&pointsPtr[-1]);
2428                break;
2429            case SkPath::kCubic_Verb:
2430                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
2431                if (reducedVerb == 0) {
2432                    break; // skip degenerate points
2433                }
2434                if (reducedVerb == 1) {
2435                    *fExtra.append() =
2436                            fCurrentContour->addLine(fReducePts.end() - 2);
2437                    break;
2438                }
2439                if (reducedVerb == 2) {
2440                    *fExtra.append() =
2441                            fCurrentContour->addQuad(fReducePts.end() - 3);
2442                    break;
2443                }
2444                fCurrentContour->addCubic(&pointsPtr[-1]);
2445                break;
2446            case SkPath::kClose_Verb:
2447                SkASSERT(fCurrentContour);
2448                if (finalCurveStart && finalCurveEnd
2449                        && *finalCurveStart != *finalCurveEnd) {
2450                    *fReducePts.append() = *finalCurveStart;
2451                    *fReducePts.append() = *finalCurveEnd;
2452                    *fExtra.append() =
2453                            fCurrentContour->addLine(fReducePts.end() - 2);
2454                }
2455                complete();
2456                continue;
2457            default:
2458                SkDEBUGFAIL("bad verb");
2459                return;
2460        }
2461        finalCurveStart = &pointsPtr[verb - 1];
2462        pointsPtr += verb;
2463        SkASSERT(fCurrentContour);
2464    }
2465    complete();
2466    if (fCurrentContour && !fCurrentContour->segments().count()) {
2467        fContours.pop_back();
2468    }
2469    // correct pointers in contours since fReducePts may have moved as it grew
2470    int cIndex = 0;
2471    int extraCount = fExtra.count();
2472    SkASSERT(extraCount == 0 || fExtra[0] == -1);
2473    int eIndex = 0;
2474    int rIndex = 0;
2475    while (++eIndex < extraCount) {
2476        int offset = fExtra[eIndex];
2477        if (offset < 0) {
2478            ++cIndex;
2479            continue;
2480        }
2481        fCurrentContour = &fContours[cIndex];
2482        rIndex += fCurrentContour->updateSegment(offset - 1,
2483                &fReducePts[rIndex]);
2484    }
2485    fExtra.reset(); // we're done with this
2486}
2487
2488private:
2489    const SkPath& fPath;
2490    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
2491    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
2492    Contour* fCurrentContour;
2493    SkTArray<Contour>& fContours;
2494    SkTDArray<SkPoint> fReducePts; // segments created on the fly
2495    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
2496};
2497
2498class Work {
2499public:
2500    enum SegmentType {
2501        kHorizontalLine_Segment = -1,
2502        kVerticalLine_Segment = 0,
2503        kLine_Segment = SkPath::kLine_Verb,
2504        kQuad_Segment = SkPath::kQuad_Verb,
2505        kCubic_Segment = SkPath::kCubic_Verb,
2506    };
2507
2508    void addCoincident(Work& other, const Intersections& ts, bool swap) {
2509        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
2510    }
2511
2512    // FIXME: does it make sense to write otherIndex now if we're going to
2513    // fix it up later?
2514    void addOtherT(int index, double otherT, int otherIndex) {
2515        fContour->addOtherT(fIndex, index, otherT, otherIndex);
2516    }
2517
2518    // Avoid collapsing t values that are close to the same since
2519    // we walk ts to describe consecutive intersections. Since a pair of ts can
2520    // be nearly equal, any problems caused by this should be taken care
2521    // of later.
2522    // On the edge or out of range values are negative; add 2 to get end
2523    int addT(double newT, const Work& other) {
2524        return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
2525    }
2526
2527    bool advance() {
2528        return ++fIndex < fLast;
2529    }
2530
2531    SkScalar bottom() const {
2532        return bounds().fBottom;
2533    }
2534
2535    const Bounds& bounds() const {
2536        return fContour->segments()[fIndex].bounds();
2537    }
2538
2539    const SkPoint* cubic() const {
2540        return fCubic;
2541    }
2542
2543    void init(Contour* contour) {
2544        fContour = contour;
2545        fIndex = 0;
2546        fLast = contour->segments().count();
2547    }
2548
2549    bool isAdjacent(const Work& next) {
2550        return fContour == next.fContour && fIndex + 1 == next.fIndex;
2551    }
2552
2553    bool isFirstLast(const Work& next) {
2554        return fContour == next.fContour && fIndex == 0
2555                && next.fIndex == fLast - 1;
2556    }
2557
2558    SkScalar left() const {
2559        return bounds().fLeft;
2560    }
2561
2562    void promoteToCubic() {
2563        fCubic[0] = pts()[0];
2564        fCubic[2] = pts()[1];
2565        fCubic[3] = pts()[2];
2566        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
2567        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
2568        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
2569        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
2570    }
2571
2572    const SkPoint* pts() const {
2573        return fContour->segments()[fIndex].pts();
2574    }
2575
2576    SkScalar right() const {
2577        return bounds().fRight;
2578    }
2579
2580    ptrdiff_t segmentIndex() const {
2581        return fIndex;
2582    }
2583
2584    SegmentType segmentType() const {
2585        const Segment& segment = fContour->segments()[fIndex];
2586        SegmentType type = (SegmentType) segment.verb();
2587        if (type != kLine_Segment) {
2588            return type;
2589        }
2590        if (segment.isHorizontal()) {
2591            return kHorizontalLine_Segment;
2592        }
2593        if (segment.isVertical()) {
2594            return kVerticalLine_Segment;
2595        }
2596        return kLine_Segment;
2597    }
2598
2599    bool startAfter(const Work& after) {
2600        fIndex = after.fIndex;
2601        return advance();
2602    }
2603
2604    SkScalar top() const {
2605        return bounds().fTop;
2606    }
2607
2608    SkPath::Verb verb() const {
2609        return fContour->segments()[fIndex].verb();
2610    }
2611
2612    SkScalar x() const {
2613        return bounds().fLeft;
2614    }
2615
2616    bool xFlipped() const {
2617        return x() != pts()[0].fX;
2618    }
2619
2620    SkScalar y() const {
2621        return bounds().fTop;
2622    }
2623
2624    bool yFlipped() const {
2625        return y() != pts()[0].fY;
2626    }
2627
2628protected:
2629    Contour* fContour;
2630    SkPoint fCubic[4];
2631    int fIndex;
2632    int fLast;
2633};
2634
2635#if DEBUG_ADD_INTERSECTING_TS
2636static void debugShowLineIntersection(int pts, const Work& wt,
2637        const Work& wn, const double wtTs[2], const double wnTs[2]) {
2638    if (!pts) {
2639        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
2640                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
2641                wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY,
2642                wn.pts()[1].fX, wn.pts()[1].fY);
2643        return;
2644    }
2645    SkPoint wtOutPt, wnOutPt;
2646    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
2647    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
2648    SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
2649            __FUNCTION__,
2650            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
2651            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
2652    if (pts == 2) {
2653        SkDebugf(" wtTs[1]=%g", wtTs[1]);
2654    }
2655    SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
2656            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
2657            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
2658    if (pts == 2) {
2659        SkDebugf(" wnTs[1]=%g", wnTs[1]);
2660    }
2661    SkDebugf("\n");
2662}
2663#else
2664static void debugShowLineIntersection(int , const Work& ,
2665        const Work& , const double [2], const double [2]) {
2666}
2667#endif
2668
2669static bool addIntersectTs(Contour* test, Contour* next) {
2670
2671    if (test != next) {
2672        if (test->bounds().fBottom < next->bounds().fTop) {
2673            return false;
2674        }
2675        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
2676            return true;
2677        }
2678    }
2679    Work wt;
2680    wt.init(test);
2681    bool foundCommonContour = test == next;
2682    do {
2683        Work wn;
2684        wn.init(next);
2685        if (test == next && !wn.startAfter(wt)) {
2686            continue;
2687        }
2688        do {
2689            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
2690                continue;
2691            }
2692            int pts;
2693            Intersections ts;
2694            bool swap = false;
2695            switch (wt.segmentType()) {
2696                case Work::kHorizontalLine_Segment:
2697                    swap = true;
2698                    switch (wn.segmentType()) {
2699                        case Work::kHorizontalLine_Segment:
2700                        case Work::kVerticalLine_Segment:
2701                        case Work::kLine_Segment: {
2702                            pts = HLineIntersect(wn.pts(), wt.left(),
2703                                    wt.right(), wt.y(), wt.xFlipped(), ts);
2704                            debugShowLineIntersection(pts, wt, wn,
2705                                    ts.fT[1], ts.fT[0]);
2706                            break;
2707                        }
2708                        case Work::kQuad_Segment: {
2709                            pts = HQuadIntersect(wn.pts(), wt.left(),
2710                                    wt.right(), wt.y(), wt.xFlipped(), ts);
2711                            break;
2712                        }
2713                        case Work::kCubic_Segment: {
2714                            pts = HCubicIntersect(wn.pts(), wt.left(),
2715                                    wt.right(), wt.y(), wt.xFlipped(), ts);
2716                            break;
2717                        }
2718                        default:
2719                            SkASSERT(0);
2720                    }
2721                    break;
2722                case Work::kVerticalLine_Segment:
2723                    swap = true;
2724                    switch (wn.segmentType()) {
2725                        case Work::kHorizontalLine_Segment:
2726                        case Work::kVerticalLine_Segment:
2727                        case Work::kLine_Segment: {
2728                            pts = VLineIntersect(wn.pts(), wt.top(),
2729                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2730                            debugShowLineIntersection(pts, wt, wn,
2731                                    ts.fT[1], ts.fT[0]);
2732                            break;
2733                        }
2734                        case Work::kQuad_Segment: {
2735                            pts = VQuadIntersect(wn.pts(), wt.top(),
2736                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2737                            break;
2738                        }
2739                        case Work::kCubic_Segment: {
2740                            pts = VCubicIntersect(wn.pts(), wt.top(),
2741                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2742                            break;
2743                        }
2744                        default:
2745                            SkASSERT(0);
2746                    }
2747                    break;
2748                case Work::kLine_Segment:
2749                    switch (wn.segmentType()) {
2750                        case Work::kHorizontalLine_Segment:
2751                            pts = HLineIntersect(wt.pts(), wn.left(),
2752                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2753                            debugShowLineIntersection(pts, wt, wn,
2754                                    ts.fT[1], ts.fT[0]);
2755                            break;
2756                        case Work::kVerticalLine_Segment:
2757                            pts = VLineIntersect(wt.pts(), wn.top(),
2758                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2759                            debugShowLineIntersection(pts, wt, wn,
2760                                    ts.fT[1], ts.fT[0]);
2761                            break;
2762                        case Work::kLine_Segment: {
2763                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
2764                            debugShowLineIntersection(pts, wt, wn,
2765                                    ts.fT[1], ts.fT[0]);
2766                            break;
2767                        }
2768                        case Work::kQuad_Segment: {
2769                            swap = true;
2770                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
2771                            break;
2772                        }
2773                        case Work::kCubic_Segment: {
2774                            swap = true;
2775                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
2776                            break;
2777                        }
2778                        default:
2779                            SkASSERT(0);
2780                    }
2781                    break;
2782                case Work::kQuad_Segment:
2783                    switch (wn.segmentType()) {
2784                        case Work::kHorizontalLine_Segment:
2785                            pts = HQuadIntersect(wt.pts(), wn.left(),
2786                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2787                            break;
2788                        case Work::kVerticalLine_Segment:
2789                            pts = VQuadIntersect(wt.pts(), wn.top(),
2790                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2791                            break;
2792                        case Work::kLine_Segment: {
2793                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
2794                            break;
2795                        }
2796                        case Work::kQuad_Segment: {
2797                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
2798                            break;
2799                        }
2800                        case Work::kCubic_Segment: {
2801                            wt.promoteToCubic();
2802                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
2803                            break;
2804                        }
2805                        default:
2806                            SkASSERT(0);
2807                    }
2808                    break;
2809                case Work::kCubic_Segment:
2810                    switch (wn.segmentType()) {
2811                        case Work::kHorizontalLine_Segment:
2812                            pts = HCubicIntersect(wt.pts(), wn.left(),
2813                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2814                            break;
2815                        case Work::kVerticalLine_Segment:
2816                            pts = VCubicIntersect(wt.pts(), wn.top(),
2817                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2818                            break;
2819                        case Work::kLine_Segment: {
2820                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
2821                            break;
2822                        }
2823                        case Work::kQuad_Segment: {
2824                            wn.promoteToCubic();
2825                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
2826                            break;
2827                        }
2828                        case Work::kCubic_Segment: {
2829                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
2830                            break;
2831                        }
2832                        default:
2833                            SkASSERT(0);
2834                    }
2835                    break;
2836                default:
2837                    SkASSERT(0);
2838            }
2839            if (!foundCommonContour && pts > 0) {
2840                test->addCross(next);
2841                next->addCross(test);
2842                foundCommonContour = true;
2843            }
2844            // in addition to recording T values, record matching segment
2845            if (pts == 2 && wn.segmentType() <= Work::kLine_Segment
2846                    && wt.segmentType() <= Work::kLine_Segment) {
2847                wt.addCoincident(wn, ts, swap);
2848                continue;
2849            }
2850            for (int pt = 0; pt < pts; ++pt) {
2851                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
2852                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
2853                int testTAt = wt.addT(ts.fT[swap][pt], wn);
2854                int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
2855                wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt);
2856                wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt);
2857            }
2858        } while (wn.advance());
2859    } while (wt.advance());
2860    return true;
2861}
2862
2863// resolve any coincident pairs found while intersecting, and
2864// see if coincidence is formed by clipping non-concident segments
2865static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) {
2866    int contourCount = contourList.count();
2867    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
2868        Contour* contour = contourList[cIndex];
2869        contour->findTooCloseToCall(winding);
2870    }
2871    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
2872        Contour* contour = contourList[cIndex];
2873        contour->resolveCoincidence(winding);
2874    }
2875}
2876
2877// project a ray from the top of the contour up and see if it hits anything
2878// note: when we compute line intersections, we keep track of whether
2879// two contours touch, so we need only look at contours not touching this one.
2880// OPTIMIZATION: sort contourList vertically to avoid linear walk
2881static int innerContourCheck(SkTDArray<Contour*>& contourList,
2882        Contour* baseContour, const SkPoint& basePt) {
2883    int contourCount = contourList.count();
2884    SkScalar bestY = SK_ScalarMin;
2885    const Segment* test = NULL;
2886    int tIndex;
2887    double tHit;
2888    for (int cTest = 0; cTest < contourCount; ++cTest) {
2889        Contour* contour = contourList[cTest];
2890        if (basePt.fY < contour->bounds().fTop) {
2891            continue;
2892        }
2893        if (bestY > contour->bounds().fBottom) {
2894            continue;
2895        }
2896        if (baseContour->crosses(contour)) {
2897           continue;
2898        }
2899        const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit);
2900        if (next) {
2901            test = next;
2902        }
2903    }
2904    if (!test) {
2905        baseContour->setWinding(0);
2906        return 0;
2907    }
2908    int winding, windValue;
2909    // If the ray hit the end of a span, we need to construct the wheel of
2910    // angles to find the span closest to the ray -- even if there are just
2911    // two spokes on the wheel.
2912    if (fabs(tHit - test->t(tIndex)) < FLT_EPSILON) {
2913        SkTDArray<Angle> angles;
2914        int end = test->nextSpan(tIndex, 1);
2915        if (end < 0) {
2916            end = test->nextSpan(tIndex, -1);
2917        }
2918        test->addTwoAngles(end, tIndex, angles);
2919        test->buildAngles(tIndex, angles);
2920        SkTDArray<Angle*> sorted;
2921        // OPTIMIZATION: call a sort that, if base point is the leftmost,
2922        // returns the first counterclockwise hour before 6 o'clock,
2923        // or if the base point is rightmost, returns the first clockwise
2924        // hour after 6 o'clock
2925        sortAngles(angles, sorted);
2926#if DEBUG_SORT
2927        sorted[0]->segment()->debugShowSort(sorted, 0, 0, 0);
2928#endif
2929        // walk the sorted angle fan to find the lowest angle
2930        // above the base point. Currently, the first angle in the sorted array
2931        // is 12 noon or an earlier hour (the next counterclockwise)
2932        int count = sorted.count();
2933        int left = -1;
2934        int right = -1;
2935        for (int index = 0; index < count; ++index) {
2936            double indexDx = sorted[index]->dx();
2937            if (indexDx < 0) {
2938                left = index;
2939            } else if (indexDx > 0) {
2940                right = index;
2941                break;
2942            }
2943        }
2944        SkASSERT(left >= 0 || right >= 0);
2945        if (left < 0) {
2946            left = right;
2947        }
2948        const Angle* angle = sorted[left];
2949        test = angle->segment();
2950        winding = test->windSum(angle);
2951        SkASSERT(winding != SK_MinS32);
2952        windValue = test->windValue(angle);
2953    #if 0
2954        int firstSign = angle->sign();
2955        if (firstSign * winding > 0) {
2956            winding -= test->rewind(angle);
2957        }
2958    #endif
2959#if DEBUG_WINDING
2960        SkDebugf("%s angle winding=%d windValue=%d\n", __FUNCTION__, winding,
2961                windValue);
2962#endif
2963    } else {
2964        winding = test->windSum(tIndex);
2965        SkASSERT(winding != SK_MinS32);
2966        windValue = test->windValue(tIndex);
2967#if DEBUG_WINDING
2968        SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
2969                windValue);
2970#endif
2971    }
2972    // see if a + change in T results in a +/- change in X (compute x'(T))
2973    SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit);
2974#if DEBUG_WINDING
2975    SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx);
2976#endif
2977    SkASSERT(dx != 0);
2978    if (winding * dx > 0) { // if same signs, result is negative
2979        winding += dx > 0 ? -windValue : windValue;
2980#if DEBUG_WINDING
2981        SkDebugf("%s final winding=%d\n", __FUNCTION__, winding);
2982#endif
2983    }
2984    baseContour->setWinding(winding);
2985    return winding;
2986}
2987
2988// OPTIMIZATION: not crazy about linear search here to find top active y.
2989// seems like we should break down and do the sort, or maybe sort each
2990// contours' segments?
2991// Once the segment array is built, there's no reason I can think of not to
2992// sort it in Y. hmmm
2993// FIXME: return the contour found to pass to inner contour check
2994static Segment* findTopContour(SkTDArray<Contour*>& contourList,
2995        Contour*& topContour) {
2996    int contourCount = contourList.count();
2997    int cIndex = 0;
2998    Segment* topStart;
2999    SkScalar bestY = SK_ScalarMax;
3000    Contour* contour;
3001    do {
3002        contour = contourList[cIndex];
3003        topStart = contour->topSegment(bestY);
3004    } while (!topStart && ++cIndex < contourCount);
3005    if (!topStart) {
3006        return NULL;
3007    }
3008    topContour = contour;
3009    while (++cIndex < contourCount) {
3010        contour = contourList[cIndex];
3011        if (bestY < contour->bounds().fTop) {
3012            continue;
3013        }
3014        SkScalar testY = SK_ScalarMax;
3015        Segment* test = contour->topSegment(testY);
3016        if (!test || bestY <= testY) {
3017            continue;
3018        }
3019        topContour = contour;
3020        topStart = test;
3021        bestY = testY;
3022    }
3023    return topStart;
3024}
3025
3026static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex,
3027        int contourWinding) {
3028    while (chase.count()) {
3029        Span* span = chase[chase.count() - 1];
3030        const Span& backPtr = span->fOther->span(span->fOtherIndex);
3031        Segment* segment = backPtr.fOther;
3032        tIndex = backPtr.fOtherIndex;
3033        SkTDArray<Angle> angles;
3034        int done = 0;
3035        if (segment->activeAngle(tIndex, done, angles)) {
3036            Angle* last = angles.end() - 1;
3037            tIndex = last->start();
3038            endIndex = last->end();
3039            return last->segment();
3040        }
3041        if (done == angles.count()) {
3042            chase.pop(&span);
3043            continue;
3044        }
3045        SkTDArray<Angle*> sorted;
3046        sortAngles(angles, sorted);
3047        // find first angle, initialize winding to computed fWindSum
3048        int firstIndex = -1;
3049        const Angle* angle;
3050        int spanWinding;
3051        do {
3052            angle = sorted[++firstIndex];
3053            spanWinding = angle->segment()->windSum(angle);
3054        } while (spanWinding == SK_MinS32);
3055    #if DEBUG_SORT
3056        angle->segment()->debugShowSort(sorted, firstIndex, contourWinding,
3057                spanWinding);
3058    #endif
3059        int firstSign = angle->sign();
3060        if (firstSign * spanWinding > 0) {
3061            spanWinding -= angle->segment()->rewind(angle);
3062        }
3063    //    SkDebugf("%s firstSign=%d\n", __FUNCTION__, firstSign);
3064        // we care about first sign and whether wind sum indicates this
3065        // edge is inside or outside. Maybe need to pass span winding
3066        // or first winding or something into this function?
3067        // advance to first undone angle, then return it and winding
3068        // (to set whether edges are active or not)
3069        int nextIndex = firstIndex + 1;
3070        int angleCount = sorted.count();
3071        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
3072        do {
3073            SkASSERT(nextIndex != firstIndex);
3074            if (nextIndex == angleCount) {
3075                nextIndex = 0;
3076            }
3077            const Angle* angle = sorted[nextIndex];
3078            segment = angle->segment();
3079            int windValue = segment->windValue(angle);
3080            SkASSERT(windValue > 0);
3081            int maxWinding = spanWinding;
3082            spanWinding -= angle->sign() * windValue;
3083            if (maxWinding * spanWinding < 0) {
3084                SkDebugf("%s flipped sign %d %d\n", __FUNCTION__, maxWinding, spanWinding);
3085            }
3086            tIndex = angle->start();
3087            endIndex = angle->end();
3088            int lesser = SkMin32(tIndex, endIndex);
3089            const Span& nextSpan = segment->span(lesser);
3090            if (!nextSpan.fDone) {
3091            // FIXME: this be wrong. assign startWinding if edge is in
3092            // same direction. If the direction is opposite, winding to
3093            // assign is flipped sign or +/- 1?
3094                if (abs(maxWinding) < abs(spanWinding)) {
3095                    maxWinding = spanWinding;
3096                }
3097                segment->markWinding(lesser, maxWinding);
3098                break;
3099            }
3100        } while (++nextIndex != lastIndex);
3101        return segment;
3102    }
3103    return NULL;
3104}
3105
3106#if DEBUG_ACTIVE_SPANS
3107static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
3108    for (int index = 0; index < contourList.count(); ++ index) {
3109        contourList[index]->debugShowActiveSpans();
3110    }
3111}
3112#endif
3113
3114// Each segment may have an inside or an outside. Segments contained within
3115// winding may have insides on either side, and form a contour that should be
3116// ignored. Segments that are coincident with opposing direction segments may
3117// have outsides on either side, and should also disappear.
3118// 'Normal' segments will have one inside and one outside. Subsequent connections
3119// when winding should follow the intersection direction. If more than one edge
3120// is an option, choose first edge that continues the inside.
3121    // since we start with leftmost top edge, we'll traverse through a
3122    // smaller angle counterclockwise to get to the next edge.
3123static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
3124    bool firstContour = true;
3125    do {
3126        Contour* topContour;
3127        Segment* topStart = findTopContour(contourList, topContour);
3128        if (!topStart) {
3129            break;
3130        }
3131        // Start at the top. Above the top is outside, below is inside.
3132        // follow edges to intersection by changing the index by direction.
3133        int index, endIndex;
3134        Segment* current = topStart->findTop(index, endIndex);
3135        int contourWinding;
3136        if (firstContour) {
3137            contourWinding = 0;
3138            firstContour = false;
3139        } else {
3140            const SkPoint& topPoint = current->xyAtT(endIndex);
3141            contourWinding = innerContourCheck(contourList, topContour, topPoint);
3142#if DEBUG_WINDING
3143            SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
3144#endif
3145        }
3146        SkPoint lastPt;
3147        bool firstTime = true;
3148        int winding = contourWinding;
3149        int spanWinding = current->spanSign(index, endIndex);
3150     //   int firstWinding = contourWinding + spanWinding;
3151        // FIXME: needs work. While it works in limited situations, it does
3152        // not always compute winding correctly. Active should be removed and instead
3153        // the initial winding should be correctly passed in so that if the
3154        // inner contour is wound the same way, it never finds an accumulated
3155        // winding of zero. Inside 'find next', we need to look for transitions
3156        // other than zero when resolving sorted angles.
3157        SkTDArray<Span*> chaseArray;
3158        do {
3159            bool active = winding * spanWinding <= 0
3160                    && abs(winding) <= abs(spanWinding);
3161        #if DEBUG_WINDING
3162            if (abs(winding) > abs(spanWinding) && winding * spanWinding < 0) {
3163                SkDebugf("%s *** unexpected active\n?", __FUNCTION__);
3164            }
3165            SkDebugf("%s active=%s winding=%d spanWinding=%d\n",
3166                    __FUNCTION__, active ? "true" : "false",
3167                    winding, spanWinding);
3168        #endif
3169            const SkPoint* firstPt = NULL;
3170            do {
3171                SkASSERT(!current->done());
3172                int nextStart, nextEnd, flipped = 1;
3173                Segment* next = current->findNext(chaseArray, winding,
3174                        contourWinding, spanWinding, index, endIndex,
3175                        nextStart, nextEnd, flipped, firstTime, active);
3176                if (!next) {
3177                    break;
3178                }
3179                if (!firstPt) {
3180                    firstPt = &current->addMoveTo(index, simple, active);
3181                }
3182                lastPt = current->addCurveTo(index, endIndex, simple, active);
3183                current = next;
3184                index = nextStart;
3185                endIndex = nextEnd;
3186                spanWinding = SkSign32(spanWinding) * flipped * next->windValue(
3187                        SkMin32(nextStart, nextEnd));
3188        #if DEBUG_WINDING
3189                SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding);
3190        #endif
3191                firstTime = false;
3192            } while (*firstPt != lastPt && (active || !current->done()));
3193            if (firstPt && active) {
3194        #if DEBUG_PATH_CONSTRUCTION
3195                SkDebugf("%s close\n", __FUNCTION__);
3196        #endif
3197                simple.close();
3198            }
3199            current = findChase(chaseArray, index, endIndex, contourWinding);
3200        #if DEBUG_ACTIVE_SPANS
3201            debugShowActiveSpans(contourList);
3202        #endif
3203            if (!current) {
3204                break;
3205            }
3206            int lesser = SkMin32(index, endIndex);
3207            spanWinding = current->windSum(lesser);
3208            int spanValue = current->windValue(lesser);
3209            SkASSERT(spanWinding != SK_MinS32);
3210            int spanSign = current->spanSign(index, endIndex);
3211        #if DEBUG_WINDING
3212            SkDebugf("%s spanWinding=%d spanSign=%d winding=%d spanValue=%d\n",
3213                    __FUNCTION__, spanWinding, spanSign, winding, spanValue);
3214        #endif
3215            if (spanWinding * spanSign < 0) {
3216        #if DEBUG_WINDING
3217                SkDebugf("%s spanWinding * spanSign < 0\n", __FUNCTION__);
3218        #endif
3219   //             SkTSwap<int>(index, endIndex);
3220            }
3221            if (abs(spanWinding) > spanValue) {
3222                winding = spanWinding;
3223                spanWinding = spanValue * SkSign32(spanWinding);
3224                winding -= spanWinding;
3225        #if DEBUG_WINDING
3226                SkDebugf("%s spanWinding=%d winding=%d\n", __FUNCTION__,
3227                        spanWinding, winding);
3228        #endif
3229            } else {
3230        #if DEBUG_WINDING
3231                SkDebugf("%s ->0 contourWinding=%d winding=%d\n", __FUNCTION__,
3232                        contourWinding, winding);
3233        #endif
3234                winding = 0;
3235            }
3236        } while (true);
3237    } while (true);
3238}
3239
3240static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
3241    int contourCount = contourList.count();
3242    for (int cTest = 0; cTest < contourCount; ++cTest) {
3243        Contour* contour = contourList[cTest];
3244        contour->fixOtherTIndex();
3245    }
3246}
3247
3248static void makeContourList(SkTArray<Contour>& contours,
3249        SkTDArray<Contour*>& list) {
3250    int count = contours.count();
3251    if (count == 0) {
3252        return;
3253    }
3254    for (int index = 0; index < count; ++index) {
3255        *list.append() = &contours[index];
3256    }
3257    QSort<Contour>(list.begin(), list.end() - 1);
3258}
3259
3260void simplifyx(const SkPath& path, SkPath& simple) {
3261    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
3262    int winding = (path.getFillType() & 1) ? 1 : -1;
3263    simple.reset();
3264    simple.setFillType(SkPath::kEvenOdd_FillType);
3265
3266    // turn path into list of segments
3267    SkTArray<Contour> contours;
3268    // FIXME: add self-intersecting cubics' T values to segment
3269    EdgeBuilder builder(path, contours);
3270    SkTDArray<Contour*> contourList;
3271    makeContourList(contours, contourList);
3272    Contour** currentPtr = contourList.begin();
3273    if (!currentPtr) {
3274        return;
3275    }
3276    Contour** listEnd = contourList.end();
3277    // find all intersections between segments
3278    do {
3279        Contour** nextPtr = currentPtr;
3280        Contour* current = *currentPtr++;
3281        Contour* next;
3282        do {
3283            next = *nextPtr++;
3284        } while (addIntersectTs(current, next) && nextPtr != listEnd);
3285    } while (currentPtr != listEnd);
3286    // eat through coincident edges
3287    coincidenceCheck(contourList, winding);
3288    fixOtherTIndex(contourList);
3289    // construct closed contours
3290    bridge(contourList, simple);
3291}
3292
3293