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