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