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