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