Simplify.cpp revision a3f05facab01712a1b58e60a70b0dbdb90a39830
1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "Simplify.h"
8
9#undef SkASSERT
10#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
11
12// Terminology:
13// A Path contains one of more Contours
14// A Contour is made up of Segment array
15// A Segment is described by a Verb and a Point array with 2, 3, or 4 points
16// A Verb is one of Line, Quad(ratic), or Cubic
17// A Segment contains a Span array
18// A Span is describes a portion of a Segment using starting and ending T
19// T values range from 0 to 1, where 0 is the first Point in the Segment
20
21// FIXME: remove once debugging is complete
22#if 0 // set to 1 for no debugging whatsoever
23
24//const bool gxRunTestsInOneThread = false;
25
26#define DEBUG_ADD_INTERSECTING_TS 0
27#define DEBUG_BRIDGE 0
28#define DEBUG_DUMP 0
29#define DEBUG_PATH_CONSTRUCTION 0
30#define DEBUG_UNUSED 0 // set to expose unused functions
31
32#else
33
34//const bool gRunTestsInOneThread = true;
35
36#define DEBUG_ADD_INTERSECTING_TS 0
37#define DEBUG_BRIDGE 1
38#define DEBUG_DUMP 1
39#define DEBUG_PATH_CONSTRUCTION 1
40#define DEBUG_UNUSED 0 // set to expose unused functions
41
42#endif
43
44#if DEBUG_DUMP
45static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
46// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
47static int gContourID;
48static int gSegmentID;
49#endif
50
51static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
52        Intersections& intersections) {
53    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
54    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
55    return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
56}
57
58static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
59        Intersections& intersections) {
60    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
61    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
62    intersect(aQuad, bLine, intersections);
63    return intersections.fUsed;
64}
65
66static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
67        Intersections& intersections) {
68    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
69            {a[3].fX, a[3].fY}};
70    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
71    return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
72}
73
74static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
75        Intersections& intersections) {
76    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
77    const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
78    intersect(aQuad, bQuad, intersections);
79    return intersections.fUsed;
80}
81
82static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
83        Intersections& intersections) {
84    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
85            {a[3].fX, a[3].fY}};
86    const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
87            {b[3].fX, b[3].fY}};
88    intersect(aCubic, bCubic, intersections);
89    return intersections.fUsed;
90}
91
92static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
93        SkScalar y, bool flipped, Intersections& intersections) {
94    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
95    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
96}
97
98static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
99        SkScalar y, bool flipped, Intersections& intersections) {
100    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
101    return verticalIntersect(aLine, left, right, y, flipped, intersections);
102}
103
104static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
105        SkScalar y, bool flipped, Intersections& intersections) {
106    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
107    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
108}
109
110static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
111        SkScalar y, bool flipped, Intersections& intersections) {
112    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
113    return verticalIntersect(aQuad, left, right, y, flipped, intersections);
114}
115
116static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
117        SkScalar y, bool flipped, Intersections& intersections) {
118    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
119            {a[3].fX, a[3].fY}};
120    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
121}
122
123static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
124        SkScalar y, bool flipped, Intersections& intersections) {
125    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
126            {a[3].fX, a[3].fY}};
127    return verticalIntersect(aCubic, left, right, y, flipped, intersections);
128}
129
130static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
131    const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
132    double x, y;
133    xy_at_t(line, t, x, y);
134    out->fX = SkDoubleToScalar(x);
135    out->fY = SkDoubleToScalar(y);
136}
137
138static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
139    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
140    double x, y;
141    xy_at_t(quad, t, x, y);
142    out->fX = SkDoubleToScalar(x);
143    out->fY = SkDoubleToScalar(y);
144}
145
146static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
147    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
148            {a[3].fX, a[3].fY}};
149    double x, y;
150    xy_at_t(cubic, t, x, y);
151    out->fX = SkDoubleToScalar(x);
152    out->fY = SkDoubleToScalar(y);
153}
154
155static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
156    NULL,
157    LineXYAtT,
158    QuadXYAtT,
159    CubicXYAtT
160};
161
162static SkScalar LineXAtT(const SkPoint a[2], double t) {
163    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
164    double x;
165    xy_at_t(aLine, t, x, *(double*) 0);
166    return SkDoubleToScalar(x);
167}
168
169static SkScalar QuadXAtT(const SkPoint a[3], double t) {
170    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
171    double x;
172    xy_at_t(quad, t, x, *(double*) 0);
173    return SkDoubleToScalar(x);
174}
175
176static SkScalar CubicXAtT(const SkPoint a[4], double t) {
177    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
178            {a[3].fX, a[3].fY}};
179    double x;
180    xy_at_t(cubic, t, x, *(double*) 0);
181    return SkDoubleToScalar(x);
182}
183
184static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
185    NULL,
186    LineXAtT,
187    QuadXAtT,
188    CubicXAtT
189};
190
191static SkScalar LineYAtT(const SkPoint a[2], double t) {
192    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
193    double y;
194    xy_at_t(aLine, t, *(double*) 0, y);
195    return SkDoubleToScalar(y);
196}
197
198static SkScalar QuadYAtT(const SkPoint a[3], double t) {
199    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
200    double y;
201    xy_at_t(quad, t, *(double*) 0, y);
202    return SkDoubleToScalar(y);
203}
204
205static SkScalar CubicYAtT(const SkPoint a[4], double t) {
206    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
207            {a[3].fX, a[3].fY}};
208    double y;
209    xy_at_t(cubic, t, *(double*) 0, y);
210    return SkDoubleToScalar(y);
211}
212
213static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
214    NULL,
215    LineYAtT,
216    QuadYAtT,
217    CubicYAtT
218};
219
220static void LineSubDivide(const SkPoint a[2], double startT, double endT,
221        SkPoint sub[2]) {
222    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
223    _Line dst;
224    sub_divide(aLine, startT, endT, dst);
225    sub[0].fX = SkDoubleToScalar(dst[0].x);
226    sub[0].fY = SkDoubleToScalar(dst[0].y);
227    sub[1].fX = SkDoubleToScalar(dst[1].x);
228    sub[1].fY = SkDoubleToScalar(dst[1].y);
229}
230
231static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
232        SkPoint sub[3]) {
233    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
234            {a[2].fX, a[2].fY}};
235    Quadratic dst;
236    sub_divide(aQuad, startT, endT, dst);
237    sub[0].fX = SkDoubleToScalar(dst[0].x);
238    sub[0].fY = SkDoubleToScalar(dst[0].y);
239    sub[1].fX = SkDoubleToScalar(dst[1].x);
240    sub[1].fY = SkDoubleToScalar(dst[1].y);
241    sub[2].fX = SkDoubleToScalar(dst[2].x);
242    sub[2].fY = SkDoubleToScalar(dst[2].y);
243}
244
245static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
246        SkPoint sub[4]) {
247    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
248            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
249    Cubic dst;
250    sub_divide(aCubic, startT, endT, dst);
251    sub[0].fX = SkDoubleToScalar(dst[0].x);
252    sub[0].fY = SkDoubleToScalar(dst[0].y);
253    sub[1].fX = SkDoubleToScalar(dst[1].x);
254    sub[1].fY = SkDoubleToScalar(dst[1].y);
255    sub[2].fX = SkDoubleToScalar(dst[2].x);
256    sub[2].fY = SkDoubleToScalar(dst[2].y);
257    sub[3].fX = SkDoubleToScalar(dst[3].x);
258    sub[3].fY = SkDoubleToScalar(dst[3].y);
259}
260
261static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
262        SkPoint []) = {
263    NULL,
264    LineSubDivide,
265    QuadSubDivide,
266    CubicSubDivide
267};
268
269#if DEBUG_UNUSED
270static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
271        SkRect& bounds) {
272    SkPoint dst[3];
273    QuadSubDivide(a, startT, endT, dst);
274    bounds.fLeft = bounds.fRight = dst[0].fX;
275    bounds.fTop = bounds.fBottom = dst[0].fY;
276    for (int index = 1; index < 3; ++index) {
277        bounds.growToInclude(dst[index].fX, dst[index].fY);
278    }
279}
280
281static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
282        SkRect& bounds) {
283    SkPoint dst[4];
284    CubicSubDivide(a, startT, endT, dst);
285    bounds.fLeft = bounds.fRight = dst[0].fX;
286    bounds.fTop = bounds.fBottom = dst[0].fY;
287    for (int index = 1; index < 4; ++index) {
288        bounds.growToInclude(dst[index].fX, dst[index].fY);
289    }
290}
291#endif
292
293static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
294        SkTDArray<SkPoint>& reducePts) {
295    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
296            {a[2].fX, a[2].fY}};
297    Quadratic dst;
298    int order = reduceOrder(aQuad, dst);
299    if (order == 3) {
300        return SkPath::kQuad_Verb;
301    }
302    for (int index = 0; index < order; ++index) {
303        SkPoint* pt = reducePts.append();
304        pt->fX = SkDoubleToScalar(dst[index].x);
305        pt->fY = SkDoubleToScalar(dst[index].y);
306    }
307    return (SkPath::Verb) (order - 1);
308}
309
310static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
311        SkTDArray<SkPoint>& reducePts) {
312    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
313            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
314    Cubic dst;
315    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
316    if (order == 4) {
317        return SkPath::kCubic_Verb;
318    }
319    for (int index = 0; index < order; ++index) {
320        SkPoint* pt = reducePts.append();
321        pt->fX = SkDoubleToScalar(dst[index].x);
322        pt->fY = SkDoubleToScalar(dst[index].y);
323    }
324    return (SkPath::Verb) (order - 1);
325}
326
327static bool QuadIsLinear(const SkPoint a[3]) {
328    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
329            {a[2].fX, a[2].fY}};
330    return isLinear(aQuad, 0, 2);
331}
332
333static bool CubicIsLinear(const SkPoint a[4]) {
334    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
335            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
336    return isLinear(aCubic, 0, 3);
337}
338
339static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
340    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
341    double x[2];
342    xy_at_t(aLine, startT, x[0], *(double*) 0);
343    xy_at_t(aLine, endT, x[1], *(double*) 0);
344    return SkMinScalar((float) x[0], (float) x[1]);
345}
346
347static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
348    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
349            {a[2].fX, a[2].fY}};
350    return (float) leftMostT(aQuad, startT, endT);
351}
352
353static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
354    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
355            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
356    return (float) leftMostT(aCubic, startT, endT);
357}
358
359static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
360    NULL,
361    LineLeftMost,
362    QuadLeftMost,
363    CubicLeftMost
364};
365
366#if DEBUG_UNUSED
367static bool IsCoincident(const SkPoint a[2], const SkPoint& above,
368        const SkPoint& below) {
369    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
370    const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
371    return implicit_matches_ulps(aLine, bLine, 32);
372}
373#endif
374
375class Segment;
376
377// sorting angles
378// given angles of {dx dy ddx ddy dddx dddy} sort them
379class Angle {
380public:
381    // FIXME: this is bogus for quads and cubics
382    // if the quads and cubics' line from end pt to ctrl pt are coincident,
383    // there's no obvious way to determine the curve ordering from the
384    // derivatives alone. In particular, if one quadratic's coincident tangent
385    // is longer than the other curve, the final control point can place the
386    // longer curve on either side of the shorter one.
387    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
388    // may provide some help, but nothing has been figured out yet.
389    bool operator<(const Angle& rh) const {
390        if ((fDy < 0) ^ (rh.fDy < 0)) {
391            return fDy < 0;
392        }
393        if (fDy == 0 && rh.fDy == 0 && fDx != rh.fDx) {
394            return fDx < rh.fDx;
395        }
396        SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy;
397        if (cmp) {
398            return cmp < 0;
399        }
400        if ((fDDy < 0) ^ (rh.fDDy < 0)) {
401            return fDDy < 0;
402        }
403        if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) {
404            return fDDx < rh.fDDx;
405        }
406        cmp = fDDx * rh.fDDy - rh.fDDx * fDDy;
407        if (cmp) {
408            return cmp < 0;
409        }
410        if ((fDDDy < 0) ^ (rh.fDDDy < 0)) {
411            return fDDDy < 0;
412        }
413        if (fDDDy == 0 && rh.fDDDy == 0) {
414            return fDDDx < rh.fDDDx;
415        }
416        return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy;
417    }
418
419    int end() const {
420        return fEnd;
421    }
422
423    // since all angles share a point, this needs to know which point
424    // is the common origin, i.e., whether the center is at pts[0] or pts[verb]
425    // practically, this should only be called by addAngle
426    void set(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
427            int start, int end) {
428        SkASSERT(start != end);
429        fSegment = segment;
430        fStart = start;
431        fEnd = end;
432        fDx = pts[1].fX - pts[0].fX; // b - a
433        fDy = pts[1].fY - pts[0].fY;
434        if (verb == SkPath::kLine_Verb) {
435            fDDx = fDDy = fDDDx = fDDDy = 0;
436            return;
437        }
438        fDDx = pts[2].fX - pts[1].fX - fDx; // a - 2b + c
439        fDDy = pts[2].fY - pts[1].fY - fDy;
440        if (verb == SkPath::kQuad_Verb) {
441            fDDDx = fDDDy = 0;
442            return;
443        }
444        fDDDx = pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX;
445        fDDDy = pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY;
446    }
447
448    // noncoincident quads/cubics may have the same initial angle
449    // as lines, so must sort by derivatives as well
450    // if flatness turns out to be a reasonable way to sort, use the below:
451    void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
452            int start, int end) {
453        fSegment = segment;
454        fStart = start;
455        fEnd = end;
456        fDx = pts[1].fX - pts[0].fX; // b - a
457        fDy = pts[1].fY - pts[0].fY;
458        if (verb == SkPath::kLine_Verb) {
459            fDDx = fDDy = fDDDx = fDDDy = 0;
460            return;
461        }
462        if (verb == SkPath::kQuad_Verb) {
463            int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx);
464            int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy);
465            int larger = std::max(abs(uplsX), abs(uplsY));
466            int shift = 0;
467            double flatT;
468            SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point)
469            LineParameters implicitLine;
470            _Line tangent = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}};
471            implicitLine.lineEndPoints(tangent);
472            implicitLine.normalize();
473            while (larger > UlpsEpsilon * 1024) {
474                larger >>= 2;
475                ++shift;
476                flatT = 0.5 / (1 << shift);
477                QuadXYAtT(pts, flatT, &ddPt);
478                _Point _pt = {ddPt.fX, ddPt.fY};
479                double distance = implicitLine.pointDistance(_pt);
480                if (approximately_zero(distance)) {
481                    SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance);
482                    break;
483                }
484            }
485            flatT = 0.5 / (1 << shift);
486            QuadXYAtT(pts, flatT, &ddPt);
487            fDDx = ddPt.fX - pts[0].fX;
488            fDDy = ddPt.fY - pts[0].fY;
489            SkASSERT(fDDx != 0 || fDDy != 0);
490            fDDDx = fDDDy = 0;
491            return;
492        }
493        SkASSERT(0); // FIXME: add cubic case
494    }
495
496    Segment* segment() const {
497        return fSegment;
498    }
499
500    int sign() const {
501        return SkSign32(fStart - fEnd);
502    }
503
504    bool slopeEquals(const Angle& rh) const {
505        return fDx == rh.fDx && fDy == rh.fDy;
506
507    }
508
509    int start() const {
510        return fStart;
511    }
512
513private:
514    SkScalar fDx;
515    SkScalar fDy;
516    SkScalar fDDx;
517    SkScalar fDDy;
518    SkScalar fDDDx;
519    SkScalar fDDDy;
520    Segment* fSegment;
521    int fStart;
522    int fEnd;
523};
524
525static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
526    int angleCount = angles.count();
527    int angleIndex;
528    angleList.setReserve(angleCount);
529    for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
530        *angleList.append() = &angles[angleIndex];
531    }
532    QSort<Angle>(angleList.begin(), angleList.end() - 1);
533}
534
535// Bounds, unlike Rect, does not consider a vertical line to be empty.
536struct Bounds : public SkRect {
537    static bool Intersects(const Bounds& a, const Bounds& b) {
538        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
539                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
540    }
541
542    bool isEmpty() {
543        return fLeft > fRight || fTop > fBottom
544                || fLeft == fRight && fTop == fBottom
545                || isnan(fLeft) || isnan(fRight)
546                || isnan(fTop) || isnan(fBottom);
547    }
548
549    void setCubicBounds(const SkPoint a[4]) {
550        _Rect dRect;
551        Cubic cubic  = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
552            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
553        dRect.setBounds(cubic);
554        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
555                (float) dRect.bottom);
556    }
557
558    void setQuadBounds(const SkPoint a[3]) {
559        const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
560                {a[2].fX, a[2].fY}};
561        _Rect dRect;
562        dRect.setBounds(quad);
563        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
564                (float) dRect.bottom);
565    }
566};
567
568struct Span {
569    double fT;
570    Segment* fOther;
571    double fOtherT; // value at fOther[fOtherIndex].fT
572    mutable SkPoint const * fPt; // lazily computed as needed
573    int fOtherIndex;  // can't be used during intersection
574    int fWinding; // accumulated from contours surrounding this one
575    // OPTIMIZATION: coincident needs only 2 bits (values are -1, 0, 1)
576    int fCoincident; // -1 start of coincidence, 0 no coincidence, 1 end
577    bool fDone; // if set, this span to next higher T has been processed
578};
579
580class Segment {
581public:
582    Segment() {
583#if DEBUG_DUMP
584        fID = ++gSegmentID;
585#endif
586    }
587
588    void addAngle(SkTDArray<Angle>& angles, int start, int end) {
589        SkASSERT(start != end);
590        int smaller = SkMin32(start, end);
591        if (fTs[smaller].fDone) {
592            return;
593        }
594        SkPoint edge[4];
595        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
596        Angle* angle = angles.append();
597        angle->set(edge, fVerb, this, start, end);
598    }
599
600    void addCubic(const SkPoint pts[4]) {
601        init(pts, SkPath::kCubic_Verb);
602        fBounds.setCubicBounds(pts);
603    }
604
605    void addCurveTo(int start, int end, SkPath& path) {
606        SkPoint edge[4];
607        (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
608    #if DEBUG_PATH_CONSTRUCTION
609        SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
610                kLVerbStr[fVerb], edge[1].fX, edge[1].fY);
611        if (fVerb > 1) {
612            SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY);
613        }
614        if (fVerb > 2) {
615            SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY);
616        }
617        SkDebugf("\n");
618    #endif
619        switch (fVerb) {
620            case SkPath::kLine_Verb:
621                path.lineTo(edge[1].fX, edge[1].fY);
622                break;
623            case SkPath::kQuad_Verb:
624                path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY);
625                break;
626            case SkPath::kCubic_Verb:
627                path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY,
628                        edge[3].fX, edge[3].fY);
629                break;
630        }
631    }
632
633    void addLine(const SkPoint pts[2]) {
634        init(pts, SkPath::kLine_Verb);
635        fBounds.set(pts, 2);
636    }
637
638    void addMoveTo(int tIndex, SkPath& path) {
639        const SkPoint& pt = xyAtT(&fTs[tIndex]);
640    #if DEBUG_PATH_CONSTRUCTION
641        SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
642    #endif
643        path.moveTo(pt.fX, pt.fY);
644    }
645
646    // add 2 to edge or out of range values to get T extremes
647    void addOtherT(int index, double otherT, int otherIndex) {
648        Span& span = fTs[index];
649        span.fOtherT = otherT;
650        span.fOtherIndex = otherIndex;
651    }
652
653    void addQuad(const SkPoint pts[3]) {
654        init(pts, SkPath::kQuad_Verb);
655        fBounds.setQuadBounds(pts);
656    }
657
658    // edges are sorted by T, then by coincidence
659    int addT(double newT, Segment& other, int coincident) {
660        // FIXME: in the pathological case where there is a ton of intercepts,
661        //  binary search?
662        int insertedAt = -1;
663        Span* span;
664        size_t tCount = fTs.count();
665        for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
666            // OPTIMIZATION: if there are three or more identical Ts, then
667            // the fourth and following could be further insertion-sorted so
668            // that all the edges are clockwise or counterclockwise.
669            // This could later limit segment tests to the two adjacent
670            // neighbors, although it doesn't help with determining which
671            // circular direction to go in.
672            if (newT < fTs[idx2].fT || (newT == fTs[idx2].fT &&
673                    coincident <= fTs[idx2].fCoincident)) {
674                insertedAt = idx2;
675                span = fTs.insert(idx2);
676                goto finish;
677            }
678        }
679        insertedAt = tCount;
680        span = fTs.append();
681finish:
682        span->fT = newT;
683        span->fOther = &other;
684        span->fPt = NULL;
685        span->fWinding = 0;
686        if (span->fDone = newT == 1) {
687            ++fDoneSpans;
688        }
689        span->fCoincident = coincident;
690        fCoincident |= coincident; // OPTIMIZATION: ever used?
691        return insertedAt;
692    }
693
694    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) {
695        // add edge leading into junction
696        addAngle(angles, end, start);
697        // add edge leading away from junction
698        int step = SkSign32(end - start);
699        int tIndex = nextSpan(end, step);
700        if (tIndex >= 0) {
701            addAngle(angles, end, tIndex);
702        }
703    }
704
705    const Bounds& bounds() const {
706        return fBounds;
707    }
708
709    void buildAngles(int index, SkTDArray<Angle>& angles) const {
710        SkASSERT(!done());
711        double referenceT = fTs[index].fT;
712        int lesser = index;
713        while (--lesser >= 0 && referenceT == fTs[lesser].fT) {
714            buildAnglesInner(lesser, angles);
715        }
716        do {
717            buildAnglesInner(index, angles);
718        } while (++index < fTs.count() && referenceT == fTs[index].fT);
719    }
720
721    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
722        Span* span = &fTs[index];
723        Segment* other = span->fOther;
724        if (other->done()) {
725            return;
726        }
727    // if there is only one live crossing, and no coincidence, continue
728    // in the same direction
729    // if there is coincidence, the only choice may be to reverse direction
730        // find edge on either side of intersection
731        int oIndex = span->fOtherIndex;
732        // if done == -1, prior span has already been processed
733        int step = 1;
734        int next = other->nextSpanEnd(oIndex, step);
735        if (next < 0) {
736            step = -step;
737            next = other->nextSpanEnd(oIndex, step);
738        }
739        oIndex = other->coincidentEnd(oIndex, -step);
740        // add candidate into and away from junction
741        other->addTwoAngles(next, oIndex, angles);
742    }
743
744    // figure out if the segment's ascending T goes clockwise or not
745    // not enough context to write this as shown
746    // instead, add all segments meeting at the top
747    // sort them using buildAngleList
748    // find the first in the sort
749    // see if ascendingT goes to top
750    bool clockwise(int /* tIndex */) const {
751        SkASSERT(0); // incomplete
752        return false;
753    }
754
755    static bool Coincident(const Angle* current, const Angle* next) {
756        const Segment* segment = current->segment();
757        const Span& span = segment->fTs[current->start()];
758        if (!span.fCoincident) {
759            return false;
760        }
761        const Segment* nextSegment = next->segment();
762        const Span& nextSpan = nextSegment->fTs[next->start()];
763        if (!nextSpan.fCoincident) {
764            return false;
765        }
766        // use angle dx/dy instead of other since 3 or more may be coincident
767        return current->slopeEquals(*next);
768    }
769
770    static bool CoincidentCancels(const Angle* current, const Angle* next) {
771        return SkSign32(current->start() - current->end())
772                != SkSign32(next->start() - next->end());
773    }
774
775    int coincidentEnd(int from, int step) const {
776        double fromT = fTs[from].fT;
777        int count = fTs.count();
778        int to = from;
779        while (step > 0 ? ++to < count : --to >= 0) {
780            const Span& span = fTs[to];
781            if (fromT != span.fT) {
782                // FIXME: we assume that if the T changes, we don't care about
783                // coincident -- but in nextSpan, we require that both the T
784                // and actual loc change to represent a span. This asymettry may
785                // be OK or may be trouble -- if trouble, probably will need to
786                // detect coincidence earlier or sort differently
787                break;
788            }
789            if (span.fCoincident == step) {
790                return to;
791            }
792            SkASSERT(step > 0 || !span.fDone);
793        }
794        return from;
795    }
796
797    bool done() const {
798        SkASSERT(fDoneSpans <= fTs.count());
799        return fDoneSpans == fTs.count();
800    }
801
802    // start is the index of the beginning T of this edge
803    // it is guaranteed to have an end which describes a non-zero length (?)
804    // winding -1 means ccw, 1 means cw
805    // step is in/out -1 or 1
806    // spanIndex is returned
807    Segment* findNext(int winding, const int startIndex, const int endIndex,
808            int& nextStart, int& nextEnd) {
809        SkASSERT(startIndex != endIndex);
810        int count = fTs.count();
811        SkASSERT(startIndex < endIndex ? startIndex < count - 1
812                : startIndex > 0);
813        // FIXME:
814        // since Ts can be stepped either way, done markers must be careful
815        // not to assume that segment was only ascending in T. This shouldn't
816        // be a problem unless pathologically a segment can be partially
817        // ascending and partially descending -- maybe quads/cubic can do this?
818
819
820        int step = SkSign32(endIndex - startIndex);
821        int end = nextSpanEnd(startIndex, step);
822        SkASSERT(end >= 0);
823
824        // preflight for coincidence -- if present, it may change winding
825        // considerations and whether reversed edges can be followed
826
827        // Discard opposing direction candidates if no coincidence was found.
828        Span* endSpan = &fTs[end];
829        Segment* other;
830        if (isSimple(end, step)) {
831        // mark the smaller of startIndex, endIndex done, and all adjacent
832        // spans with the same T value (but not 'other' spans)
833            markDone(SkMin32(startIndex, endIndex), winding);
834            // move in winding direction until edge in correct direction
835            // balance wrong direction edges before finding correct one
836            // this requres that the intersection is angularly sorted
837            // for a single intersection, special case -- choose the opposite
838            // edge that steps the same
839            other = endSpan->fOther;
840            nextStart = endSpan->fOtherIndex;
841            nextEnd = nextStart + step;
842            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
843            return other;
844        }
845        // more than one viable candidate -- measure angles to find best
846        SkTDArray<Angle> angles;
847        SkASSERT(startIndex - endIndex != 0);
848        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
849        addTwoAngles(startIndex, end, angles);
850        buildAngles(end, angles);
851        SkTDArray<Angle*> sorted;
852        sortAngles(angles, sorted);
853        // find the starting edge
854        int firstIndex = -1;
855        int angleCount = angles.count();
856        int angleIndex;
857        const Angle* angle;
858        for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
859            angle = sorted[angleIndex];
860            if (angle->segment() == this && angle->start() == end &&
861                    angle->end() == startIndex) {
862                firstIndex = angleIndex;
863                break;
864            }
865        }
866
867    // put some thought into handling coincident edges
868    // 1) defer the initial moveTo/curveTo until we know that firstIndex
869    //    isn't coincident (although maybe findTop could tell us that)
870    // 2) allow the below to mark and skip coincident pairs
871    // 3) return something (null?) if all segments cancel each other out
872    // 4) if coincident edges don't cancel, figure out which to return (follow)
873
874        SkASSERT(firstIndex >= 0);
875        int startWinding = winding;
876        int nextIndex = firstIndex;
877        const Angle* nextAngle;
878        Segment* nextSegment;
879        do {
880            if (++nextIndex == angleCount) {
881                nextIndex = 0;
882            }
883            SkASSERT(nextIndex != firstIndex); // should never wrap around
884            nextAngle = sorted[nextIndex];
885            nextSegment = nextAngle->segment();
886            bool pairCoincides = Coincident(angle, nextAngle);
887            int maxWinding = winding;
888            winding -= nextAngle->sign();
889            if (!winding) {
890                if (!pairCoincides || !CoincidentCancels(angle, nextAngle)) {
891                    break;
892                }
893                markAndChaseCoincident(startIndex, endIndex, nextSegment);
894                return NULL;
895            }
896            if (pairCoincides) {
897                bool markNext = abs(maxWinding) < abs(winding);
898                if (markNext) {
899                    nextSegment->markDone(SkMin32(nextAngle->start(),
900                            nextAngle->end()), winding);
901                } else {
902                    angle->segment()->markDone(SkMin32(angle->start(),
903                            angle->end()), maxWinding);
904                }
905            }
906            // if the winding is non-zero, nextAngle does not connect to
907            // current chain. If we haven't done so already, mark the angle
908            // as done, record the winding value, and mark connected unambiguous
909            // segments as well.
910            else if (nextSegment->winding(nextAngle) == 0) {
911                if (abs(maxWinding) < abs(winding)) {
912                    maxWinding = winding;
913                }
914                nextSegment->markAndChaseWinding(nextAngle, maxWinding);
915            }
916            angle = nextAngle;
917        } while (true);
918        markDone(SkMin32(startIndex, endIndex), startWinding);
919        nextStart = nextAngle->start();
920        nextEnd = nextAngle->end();
921        return nextSegment;
922    }
923
924
925        // so the span needs to contain the pairing info found here
926        // this should include the winding computed for the edge, and
927        //  what edge it connects to, and whether it is discarded
928        //  (maybe discarded == abs(winding) > 1) ?
929        // only need derivatives for duration of sorting, add a new struct
930        // for pairings, remove extra spans that have zero length and
931        //  reference an unused other
932        // for coincident, the last span on the other may be marked done
933        //  (always?)
934
935        // if loop is exhausted, contour may be closed.
936        // FIXME: pass in close point so we can check for closure
937
938        // given a segment, and a sense of where 'inside' is, return the next
939        // segment. If this segment has an intersection, or ends in multiple
940        // segments, find the mate that continues the outside.
941        // note that if there are multiples, but no coincidence, we can limit
942        // choices to connections in the correct direction
943
944        // mark found segments as done
945
946    // FIXME: this is tricky code; needs its own unit test
947    void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered
948        int count = fTs.count();
949        if (count < 3) { // require t=0, x, 1 at minimum
950            return;
951        }
952        int matchIndex = 0;
953        int moCount;
954        Span* match;
955        Segment* mOther;
956        do {
957            match = &fTs[matchIndex];
958            mOther = match->fOther;
959            moCount = mOther->fTs.count();
960            if (moCount >= 3) {
961                break;
962            }
963            if (++matchIndex >= count) {
964                return;
965            }
966        } while (true); // require t=0, x, 1 at minimum
967        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
968        const SkPoint* matchPt = &xyAtT(match);
969        // look for a pair of nearby T values that map to the same (x,y) value
970        // if found, see if the pair of other segments share a common point. If
971        // so, the span from here to there is coincident.
972        for (int index = matchIndex + 1; index < count; ++index) {
973            Span* test = &fTs[index];
974            if (test->fCoincident) {
975                continue;
976            }
977            Segment* tOther = test->fOther;
978            int toCount = tOther->fTs.count();
979            if (toCount < 3) { // require t=0, x, 1 at minimum
980                continue;
981            }
982            const SkPoint* testPt = &xyAtT(test);
983            if (*matchPt != *testPt) {
984                matchIndex = index;
985                moCount = toCount;
986                match = test;
987                mOther = tOther;
988                matchPt = testPt;
989                continue;
990            }
991            int moStart = -1;
992            int moEnd = -1;
993            double moStartT, moEndT;
994            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
995                Span& moSpan = mOther->fTs[moIndex];
996                if (moSpan.fCoincident) {
997                    continue;
998                }
999                if (moSpan.fOther == this) {
1000                    if (moSpan.fOtherT == match->fT) {
1001                        moStart = moIndex;
1002                        moStartT = moSpan.fT;
1003                    }
1004                    continue;
1005                }
1006                if (moSpan.fOther == tOther) {
1007                    SkASSERT(moEnd == -1);
1008                    moEnd = moIndex;
1009                    moEndT = moSpan.fT;
1010                }
1011            }
1012            if (moStart < 0 || moEnd < 0) {
1013                continue;
1014            }
1015            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
1016            if (moStartT == moEndT) {
1017                continue;
1018            }
1019            int toStart = -1;
1020            int toEnd = -1;
1021            double toStartT, toEndT;
1022            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
1023                Span& toSpan = tOther->fTs[toIndex];
1024                if (toSpan.fOther == this) {
1025                    if (toSpan.fOtherT == test->fT) {
1026                        toStart = toIndex;
1027                        toStartT = toSpan.fT;
1028                    }
1029                    continue;
1030                }
1031                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
1032                    SkASSERT(toEnd == -1);
1033                    toEnd = toIndex;
1034                    toEndT = toSpan.fT;
1035                }
1036            }
1037            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
1038            if (toStart <= 0 || toEnd <= 0) {
1039                continue;
1040            }
1041            if (toStartT == toEndT) {
1042                continue;
1043            }
1044            // test to see if the segment between there and here is linear
1045            if (!mOther->isLinear(moStart, moEnd)
1046                    || !tOther->isLinear(toStart, toEnd)) {
1047                continue;
1048            }
1049            // FIXME: may need to resort if we depend on coincidence first, last
1050            mOther->fTs[moStart].fCoincident = -1;
1051            tOther->fTs[toStart].fCoincident = -1;
1052            mOther->fTs[moEnd].fCoincident = 1;
1053            tOther->fTs[toEnd].fCoincident = 1;
1054        }
1055    }
1056
1057    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
1058    // and use more concise logic like the old edge walker code?
1059    // FIXME: this needs to deal with coincident edges
1060    Segment* findTop(int& tIndex, int& endIndex) {
1061        // iterate through T intersections and return topmost
1062        // topmost tangent from y-min to first pt is closer to horizontal
1063        int firstT = 0;
1064        int lastT = 0;
1065        int firstCoinT = 0;
1066        SkScalar topY = fPts[0].fY;
1067        int count = fTs.count();
1068        int index;
1069        for (index = 1; index < count; ++index) {
1070            const Span& span = fTs[index];
1071            double t = span.fT;
1072            SkScalar yIntercept = t == 1 ? fPts[fVerb].fY : yAtT(t);
1073            if (topY > yIntercept) {
1074                topY = yIntercept;
1075                firstT = lastT = firstCoinT = index;
1076            } else if (topY == yIntercept) {
1077                lastT = index;
1078                if (span.fCoincident) {
1079                    firstCoinT = index;
1080                }
1081            }
1082        }
1083        // if there's only a pair of segments, go with the endpoint chosen above
1084        if (firstT == lastT) {
1085            tIndex = firstT;
1086            endIndex = firstT > 0 ? tIndex - 1 : tIndex + 1;
1087            return this;
1088        }
1089        // sort the edges to find the leftmost
1090        int step = 1;
1091        int end = nextSpan(firstT, step);
1092        if (end == -1) {
1093            step = -1;
1094            end = nextSpan(firstT, step);
1095            SkASSERT(end != -1);
1096        }
1097        // if the topmost T is not on end, or is three-way or more, find left
1098        // look for left-ness from tLeft to firstT (matching y of other)
1099        SkTDArray<Angle> angles;
1100        SkASSERT(firstT - end != 0);
1101        addTwoAngles(end, firstCoinT, angles);
1102        buildAngles(firstT, angles);
1103        SkTDArray<Angle*> sorted;
1104        sortAngles(angles, sorted);
1105        Segment* leftSegment = sorted[0]->segment();
1106        tIndex = sorted[0]->end();
1107        endIndex = sorted[0]->start();
1108        return leftSegment;
1109    }
1110
1111    // FIXME: not crazy about this
1112    // when the intersections are performed, the other index is into an
1113    // incomplete array. as the array grows, the indices become incorrect
1114    // while the following fixes the indices up again, it isn't smart about
1115    // skipping segments whose indices are already correct
1116    // assuming we leave the code that wrote the index in the first place
1117    void fixOtherTIndex() {
1118        int iCount = fTs.count();
1119        for (int i = 0; i < iCount; ++i) {
1120            Span& iSpan = fTs[i];
1121            double oT = iSpan.fOtherT;
1122            Segment* other = iSpan.fOther;
1123            int oCount = other->fTs.count();
1124            for (int o = 0; o < oCount; ++o) {
1125                Span& oSpan = other->fTs[o];
1126                if (oT == oSpan.fT && this == oSpan.fOther) {
1127                    iSpan.fOtherIndex = o;
1128                }
1129            }
1130        }
1131    }
1132
1133    // OPTIMIZATION: uses tail recursion. Unwise?
1134    void innerCoincidentChase(int step, Segment* other) {
1135        // find other at index
1136        SkASSERT(!done());
1137        const Span* start = NULL;
1138        const Span* end = NULL;
1139        int index, startIndex, endIndex;
1140        int count = fTs.count();
1141        for (index = 0; index < count; ++index) {
1142            const Span& span = fTs[index];
1143            if (!span.fCoincident || span.fOther != other) {
1144                continue;
1145            }
1146            if (!start) {
1147                if (span.fDone) {
1148                    continue;
1149                }
1150                startIndex = index;
1151                start = &span;
1152            } else {
1153                SkASSERT(!end);
1154                endIndex = index;
1155                end = &span;
1156            }
1157        }
1158        if (!end) {
1159            return;
1160        }
1161        Segment* next;
1162        Segment* nextOther;
1163        if (step < 0) {
1164            next = start->fT == 0 ? NULL : this;
1165            nextOther = other->fTs[start->fOtherIndex].fT == 1 ? NULL : other;
1166        } else {
1167            next = end->fT == 1 ? NULL : this;
1168            nextOther = other->fTs[end->fOtherIndex].fT == 0 ? NULL : other;
1169        }
1170        SkASSERT(!next || !nextOther);
1171        for (index = 0; index < count; ++index) {
1172            const Span& span = fTs[index];
1173            if (span.fCoincident || span.fOther == other) {
1174                continue;
1175            }
1176            bool checkNext = !next && (step < 0 ? span.fT == 0
1177                && span.fOtherT == 1 : span.fT == 1 && span.fOtherT == 0);
1178            bool checkOther = !nextOther && (step < 0 ? span.fT == start->fT
1179                && span.fOtherT == 0 : span.fT == end->fT && span.fOtherT == 1);
1180            if (!checkNext && !checkOther) {
1181                continue;
1182            }
1183            Segment* oSegment = span.fOther;
1184            if (oSegment->done()) {
1185                continue;
1186            }
1187            int oCount = oSegment->fTs.count();
1188            for (int oIndex = 0; oIndex < oCount; ++oIndex) {
1189                const Span& oSpan = oSegment->fTs[oIndex];
1190                if (oSpan.fT > 0 && oSpan.fT < 1) {
1191                    continue;
1192                }
1193                if (!oSpan.fCoincident) {
1194                    continue;
1195                }
1196                if (checkNext && (oSpan.fT == 0 ^ step < 0)) {
1197                    next = oSegment;
1198                    checkNext = false;
1199                }
1200                if (checkOther && (oSpan.fT == 1 ^ step < 0)) {
1201                    nextOther = oSegment;
1202                    checkOther = false;
1203                }
1204            }
1205        }
1206        markDone(SkMin32(startIndex, endIndex), 0);
1207        other->markDone(SkMin32(start->fOtherIndex, end->fOtherIndex), 0);
1208        if (next && nextOther) {
1209            next->innerCoincidentChase(step, nextOther);
1210        }
1211    }
1212
1213    // OPTIMIZATION: uses tail recursion. Unwise?
1214    void innerChase(int index, int step, int winding) {
1215        int end = nextSpan(index, step);
1216        bool many;
1217        lastSpan(end, step, &many);
1218        if (many) {
1219            return;
1220        }
1221        Span* endSpan = &fTs[end];
1222        Segment* other = endSpan->fOther;
1223        index = endSpan->fOtherIndex;
1224        int otherEnd = other->nextSpan(index, step);
1225        other->innerChase(index, step, winding);
1226        other->markDone(SkMin32(index, otherEnd), winding);
1227    }
1228
1229    void init(const SkPoint pts[], SkPath::Verb verb) {
1230        fPts = pts;
1231        fVerb = verb;
1232        fDoneSpans = 0;
1233        fCoincident = 0;
1234    }
1235
1236    bool intersected() const {
1237        return fTs.count() > 0;
1238    }
1239
1240    bool isLinear(int start, int end) const {
1241        if (fVerb == SkPath::kLine_Verb) {
1242            return true;
1243        }
1244        if (fVerb == SkPath::kQuad_Verb) {
1245            SkPoint qPart[3];
1246            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
1247            return QuadIsLinear(qPart);
1248        } else {
1249            SkASSERT(fVerb == SkPath::kCubic_Verb);
1250            SkPoint cPart[4];
1251            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
1252            return CubicIsLinear(cPart);
1253        }
1254    }
1255
1256    bool isSimple(int index, int step) const {
1257        int count = fTs.count();
1258        if (count == 2) {
1259            return true;
1260        }
1261       double spanT = fTs[index].fT;
1262        if (spanT > 0 && spanT < 1) {
1263            return false;
1264        }
1265        if (step < 0) {
1266            const Span& secondSpan = fTs[1];
1267            if (secondSpan.fT == 0) {
1268                return false;
1269            }
1270            return xyAtT(&fTs[0]) != xyAtT(&secondSpan);
1271        }
1272        const Span& penultimateSpan = fTs[count - 2];
1273        if (penultimateSpan.fT == 1) {
1274            return false;
1275        }
1276        return xyAtT(&fTs[count - 1]) != xyAtT(&penultimateSpan);
1277    }
1278
1279    bool isHorizontal() const {
1280        return fBounds.fTop == fBounds.fBottom;
1281    }
1282
1283    bool isVertical() const {
1284        return fBounds.fLeft == fBounds.fRight;
1285    }
1286
1287    // last does not check for done spans because done is only set for the start
1288    int lastSpan(int end, int step, bool* manyPtr = NULL) const {
1289        int last = end;
1290        int count = fTs.count();
1291        int found = 0;
1292        const Span& endSpan = fTs[end];
1293        double endT = endSpan.fT;
1294        do {
1295            end = last;
1296            if (step > 0 ? ++last >= count : --last < 0) {
1297                break;
1298            }
1299            const Span& lastSpan = fTs[last];
1300            if (lastSpan.fT == endT) {
1301                ++found;
1302                continue;
1303            }
1304            const SkPoint& lastLoc = xyAtT(&lastSpan);
1305            const SkPoint& endLoc = xyAtT(&endSpan);
1306            if (endLoc != lastLoc) {
1307                break;
1308            }
1309            ++found;
1310        } while (true);
1311        if (manyPtr) {
1312            *manyPtr = found > 0;
1313        }
1314        return end;
1315    }
1316
1317    SkScalar leftMost(int start, int end) const {
1318        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
1319    }
1320
1321    void markAndChaseCoincident(int index, int endIndex, Segment* other) {
1322        int step = SkSign32(endIndex - index);
1323        innerCoincidentChase(step, other);
1324    }
1325
1326    // this span is excluded by the winding rule -- chase the ends
1327    // as long as they are unambiguous to mark connections as done
1328    // and give them the same winding value
1329    void markAndChaseWinding(const Angle* angle, int winding) {
1330        int index = angle->start();
1331        int endIndex = angle->end();
1332        int step = SkSign32(endIndex - index);
1333        innerChase(index, step, winding);
1334        markDone(SkMin32(index, endIndex), winding);
1335    }
1336
1337    // FIXME: this should also mark spans with equal (x,y)
1338    void markDone(int index, int winding) {
1339        SkASSERT(!done());
1340        double referenceT = fTs[index].fT;
1341        int lesser = index;
1342        while (--lesser >= 0 && referenceT == fTs[lesser].fT) {
1343            Span& span = fTs[lesser];
1344            SkASSERT(!span.fDone);
1345            fTs[lesser].fDone = true;
1346            SkASSERT(!span.fWinding || span.fWinding == winding);
1347            span.fWinding = winding;
1348            fDoneSpans++;
1349        }
1350        do {
1351            Span& span = fTs[index];
1352            SkASSERT(!span.fDone);
1353            span.fDone = true;
1354            SkASSERT(!span.fWinding || span.fWinding == winding);
1355            span.fWinding = winding;
1356            fDoneSpans++;
1357        } while (++index < fTs.count() && referenceT == fTs[index].fT);
1358    }
1359
1360    // note the assert logic looks for unexpected done of span start
1361    // This has callers for two different situations: one establishes the end
1362    // of the current span, and one establishes the beginning of the next span
1363    // (thus the name). When this is looking for the end of the current span,
1364    // coincidence is found when the beginning Ts contain -step and the end
1365    // contains step. When it is looking for the beginning of the next, the
1366    // first Ts found can be ignored and the last Ts should contain -step.
1367
1368    int nextSpan(int from, int step) const {
1369        SkASSERT(!done());
1370        const Span& fromSpan = fTs[from];
1371        int count = fTs.count();
1372        int to = from;
1373        while (step > 0 ? ++to < count : --to >= 0) {
1374            const Span& span = fTs[to];
1375            if (fromSpan.fT == span.fT) {
1376                continue;
1377            }
1378            const SkPoint& loc = xyAtT(&span);
1379            const SkPoint& fromLoc = xyAtT(&fromSpan);
1380            if (fromLoc == loc) {
1381                continue;
1382            }
1383            SkASSERT(step < 0 || !fromSpan.fDone);
1384            SkASSERT(step > 0 || !span.fDone);
1385            return to;
1386        }
1387        return -1;
1388    }
1389
1390    // once past current span, if step>0, look for coicident==1
1391    // if step<0, look for coincident==-1
1392    int nextSpanEnd(int from, int step) const {
1393        int result = nextSpan(from, step);
1394        if (result < 0) {
1395            return result;
1396        }
1397        return coincidentEnd(result, step);
1398    }
1399
1400    const SkPoint* pts() const {
1401        return fPts;
1402    }
1403
1404    void reset() {
1405        init(NULL, (SkPath::Verb) -1);
1406        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1407        fTs.reset();
1408    }
1409
1410    // OPTIMIZATION: mark as debugging only if used solely by tests
1411    const Span& span(int tIndex) const {
1412        return fTs[tIndex];
1413    }
1414
1415    // OPTIMIZATION: mark as debugging only if used solely by tests
1416    double t(int tIndex) const {
1417        return fTs[tIndex].fT;
1418    }
1419
1420    void updatePts(const SkPoint pts[]) {
1421        fPts = pts;
1422    }
1423
1424    SkPath::Verb verb() const {
1425        return fVerb;
1426    }
1427
1428    bool winding(const Angle* angle) {
1429        int start = angle->start();
1430        int end = angle->end();
1431        int index = SkMin32(start, end);
1432        Span& span = fTs[index];
1433        return span.fWinding;
1434    }
1435
1436    SkScalar xAtT(double t) const {
1437        SkASSERT(t >= 0 && t <= 1);
1438        return (*SegmentXAtT[fVerb])(fPts, t);
1439    }
1440
1441    const SkPoint& xyAtT(const Span* span) const {
1442        if (!span->fPt) {
1443            if (span->fT == 0) {
1444                span->fPt = &fPts[0];
1445            } else if (span->fT == 1) {
1446                span->fPt = &fPts[fVerb];
1447            } else {
1448                SkPoint* pt = fIntersections.append();
1449                (*SegmentXYAtT[fVerb])(fPts, span->fT, pt);
1450                span->fPt = pt;
1451            }
1452        }
1453        return *span->fPt;
1454    }
1455
1456    SkScalar yAtT(double t) const {
1457        SkASSERT(t >= 0 && t <= 1);
1458        return (*SegmentYAtT[fVerb])(fPts, t);
1459    }
1460
1461#if DEBUG_DUMP
1462    void dump() const {
1463        const char className[] = "Segment";
1464        const int tab = 4;
1465        for (int i = 0; i < fTs.count(); ++i) {
1466            SkPoint out;
1467            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
1468            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
1469                    " otherT=%1.9g winding=%d\n",
1470                    tab + sizeof(className), className, fID,
1471                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
1472                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding);
1473        }
1474        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
1475                tab + sizeof(className), className, fID,
1476                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
1477    }
1478#endif
1479
1480private:
1481    const SkPoint* fPts;
1482    SkPath::Verb fVerb;
1483    Bounds fBounds;
1484    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
1485    // OPTIMIZATION:if intersections array is a pointer, the it could only
1486    // be allocated as needed instead of always initialized -- though maybe
1487    // the initialization is lightweight enough that it hardly matters
1488    mutable SkTDArray<SkPoint> fIntersections;
1489    // FIXME: coincident only needs two bits (-1, 0, 1)
1490    int fCoincident; // non-zero if some coincident span inside
1491    int fDoneSpans; // used for quick check that segment is finished
1492#if DEBUG_DUMP
1493    int fID;
1494#endif
1495};
1496
1497class Contour {
1498public:
1499    Contour() {
1500        reset();
1501#if DEBUG_DUMP
1502        fID = ++gContourID;
1503#endif
1504    }
1505
1506    bool operator<(const Contour& rh) const {
1507        return fBounds.fTop == rh.fBounds.fTop
1508                ? fBounds.fLeft < rh.fBounds.fLeft
1509                : fBounds.fTop < rh.fBounds.fTop;
1510    }
1511
1512    void addCubic(const SkPoint pts[4]) {
1513        fSegments.push_back().addCubic(pts);
1514        fContainsCurves = true;
1515    }
1516
1517    int addLine(const SkPoint pts[2]) {
1518        fSegments.push_back().addLine(pts);
1519        return fSegments.count();
1520    }
1521
1522    int addQuad(const SkPoint pts[3]) {
1523        fSegments.push_back().addQuad(pts);
1524        fContainsCurves = true;
1525        return fSegments.count();
1526    }
1527
1528    const Bounds& bounds() const {
1529        return fBounds;
1530    }
1531
1532    void complete() {
1533        setBounds();
1534        fContainsIntercepts = false;
1535    }
1536
1537    void containsIntercepts() {
1538        fContainsIntercepts = true;
1539    }
1540
1541    void findTooCloseToCall(int winding) {
1542        int segmentCount = fSegments.count();
1543        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
1544            fSegments[sIndex].findTooCloseToCall(winding);
1545        }
1546    }
1547
1548    void fixOtherTIndex() {
1549        int segmentCount = fSegments.count();
1550        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
1551            fSegments[sIndex].fixOtherTIndex();
1552        }
1553    }
1554
1555    void reset() {
1556        fSegments.reset();
1557        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1558        fContainsCurves = fContainsIntercepts = false;
1559    }
1560
1561    // OPTIMIZATION: feel pretty uneasy about this. It seems like once again
1562    // we need to sort and walk edges in y, but that on the surface opens the
1563    // same can of worms as before. But then, this is a rough sort based on
1564    // segments' top, and not a true sort, so it could be ameniable to regular
1565    // sorting instead of linear searching. Still feel like I'm missing something
1566    Segment* topSegment() {
1567        int segmentCount = fSegments.count();
1568        SkASSERT(segmentCount > 0);
1569        int best = -1;
1570        Segment* bestSegment = NULL;
1571        while (++best < segmentCount) {
1572            Segment* testSegment = &fSegments[best];
1573            if (testSegment->done()) {
1574                continue;
1575            }
1576            bestSegment = testSegment;
1577            break;
1578        }
1579        if (!bestSegment) {
1580            return NULL;
1581        }
1582        SkScalar bestTop = bestSegment->bounds().fTop;
1583        for (int test = best + 1; test < segmentCount; ++test) {
1584            Segment* testSegment = &fSegments[test];
1585            if (testSegment->done()) {
1586                continue;
1587            }
1588            SkScalar testTop = testSegment->bounds().fTop;
1589            if (bestTop > testTop) {
1590                bestTop = testTop;
1591                bestSegment = testSegment;
1592            }
1593        }
1594        return bestSegment;
1595    }
1596
1597#if DEBUG_DUMP
1598    void dump() {
1599        int i;
1600        const char className[] = "Contour";
1601        const int tab = 4;
1602        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
1603        for (i = 0; i < fSegments.count(); ++i) {
1604            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
1605                    className, i);
1606            fSegments[i].dump();
1607        }
1608        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
1609                tab + sizeof(className), className,
1610                fBounds.fLeft, fBounds.fTop,
1611                fBounds.fRight, fBounds.fBottom);
1612        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
1613                className, fContainsIntercepts);
1614        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
1615                className, fContainsCurves);
1616    }
1617#endif
1618
1619protected:
1620    void setBounds() {
1621        int count = fSegments.count();
1622        if (count == 0) {
1623            SkDebugf("%s empty contour\n", __FUNCTION__);
1624            SkASSERT(0);
1625            // FIXME: delete empty contour?
1626            return;
1627        }
1628        fBounds = fSegments.front().bounds();
1629        for (int index = 1; index < count; ++index) {
1630            fBounds.growToInclude(fSegments[index].bounds());
1631        }
1632    }
1633
1634public:
1635    SkTArray<Segment> fSegments; // not worth accessor functions?
1636
1637private:
1638    Bounds fBounds;
1639    bool fContainsIntercepts;
1640    bool fContainsCurves;
1641#if DEBUG_DUMP
1642    int fID;
1643#endif
1644};
1645
1646class EdgeBuilder {
1647public:
1648
1649EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
1650    : fPath(path)
1651    , fCurrentContour(NULL)
1652    , fContours(contours)
1653{
1654#if DEBUG_DUMP
1655    gContourID = 0;
1656    gSegmentID = 0;
1657#endif
1658    walk();
1659}
1660
1661protected:
1662
1663void complete() {
1664    if (fCurrentContour && fCurrentContour->fSegments.count()) {
1665        fCurrentContour->complete();
1666        fCurrentContour = NULL;
1667    }
1668}
1669
1670void walk() {
1671    // FIXME:remove once we can access path pts directly
1672    SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed
1673    SkPoint pts[4];
1674    SkPath::Verb verb;
1675    do {
1676        verb = iter.next(pts);
1677        *fPathVerbs.append() = verb;
1678        if (verb == SkPath::kMove_Verb) {
1679            *fPathPts.append() = pts[0];
1680        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
1681            fPathPts.append(verb, &pts[1]);
1682        }
1683    } while (verb != SkPath::kDone_Verb);
1684    // FIXME: end of section to remove once path pts are accessed directly
1685
1686    SkPath::Verb reducedVerb;
1687    uint8_t* verbPtr = fPathVerbs.begin();
1688    const SkPoint* pointsPtr = fPathPts.begin();
1689    const SkPoint* finalCurveStart = NULL;
1690    const SkPoint* finalCurveEnd = NULL;
1691    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
1692        switch (verb) {
1693            case SkPath::kMove_Verb:
1694                complete();
1695                if (!fCurrentContour) {
1696                    fCurrentContour = fContours.push_back_n(1);
1697                    finalCurveEnd = pointsPtr++;
1698                    *fExtra.append() = -1; // start new contour
1699                }
1700                continue;
1701            case SkPath::kLine_Verb:
1702                // skip degenerate points
1703                if (pointsPtr[-1].fX != pointsPtr[0].fX
1704                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
1705                    fCurrentContour->addLine(&pointsPtr[-1]);
1706                }
1707                break;
1708            case SkPath::kQuad_Verb:
1709
1710                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
1711                if (reducedVerb == 0) {
1712                    break; // skip degenerate points
1713                }
1714                if (reducedVerb == 1) {
1715                    *fExtra.append() =
1716                            fCurrentContour->addLine(fReducePts.end() - 2);
1717                    break;
1718                }
1719                fCurrentContour->addQuad(&pointsPtr[-1]);
1720                break;
1721            case SkPath::kCubic_Verb:
1722                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
1723                if (reducedVerb == 0) {
1724                    break; // skip degenerate points
1725                }
1726                if (reducedVerb == 1) {
1727                    *fExtra.append() =
1728                            fCurrentContour->addLine(fReducePts.end() - 2);
1729                    break;
1730                }
1731                if (reducedVerb == 2) {
1732                    *fExtra.append() =
1733                            fCurrentContour->addQuad(fReducePts.end() - 3);
1734                    break;
1735                }
1736                fCurrentContour->addCubic(&pointsPtr[-1]);
1737                break;
1738            case SkPath::kClose_Verb:
1739                SkASSERT(fCurrentContour);
1740                if (finalCurveStart && finalCurveEnd
1741                        && *finalCurveStart != *finalCurveEnd) {
1742                    *fReducePts.append() = *finalCurveStart;
1743                    *fReducePts.append() = *finalCurveEnd;
1744                    *fExtra.append() =
1745                            fCurrentContour->addLine(fReducePts.end() - 2);
1746                }
1747                complete();
1748                continue;
1749            default:
1750                SkDEBUGFAIL("bad verb");
1751                return;
1752        }
1753        finalCurveStart = &pointsPtr[verb - 1];
1754        pointsPtr += verb;
1755        SkASSERT(fCurrentContour);
1756    }
1757    complete();
1758    if (fCurrentContour && !fCurrentContour->fSegments.count()) {
1759        fContours.pop_back();
1760    }
1761    // correct pointers in contours since fReducePts may have moved as it grew
1762    int cIndex = 0;
1763    fCurrentContour = &fContours[0];
1764    int extraCount = fExtra.count();
1765    SkASSERT(fExtra[0] == -1);
1766    int eIndex = 0;
1767    int rIndex = 0;
1768    while (++eIndex < extraCount) {
1769        int offset = fExtra[eIndex];
1770        if (offset < 0) {
1771            fCurrentContour = &fContours[++cIndex];
1772            continue;
1773        }
1774        Segment& segment = fCurrentContour->fSegments[offset - 1];
1775        segment.updatePts(&fReducePts[rIndex]);
1776        rIndex += segment.verb() + 1;
1777    }
1778    fExtra.reset(); // we're done with this
1779}
1780
1781private:
1782    const SkPath& fPath;
1783    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
1784    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
1785    Contour* fCurrentContour;
1786    SkTArray<Contour>& fContours;
1787    SkTDArray<SkPoint> fReducePts; // segments created on the fly
1788    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
1789};
1790
1791class Work {
1792public:
1793    enum SegmentType {
1794        kHorizontalLine_Segment = -1,
1795        kVerticalLine_Segment = 0,
1796        kLine_Segment = SkPath::kLine_Verb,
1797        kQuad_Segment = SkPath::kQuad_Verb,
1798        kCubic_Segment = SkPath::kCubic_Verb,
1799    };
1800
1801    // FIXME: does it make sense to write otherIndex now if we're going to
1802    // fix it up later?
1803    void addOtherT(int index, double otherT, int otherIndex) {
1804        fContour->fSegments[fIndex].addOtherT(index, otherT, otherIndex);
1805    }
1806
1807    // Avoid collapsing t values that are close to the same since
1808    // we walk ts to describe consecutive intersections. Since a pair of ts can
1809    // be nearly equal, any problems caused by this should be taken care
1810    // of later.
1811    // On the edge or out of range values are negative; add 2 to get end
1812    int addT(double newT, const Work& other, int coincident) {
1813        fContour->containsIntercepts();
1814        return fContour->fSegments[fIndex].addT(newT,
1815                other.fContour->fSegments[other.fIndex], coincident);
1816    }
1817
1818    bool advance() {
1819        return ++fIndex < fLast;
1820    }
1821
1822    SkScalar bottom() const {
1823        return bounds().fBottom;
1824    }
1825
1826    const Bounds& bounds() const {
1827        return fContour->fSegments[fIndex].bounds();
1828    }
1829
1830    const SkPoint* cubic() const {
1831        return fCubic;
1832    }
1833
1834    void init(Contour* contour) {
1835        fContour = contour;
1836        fIndex = 0;
1837        fLast = contour->fSegments.count();
1838    }
1839
1840    SkScalar left() const {
1841        return bounds().fLeft;
1842    }
1843
1844    void promoteToCubic() {
1845        fCubic[0] = pts()[0];
1846        fCubic[2] = pts()[1];
1847        fCubic[3] = pts()[2];
1848        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
1849        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
1850        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
1851        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
1852    }
1853
1854    const SkPoint* pts() const {
1855        return fContour->fSegments[fIndex].pts();
1856    }
1857
1858    SkScalar right() const {
1859        return bounds().fRight;
1860    }
1861
1862    ptrdiff_t segmentIndex() const {
1863        return fIndex;
1864    }
1865
1866    SegmentType segmentType() const {
1867        const Segment& segment = fContour->fSegments[fIndex];
1868        SegmentType type = (SegmentType) segment.verb();
1869        if (type != kLine_Segment) {
1870            return type;
1871        }
1872        if (segment.isHorizontal()) {
1873            return kHorizontalLine_Segment;
1874        }
1875        if (segment.isVertical()) {
1876            return kVerticalLine_Segment;
1877        }
1878        return kLine_Segment;
1879    }
1880
1881    bool startAfter(const Work& after) {
1882        fIndex = after.fIndex;
1883        return advance();
1884    }
1885
1886    SkScalar top() const {
1887        return bounds().fTop;
1888    }
1889
1890    SkPath::Verb verb() const {
1891        return fContour->fSegments[fIndex].verb();
1892    }
1893
1894    SkScalar x() const {
1895        return bounds().fLeft;
1896    }
1897
1898    bool xFlipped() const {
1899        return x() != pts()[0].fX;
1900    }
1901
1902    SkScalar y() const {
1903        return bounds().fTop;
1904    }
1905
1906    bool yFlipped() const {
1907        return y() != pts()[0].fX;
1908    }
1909
1910protected:
1911    Contour* fContour;
1912    SkPoint fCubic[4];
1913    int fIndex;
1914    int fLast;
1915};
1916
1917#if DEBUG_ADD_INTERSECTING_TS
1918static void debugShowLineIntersection(int pts, const Work& wt,
1919        const Work& wn, const double wtTs[2], const double wnTs[2]) {
1920    if (!pts) {
1921        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
1922                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
1923                wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY,
1924                wn.pts()[1].fX, wn.pts()[1].fY);
1925        return;
1926    }
1927    SkPoint wtOutPt, wnOutPt;
1928    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
1929    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
1930    SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
1931            __FUNCTION__,
1932            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
1933            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
1934    if (pts == 2) {
1935        SkDebugf(" wtTs[1]=%g", wtTs[1]);
1936    }
1937    SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
1938            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
1939            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
1940    if (pts == 2) {
1941        SkDebugf(" wnTs[1]=%g", wnTs[1]);
1942    SkDebugf("\n");
1943    }
1944#else
1945static void debugShowLineIntersection(int , const Work& ,
1946        const Work& , const double [2], const double [2]) {
1947}
1948#endif
1949
1950static bool addIntersectTs(Contour* test, Contour* next) {
1951
1952    if (test != next) {
1953        if (test->bounds().fBottom < next->bounds().fTop) {
1954            return false;
1955        }
1956        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
1957            return true;
1958        }
1959    }
1960    Work wt;
1961    wt.init(test);
1962    do {
1963        Work wn;
1964        wn.init(next);
1965        if (test == next && !wn.startAfter(wt)) {
1966            continue;
1967        }
1968        do {
1969            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
1970                continue;
1971            }
1972            int pts;
1973            Intersections ts;
1974            bool swap = false;
1975            switch (wt.segmentType()) {
1976                case Work::kHorizontalLine_Segment:
1977                    swap = true;
1978                    switch (wn.segmentType()) {
1979                        case Work::kHorizontalLine_Segment:
1980                        case Work::kVerticalLine_Segment:
1981                        case Work::kLine_Segment: {
1982                            pts = HLineIntersect(wn.pts(), wt.left(),
1983                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1984                            debugShowLineIntersection(pts, wt, wn,
1985                                    ts.fT[1], ts.fT[0]);
1986                            break;
1987                        }
1988                        case Work::kQuad_Segment: {
1989                            pts = HQuadIntersect(wn.pts(), wt.left(),
1990                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1991                            break;
1992                        }
1993                        case Work::kCubic_Segment: {
1994                            pts = HCubicIntersect(wn.pts(), wt.left(),
1995                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1996                            break;
1997                        }
1998                        default:
1999                            SkASSERT(0);
2000                    }
2001                    break;
2002                case Work::kVerticalLine_Segment:
2003                    swap = true;
2004                    switch (wn.segmentType()) {
2005                        case Work::kHorizontalLine_Segment:
2006                        case Work::kVerticalLine_Segment:
2007                        case Work::kLine_Segment: {
2008                            pts = VLineIntersect(wn.pts(), wt.top(),
2009                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2010                            debugShowLineIntersection(pts, wt, wn,
2011                                    ts.fT[1], ts.fT[0]);
2012                            break;
2013                        }
2014                        case Work::kQuad_Segment: {
2015                            pts = VQuadIntersect(wn.pts(), wt.top(),
2016                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2017                            break;
2018                        }
2019                        case Work::kCubic_Segment: {
2020                            pts = VCubicIntersect(wn.pts(), wt.top(),
2021                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
2022                            break;
2023                        }
2024                        default:
2025                            SkASSERT(0);
2026                    }
2027                    break;
2028                case Work::kLine_Segment:
2029                    switch (wn.segmentType()) {
2030                        case Work::kHorizontalLine_Segment:
2031                            pts = HLineIntersect(wt.pts(), wn.left(),
2032                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2033                            debugShowLineIntersection(pts, wt, wn,
2034                                    ts.fT[1], ts.fT[0]);
2035                            break;
2036                        case Work::kVerticalLine_Segment:
2037                            pts = VLineIntersect(wt.pts(), wn.top(),
2038                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2039                            debugShowLineIntersection(pts, wt, wn,
2040                                    ts.fT[1], ts.fT[0]);
2041                            break;
2042                        case Work::kLine_Segment: {
2043                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
2044                            debugShowLineIntersection(pts, wt, wn,
2045                                    ts.fT[1], ts.fT[0]);
2046                            break;
2047                        }
2048                        case Work::kQuad_Segment: {
2049                            swap = true;
2050                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
2051                            break;
2052                        }
2053                        case Work::kCubic_Segment: {
2054                            swap = true;
2055                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
2056                            break;
2057                        }
2058                        default:
2059                            SkASSERT(0);
2060                    }
2061                    break;
2062                case Work::kQuad_Segment:
2063                    switch (wn.segmentType()) {
2064                        case Work::kHorizontalLine_Segment:
2065                            pts = HQuadIntersect(wt.pts(), wn.left(),
2066                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2067                            break;
2068                        case Work::kVerticalLine_Segment:
2069                            pts = VQuadIntersect(wt.pts(), wn.top(),
2070                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2071                            break;
2072                        case Work::kLine_Segment: {
2073                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
2074                            break;
2075                        }
2076                        case Work::kQuad_Segment: {
2077                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
2078                            break;
2079                        }
2080                        case Work::kCubic_Segment: {
2081                            wt.promoteToCubic();
2082                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
2083                            break;
2084                        }
2085                        default:
2086                            SkASSERT(0);
2087                    }
2088                    break;
2089                case Work::kCubic_Segment:
2090                    switch (wn.segmentType()) {
2091                        case Work::kHorizontalLine_Segment:
2092                            pts = HCubicIntersect(wt.pts(), wn.left(),
2093                                    wn.right(), wn.y(), wn.xFlipped(), ts);
2094                            break;
2095                        case Work::kVerticalLine_Segment:
2096                            pts = VCubicIntersect(wt.pts(), wn.top(),
2097                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
2098                            break;
2099                        case Work::kLine_Segment: {
2100                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
2101                            break;
2102                        }
2103                        case Work::kQuad_Segment: {
2104                            wn.promoteToCubic();
2105                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
2106                            break;
2107                        }
2108                        case Work::kCubic_Segment: {
2109                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
2110                            break;
2111                        }
2112                        default:
2113                            SkASSERT(0);
2114                    }
2115                    break;
2116                default:
2117                    SkASSERT(0);
2118            }
2119            // in addition to recording T values, record matching segment
2120            int testCoin;
2121            int nextCoin;
2122            if (pts == 2 && wn.segmentType() <= Work::kLine_Segment
2123                    && wt.segmentType() <= Work::kLine_Segment) {
2124                // pass coincident so that smaller T is -1, larger T is 1
2125                testCoin = ts.fT[swap][0] < ts.fT[swap][1] ? -1 : 1;
2126                nextCoin = ts.fT[!swap][0] < ts.fT[!swap][1] ? -1 : 1;
2127            } else {
2128                testCoin = nextCoin = 0;
2129            }
2130            for (int pt = 0; pt < pts; ++pt) {
2131                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
2132                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
2133                int testTAt = wt.addT(ts.fT[swap][pt], wn, testCoin);
2134                int nextTAt = wn.addT(ts.fT[!swap][pt], wt, nextCoin);
2135                wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt);
2136                wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt);
2137                testCoin = -testCoin;
2138                nextCoin = -nextCoin;
2139            }
2140        } while (wn.advance());
2141    } while (wt.advance());
2142    return true;
2143}
2144
2145// see if coincidence is formed by clipping non-concident segments
2146static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) {
2147    int contourCount = contourList.count();
2148    for (size_t cIndex = 0; cIndex < contourCount; ++cIndex) {
2149        Contour* contour = contourList[cIndex];
2150        contour->findTooCloseToCall(winding);
2151    }
2152}
2153
2154
2155// OPTIMIZATION: not crazy about linear search here to find top active y.
2156// seems like we should break down and do the sort, or maybe sort each
2157// contours' segments?
2158// Once the segment array is built, there's no reason I can think of not to
2159// sort it in Y. hmmm
2160static Segment* findTopContour(SkTDArray<Contour*>& contourList,
2161        int contourCount) {
2162    int cIndex = 0;
2163    Segment* topStart;
2164    do {
2165        Contour* topContour = contourList[cIndex];
2166        topStart = topContour->topSegment();
2167    } while (!topStart && ++cIndex < contourCount);
2168    if (!topStart) {
2169        return NULL;
2170    }
2171    SkScalar top = topStart->bounds().fTop;
2172    for (int cTest = cIndex + 1; cTest < contourCount; ++cTest) {
2173        Contour* contour = contourList[cTest];
2174        if (top < contour->bounds().fTop) {
2175            continue;
2176        }
2177        Segment* test = contour->topSegment();
2178        if (top > test->bounds().fTop) {
2179            cIndex = cTest;
2180            topStart = test;
2181            top = test->bounds().fTop;
2182        }
2183    }
2184    return topStart;
2185}
2186
2187// Each segment may have an inside or an outside. Segments contained within
2188// winding may have insides on either side, and form a contour that should be
2189// ignored. Segments that are coincident with opposing direction segments may
2190// have outsides on either side, and should also disappear.
2191// 'Normal' segments will have one inside and one outside. Subsequent connections
2192// when winding should follow the intersection direction. If more than one edge
2193// is an option, choose first edge that continues the inside.
2194    // since we start with leftmost top edge, we'll traverse through a
2195    // smaller angle counterclockwise to get to the next edge.
2196static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
2197    int contourCount = contourList.count();
2198    int winding = 0; // there are no contours outside this one
2199    do {
2200        Segment* topStart = findTopContour(contourList, contourCount);
2201        if (!topStart) {
2202            break;
2203        }
2204        // Start at the top. Above the top is outside, below is inside.
2205        // follow edges to intersection by changing the index by direction.
2206        int index, endIndex;
2207        Segment* topSegment = topStart->findTop(index, endIndex);
2208        Segment* current = topSegment;
2209        winding += SkSign32(index - endIndex);
2210        bool first = true;
2211        do {
2212            SkASSERT(!current->done());
2213            int nextStart, nextEnd;
2214            Segment* next = current->findNext(winding, index, endIndex,
2215                    nextStart, nextEnd);
2216            if (!next) {
2217                break;
2218            }
2219            if (first) {
2220                current->addMoveTo(index, simple);
2221                first = false;
2222            }
2223            current->addCurveTo(index, endIndex, simple);
2224            current = next;
2225            index = nextStart;
2226            endIndex = nextEnd;
2227        } while (current != topSegment);
2228        if (!first) {
2229    #if DEBUG_PATH_CONSTRUCTION
2230            SkDebugf("%s close\n", __FUNCTION__);
2231    #endif
2232            simple.close();
2233        }
2234    } while (true);
2235    // FIXME: more work to be done for contained (but not intersecting)
2236    //  segments
2237}
2238
2239static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
2240    int contourCount = contourList.count();
2241    for (int cTest = 0; cTest < contourCount; ++cTest) {
2242        Contour* contour = contourList[cTest];
2243        contour->fixOtherTIndex();
2244    }
2245}
2246
2247static void makeContourList(SkTArray<Contour>& contours,
2248        SkTDArray<Contour*>& list) {
2249    int count = contours.count();
2250    if (count == 0) {
2251        return;
2252    }
2253    for (int index = 0; index < count; ++index) {
2254        *list.append() = &contours[index];
2255    }
2256    QSort<Contour>(list.begin(), list.end() - 1);
2257}
2258
2259void simplifyx(const SkPath& path, SkPath& simple) {
2260    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
2261    int winding = (path.getFillType() & 1) ? 1 : -1;
2262    simple.reset();
2263    simple.setFillType(SkPath::kEvenOdd_FillType);
2264
2265    // turn path into list of segments
2266    SkTArray<Contour> contours;
2267    // FIXME: add self-intersecting cubics' T values to segment
2268    EdgeBuilder builder(path, contours);
2269    SkTDArray<Contour*> contourList;
2270    makeContourList(contours, contourList);
2271    Contour** currentPtr = contourList.begin();
2272    if (!currentPtr) {
2273        return;
2274    }
2275    Contour** listEnd = contourList.end();
2276    // find all intersections between segments
2277    do {
2278        Contour** nextPtr = currentPtr;
2279        Contour* current = *currentPtr++;
2280        Contour* next;
2281        do {
2282            next = *nextPtr++;
2283        } while (addIntersectTs(current, next) && nextPtr != listEnd);
2284    } while (currentPtr != listEnd);
2285    fixOtherTIndex(contourList);
2286    // eat through coincident edges
2287    coincidenceCheck(contourList, winding);
2288    // construct closed contours
2289    bridge(contourList, simple);
2290}
2291
2292