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