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