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