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