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