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