Simplify.cpp revision a833b5c40d0516237e0889fce8af44880423fc20
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 "CurveIntersection.h"
8#include "Intersections.h"
9#include "LineIntersection.h"
10#include "SkPath.h"
11#include "SkRect.h"
12#include "SkTArray.h"
13#include "SkTDArray.h"
14#include "ShapeOps.h"
15#include "TSearch.h"
16#include <algorithm> // used for std::min
17
18#undef SkASSERT
19#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
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 QuadSubBounds(const SkPoint a[3], double startT, double endT,
258        SkRect& bounds) {
259    SkPoint dst[3];
260    QuadSubDivide(a, startT, endT, dst);
261    bounds.fLeft = bounds.fRight = dst[0].fX;
262    bounds.fTop = bounds.fBottom = dst[0].fY;
263    for (int index = 1; index < 3; ++index) {
264        bounds.growToInclude(dst[index].fX, dst[index].fY);
265    }
266}
267
268static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
269        SkRect& bounds) {
270    SkPoint dst[4];
271    CubicSubDivide(a, startT, endT, dst);
272    bounds.fLeft = bounds.fRight = dst[0].fX;
273    bounds.fTop = bounds.fBottom = dst[0].fY;
274    for (int index = 1; index < 4; ++index) {
275        bounds.growToInclude(dst[index].fX, dst[index].fY);
276    }
277}
278
279static SkPath::Verb QuadReduceOrder(const SkPoint a[4],
280        SkTDArray<SkPoint>& reducePts) {
281    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
282            {a[2].fX, a[2].fY}};
283    Quadratic dst;
284    int order = reduceOrder(aQuad, dst);
285    for (int index = 0; index < order; ++index) {
286        SkPoint* pt = reducePts.append();
287        pt->fX = SkDoubleToScalar(dst[index].x);
288        pt->fY = SkDoubleToScalar(dst[index].y);
289    }
290    return (SkPath::Verb) (order - 1);
291}
292
293static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
294        SkTDArray<SkPoint>& reducePts) {
295    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
296            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
297    Cubic dst;
298    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
299    for (int index = 0; index < order; ++index) {
300        SkPoint* pt = reducePts.append();
301        pt->fX = SkDoubleToScalar(dst[index].x);
302        pt->fY = SkDoubleToScalar(dst[index].y);
303    }
304    return (SkPath::Verb) (order - 1);
305}
306
307static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
308    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
309    double x[2];
310    xy_at_t(aLine, startT, x[0], *(double*) 0);
311    xy_at_t(aLine, endT, x[0], *(double*) 0);
312    return startT < endT ? startT : endT;
313}
314
315static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
316    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
317            {a[2].fX, a[2].fY}};
318    return leftMostT(aQuad, startT, endT);
319}
320
321static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
322    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
323            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
324    return leftMostT(aCubic, startT, endT);
325}
326
327static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
328    NULL,
329    LineLeftMost,
330    QuadLeftMost,
331    CubicLeftMost
332};
333
334static bool IsCoincident(const SkPoint a[2], const SkPoint& above,
335        const SkPoint& below) {
336    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
337    const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
338    return implicit_matches_ulps(aLine, bLine, 32);
339}
340
341// Bounds, unlike Rect, does not consider a vertical line to be empty.
342struct Bounds : public SkRect {
343    static bool Intersects(const Bounds& a, const Bounds& b) {
344        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
345                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
346    }
347
348    bool isEmpty() {
349        return fLeft > fRight || fTop > fBottom
350                || fLeft == fRight && fTop == fBottom
351                || isnan(fLeft) || isnan(fRight)
352                || isnan(fTop) || isnan(fBottom);
353    }
354
355    void setCubicBounds(const SkPoint a[4]) {
356        _Rect dRect;
357        Cubic cubic  = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
358            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
359        dRect.setBounds(cubic);
360        set(dRect.left, dRect.top, dRect.right, dRect.bottom);
361    }
362
363    void setQuadBounds(const SkPoint a[3]) {
364        const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
365                {a[2].fX, a[2].fY}};
366        _Rect dRect;
367        dRect.setBounds(quad);
368        set(dRect.left, dRect.top, dRect.right, dRect.bottom);
369    }
370};
371
372class Segment;
373
374struct TEntry {
375    double fT;
376    Segment* fOther;
377    double fOtherT;
378    int fWinding;
379    bool fDone; // set true when t to t+1 is processed
380};
381
382class Segment {
383public:
384    Segment() {
385#if DEBUG_DUMP
386        fID = ++gSegmentID;
387#endif
388    }
389
390    int addT(double newT, Segment& other) {
391        // FIXME: in the pathological case where there is a ton of intercepts,
392        //  binary search?
393        int insertedAt = -1;
394        TEntry* entry;
395        size_t tCount = fTs.count();
396        double delta;
397        for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
398            // OPTIMIZATION: if there are three or more identical Ts, then
399            // the fourth and following could be further insertion-sorted so
400            // that all the edges are clockwise or counterclockwise.
401            // This could later limit segment tests to the two adjacent
402            // neighbors, although it doesn't help with determining which
403            // circular direction to go in.
404            if (newT <= fTs[idx2].fT) {
405                insertedAt = idx2;
406                entry = fTs.insert(idx2);
407                goto finish;
408            }
409        }
410        insertedAt = tCount;
411        entry = fTs.append();
412finish:
413        entry->fT = newT;
414        entry->fOther = &other;
415        entry->fWinding = 1;
416        entry->fDone = false;
417        return insertedAt;
418    }
419
420    bool addCubic(const SkPoint pts[4]) {
421        fPts = pts;
422        fVerb = SkPath::kCubic_Verb;
423        fBounds.setCubicBounds(pts);
424    }
425
426    bool addLine(const SkPoint pts[2]) {
427        fPts = pts;
428        fVerb = SkPath::kLine_Verb;
429        fBounds.set(pts, 2);
430    }
431
432    // add 2 to edge or out of range values to get T extremes
433    void addOtherT(int index, double other) {
434        fTs[index].fOtherT = other;
435    }
436
437    bool addQuad(const SkPoint pts[3]) {
438        fPts = pts;
439        fVerb = SkPath::kQuad_Verb;
440        fBounds.setQuadBounds(pts);
441    }
442
443    const Bounds& bounds() const {
444        return fBounds;
445    }
446
447    int coincidentCount() const {
448        return fCoincidentCount;
449    }
450
451    int coincidentT(double newT, Segment& other, bool combo) {
452        int index = addT(newT, other);
453        if (combo) {
454            fTs[index].fWinding = 2;
455        } else {
456            fTs[index].fWinding = 0;
457            fTs[index].fDone = true;
458        }
459        ++fCoincidentCount;
460        return index;
461    }
462
463    void findTooCloseToCall(int winding) {
464        int limit = fTs.count() - 1;
465        SkPoint matchPt;
466        int matchIndex = 0;
467        TEntry* match = &fTs[0];
468        (*SegmentXYAtT[fVerb])(fPts, match->fT, &matchPt);
469        // look for a pair of nearby T values that map to the same (x,y) value
470        // if found, see if the pair of other segments share a common point. If
471        // so, the span from here to there is coincident.
472        for (int index = 1; index < limit; ++index) {
473            TEntry* test = &fTs[index];
474            if (test->fDone) {
475                continue;
476            }
477            SkPoint testPt;
478            (*SegmentXYAtT[fVerb])(fPts, test->fT, &testPt);
479            if (matchPt != testPt) {
480                matchIndex = index;
481                matchPt = testPt;
482                continue;
483            }
484            Segment* mOther = match->fOther;
485            Segment* tOther = test->fOther;
486            int moCount = mOther->fTs.count();
487            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
488                TEntry& moEntry = mOther->fTs[moIndex];
489                if (moEntry.fOther != tOther) {
490                    continue;
491                }
492                int toIndex;
493                int toCount = tOther->fTs.count();
494                for (toIndex = 0; toIndex < toCount; ++toIndex) {
495                    if (tOther->fTs[toIndex].fOther == mOther
496                            && tOther->fTs[toIndex].fOtherT
497                            == mOther->fTs[moIndex].fT) {
498                        break;
499                    }
500                }
501                bool sameDirection;
502                // test to see if the segment between there and here is linear
503                if (mOther->fVerb == SkPath::kLine_Verb
504                        && tOther->fVerb == SkPath::kLine_Verb) {
505                    sameDirection = mOther->fPts[0].fY != mOther->fPts[1].fY ?
506                        (mOther->fPts[0].fY < mOther->fPts[1].fY)
507                        ^ ((tOther->fPts[0].fY != tOther->fPts[1].fY)
508                        ? mOther->fPts[0].fY > mOther->fPts[1].fY
509                        : mOther->fPts[0].fX > mOther->fPts[1].fX)
510                        : (mOther->fPts[0].fX < mOther->fPts[1].fX)
511                        ^ (tOther->fPts[0].fY != tOther->fPts[1].fY
512                        ? tOther->fPts[0].fY > tOther->fPts[1].fY
513                        : tOther->fPts[0].fX > tOther->fPts[1].fX);
514                    goto isLinear;
515                }
516                // FIXME: determine if non-lines are essentially flat
517
518        isLinear:
519                if (sameDirection || winding == 1) { // FIXME: should check if y direction is same
520                    ++mOther->fTs[moIndex].fWinding;
521                } else if (!--mOther->fTs[moIndex].fWinding) {
522                    mOther->fTs[moIndex].fDone = true;
523                }
524                if (!--tOther->fTs[toIndex].fWinding) {
525                    tOther->fTs[toIndex].fDone = true;
526                }
527            }
528    nextStart:
529            ;
530        }
531    }
532
533    int findByT(double t, const Segment* match) const {
534        // OPTIMIZATION: bsearch if count is honkin huge
535        int count = fTs.count();
536        for (int index = 0; index < count; ++index) {
537            const TEntry& entry = fTs[index];
538            if (t == entry.fT && match == entry.fOther) {
539                return index;
540            }
541        }
542        SkASSERT(0); // should never get here
543        return -1;
544    }
545
546    // find the adjacent T that is leftmost, with a point != base
547    int findLefty(int tIndex, const SkPoint& base) const {
548        int bestTIndex;
549        SkPoint test;
550        SkScalar bestX = DBL_MAX;
551        int testTIndex = tIndex;
552        while (--testTIndex >= 0) {
553            xyAtT(testTIndex, &test);
554            if (test != base) {
555                continue;
556            }
557            bestX = test.fX;
558            bestTIndex = testTIndex;
559            break;
560        }
561        int count = fTs.count();
562        testTIndex = tIndex;
563        while (++testTIndex < count) {
564            xyAtT(testTIndex, &test);
565            if (test == base) {
566                continue;
567            }
568            return bestX > test.fX ? testTIndex : bestTIndex;
569        }
570        SkASSERT(0); // can't get here (?)
571        return -1;
572    }
573
574    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
575    // and use more concise logic like the old edge walker code?
576    // FIXME: this needs to deal with coincident edges
577    const Segment* findTop(int& tIndex) const {
578        // iterate through T intersections and return topmost
579        // topmost tangent from y-min to first pt is closer to horizontal
580        int firstT = 0;
581        int lastT = 0;
582        SkScalar topY = fPts[0].fY;
583        int count = fTs.count();
584        int index;
585        for (index = 1; index < count; ++index) {
586            const TEntry& entry = fTs[index];
587            double t = entry.fT;
588            SkScalar yIntercept = yAtT(t);
589            if (topY > yIntercept) {
590                topY = yIntercept;
591                firstT = lastT = index;
592            } else if (topY == yIntercept) {
593                lastT = index;
594            }
595        }
596        // if there's only a pair of segments, go with the endpoint chosen above
597        if (firstT == lastT && (firstT == 0 || firstT == count - 1)) {
598            tIndex = firstT;
599            return this;
600        }
601        // if the topmost T is not on end, or is three-way or more, find left
602        SkPoint leftBase;
603        xyAtT(firstT, &leftBase);
604        int tLeft = findLefty(firstT, leftBase);
605        const Segment* leftSegment = this;
606        // look for left-ness from tLeft to firstT (matching y of other)
607        for (index = firstT; index <= lastT; ++index) {
608            const Segment* other = fTs[index].fOther;
609            double otherT = fTs[index].fOtherT;
610            int otherTIndex = other->findByT(otherT, this);
611            // pick companionT closest (but not too close) on either side
612            int otherTLeft = other->findLefty(otherTIndex, leftBase);
613            // within this span, find highest y
614            SkPoint testPt, otherPt;
615            testPt.fY = yAtT(tLeft);
616            otherPt.fY = other->yAtT(otherTLeft);
617            // FIXME: incomplete
618            // find the y intercept with the opposite segment
619            if (testPt.fY < otherPt.fY) {
620
621            } else if (testPt.fY > otherPt.fY) {
622
623            }
624            // FIXME: leftMost no good. Use y intercept instead
625#if 0
626            SkScalar otherMost = other->leftMost(otherTIndex, otherTLeft);
627            if (otherMost < left) {
628                leftSegment = other;
629            }
630#endif
631        }
632        return leftSegment;
633    }
634
635    bool intersected() const {
636        return fTs.count() > 0;
637    }
638
639    bool isHorizontal() const {
640        return fBounds.fTop == fBounds.fBottom;
641    }
642
643    bool isVertical() const {
644        return fBounds.fLeft == fBounds.fRight;
645    }
646
647    SkScalar leftMost(int start, int end) const {
648        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
649    }
650
651    const SkPoint* pts() const {
652        return fPts;
653    }
654
655    void reset() {
656        fPts = NULL;
657        fVerb = (SkPath::Verb) -1;
658        fCoincidentCount = 0;
659        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
660        fTs.reset();
661    }
662
663    void resolveCoincidence() {
664        if (fCoincidentCount <= 2) {
665            return;
666        }
667        SkASSERT(fVerb == SkPath::kLine_Verb);
668        int tCount = fTs.count();
669        for (int index = 0; index < tCount; ++index) {
670            const TEntry& entry = fTs[index];
671            if (entry.fWinding == 1) {
672                continue;
673            }
674            for (int mIndex = index + 1; mIndex < tCount; ++mIndex) {
675                const TEntry& match = fTs[mIndex];
676                if (match.fT > entry.fT) {
677                    break;
678                }
679                if (match.fWinding == 1) {
680                    continue;
681                }
682
683            }
684        }
685    }
686
687    // OPTIMIZATION: remove this function if it's never called
688    double t(int tIndex) const {
689        return fTs[tIndex].fT;
690    }
691
692    SkPath::Verb verb() const {
693        return fVerb;
694    }
695
696    SkScalar xAtT(double t) const {
697        return (*SegmentXAtT[fVerb])(fPts, t);
698    }
699
700    void xyAtT(double t, SkPoint* pt) const {
701        (*SegmentXYAtT[fVerb])(fPts, t, pt);
702    }
703
704    SkScalar yAtT(double t) const {
705        return (*SegmentYAtT[fVerb])(fPts, t);
706    }
707
708#if DEBUG_DUMP
709    void dump() const {
710        const char className[] = "Segment";
711        const int tab = 4;
712        for (int i = 0; i < fTs.count(); ++i) {
713            SkPoint out;
714            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
715            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
716                    " otherT=%1.9g winding=%d\n",
717                    tab + sizeof(className), className, fID,
718                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
719                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding);
720        }
721        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)"
722                " coincidentCount=%d\n",
723                tab + sizeof(className), className, fID,
724                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom,
725                fCoincidentCount);
726    }
727#endif
728
729private:
730    const SkPoint* fPts;
731    SkPath::Verb fVerb;
732    Bounds fBounds;
733    SkTDArray<TEntry> fTs; // two or more (always includes t=0 t=1)
734    int fCoincidentCount;
735#if DEBUG_DUMP
736    int fID;
737#endif
738};
739
740class Contour {
741public:
742    Contour() {
743        reset();
744#if DEBUG_DUMP
745        fID = ++gContourID;
746#endif
747    }
748
749    bool operator<(const Contour& rh) const {
750        return fBounds.fTop == rh.fBounds.fTop
751                ? fBounds.fLeft < rh.fBounds.fLeft
752                : fBounds.fTop < rh.fBounds.fTop;
753    }
754
755    void addCubic(const SkPoint pts[4]) {
756        fSegments.push_back().addCubic(pts);
757        fContainsCurves = true;
758    }
759
760    void addLine(const SkPoint pts[2]) {
761        fSegments.push_back().addLine(pts);
762    }
763
764    void addQuad(const SkPoint pts[3]) {
765        fSegments.push_back().addQuad(pts);
766        fContainsCurves = true;
767    }
768
769    const Bounds& bounds() const {
770        return fBounds;
771    }
772
773    void checkMultiple() {
774        fCheckMultiple = true;
775    }
776
777    void complete() {
778        setBounds();
779        fContainsIntercepts = false;
780    }
781
782    void containsIntercepts() {
783        fContainsIntercepts = true;
784    }
785
786    void findTooCloseToCall(int winding) {
787        int segmentCount = fSegments.count();
788        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
789            fSegments[sIndex].findTooCloseToCall(winding);
790        }
791    }
792
793    void reset() {
794        fSegments.reset();
795        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
796        fCheckMultiple = fContainsCurves = fContainsIntercepts = false;
797    }
798
799    void resolveCoincidence() {
800        if (!fCheckMultiple) {
801            return;
802        }
803        int count = fSegments.count();
804        for (int index = 0; index < count; ++index) {
805            fSegments[index].resolveCoincidence();
806        }
807    }
808
809    Segment& topSegment() {
810        return fSegments[fTopSegment];
811    }
812
813#if DEBUG_DUMP
814    void dump() {
815        int i;
816        const char className[] = "Contour";
817        const int tab = 4;
818        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
819        for (i = 0; i < fSegments.count(); ++i) {
820            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
821                    className, i);
822            fSegments[i].dump();
823        }
824        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
825                tab + sizeof(className), className,
826                fBounds.fLeft, fBounds.fTop,
827                fBounds.fRight, fBounds.fBottom);
828        SkDebugf("%*s.fTopSegment=%d\n", tab + sizeof(className), className,
829                fTopSegment);
830        SkDebugf("%*s.fCheckMultiple=%d\n", tab + sizeof(className),
831                className, fCheckMultiple);
832        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
833                className, fContainsIntercepts);
834        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
835                className, fContainsCurves);
836    }
837#endif
838
839protected:
840    void setBounds() {
841        int count = fSegments.count();
842        if (count == 0) {
843            SkDebugf("%s empty contour\n", __FUNCTION__);
844            SkASSERT(0);
845            // FIXME: delete empty contour?
846            return;
847        }
848        fTopSegment = 0;
849        fBounds = fSegments.front().bounds();
850        SkScalar top = fBounds.fTop;
851        for (int index = 1; index < count; ++index) {
852            fBounds.growToInclude(fSegments[index].bounds());
853            if (top > fBounds.fTop) {
854                fTopSegment = index;
855                top = fBounds.fTop;
856            }
857        }
858    }
859
860public:
861    SkTArray<Segment> fSegments; // not worth accessor functions?
862
863private:
864    Bounds fBounds;
865    int fTopSegment;
866    bool fCheckMultiple; // more than 2 lines are coincident; resolve later
867    bool fContainsIntercepts;
868    bool fContainsCurves;
869#if DEBUG_DUMP
870    int fID;
871#endif
872};
873
874class EdgeBuilder {
875public:
876
877EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
878    : fPath(path)
879    , fCurrentContour(NULL)
880    , fContours(contours)
881{
882#if DEBUG_DUMP
883    gContourID = 0;
884    gSegmentID = 0;
885#endif
886    walk();
887}
888
889protected:
890
891void complete() {
892    if (fCurrentContour && fCurrentContour->fSegments.count()) {
893        fCurrentContour->complete();
894        fCurrentContour = NULL;
895    }
896}
897
898void startContour() {
899    if (!fCurrentContour) {
900        fCurrentContour = fContours.push_back_n(1);
901    }
902}
903
904void walk() {
905    // FIXME:remove once we can access path pts directly
906    SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed
907    SkPoint pts[4];
908    SkPath::Verb verb;
909    do {
910        verb = iter.next(pts);
911        *fPathVerbs.append() = verb;
912        if (verb == SkPath::kMove_Verb) {
913            *fPathPts.append() = pts[0];
914        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
915            fPathPts.append(verb, &pts[1]);
916        }
917    } while (verb != SkPath::kDone_Verb);
918    // FIXME: end of section to remove once path pts are accessed directly
919
920    SkPath::Verb reducedVerb;
921    uint8_t* verbPtr = fPathVerbs.begin();
922    const SkPoint* pointsPtr = fPathPts.begin();
923    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
924        switch (verb) {
925            case SkPath::kMove_Verb:
926                complete();
927                startContour();
928                pointsPtr += 1;
929                continue;
930            case SkPath::kLine_Verb:
931                // skip degenerate points
932                if (pointsPtr[-1].fX != pointsPtr[0].fX
933                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
934                    fCurrentContour->addLine(&pointsPtr[-1]);
935                }
936                break;
937            case SkPath::kQuad_Verb:
938                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
939                if (reducedVerb == 0) {
940                    break; // skip degenerate points
941                }
942                if (reducedVerb == 1) {
943                    fCurrentContour->addLine(fReducePts.end() - 2);
944                    break;
945                }
946                fCurrentContour->addQuad(&pointsPtr[-1]);
947                break;
948            case SkPath::kCubic_Verb:
949                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
950                if (reducedVerb == 0) {
951                    break; // skip degenerate points
952                }
953                if (reducedVerb == 1) {
954                    fCurrentContour->addLine(fReducePts.end() - 2);
955                    break;
956                }
957                if (reducedVerb == 2) {
958                    fCurrentContour->addQuad(fReducePts.end() - 3);
959                    break;
960                }
961                fCurrentContour->addCubic(&pointsPtr[-1]);
962                break;
963            case SkPath::kClose_Verb:
964                SkASSERT(fCurrentContour);
965                complete();
966                continue;
967            default:
968                SkDEBUGFAIL("bad verb");
969                return;
970        }
971        pointsPtr += verb;
972        SkASSERT(fCurrentContour);
973    }
974    complete();
975    if (fCurrentContour && !fCurrentContour->fSegments.count()) {
976        fContours.pop_back();
977    }
978}
979
980private:
981    const SkPath& fPath;
982    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
983    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
984    Contour* fCurrentContour;
985    SkTArray<Contour>& fContours;
986    SkTDArray<SkPoint> fReducePts; // segments created on the fly
987};
988
989class Work {
990public:
991    enum CoincidentType {
992        kEmpty,
993        kCombo
994    };
995
996    enum SegmentType {
997        kHorizontalLine_Segment = -1,
998        kVerticalLine_Segment = 0,
999        kLine_Segment = SkPath::kLine_Verb,
1000        kQuad_Segment = SkPath::kQuad_Verb,
1001        kCubic_Segment = SkPath::kCubic_Verb,
1002    };
1003
1004    void addOtherT(int index, double other) {
1005        fContour->fSegments[fIndex].addOtherT(index, other);
1006    }
1007
1008    // Avoid collapsing t values that are close to the same since
1009    // we walk ts to describe consecutive intersections. Since a pair of ts can
1010    // be nearly equal, any problems caused by this should be taken care
1011    // of later.
1012    // On the edge or out of range values are negative; add 2 to get end
1013    int addT(double newT, const Work& other) {
1014        fContour->containsIntercepts();
1015        int index = fContour->fSegments[fIndex].addT(newT,
1016                other.fContour->fSegments[other.fIndex]);
1017        return index;
1018    }
1019
1020    bool advance() {
1021        return ++fIndex < fLast;
1022    }
1023
1024    SkScalar bottom() const {
1025        return bounds().fBottom;
1026    }
1027
1028    const Bounds& bounds() const {
1029        return fContour->fSegments[fIndex].bounds();
1030    }
1031
1032    void checkForMultipleCoincidence() const {
1033        if (fContour->fSegments[fIndex].coincidentCount() > 0) {
1034            fContour->checkMultiple();
1035        }
1036    }
1037
1038    int coincidentT(double newT, const Work& other, CoincidentType type) {
1039        fContour->containsIntercepts();
1040        return fContour->fSegments[fIndex].coincidentT(newT,
1041                other.fContour->fSegments[other.fIndex], (bool) type);
1042    }
1043
1044    const SkPoint* cubic() const {
1045        return fCubic;
1046    }
1047
1048    void init(Contour* contour) {
1049        fContour = contour;
1050        fIndex = 0;
1051        fLast = contour->fSegments.count();
1052    }
1053
1054    SkScalar left() const {
1055        return bounds().fLeft;
1056    }
1057
1058    void promoteToCubic() {
1059        fCubic[0] = pts()[0];
1060        fCubic[2] = pts()[1];
1061        fCubic[3] = pts()[2];
1062        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
1063        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
1064        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
1065        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
1066    }
1067
1068    const SkPoint* pts() const {
1069        return fContour->fSegments[fIndex].pts();
1070    }
1071
1072    SkScalar right() const {
1073        return bounds().fRight;
1074    }
1075
1076    ptrdiff_t segmentIndex() const {
1077        return fIndex;
1078    }
1079
1080    SegmentType segmentType() const {
1081        const Segment& segment = fContour->fSegments[fIndex];
1082        SegmentType type = (SegmentType) segment.verb();
1083        if (type != kLine_Segment) {
1084            return type;
1085        }
1086        if (segment.isHorizontal()) {
1087            return kHorizontalLine_Segment;
1088        }
1089        if (segment.isVertical()) {
1090            return kVerticalLine_Segment;
1091        }
1092        return kLine_Segment;
1093    }
1094
1095    bool startAfter(const Work& after) {
1096        fIndex = after.fIndex;
1097        return advance();
1098    }
1099
1100    SkScalar top() const {
1101        return bounds().fTop;
1102    }
1103
1104    SkPath::Verb verb() const {
1105        return fContour->fSegments[fIndex].verb();
1106    }
1107
1108    SkScalar x() const {
1109        return bounds().fLeft;
1110    }
1111
1112    bool xFlipped() const {
1113        return x() != pts()[0].fX;
1114    }
1115
1116    SkScalar y() const {
1117        return bounds().fTop;
1118    }
1119
1120    bool yFlipped() const {
1121        return y() != pts()[0].fX;
1122    }
1123
1124protected:
1125    Contour* fContour;
1126    SkPoint fCubic[4];
1127    int fIndex;
1128    int fLast;
1129};
1130
1131static void debugShowLineIntersection(int pts, const Work& wt,
1132        const Work& wn, const double wtTs[2], const double wnTs[2]) {
1133#if DEBUG_ADD_INTERSECTING_TS
1134    if (!pts) {
1135        return;
1136    }
1137    SkPoint wtOutPt, wnOutPt;
1138    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
1139    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
1140    SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
1141            __FUNCTION__,
1142            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
1143            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
1144    if (pts == 2) {
1145        SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
1146    }
1147    SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
1148            __FUNCTION__,
1149            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
1150            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
1151    if (pts == 2) {
1152        SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
1153    }
1154#endif
1155}
1156
1157static bool addIntersectTs(Contour* test, Contour* next, int winding) {
1158    if (test != next) {
1159        if (test->bounds().fBottom < next->bounds().fTop) {
1160            return false;
1161        }
1162        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
1163            return true;
1164        }
1165    }
1166    Work wt, wn;
1167    wt.init(test);
1168    wn.init(next);
1169    do {
1170        if (test == next && !wn.startAfter(wt)) {
1171            continue;
1172        }
1173        do {
1174            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
1175                continue;
1176            }
1177            int pts;
1178            Intersections ts;
1179            bool swap = false;
1180            switch (wt.segmentType()) {
1181                case Work::kHorizontalLine_Segment:
1182                    swap = true;
1183                    switch (wn.segmentType()) {
1184                        case Work::kHorizontalLine_Segment:
1185                        case Work::kVerticalLine_Segment:
1186                        case Work::kLine_Segment: {
1187                            pts = HLineIntersect(wn.pts(), wt.left(),
1188                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1189                            break;
1190                        }
1191                        case Work::kQuad_Segment: {
1192                            pts = HQuadIntersect(wn.pts(), wt.left(),
1193                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1194                            break;
1195                        }
1196                        case Work::kCubic_Segment: {
1197                            pts = HCubicIntersect(wn.pts(), wt.left(),
1198                                    wt.right(), wt.y(), wt.xFlipped(), ts);
1199                            break;
1200                        }
1201                        default:
1202                            SkASSERT(0);
1203                    }
1204                    break;
1205                case Work::kVerticalLine_Segment:
1206                    swap = true;
1207                    switch (wn.segmentType()) {
1208                        case Work::kHorizontalLine_Segment:
1209                        case Work::kVerticalLine_Segment:
1210                        case Work::kLine_Segment: {
1211                            pts = VLineIntersect(wn.pts(), wt.top(),
1212                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
1213                            break;
1214                        }
1215                        case Work::kQuad_Segment: {
1216                            pts = VQuadIntersect(wn.pts(), wt.top(),
1217                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
1218                            break;
1219                        }
1220                        case Work::kCubic_Segment: {
1221                            pts = VCubicIntersect(wn.pts(), wt.top(),
1222                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
1223                            break;
1224                        }
1225                        default:
1226                            SkASSERT(0);
1227                    }
1228                    break;
1229                case Work::kLine_Segment:
1230                    switch (wn.segmentType()) {
1231                        case Work::kHorizontalLine_Segment:
1232                            pts = HLineIntersect(wt.pts(), wn.left(),
1233                                    wn.right(), wn.y(), wn.xFlipped(), ts);
1234                            break;
1235                        case Work::kVerticalLine_Segment:
1236                            pts = VLineIntersect(wt.pts(), wn.top(),
1237                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
1238                            break;
1239                        case Work::kLine_Segment: {
1240                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
1241                            debugShowLineIntersection(pts, wt, wn,
1242                                    ts.fT[1], ts.fT[0]);
1243                            break;
1244                        }
1245                        case Work::kQuad_Segment: {
1246                            swap = true;
1247                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
1248                            break;
1249                        }
1250                        case Work::kCubic_Segment: {
1251                            swap = true;
1252                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
1253                            break;
1254                        }
1255                        default:
1256                            SkASSERT(0);
1257                    }
1258                    break;
1259                case Work::kQuad_Segment:
1260                    switch (wn.segmentType()) {
1261                        case Work::kHorizontalLine_Segment:
1262                            pts = HQuadIntersect(wt.pts(), wn.left(),
1263                                    wn.right(), wn.y(), wn.xFlipped(), ts);
1264                            break;
1265                        case Work::kVerticalLine_Segment:
1266                            pts = VQuadIntersect(wt.pts(), wn.top(),
1267                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
1268                            break;
1269                        case Work::kLine_Segment: {
1270                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
1271                            break;
1272                        }
1273                        case Work::kQuad_Segment: {
1274                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
1275                            break;
1276                        }
1277                        case Work::kCubic_Segment: {
1278                            wt.promoteToCubic();
1279                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
1280                            break;
1281                        }
1282                        default:
1283                            SkASSERT(0);
1284                    }
1285                    break;
1286                case Work::kCubic_Segment:
1287                    switch (wn.segmentType()) {
1288                        case Work::kHorizontalLine_Segment:
1289                            pts = HCubicIntersect(wt.pts(), wn.left(),
1290                                    wn.right(), wn.y(), wn.xFlipped(), ts);
1291                            break;
1292                        case Work::kVerticalLine_Segment:
1293                            pts = VCubicIntersect(wt.pts(), wn.top(),
1294                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
1295                            break;
1296                        case Work::kLine_Segment: {
1297                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
1298                            break;
1299                        }
1300                        case Work::kQuad_Segment: {
1301                            wn.promoteToCubic();
1302                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
1303                            break;
1304                        }
1305                        case Work::kCubic_Segment: {
1306                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
1307                            break;
1308                        }
1309                        default:
1310                            SkASSERT(0);
1311                    }
1312                    break;
1313                default:
1314                    SkASSERT(0);
1315            }
1316            // in addition to recording T values, record matching segment
1317            int pt = 0;
1318            if (pts == 2 && wn.segmentType() <= Work::kLine_Segment
1319                    && wt.segmentType() <= Work::kLine_Segment) {
1320                wt.checkForMultipleCoincidence();
1321                wn.checkForMultipleCoincidence();
1322                // see if segment have same (combo) or opposite (empty) winding
1323                int testTAt;
1324                if ((ts.fT[0][0] < ts.fT[0][1]) ^ (ts.fT[1][0] < ts.fT[1][1])
1325                        || winding == 1) { // even-odd
1326                    testTAt = wt.coincidentT(ts.fT[swap][0], wn, Work::kEmpty);
1327                } else {
1328                    testTAt = wt.coincidentT(ts.fT[swap][0], wn, Work::kCombo);
1329                }
1330                int nextTAt = wn.coincidentT(ts.fT[!swap][0], wn, Work::kEmpty);
1331                wt.addOtherT(testTAt, ts.fT[!swap][0]);
1332                wn.addOtherT(nextTAt, ts.fT[swap][0]);
1333                pt = 1;
1334            }
1335            for (; pt < pts; ++pt) {
1336                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
1337                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
1338                int testTAt = wt.addT(ts.fT[swap][pt], wn);
1339                int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
1340                wt.addOtherT(testTAt, ts.fT[!swap][pt]);
1341                wn.addOtherT(nextTAt, ts.fT[swap][pt]);
1342            }
1343        } while (wn.advance());
1344    } while (wt.advance());
1345    return true;
1346}
1347
1348// check if a segment is coincident three or more ways, and
1349// see if coincidence is formed by clipping non-concident segments
1350static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) {
1351    int contourCount = contourList.count();
1352    for (size_t cIndex = 0; cIndex < contourCount; ++cIndex) {
1353        Contour* contour = contourList[cIndex];
1354        contour->resolveCoincidence();
1355    }
1356    for (size_t cIndex = 0; cIndex < contourCount; ++cIndex) {
1357        Contour* contour = contourList[cIndex];
1358        contour->findTooCloseToCall(winding);
1359    }
1360}
1361
1362// Each segment may have an inside or an outside. Segments contained within
1363// winding may have insides on either side, and form a contour that should be
1364// ignored. Segments that are coincident with opposing direction segments may
1365// have outsides on either side, and should also disappear.
1366// 'Normal' segments will have one inside and one outside. Subsequent connections
1367// when winding should follow the intersection direction. If more than one edge
1368// is an option, choose first edge that continues the inside.
1369
1370static void bridge(SkTDArray<Contour*>& contourList) {
1371    // Start at the top. Above the top is outside, below is inside.
1372    Contour* topContour = contourList[0];
1373    Segment& topStart = topContour->topSegment();
1374    int index;
1375    const Segment* topSegment = topStart.findTop(index);
1376 //   start here ;
1377    // find span
1378    // mark neighbors winding coverage
1379    // output span
1380    // mark span as processed
1381
1382}
1383
1384static void makeContourList(SkTArray<Contour>& contours, Contour& sentinel,
1385        SkTDArray<Contour*>& list) {
1386    int count = contours.count();
1387    if (count == 0) {
1388        return;
1389    }
1390    for (int index = 0; index < count; ++index) {
1391        *list.append() = &contours[index];
1392    }
1393    *list.append() = &sentinel;
1394    QSort<Contour>(list.begin(), list.end() - 1);
1395}
1396
1397void simplifyx(const SkPath& path, bool asFill, SkPath& simple) {
1398    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
1399    int winding = (path.getFillType() & 1) ? 1 : -1;
1400    simple.reset();
1401    simple.setFillType(SkPath::kEvenOdd_FillType);
1402
1403    // turn path into list of segments
1404    SkTArray<Contour> contours;
1405    // FIXME: add self-intersecting cubics' T values to segment
1406    EdgeBuilder builder(path, contours);
1407    SkTDArray<Contour*> contourList;
1408    Contour sentinel;
1409    sentinel.reset();
1410    makeContourList(contours, sentinel, contourList);
1411    Contour** currentPtr = contourList.begin();
1412    if (!currentPtr) {
1413        return;
1414    }
1415    // find all intersections between segments
1416    do {
1417        Contour** nextPtr = currentPtr;
1418        Contour* current = *currentPtr++;
1419        Contour* next;
1420        do {
1421            next = *nextPtr++;
1422        } while (next != &sentinel && addIntersectTs(current, next, winding));
1423    } while (*currentPtr != &sentinel);
1424    // eat through coincident edges
1425    coincidenceCheck(contourList, winding);
1426    // construct closed contours
1427    bridge(contourList);
1428}
1429
1430