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