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