Simplify.cpp revision 85ec74ca543b13739db1ad55dedd7bdfae4ab1a6
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 PIN_ADD_T 0
29#define TRY_ROTATE 1
30#define ONE_PASS_COINCIDENCE_CHECK 0
31#define APPROXIMATE_CUBICS 1
32
33#define DEBUG_UNUSED 0 // set to expose unused functions
34#define FORCE_RELEASE 0  // set force release to 1 for multiple thread -- no debugging
35
36#if FORCE_RELEASE || defined SK_RELEASE
37
38const bool gRunTestsInOneThread = false;
39
40#define DEBUG_ACTIVE_SPANS 0
41#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
42#define DEBUG_ADD_INTERSECTING_TS 0
43#define DEBUG_ADD_T_PAIR 0
44#define DEBUG_ANGLE 0
45#define DEBUG_ASSEMBLE 0
46#define DEBUG_CONCIDENT 0
47#define DEBUG_CROSS 0
48#define DEBUG_FLOW 0
49#define DEBUG_MARK_DONE 0
50#define DEBUG_PATH_CONSTRUCTION 0
51#define DEBUG_SHOW_WINDING 0
52#define DEBUG_SORT 0
53#define DEBUG_UNSORTABLE 0
54#define DEBUG_WIND_BUMP 0
55#define DEBUG_WINDING 0
56#define DEBUG_WINDING_AT_T 0
57
58#else
59
60const bool gRunTestsInOneThread = true;
61
62#define DEBUG_ACTIVE_SPANS 1
63#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
64#define DEBUG_ADD_INTERSECTING_TS 1
65#define DEBUG_ADD_T_PAIR 1
66#define DEBUG_ANGLE 1
67#define DEBUG_ASSEMBLE 1
68#define DEBUG_CONCIDENT 1
69#define DEBUG_CROSS 0
70#define DEBUG_FLOW 1
71#define DEBUG_MARK_DONE 1
72#define DEBUG_PATH_CONSTRUCTION 1
73#define DEBUG_SHOW_WINDING 0
74#define DEBUG_SORT 1
75#define DEBUG_UNSORTABLE 1
76#define DEBUG_WIND_BUMP 0
77#define DEBUG_WINDING 1
78#define DEBUG_WINDING_AT_T 1
79
80#endif
81
82#define DEBUG_DUMP (DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | DEBUG_PATH_CONSTRUCTION)
83
84#if DEBUG_DUMP
85static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
86// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
87static int gContourID;
88static int gSegmentID;
89#endif
90
91#ifndef DEBUG_TEST
92#define DEBUG_TEST 0
93#endif
94
95#define MAKE_CONST_LINE(line, pts) \
96    const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}
97#define MAKE_CONST_QUAD(quad, pts) \
98    const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
99            {pts[2].fX, pts[2].fY}}
100#define MAKE_CONST_CUBIC(cubic, pts) \
101    const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
102            {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}
103
104static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
105        Intersections& intersections) {
106    MAKE_CONST_LINE(aLine, a);
107    MAKE_CONST_LINE(bLine, b);
108    return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
109}
110
111static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
112        Intersections& intersections) {
113    MAKE_CONST_QUAD(aQuad, a);
114    MAKE_CONST_LINE(bLine, b);
115    return intersect(aQuad, bLine, intersections);
116}
117
118static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],
119        Intersections& intersections) {
120    MAKE_CONST_CUBIC(aCubic, a);
121    MAKE_CONST_LINE(bLine, b);
122    return intersect(aCubic, bLine, intersections);
123}
124
125static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
126        Intersections& intersections) {
127    MAKE_CONST_QUAD(aQuad, a);
128    MAKE_CONST_QUAD(bQuad, b);
129#define TRY_QUARTIC_SOLUTION 1
130#if TRY_QUARTIC_SOLUTION
131    intersect2(aQuad, bQuad, intersections);
132#else
133    intersect(aQuad, bQuad, intersections);
134#endif
135    return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed;
136}
137
138#if APPROXIMATE_CUBICS
139static int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3],
140        Intersections& intersections) {
141    MAKE_CONST_CUBIC(aCubic, a);
142    MAKE_CONST_QUAD(bQuad, b);
143    return intersect(aCubic, bQuad, intersections);
144}
145#endif
146
147static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) {
148    MAKE_CONST_CUBIC(aCubic, a);
149    MAKE_CONST_CUBIC(bCubic, b);
150#if APPROXIMATE_CUBICS
151    intersect2(aCubic, bCubic, intersections);
152#else
153    intersect(aCubic, bCubic, intersections);
154#endif
155    return intersections.fUsed;
156}
157
158static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
159        SkScalar y, bool flipped, Intersections& intersections) {
160    MAKE_CONST_LINE(aLine, a);
161    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
162}
163
164static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
165        SkScalar y, bool flipped, Intersections& intersections) {
166    MAKE_CONST_QUAD(aQuad, a);
167    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
168}
169
170static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
171        SkScalar y, bool flipped, Intersections& intersections) {
172    MAKE_CONST_CUBIC(aCubic, a);
173    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
174}
175
176static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,
177        SkScalar , SkScalar , bool , Intersections& ) = {
178    NULL,
179    HLineIntersect,
180    HQuadIntersect,
181    HCubicIntersect
182};
183
184static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
185        SkScalar x, bool flipped, Intersections& intersections) {
186    MAKE_CONST_LINE(aLine, a);
187    return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
188}
189
190static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
191        SkScalar x, bool flipped, Intersections& intersections) {
192    MAKE_CONST_QUAD(aQuad, a);
193    return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
194}
195
196static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
197        SkScalar x, bool flipped, Intersections& intersections) {
198    MAKE_CONST_CUBIC(aCubic, a);
199    return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
200}
201
202static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
203        SkScalar , SkScalar , bool , Intersections& ) = {
204    NULL,
205    VLineIntersect,
206    VQuadIntersect,
207    VCubicIntersect
208};
209
210static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
211    MAKE_CONST_LINE(line, a);
212    double x, y;
213    xy_at_t(line, t, x, y);
214    out->fX = SkDoubleToScalar(x);
215    out->fY = SkDoubleToScalar(y);
216}
217
218static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
219    MAKE_CONST_QUAD(quad, a);
220    double x, y;
221    xy_at_t(quad, t, x, y);
222    out->fX = SkDoubleToScalar(x);
223    out->fY = SkDoubleToScalar(y);
224}
225
226static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {
227    MAKE_CONST_QUAD(quad, a);
228    xy_at_t(quad, t, out->x, out->y);
229}
230
231static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
232    MAKE_CONST_CUBIC(cubic, a);
233    double x, y;
234    xy_at_t(cubic, t, x, y);
235    out->fX = SkDoubleToScalar(x);
236    out->fY = SkDoubleToScalar(y);
237}
238
239static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
240    NULL,
241    LineXYAtT,
242    QuadXYAtT,
243    CubicXYAtT
244};
245
246static SkScalar LineXAtT(const SkPoint a[2], double t) {
247    MAKE_CONST_LINE(aLine, a);
248    double x;
249    xy_at_t(aLine, t, x, *(double*) 0);
250    return SkDoubleToScalar(x);
251}
252
253static SkScalar QuadXAtT(const SkPoint a[3], double t) {
254    MAKE_CONST_QUAD(quad, a);
255    double x;
256    xy_at_t(quad, t, x, *(double*) 0);
257    return SkDoubleToScalar(x);
258}
259
260static SkScalar CubicXAtT(const SkPoint a[4], double t) {
261    MAKE_CONST_CUBIC(cubic, a);
262    double x;
263    xy_at_t(cubic, t, x, *(double*) 0);
264    return SkDoubleToScalar(x);
265}
266
267static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
268    NULL,
269    LineXAtT,
270    QuadXAtT,
271    CubicXAtT
272};
273
274static SkScalar LineYAtT(const SkPoint a[2], double t) {
275    MAKE_CONST_LINE(aLine, a);
276    double y;
277    xy_at_t(aLine, t, *(double*) 0, y);
278    return SkDoubleToScalar(y);
279}
280
281static SkScalar QuadYAtT(const SkPoint a[3], double t) {
282    MAKE_CONST_QUAD(quad, a);
283    double y;
284    xy_at_t(quad, t, *(double*) 0, y);
285    return SkDoubleToScalar(y);
286}
287
288static SkScalar CubicYAtT(const SkPoint a[4], double t) {
289    MAKE_CONST_CUBIC(cubic, a);
290    double y;
291    xy_at_t(cubic, t, *(double*) 0, y);
292    return SkDoubleToScalar(y);
293}
294
295static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
296    NULL,
297    LineYAtT,
298    QuadYAtT,
299    CubicYAtT
300};
301
302static SkScalar LineDXAtT(const SkPoint a[2], double ) {
303    return a[1].fX - a[0].fX;
304}
305
306static SkScalar QuadDXAtT(const SkPoint a[3], double t) {
307    MAKE_CONST_QUAD(quad, a);
308    double x = dx_at_t(quad, t);
309    return SkDoubleToScalar(x);
310}
311
312static SkScalar CubicDXAtT(const SkPoint a[4], double t) {
313    MAKE_CONST_CUBIC(cubic, a);
314    double x = dx_at_t(cubic, t);
315    return SkDoubleToScalar(x);
316}
317
318static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
319    NULL,
320    LineDXAtT,
321    QuadDXAtT,
322    CubicDXAtT
323};
324
325static SkScalar LineDYAtT(const SkPoint a[2], double ) {
326    return a[1].fY - a[0].fY;
327}
328
329static SkScalar QuadDYAtT(const SkPoint a[3], double t) {
330    MAKE_CONST_QUAD(quad, a);
331    double y = dy_at_t(quad, t);
332    return SkDoubleToScalar(y);
333}
334
335static SkScalar CubicDYAtT(const SkPoint a[4], double t) {
336    MAKE_CONST_CUBIC(cubic, a);
337    double y = dy_at_t(cubic, t);
338    return SkDoubleToScalar(y);
339}
340
341static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {
342    NULL,
343    LineDYAtT,
344    QuadDYAtT,
345    CubicDYAtT
346};
347
348static void LineSubDivide(const SkPoint a[2], double startT, double endT,
349        SkPoint sub[2]) {
350    MAKE_CONST_LINE(aLine, a);
351    _Line dst;
352    sub_divide(aLine, startT, endT, dst);
353    sub[0].fX = SkDoubleToScalar(dst[0].x);
354    sub[0].fY = SkDoubleToScalar(dst[0].y);
355    sub[1].fX = SkDoubleToScalar(dst[1].x);
356    sub[1].fY = SkDoubleToScalar(dst[1].y);
357}
358
359static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
360        SkPoint sub[3]) {
361    MAKE_CONST_QUAD(aQuad, a);
362    Quadratic dst;
363    sub_divide(aQuad, startT, endT, dst);
364    sub[0].fX = SkDoubleToScalar(dst[0].x);
365    sub[0].fY = SkDoubleToScalar(dst[0].y);
366    sub[1].fX = SkDoubleToScalar(dst[1].x);
367    sub[1].fY = SkDoubleToScalar(dst[1].y);
368    sub[2].fX = SkDoubleToScalar(dst[2].x);
369    sub[2].fY = SkDoubleToScalar(dst[2].y);
370}
371
372static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
373        SkPoint sub[4]) {
374    MAKE_CONST_CUBIC(aCubic, a);
375    Cubic dst;
376    sub_divide(aCubic, startT, endT, dst);
377    sub[0].fX = SkDoubleToScalar(dst[0].x);
378    sub[0].fY = SkDoubleToScalar(dst[0].y);
379    sub[1].fX = SkDoubleToScalar(dst[1].x);
380    sub[1].fY = SkDoubleToScalar(dst[1].y);
381    sub[2].fX = SkDoubleToScalar(dst[2].x);
382    sub[2].fY = SkDoubleToScalar(dst[2].y);
383    sub[3].fX = SkDoubleToScalar(dst[3].x);
384    sub[3].fY = SkDoubleToScalar(dst[3].y);
385}
386
387static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
388        SkPoint []) = {
389    NULL,
390    LineSubDivide,
391    QuadSubDivide,
392    CubicSubDivide
393};
394
395static void LineSubDivideHD(const SkPoint a[2], double startT, double endT,
396        _Line sub) {
397    MAKE_CONST_LINE(aLine, a);
398    _Line dst;
399    sub_divide(aLine, startT, endT, dst);
400    sub[0] = dst[0];
401    sub[1] = dst[1];
402}
403
404static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT,
405        Quadratic sub) {
406    MAKE_CONST_QUAD(aQuad, a);
407    Quadratic dst;
408    sub_divide(aQuad, startT, endT, dst);
409    sub[0] = dst[0];
410    sub[1] = dst[1];
411    sub[2] = dst[2];
412}
413
414static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT,
415        Cubic sub) {
416    MAKE_CONST_CUBIC(aCubic, a);
417    Cubic dst;
418    sub_divide(aCubic, startT, endT, dst);
419    sub[0] = dst[0];
420    sub[1] = dst[1];
421    sub[2] = dst[2];
422    sub[3] = dst[3];
423}
424
425#if DEBUG_UNUSED
426static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
427        SkRect& bounds) {
428    SkPoint dst[3];
429    QuadSubDivide(a, startT, endT, dst);
430    bounds.fLeft = bounds.fRight = dst[0].fX;
431    bounds.fTop = bounds.fBottom = dst[0].fY;
432    for (int index = 1; index < 3; ++index) {
433        bounds.growToInclude(dst[index].fX, dst[index].fY);
434    }
435}
436
437static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
438        SkRect& bounds) {
439    SkPoint dst[4];
440    CubicSubDivide(a, startT, endT, dst);
441    bounds.fLeft = bounds.fRight = dst[0].fX;
442    bounds.fTop = bounds.fBottom = dst[0].fY;
443    for (int index = 1; index < 4; ++index) {
444        bounds.growToInclude(dst[index].fX, dst[index].fY);
445    }
446}
447#endif
448
449static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
450        SkTDArray<SkPoint>& reducePts) {
451    MAKE_CONST_QUAD(aQuad, a);
452    Quadratic dst;
453    int order = reduceOrder(aQuad, dst);
454    if (order == 2) { // quad became line
455        for (int index = 0; index < order; ++index) {
456            SkPoint* pt = reducePts.append();
457            pt->fX = SkDoubleToScalar(dst[index].x);
458            pt->fY = SkDoubleToScalar(dst[index].y);
459        }
460    }
461    return (SkPath::Verb) (order - 1);
462}
463
464static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
465        SkTDArray<SkPoint>& reducePts) {
466    MAKE_CONST_CUBIC(aCubic, a);
467    Cubic dst;
468    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
469    if (order == 2 || order == 3) { // cubic became line or quad
470        for (int index = 0; index < order; ++index) {
471            SkPoint* pt = reducePts.append();
472            pt->fX = SkDoubleToScalar(dst[index].x);
473            pt->fY = SkDoubleToScalar(dst[index].y);
474        }
475    }
476    return (SkPath::Verb) (order - 1);
477}
478
479static bool QuadIsLinear(const SkPoint a[3]) {
480    MAKE_CONST_QUAD(aQuad, a);
481    return isLinear(aQuad, 0, 2);
482}
483
484static bool CubicIsLinear(const SkPoint a[4]) {
485    MAKE_CONST_CUBIC(aCubic, a);
486    return isLinear(aCubic, 0, 3);
487}
488
489static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
490    MAKE_CONST_LINE(aLine, a);
491    double x[2];
492    xy_at_t(aLine, startT, x[0], *(double*) 0);
493    xy_at_t(aLine, endT, x[1], *(double*) 0);
494    return SkMinScalar((float) x[0], (float) x[1]);
495}
496
497static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
498    MAKE_CONST_QUAD(aQuad, a);
499    return (float) leftMostT(aQuad, startT, endT);
500}
501
502static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
503    MAKE_CONST_CUBIC(aCubic, a);
504    return (float) leftMostT(aCubic, startT, endT);
505}
506
507static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
508    NULL,
509    LineLeftMost,
510    QuadLeftMost,
511    CubicLeftMost
512};
513
514#if 0 // currently unused
515static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
516        Intersections& intersections) {
517    MAKE_CONST_QUAD(aQuad, a);
518    MAKE_CONST_LINE(bLine, b);
519    return intersectRay(aQuad, bLine, intersections);
520}
521#endif
522
523static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine,
524        Intersections& intersections) {
525    MAKE_CONST_QUAD(aQuad, a);
526    return intersectRay(aQuad, bLine, intersections);
527}
528
529static bool LineVertical(const SkPoint a[2], double startT, double endT) {
530    MAKE_CONST_LINE(aLine, a);
531    double x[2];
532    xy_at_t(aLine, startT, x[0], *(double*) 0);
533    xy_at_t(aLine, endT, x[1], *(double*) 0);
534    return AlmostEqualUlps((float) x[0], (float) x[1]);
535}
536
537static bool QuadVertical(const SkPoint a[3], double startT, double endT) {
538    SkPoint dst[3];
539    QuadSubDivide(a, startT, endT, dst);
540    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
541}
542
543static bool CubicVertical(const SkPoint a[4], double startT, double endT) {
544    SkPoint dst[4];
545    CubicSubDivide(a, startT, endT, dst);
546    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
547            && AlmostEqualUlps(dst[2].fX, dst[3].fX);
548}
549
550static bool (* const SegmentVertical[])(const SkPoint [], double , double) = {
551    NULL,
552    LineVertical,
553    QuadVertical,
554    CubicVertical
555};
556
557class Segment;
558
559struct Span {
560    Segment* fOther;
561    mutable SkPoint fPt; // lazily computed as needed
562    double fT;
563    double fOtherT; // value at fOther[fOtherIndex].fT
564    int fOtherIndex;  // can't be used during intersection
565    int fWindSum; // accumulated from contours surrounding this one.
566    int fOppSum; // for binary operators: the opposite winding sum
567    int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
568    int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
569    bool fDone; // if set, this span to next higher T has been processed
570    bool fUnsortableStart; // set when start is part of an unsortable pair
571    bool fUnsortableEnd; // set when end is part of an unsortable pair
572    bool fTiny; // if set, span may still be considered once for edge following
573};
574
575// sorting angles
576// given angles of {dx dy ddx ddy dddx dddy} sort them
577class Angle {
578public:
579    // FIXME: this is bogus for quads and cubics
580    // if the quads and cubics' line from end pt to ctrl pt are coincident,
581    // there's no obvious way to determine the curve ordering from the
582    // derivatives alone. In particular, if one quadratic's coincident tangent
583    // is longer than the other curve, the final control point can place the
584    // longer curve on either side of the shorter one.
585    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
586    // may provide some help, but nothing has been figured out yet.
587
588    /*(
589    for quads and cubics, set up a parameterized line (e.g. LineParameters )
590    for points [0] to [1]. See if point [2] is on that line, or on one side
591    or the other. If it both quads' end points are on the same side, choose
592    the shorter tangent. If the tangents are equal, choose the better second
593    tangent angle
594
595    maybe I could set up LineParameters lazily
596    */
597    bool operator<(const Angle& rh) const {
598        double y = dy();
599        double ry = rh.dy();
600        if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
601            return y < 0;
602        }
603        double x = dx();
604        double rx = rh.dx();
605        if (y == 0 && ry == 0 && x * rx < 0) {
606            return x < rx;
607        }
608        double x_ry = x * ry;
609        double rx_y = rx * y;
610        double cmp = x_ry - rx_y;
611        if (!approximately_zero(cmp)) {
612            return cmp < 0;
613        }
614        if (approximately_zero(x_ry) && approximately_zero(rx_y)
615                && !approximately_zero_squared(cmp)) {
616            return cmp < 0;
617        }
618        // at this point, the initial tangent line is coincident
619        if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
620                || !approximately_zero(rh.fSide))) {
621            // FIXME: running demo will trigger this assertion
622            // (don't know if commenting out will trigger further assertion or not)
623            // commenting it out allows demo to run in release, though
624     //       SkASSERT(fSide != rh.fSide);
625            return fSide < rh.fSide;
626        }
627        // see if either curve can be lengthened and try the tangent compare again
628        if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
629                && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
630            Angle longer = *this;
631            Angle rhLonger = rh;
632            if (longer.lengthen() | rhLonger.lengthen()) {
633                return longer < rhLonger;
634            }
635    #if 0
636            // what if we extend in the other direction?
637            longer = *this;
638            rhLonger = rh;
639            if (longer.reverseLengthen() | rhLonger.reverseLengthen()) {
640                return longer < rhLonger;
641            }
642    #endif
643        }
644        if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
645                || (rh.fVerb == SkPath::kLine_Verb
646                && approximately_zero(rx) && approximately_zero(ry))) {
647            // See general unsortable comment below. This case can happen when
648            // one line has a non-zero change in t but no change in x and y.
649            fUnsortable = true;
650            rh.fUnsortable = true;
651            return this < &rh; // even with no solution, return a stable sort
652        }
653        if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
654                || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
655            fUnsortable = true;
656            rh.fUnsortable = true;
657            return this < &rh; // even with no solution, return a stable sort
658        }
659        SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
660        SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
661        // FIXME: until I can think of something better, project a ray from the
662        // end of the shorter tangent to midway between the end points
663        // through both curves and use the resulting angle to sort
664        // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
665        double len = fTangent1.normalSquared();
666        double rlen = rh.fTangent1.normalSquared();
667        _Line ray;
668        Intersections i, ri;
669        int roots, rroots;
670        bool flip = false;
671        do {
672            const Quadratic& q = (len < rlen) ^ flip ? fQ : rh.fQ;
673            double midX = (q[0].x + q[2].x) / 2;
674            double midY = (q[0].y + q[2].y) / 2;
675            ray[0] = q[1];
676            ray[1].x = midX;
677            ray[1].y = midY;
678            SkASSERT(ray[0] != ray[1]);
679            roots = QuadRayIntersect(fPts, ray, i);
680            rroots = QuadRayIntersect(rh.fPts, ray, ri);
681        } while ((roots == 0 || rroots == 0) && (flip ^= true));
682        if (roots == 0 || rroots == 0) {
683            // FIXME: we don't have a solution in this case. The interim solution
684            // is to mark the edges as unsortable, exclude them from this and
685            // future computations, and allow the returned path to be fragmented
686            fUnsortable = true;
687            rh.fUnsortable = true;
688            return this < &rh; // even with no solution, return a stable sort
689        }
690        _Point loc;
691        double best = SK_ScalarInfinity;
692        double dx, dy, dist;
693        int index;
694        for (index = 0; index < roots; ++index) {
695            QuadXYAtT(fPts, i.fT[0][index], &loc);
696            dx = loc.x - ray[0].x;
697            dy = loc.y - ray[0].y;
698            dist = dx * dx + dy * dy;
699            if (best > dist) {
700                best = dist;
701            }
702        }
703        for (index = 0; index < rroots; ++index) {
704            QuadXYAtT(rh.fPts, ri.fT[0][index], &loc);
705            dx = loc.x - ray[0].x;
706            dy = loc.y - ray[0].y;
707            dist = dx * dx + dy * dy;
708            if (best > dist) {
709                return fSide < 0;
710            }
711        }
712        return fSide > 0;
713    }
714
715    double dx() const {
716        return fTangent1.dx();
717    }
718
719    double dy() const {
720        return fTangent1.dy();
721    }
722
723    int end() const {
724        return fEnd;
725    }
726
727    bool isHorizontal() const {
728        return dy() == 0 && fVerb == SkPath::kLine_Verb;
729    }
730
731    bool lengthen() {
732        int newEnd = fEnd;
733        if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
734            fEnd = newEnd;
735            setSpans();
736            return true;
737        }
738        return false;
739    }
740
741    bool reverseLengthen() {
742        if (fReversed) {
743            return false;
744        }
745        int newEnd = fStart;
746        if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
747            fEnd = newEnd;
748            fReversed = true;
749            setSpans();
750            return true;
751        }
752        return false;
753    }
754
755    void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
756            int start, int end, const SkTDArray<Span>& spans) {
757        fSegment = segment;
758        fStart = start;
759        fEnd = end;
760        fPts = orig;
761        fVerb = verb;
762        fSpans = &spans;
763        fReversed = false;
764        fUnsortable = false;
765        setSpans();
766    }
767
768
769    void setSpans() {
770        double startT = (*fSpans)[fStart].fT;
771        double endT = (*fSpans)[fEnd].fT;
772        switch (fVerb) {
773        case SkPath::kLine_Verb:
774            _Line l;
775            LineSubDivideHD(fPts, startT, endT, l);
776            // OPTIMIZATION: for pure line compares, we never need fTangent1.c
777            fTangent1.lineEndPoints(l);
778            fSide = 0;
779            break;
780        case SkPath::kQuad_Verb:
781            QuadSubDivideHD(fPts, startT, endT, fQ);
782            fTangent1.quadEndPoints(fQ, 0, 1);
783            fSide = -fTangent1.pointDistance(fQ[2]); // not normalized -- compare sign only
784            break;
785        case SkPath::kCubic_Verb:
786            Cubic c;
787            CubicSubDivideHD(fPts, startT, endT, c);
788            fTangent1.cubicEndPoints(c, 0, 1);
789            fSide = -fTangent1.pointDistance(c[2]); // not normalized -- compare sign only
790            break;
791        default:
792            SkASSERT(0);
793        }
794        fUnsortable = dx() == 0 && dy() == 0;
795        if (fUnsortable) {
796            return;
797        }
798        SkASSERT(fStart != fEnd);
799        int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
800        for (int index = fStart; index != fEnd; index += step) {
801#if 1
802            const Span& thisSpan = (*fSpans)[index];
803            const Span& nextSpan = (*fSpans)[index + step];
804            if (thisSpan.fTiny || thisSpan.fT == nextSpan.fT) {
805                continue;
806            }
807            fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
808#if DEBUG_UNSORTABLE
809            if (fUnsortable) {
810                SkPoint iPt, ePt;
811                (*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt);
812                (*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt);
813                SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
814                        index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
815            }
816#endif
817            return;
818#else
819            if ((*fSpans)[index].fUnsortableStart) {
820                fUnsortable = true;
821                return;
822            }
823#endif
824        }
825#if 1
826#if DEBUG_UNSORTABLE
827        SkPoint iPt, ePt;
828        (*SegmentXYAtT[fVerb])(fPts, startT, &iPt);
829        (*SegmentXYAtT[fVerb])(fPts, endT, &ePt);
830        SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
831            fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
832#endif
833        fUnsortable = true;
834#endif
835    }
836
837    Segment* segment() const {
838        return const_cast<Segment*>(fSegment);
839    }
840
841    int sign() const {
842        return SkSign32(fStart - fEnd);
843    }
844
845    const SkTDArray<Span>* spans() const {
846        return fSpans;
847    }
848
849    int start() const {
850        return fStart;
851    }
852
853    bool unsortable() const {
854        return fUnsortable;
855    }
856
857#if DEBUG_ANGLE
858    const SkPoint* pts() const {
859        return fPts;
860    }
861
862    SkPath::Verb verb() const {
863        return fVerb;
864    }
865
866    void debugShow(const SkPoint& a) const {
867        SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
868    }
869#endif
870
871private:
872    const SkPoint* fPts;
873    Quadratic fQ;
874    SkPath::Verb fVerb;
875    double fSide;
876    LineParameters fTangent1;
877    const SkTDArray<Span>* fSpans;
878    const Segment* fSegment;
879    int fStart;
880    int fEnd;
881    bool fReversed;
882    mutable bool fUnsortable; // this alone is editable by the less than operator
883};
884
885// Bounds, unlike Rect, does not consider a line to be empty.
886struct Bounds : public SkRect {
887    static bool Intersects(const Bounds& a, const Bounds& b) {
888        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
889                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
890    }
891
892    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
893        if (left < fLeft) {
894            fLeft = left;
895        }
896        if (top < fTop) {
897            fTop = top;
898        }
899        if (right > fRight) {
900            fRight = right;
901        }
902        if (bottom > fBottom) {
903            fBottom = bottom;
904        }
905    }
906
907    void add(const Bounds& toAdd) {
908        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
909    }
910
911    void add(const SkPoint& pt) {
912        if (pt.fX < fLeft) fLeft = pt.fX;
913        if (pt.fY < fTop) fTop = pt.fY;
914        if (pt.fX > fRight) fRight = pt.fX;
915        if (pt.fY > fBottom) fBottom = pt.fY;
916    }
917
918    bool isEmpty() {
919        return fLeft > fRight || fTop > fBottom
920                || (fLeft == fRight && fTop == fBottom)
921                || isnan(fLeft) || isnan(fRight)
922                || isnan(fTop) || isnan(fBottom);
923    }
924
925    void setCubicBounds(const SkPoint a[4]) {
926        _Rect dRect;
927        MAKE_CONST_CUBIC(cubic, a);
928        dRect.setBounds(cubic);
929        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
930                (float) dRect.bottom);
931    }
932
933    void setQuadBounds(const SkPoint a[3]) {
934        MAKE_CONST_QUAD(quad, a);
935        _Rect dRect;
936        dRect.setBounds(quad);
937        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
938                (float) dRect.bottom);
939    }
940
941    void setPoint(const SkPoint& pt) {
942        fLeft = fRight = pt.fX;
943        fTop = fBottom = pt.fY;
944    }
945};
946
947// OPTIMIZATION: does the following also work, and is it any faster?
948// return outerWinding * innerWinding > 0
949//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
950static bool useInnerWinding(int outerWinding, int innerWinding) {
951  //  SkASSERT(outerWinding != innerWinding);
952    int absOut = abs(outerWinding);
953    int absIn = abs(innerWinding);
954    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
955    if (outerWinding * innerWinding < 0) {
956#if DEBUG_WINDING
957        SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
958                outerWinding, innerWinding, result ? "true" : "false");
959#endif
960    }
961    return result;
962}
963
964#define F (false)      // discard the edge
965#define T (true)       // keep the edge
966
967static const bool gUnaryActiveEdge[2][2] = {
968//  from=0  from=1
969//  to=0,1  to=0,1
970    {F, T}, {T, F},
971};
972
973static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {
974//                 miFrom=0                              miFrom=1
975//         miTo=0            miTo=1              miTo=0             miTo=1
976//    suFrom=0    1     suFrom=0     1      suFrom=0    1      suFrom=0    1
977//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
978    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
979    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
980    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
981    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
982};
983
984#undef F
985#undef T
986
987// wrap path to keep track of whether the contour is initialized and non-empty
988class PathWrapper {
989public:
990    PathWrapper(SkPath& path)
991        : fPathPtr(&path)
992        , fCloses(0)
993        , fMoves(0)
994    {
995        init();
996    }
997
998    void close() {
999        if (!fHasMove) {
1000            return;
1001        }
1002        bool callClose = isClosed();
1003        lineTo();
1004        if (fEmpty) {
1005            return;
1006        }
1007        if (callClose) {
1008    #if DEBUG_PATH_CONSTRUCTION
1009            SkDebugf("path.close();\n");
1010    #endif
1011            fPathPtr->close();
1012            fCloses++;
1013        }
1014        init();
1015    }
1016
1017    void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
1018        lineTo();
1019        moveTo();
1020        fDefer[1] = pt3;
1021        nudge();
1022        fDefer[0] = fDefer[1];
1023#if DEBUG_PATH_CONSTRUCTION
1024        SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
1025                pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1026#endif
1027        fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1028        fEmpty = false;
1029    }
1030
1031    void deferredLine(const SkPoint& pt) {
1032        if (pt == fDefer[1]) {
1033            return;
1034        }
1035        if (changedSlopes(pt)) {
1036            lineTo();
1037            fDefer[0] = fDefer[1];
1038        }
1039        fDefer[1] = pt;
1040    }
1041
1042    void deferredMove(const SkPoint& pt) {
1043        fMoved = true;
1044        fHasMove = true;
1045        fEmpty = true;
1046        fDefer[0] = fDefer[1] = pt;
1047    }
1048
1049    void deferredMoveLine(const SkPoint& pt) {
1050        if (!fHasMove) {
1051            deferredMove(pt);
1052        }
1053        deferredLine(pt);
1054    }
1055
1056    bool hasMove() const {
1057        return fHasMove;
1058    }
1059
1060    void init() {
1061        fEmpty = true;
1062        fHasMove = false;
1063        fMoved = false;
1064    }
1065
1066    bool isClosed() const {
1067        return !fEmpty && fFirstPt == fDefer[1];
1068    }
1069
1070    void lineTo() {
1071        if (fDefer[0] == fDefer[1]) {
1072            return;
1073        }
1074        moveTo();
1075        nudge();
1076        fEmpty = false;
1077#if DEBUG_PATH_CONSTRUCTION
1078        SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
1079#endif
1080        fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);
1081        fDefer[0] = fDefer[1];
1082    }
1083
1084    const SkPath* nativePath() const {
1085        return fPathPtr;
1086    }
1087
1088    void nudge() {
1089        if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)
1090                || !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {
1091            return;
1092        }
1093        fDefer[1] = fFirstPt;
1094    }
1095
1096    void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
1097        lineTo();
1098        moveTo();
1099        fDefer[1] = pt2;
1100        nudge();
1101        fDefer[0] = fDefer[1];
1102#if DEBUG_PATH_CONSTRUCTION
1103        SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
1104                pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1105#endif
1106        fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1107        fEmpty = false;
1108    }
1109
1110    bool someAssemblyRequired() const {
1111        return fCloses < fMoves;
1112    }
1113
1114protected:
1115    bool changedSlopes(const SkPoint& pt) const {
1116        if (fDefer[0] == fDefer[1]) {
1117            return false;
1118        }
1119        SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;
1120        SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;
1121        SkScalar lineDx = pt.fX - fDefer[1].fX;
1122        SkScalar lineDy = pt.fY - fDefer[1].fY;
1123        return deferDx * lineDy != deferDy * lineDx;
1124    }
1125
1126    void moveTo() {
1127        if (!fMoved) {
1128            return;
1129        }
1130        fFirstPt = fDefer[0];
1131#if DEBUG_PATH_CONSTRUCTION
1132        SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);
1133#endif
1134        fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);
1135        fMoved = false;
1136        fMoves++;
1137    }
1138
1139private:
1140    SkPath* fPathPtr;
1141    SkPoint fDefer[2];
1142    SkPoint fFirstPt;
1143    int fCloses;
1144    int fMoves;
1145    bool fEmpty;
1146    bool fHasMove;
1147    bool fMoved;
1148};
1149
1150class Segment {
1151public:
1152    Segment() {
1153#if DEBUG_DUMP
1154        fID = ++gSegmentID;
1155#endif
1156    }
1157
1158    bool operator<(const Segment& rh) const {
1159        return fBounds.fTop < rh.fBounds.fTop;
1160    }
1161
1162    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
1163        if (activeAngleInner(index, done, angles)) {
1164            return true;
1165        }
1166        int lesser = index;
1167        while (--lesser >= 0 && equalPoints(index, lesser)) {
1168            if (activeAngleOther(lesser, done, angles)) {
1169                return true;
1170            }
1171        }
1172        lesser = index;
1173        do {
1174            if (activeAngleOther(index, done, angles)) {
1175                return true;
1176            }
1177        } while (++index < fTs.count() && equalPoints(index, lesser));
1178        return false;
1179    }
1180
1181    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
1182        Span* span = &fTs[index];
1183        Segment* other = span->fOther;
1184        int oIndex = span->fOtherIndex;
1185        return other->activeAngleInner(oIndex, done, angles);
1186    }
1187
1188    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
1189        int next = nextExactSpan(index, 1);
1190        if (next > 0) {
1191            Span& upSpan = fTs[index];
1192            if (upSpan.fWindValue || upSpan.fOppValue) {
1193                addAngle(angles, index, next);
1194                if (upSpan.fDone || upSpan.fUnsortableEnd) {
1195                    done++;
1196                } else if (upSpan.fWindSum != SK_MinS32) {
1197                    return true;
1198                }
1199            } else if (!upSpan.fDone) {
1200                upSpan.fDone = true;
1201                fDoneSpans++;
1202            }
1203        }
1204        int prev = nextExactSpan(index, -1);
1205        // edge leading into junction
1206        if (prev >= 0) {
1207            Span& downSpan = fTs[prev];
1208            if (downSpan.fWindValue || downSpan.fOppValue) {
1209                addAngle(angles, index, prev);
1210                if (downSpan.fDone) {
1211                    done++;
1212                 } else if (downSpan.fWindSum != SK_MinS32) {
1213                    return true;
1214                }
1215            } else if (!downSpan.fDone) {
1216                downSpan.fDone = true;
1217                fDoneSpans++;
1218            }
1219        }
1220        return false;
1221    }
1222
1223    void activeLeftTop(SkPoint& result) const {
1224        SkASSERT(!done());
1225        int count = fTs.count();
1226        result.fX = result.fY = SK_ScalarMax;
1227        bool lastDone = true;
1228        bool lastUnsortable = false;
1229        for (int index = 0; index < count; ++index) {
1230            const Span& span = fTs[index];
1231            if (span.fUnsortableStart | lastUnsortable) {
1232                goto next;
1233            }
1234            if (!span.fDone | !lastDone) {
1235                const SkPoint& xy = xyAtT(index);
1236                if (result.fY < xy.fY) {
1237                    goto next;
1238                }
1239                if (result.fY == xy.fY && result.fX < xy.fX) {
1240                    goto next;
1241                }
1242                result = xy;
1243            }
1244    next:
1245            lastDone = span.fDone;
1246            lastUnsortable = span.fUnsortableEnd;
1247        }
1248    }
1249
1250    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
1251        int sumMiWinding = updateWinding(endIndex, index);
1252        int sumSuWinding = updateOppWinding(endIndex, index);
1253        if (fOperand) {
1254            SkTSwap<int>(sumMiWinding, sumSuWinding);
1255        }
1256        int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1257        return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,
1258                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1259    }
1260
1261    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,
1262            int& sumMiWinding, int& sumSuWinding,
1263            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
1264        setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
1265                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1266        bool miFrom;
1267        bool miTo;
1268        bool suFrom;
1269        bool suTo;
1270        if (operand()) {
1271            miFrom = (oppMaxWinding & xorMiMask) != 0;
1272            miTo = (oppSumWinding & xorMiMask) != 0;
1273            suFrom = (maxWinding & xorSuMask) != 0;
1274            suTo = (sumWinding & xorSuMask) != 0;
1275        } else {
1276            miFrom = (maxWinding & xorMiMask) != 0;
1277            miTo = (sumWinding & xorMiMask) != 0;
1278            suFrom = (oppMaxWinding & xorSuMask) != 0;
1279            suTo = (oppSumWinding & xorSuMask) != 0;
1280        }
1281        bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
1282        SkASSERT(result != -1);
1283        return result;
1284    }
1285
1286    bool activeWinding(int index, int endIndex) {
1287        int sumWinding = updateWinding(endIndex, index);
1288        int maxWinding;
1289        return activeWinding(index, endIndex, maxWinding, sumWinding);
1290    }
1291
1292    bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
1293        setUpWinding(index, endIndex, maxWinding, sumWinding);
1294        bool from = maxWinding != 0;
1295        bool to = sumWinding  != 0;
1296        bool result = gUnaryActiveEdge[from][to];
1297        SkASSERT(result != -1);
1298        return result;
1299    }
1300
1301    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
1302        SkASSERT(start != end);
1303        Angle* angle = angles.append();
1304#if DEBUG_ANGLE
1305        if (angles.count() > 1 && !fTs[start].fTiny) {
1306            SkPoint angle0Pt, newPt;
1307            (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
1308                    (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
1309            (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
1310            SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX));
1311            SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY));
1312        }
1313#endif
1314        angle->set(fPts, fVerb, this, start, end, fTs);
1315    }
1316
1317    void addCancelOutsides(double tStart, double oStart, Segment& other,
1318            double oEnd) {
1319        int tIndex = -1;
1320        int tCount = fTs.count();
1321        int oIndex = -1;
1322        int oCount = other.fTs.count();
1323        do {
1324            ++tIndex;
1325        } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
1326        int tIndexStart = tIndex;
1327        do {
1328            ++oIndex;
1329        } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
1330        int oIndexStart = oIndex;
1331        double nextT;
1332        do {
1333            nextT = fTs[++tIndex].fT;
1334        } while (nextT < 1 && approximately_negative(nextT - tStart));
1335        double oNextT;
1336        do {
1337            oNextT = other.fTs[++oIndex].fT;
1338        } while (oNextT < 1 && approximately_negative(oNextT - oStart));
1339        // at this point, spans before and after are at:
1340        //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1341        // if tIndexStart == 0, no prior span
1342        // if nextT == 1, no following span
1343
1344        // advance the span with zero winding
1345        // if the following span exists (not past the end, non-zero winding)
1346        // connect the two edges
1347        if (!fTs[tIndexStart].fWindValue) {
1348            if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1349    #if DEBUG_CONCIDENT
1350                SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1351                        __FUNCTION__, fID, other.fID, tIndexStart - 1,
1352                        fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
1353                        xyAtT(tIndexStart).fY);
1354    #endif
1355                addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false);
1356            }
1357            if (nextT < 1 && fTs[tIndex].fWindValue) {
1358    #if DEBUG_CONCIDENT
1359                SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1360                        __FUNCTION__, fID, other.fID, tIndex,
1361                        fTs[tIndex].fT, xyAtT(tIndex).fX,
1362                        xyAtT(tIndex).fY);
1363    #endif
1364                addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false);
1365            }
1366        } else {
1367            SkASSERT(!other.fTs[oIndexStart].fWindValue);
1368            if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
1369    #if DEBUG_CONCIDENT
1370                SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1371                        __FUNCTION__, fID, other.fID, oIndexStart - 1,
1372                        other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
1373                        other.xyAtT(oIndexStart).fY);
1374                other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1375    #endif
1376            }
1377            if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
1378    #if DEBUG_CONCIDENT
1379                SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1380                        __FUNCTION__, fID, other.fID, oIndex,
1381                        other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
1382                        other.xyAtT(oIndex).fY);
1383                other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1384    #endif
1385            }
1386        }
1387    }
1388
1389    void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
1390            double oEnd) {
1391        // walk this to outsideTs[0]
1392        // walk other to outsideTs[1]
1393        // if either is > 0, add a pointer to the other, copying adjacent winding
1394        int tIndex = -1;
1395        int oIndex = -1;
1396        double tStart = outsideTs[0];
1397        double oStart = outsideTs[1];
1398        do {
1399            ++tIndex;
1400        } while (!approximately_negative(tStart - fTs[tIndex].fT));
1401        do {
1402            ++oIndex;
1403        } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
1404        if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
1405            addTPair(tStart, other, oStart, false);
1406        }
1407        tStart = fTs[tIndex].fT;
1408        oStart = other.fTs[oIndex].fT;
1409        do {
1410            double nextT;
1411            do {
1412                nextT = fTs[++tIndex].fT;
1413            } while (approximately_negative(nextT - tStart));
1414            tStart = nextT;
1415            do {
1416                nextT = other.fTs[++oIndex].fT;
1417            } while (approximately_negative(nextT - oStart));
1418            oStart = nextT;
1419            if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
1420                break;
1421            }
1422            addTPair(tStart, other, oStart, false);
1423        } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
1424    }
1425
1426    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
1427        init(pts, SkPath::kCubic_Verb, operand, evenOdd);
1428        fBounds.setCubicBounds(pts);
1429    }
1430
1431    /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const {
1432        SkPoint edge[4];
1433        const SkPoint* ePtr;
1434        int lastT = fTs.count() - 1;
1435        if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
1436            ePtr = fPts;
1437        } else {
1438        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
1439            (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
1440            ePtr = edge;
1441        }
1442        if (active) {
1443            bool reverse = ePtr == fPts && start != 0;
1444            if (reverse) {
1445                path.deferredMoveLine(ePtr[fVerb]);
1446                switch (fVerb) {
1447                    case SkPath::kLine_Verb:
1448                        path.deferredLine(ePtr[0]);
1449                        break;
1450                    case SkPath::kQuad_Verb:
1451                        path.quadTo(ePtr[1], ePtr[0]);
1452                        break;
1453                    case SkPath::kCubic_Verb:
1454                        path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);
1455                        break;
1456                    default:
1457                        SkASSERT(0);
1458                }
1459       //         return ePtr[0];
1460           } else {
1461                path.deferredMoveLine(ePtr[0]);
1462                switch (fVerb) {
1463                    case SkPath::kLine_Verb:
1464                        path.deferredLine(ePtr[1]);
1465                        break;
1466                    case SkPath::kQuad_Verb:
1467                        path.quadTo(ePtr[1], ePtr[2]);
1468                        break;
1469                    case SkPath::kCubic_Verb:
1470                        path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);
1471                        break;
1472                    default:
1473                        SkASSERT(0);
1474                }
1475            }
1476        }
1477      //  return ePtr[fVerb];
1478    }
1479
1480    void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
1481        init(pts, SkPath::kLine_Verb, operand, evenOdd);
1482        fBounds.set(pts, 2);
1483    }
1484
1485#if 0
1486    const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {
1487        const SkPoint& pt = xyAtT(tIndex);
1488        if (active) {
1489            path.deferredMove(pt);
1490        }
1491        return pt;
1492    }
1493#endif
1494
1495    // add 2 to edge or out of range values to get T extremes
1496    void addOtherT(int index, double otherT, int otherIndex) {
1497        Span& span = fTs[index];
1498    #if PIN_ADD_T
1499        if (precisely_less_than_zero(otherT)) {
1500            otherT = 0;
1501        } else if (precisely_greater_than_one(otherT)) {
1502            otherT = 1;
1503        }
1504    #endif
1505        span.fOtherT = otherT;
1506        span.fOtherIndex = otherIndex;
1507    }
1508
1509    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
1510        init(pts, SkPath::kQuad_Verb, operand, evenOdd);
1511        fBounds.setQuadBounds(pts);
1512    }
1513
1514    // Defer all coincident edge processing until
1515    // after normal intersections have been computed
1516
1517// no need to be tricky; insert in normal T order
1518// resolve overlapping ts when considering coincidence later
1519
1520    // add non-coincident intersection. Resulting edges are sorted in T.
1521    int addT(double newT, Segment* other) {
1522        // FIXME: in the pathological case where there is a ton of intercepts,
1523        //  binary search?
1524        int insertedAt = -1;
1525        size_t tCount = fTs.count();
1526    #if PIN_ADD_T
1527        // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
1528        if (precisely_less_than_zero(newT)) {
1529            newT = 0;
1530        } else if (precisely_greater_than_one(newT)) {
1531            newT = 1;
1532        }
1533    #endif
1534        for (size_t index = 0; index < tCount; ++index) {
1535            // OPTIMIZATION: if there are three or more identical Ts, then
1536            // the fourth and following could be further insertion-sorted so
1537            // that all the edges are clockwise or counterclockwise.
1538            // This could later limit segment tests to the two adjacent
1539            // neighbors, although it doesn't help with determining which
1540            // circular direction to go in.
1541            if (newT < fTs[index].fT) {
1542                insertedAt = index;
1543                break;
1544            }
1545        }
1546        Span* span;
1547        if (insertedAt >= 0) {
1548            span = fTs.insert(insertedAt);
1549        } else {
1550            insertedAt = tCount;
1551            span = fTs.append();
1552        }
1553        span->fT = newT;
1554        span->fOther = other;
1555        span->fPt.fX = SK_ScalarNaN;
1556        span->fWindSum = SK_MinS32;
1557        span->fOppSum = SK_MinS32;
1558        span->fWindValue = 1;
1559        span->fOppValue = 0;
1560        span->fTiny = false;
1561        if ((span->fDone = newT == 1)) {
1562            ++fDoneSpans;
1563        }
1564        span->fUnsortableStart = false;
1565        span->fUnsortableEnd = false;
1566        int less = -1;
1567        while (&span[less + 1] - fTs.begin() > 0 && !span[less].fDone
1568                && !precisely_negative(newT - span[less].fT)
1569 //               && approximately_negative(newT - span[less].fT)
1570                && xyAtT(&span[less]) == xyAtT(span)) {
1571            span[less].fTiny = true;
1572            span[less].fDone = true;
1573            if (approximately_negative(newT - span[less].fT)) {
1574                if (approximately_greater_than_one(newT)) {
1575                    span[less].fUnsortableStart = true;
1576                    span[less - 1].fUnsortableEnd = true;
1577                }
1578                if (approximately_less_than_zero(span[less].fT)) {
1579                    span[less + 1].fUnsortableStart = true;
1580                    span[less].fUnsortableEnd = true;
1581                }
1582            }
1583            ++fDoneSpans;
1584            --less;
1585        }
1586        int more = 1;
1587        while (fTs.end() - &span[more - 1] > 1 && !span[more - 1].fDone
1588                && !precisely_negative(span[more].fT - newT)
1589 //               && approximately_negative(span[more].fT - newT)
1590                && xyAtT(&span[more]) == xyAtT(span)) {
1591            span[more - 1].fTiny = true;
1592            span[more - 1].fDone = true;
1593            if (approximately_negative(span[more].fT - newT)) {
1594                if (approximately_greater_than_one(span[more].fT)) {
1595                    span[more + 1].fUnsortableStart = true;
1596                    span[more].fUnsortableEnd = true;
1597                }
1598                if (approximately_less_than_zero(newT)) {
1599                    span[more].fUnsortableStart = true;
1600                    span[more - 1].fUnsortableEnd = true;
1601                }
1602            }
1603            ++fDoneSpans;
1604            ++more;
1605        }
1606        return insertedAt;
1607    }
1608
1609    // set spans from start to end to decrement by one
1610    // note this walks other backwards
1611    // FIMXE: there's probably an edge case that can be constructed where
1612    // two span in one segment are separated by float epsilon on one span but
1613    // not the other, if one segment is very small. For this
1614    // case the counts asserted below may or may not be enough to separate the
1615    // spans. Even if the counts work out, what if the spans aren't correctly
1616    // sorted? It feels better in such a case to match the span's other span
1617    // pointer since both coincident segments must contain the same spans.
1618    void addTCancel(double startT, double endT, Segment& other,
1619            double oStartT, double oEndT) {
1620        SkASSERT(!approximately_negative(endT - startT));
1621        SkASSERT(!approximately_negative(oEndT - oStartT));
1622        bool binary = fOperand != other.fOperand;
1623        int index = 0;
1624        while (!approximately_negative(startT - fTs[index].fT)) {
1625            ++index;
1626        }
1627        int oIndex = other.fTs.count();
1628        while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
1629            ;
1630        double tRatio = (oEndT - oStartT) / (endT - startT);
1631        Span* test = &fTs[index];
1632        Span* oTest = &other.fTs[oIndex];
1633        SkTDArray<double> outsideTs;
1634        SkTDArray<double> oOutsideTs;
1635        do {
1636            bool decrement = test->fWindValue && oTest->fWindValue && !binary;
1637            bool track = test->fWindValue || oTest->fWindValue;
1638            double testT = test->fT;
1639            double oTestT = oTest->fT;
1640            Span* span = test;
1641            do {
1642                if (decrement) {
1643                    decrementSpan(span);
1644                } else if (track && span->fT < 1 && oTestT < 1) {
1645                    TrackOutside(outsideTs, span->fT, oTestT);
1646                }
1647                span = &fTs[++index];
1648            } while (approximately_negative(span->fT - testT));
1649            Span* oSpan = oTest;
1650            double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
1651            double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
1652            SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
1653            while (approximately_negative(otherTMatchStart - oSpan->fT)
1654                    && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
1655        #ifdef SK_DEBUG
1656                SkASSERT(originalWindValue == oSpan->fWindValue);
1657        #endif
1658                if (decrement) {
1659                    other.decrementSpan(oSpan);
1660                } else if (track && oSpan->fT < 1 && testT < 1) {
1661                    TrackOutside(oOutsideTs, oSpan->fT, testT);
1662                }
1663                if (!oIndex) {
1664                    break;
1665                }
1666                oSpan = &other.fTs[--oIndex];
1667            }
1668            test = span;
1669            oTest = oSpan;
1670        } while (!approximately_negative(endT - test->fT));
1671        SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
1672        // FIXME: determine if canceled edges need outside ts added
1673        if (!done() && outsideTs.count()) {
1674            double tStart = outsideTs[0];
1675            double oStart = outsideTs[1];
1676            addCancelOutsides(tStart, oStart, other, oEndT);
1677            int count = outsideTs.count();
1678            if (count > 2) {
1679                double tStart = outsideTs[count - 2];
1680                double oStart = outsideTs[count - 1];
1681                addCancelOutsides(tStart, oStart, other, oEndT);
1682            }
1683        }
1684        if (!other.done() && oOutsideTs.count()) {
1685            double tStart = oOutsideTs[0];
1686            double oStart = oOutsideTs[1];
1687            other.addCancelOutsides(tStart, oStart, *this, endT);
1688        }
1689    }
1690
1691    int addUnsortableT(double newT, Segment* other, bool start) {
1692        int result = addT(newT, other);
1693        Span* span = &fTs[result];
1694        if (start) {
1695            if (result > 0) {
1696                span[result - 1].fUnsortableEnd = true;
1697            }
1698            span[result].fUnsortableStart = true;
1699        } else {
1700            span[result].fUnsortableEnd = true;
1701            if (result + 1 < fTs.count()) {
1702                span[result + 1].fUnsortableStart = true;
1703            }
1704        }
1705        return result;
1706    }
1707
1708    int bumpCoincidentThis(const Span* oTest, bool opp, int index,
1709            SkTDArray<double>& outsideTs) {
1710        int oWindValue = oTest->fWindValue;
1711        int oOppValue = oTest->fOppValue;
1712        if (opp) {
1713            SkTSwap<int>(oWindValue, oOppValue);
1714        }
1715        Span* const test = &fTs[index];
1716        Span* end = test;
1717        const double oStartT = oTest->fT;
1718        do {
1719            if (bumpSpan(end, oWindValue, oOppValue)) {
1720                TrackOutside(outsideTs, end->fT, oStartT);
1721            }
1722            end = &fTs[++index];
1723        } while (approximately_negative(end->fT - test->fT));
1724        return index;
1725    }
1726
1727    // because of the order in which coincidences are resolved, this and other
1728    // may not have the same intermediate points. Compute the corresponding
1729    // intermediate T values (using this as the master, other as the follower)
1730    // and walk other conditionally -- hoping that it catches up in the end
1731    int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,
1732            SkTDArray<double>& oOutsideTs) {
1733        Span* const oTest = &fTs[oIndex];
1734        Span* oEnd = oTest;
1735        const double startT = test->fT;
1736        const double oStartT = oTest->fT;
1737        while (!approximately_negative(oEndT - oEnd->fT)
1738                && approximately_negative(oEnd->fT - oStartT)) {
1739            zeroSpan(oEnd);
1740            TrackOutside(oOutsideTs, oEnd->fT, startT);
1741            oEnd = &fTs[++oIndex];
1742        }
1743        return oIndex;
1744    }
1745
1746    // FIXME: need to test this case:
1747    // contourA has two segments that are coincident
1748    // contourB has two segments that are coincident in the same place
1749    // each ends up with +2/0 pairs for winding count
1750    // since logic below doesn't transfer count (only increments/decrements) can this be
1751    // resolved to +4/0 ?
1752
1753    // set spans from start to end to increment the greater by one and decrement
1754    // the lesser
1755    void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
1756        SkASSERT(!approximately_negative(endT - startT));
1757        SkASSERT(!approximately_negative(oEndT - oStartT));
1758        bool opp = fOperand ^ other.fOperand;
1759        int index = 0;
1760        while (!approximately_negative(startT - fTs[index].fT)) {
1761            ++index;
1762        }
1763        int oIndex = 0;
1764        while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
1765            ++oIndex;
1766        }
1767        Span* test = &fTs[index];
1768        Span* oTest = &other.fTs[oIndex];
1769        SkTDArray<double> outsideTs;
1770        SkTDArray<double> oOutsideTs;
1771        do {
1772            // if either span has an opposite value and the operands don't match, resolve first
1773     //       SkASSERT(!test->fDone || !oTest->fDone);
1774            if (test->fDone || oTest->fDone) {
1775                index = advanceCoincidentThis(oTest, opp, index);
1776                oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
1777            } else {
1778                index = bumpCoincidentThis(oTest, opp, index, outsideTs);
1779                oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
1780            }
1781            test = &fTs[index];
1782            oTest = &other.fTs[oIndex];
1783        } while (!approximately_negative(endT - test->fT));
1784        SkASSERT(approximately_negative(oTest->fT - oEndT));
1785        SkASSERT(approximately_negative(oEndT - oTest->fT));
1786        if (!done() && outsideTs.count()) {
1787            addCoinOutsides(outsideTs, other, oEndT);
1788        }
1789        if (!other.done() && oOutsideTs.count()) {
1790            other.addCoinOutsides(oOutsideTs, *this, endT);
1791        }
1792    }
1793
1794    // FIXME: this doesn't prevent the same span from being added twice
1795    // fix in caller, assert here?
1796    void addTPair(double t, Segment& other, double otherT, bool borrowWind) {
1797        int tCount = fTs.count();
1798        for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1799            const Span& span = fTs[tIndex];
1800            if (!approximately_negative(span.fT - t)) {
1801                break;
1802            }
1803            if (approximately_negative(span.fT - t) && span.fOther == &other
1804                    && approximately_equal(span.fOtherT, otherT)) {
1805#if DEBUG_ADD_T_PAIR
1806                SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1807                        __FUNCTION__, fID, t, other.fID, otherT);
1808#endif
1809                return;
1810            }
1811        }
1812#if DEBUG_ADD_T_PAIR
1813        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1814                __FUNCTION__, fID, t, other.fID, otherT);
1815#endif
1816        int insertedAt = addT(t, &other);
1817        int otherInsertedAt = other.addT(otherT, this);
1818        addOtherT(insertedAt, otherT, otherInsertedAt);
1819        other.addOtherT(otherInsertedAt, t, insertedAt);
1820        matchWindingValue(insertedAt, t, borrowWind);
1821        other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
1822    }
1823
1824    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
1825        // add edge leading into junction
1826        int min = SkMin32(end, start);
1827        if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
1828            addAngle(angles, end, start);
1829        }
1830        // add edge leading away from junction
1831        int step = SkSign32(end - start);
1832        int tIndex = nextExactSpan(end, step);
1833        min = SkMin32(end, tIndex);
1834        if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
1835            addAngle(angles, end, tIndex);
1836        }
1837    }
1838
1839    int advanceCoincidentThis(const Span* oTest, bool opp, int index) {
1840        Span* const test = &fTs[index];
1841        Span* end = test;
1842        do {
1843            end = &fTs[++index];
1844        } while (approximately_negative(end->fT - test->fT));
1845        return index;
1846    }
1847
1848    int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {
1849        Span* const oTest = &fTs[oIndex];
1850        Span* oEnd = oTest;
1851        const double oStartT = oTest->fT;
1852        while (!approximately_negative(oEndT - oEnd->fT)
1853                && approximately_negative(oEnd->fT - oStartT)) {
1854            oEnd = &fTs[++oIndex];
1855        }
1856        return oIndex;
1857    }
1858
1859    bool betweenTs(int lesser, double testT, int greater) {
1860        if (lesser > greater) {
1861            SkTSwap<int>(lesser, greater);
1862        }
1863        return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
1864    }
1865
1866    const Bounds& bounds() const {
1867        return fBounds;
1868    }
1869
1870    void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {
1871        double referenceT = fTs[index].fT;
1872        int lesser = index;
1873        while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
1874                && precisely_negative(referenceT - fTs[lesser].fT)) {
1875            buildAnglesInner(lesser, angles);
1876        }
1877        do {
1878            buildAnglesInner(index, angles);
1879        } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
1880                && precisely_negative(fTs[index].fT - referenceT));
1881    }
1882
1883    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
1884        Span* span = &fTs[index];
1885        Segment* other = span->fOther;
1886    // if there is only one live crossing, and no coincidence, continue
1887    // in the same direction
1888    // if there is coincidence, the only choice may be to reverse direction
1889        // find edge on either side of intersection
1890        int oIndex = span->fOtherIndex;
1891        // if done == -1, prior span has already been processed
1892        int step = 1;
1893        int next = other->nextExactSpan(oIndex, step);
1894       if (next < 0) {
1895            step = -step;
1896            next = other->nextExactSpan(oIndex, step);
1897        }
1898        // add candidate into and away from junction
1899        other->addTwoAngles(next, oIndex, angles);
1900    }
1901
1902    int computeSum(int startIndex, int endIndex, bool binary) {
1903        SkTDArray<Angle> angles;
1904        addTwoAngles(startIndex, endIndex, angles);
1905        buildAngles(endIndex, angles, false);
1906        // OPTIMIZATION: check all angles to see if any have computed wind sum
1907        // before sorting (early exit if none)
1908        SkTDArray<Angle*> sorted;
1909        bool sortable = SortAngles(angles, sorted);
1910#if DEBUG_SORT
1911        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
1912#endif
1913        if (!sortable) {
1914            return SK_MinS32;
1915        }
1916        int angleCount = angles.count();
1917        const Angle* angle;
1918        const Segment* base;
1919        int winding;
1920        int oWinding;
1921        int firstIndex = 0;
1922        do {
1923            angle = sorted[firstIndex];
1924            base = angle->segment();
1925            winding = base->windSum(angle);
1926            if (winding != SK_MinS32) {
1927                oWinding = base->oppSum(angle);
1928                break;
1929            }
1930            if (++firstIndex == angleCount) {
1931                return SK_MinS32;
1932            }
1933        } while (true);
1934        // turn winding into contourWinding
1935        int spanWinding = base->spanSign(angle);
1936        bool inner = useInnerWinding(winding + spanWinding, winding);
1937    #if DEBUG_WINDING
1938        SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
1939            spanWinding, winding, angle->sign(), inner,
1940            inner ? winding + spanWinding : winding);
1941    #endif
1942        if (inner) {
1943            winding += spanWinding;
1944        }
1945    #if DEBUG_SORT
1946        base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
1947    #endif
1948        int nextIndex = firstIndex + 1;
1949        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1950        winding -= base->spanSign(angle);
1951        oWinding -= base->oppSign(angle);
1952        do {
1953            if (nextIndex == angleCount) {
1954                nextIndex = 0;
1955            }
1956            angle = sorted[nextIndex];
1957            Segment* segment = angle->segment();
1958            bool opp = base->fOperand ^ segment->fOperand;
1959            int maxWinding, oMaxWinding;
1960            int spanSign = segment->spanSign(angle);
1961            int oppoSign = segment->oppSign(angle);
1962            if (opp) {
1963                oMaxWinding = oWinding;
1964                oWinding -= spanSign;
1965                maxWinding = winding;
1966                if (oppoSign) {
1967                    winding -= oppoSign;
1968                }
1969            } else {
1970                maxWinding = winding;
1971                winding -= spanSign;
1972                oMaxWinding = oWinding;
1973                if (oppoSign) {
1974                    oWinding -= oppoSign;
1975                }
1976            }
1977            if (segment->windSum(angle) == SK_MinS32) {
1978                if (opp) {
1979                    if (useInnerWinding(oMaxWinding, oWinding)) {
1980                        oMaxWinding = oWinding;
1981                    }
1982                    if (oppoSign && useInnerWinding(maxWinding, winding)) {
1983                        maxWinding = winding;
1984                    }
1985                    (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
1986                } else {
1987                    if (useInnerWinding(maxWinding, winding)) {
1988                        maxWinding = winding;
1989                    }
1990                    if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
1991                        oMaxWinding = oWinding;
1992                    }
1993                    (void) segment->markAndChaseWinding(angle, maxWinding,
1994                            binary ? oMaxWinding : 0);
1995                }
1996            }
1997        } while (++nextIndex != lastIndex);
1998        int minIndex = SkMin32(startIndex, endIndex);
1999        return windSum(minIndex);
2000    }
2001
2002    int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething,
2003            double mid, bool opp, bool current) const {
2004        SkScalar bottom = fBounds.fBottom;
2005        int bestTIndex = -1;
2006        if (bottom <= bestY) {
2007            return bestTIndex;
2008        }
2009        SkScalar top = fBounds.fTop;
2010        if (top >= basePt.fY) {
2011            return bestTIndex;
2012        }
2013        if (fBounds.fLeft > basePt.fX) {
2014            return bestTIndex;
2015        }
2016        if (fBounds.fRight < basePt.fX) {
2017            return bestTIndex;
2018        }
2019        if (fBounds.fLeft == fBounds.fRight) {
2020            // if vertical, and directly above test point, wait for another one
2021            return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
2022        }
2023        // intersect ray starting at basePt with edge
2024        Intersections intersections;
2025        // OPTIMIZE: use specialty function that intersects ray with curve,
2026        // returning t values only for curve (we don't care about t on ray)
2027        int pts = (*VSegmentIntersect[fVerb])(fPts, top, bottom, basePt.fX, false, intersections);
2028        if (pts == 0 || (current && pts == 1)) {
2029            return bestTIndex;
2030        }
2031        if (current) {
2032            SkASSERT(pts > 1);
2033            int closestIdx = 0;
2034            double closest = fabs(intersections.fT[0][0] - mid);
2035            for (int idx = 1; idx < pts; ++idx) {
2036                double test = fabs(intersections.fT[0][idx] - mid);
2037                if (closest > test) {
2038                    closestIdx = idx;
2039                    closest = test;
2040                }
2041            }
2042            if (closestIdx < pts - 1) {
2043                intersections.fT[0][closestIdx] = intersections.fT[0][pts - 1];
2044            }
2045            --pts;
2046        }
2047        double bestT = -1;
2048        for (int index = 0; index < pts; ++index) {
2049            double foundT = intersections.fT[0][index];
2050            if (approximately_less_than_zero(foundT)
2051                        || approximately_greater_than_one(foundT)) {
2052                continue;
2053            }
2054            SkScalar testY = (*SegmentYAtT[fVerb])(fPts, foundT);
2055            if (approximately_negative(testY - bestY)
2056                    || approximately_negative(basePt.fY - testY)) {
2057                continue;
2058            }
2059            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
2060                return SK_MinS32; // if the intersection is edge on, wait for another one
2061            }
2062            if (fVerb > SkPath::kLine_Verb) {
2063                SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, foundT);
2064                if (approximately_zero(dx)) {
2065                    return SK_MinS32; // hit vertical, wait for another one
2066                }
2067            }
2068            bestY = testY;
2069            bestT = foundT;
2070        }
2071        if (bestT < 0) {
2072            return bestTIndex;
2073        }
2074        SkASSERT(bestT >= 0);
2075        SkASSERT(bestT <= 1);
2076        int start;
2077        int end = 0;
2078        do {
2079            start = end;
2080            end = nextSpan(start, 1);
2081        } while (fTs[end].fT < bestT);
2082        // FIXME: see next candidate for a better pattern to find the next start/end pair
2083        while (start + 1 < end && fTs[start].fDone) {
2084            ++start;
2085        }
2086        if (!isCanceled(start)) {
2087            hitT = bestT;
2088            bestTIndex = start;
2089            hitSomething = true;
2090        }
2091        return bestTIndex;
2092    }
2093
2094    void decrementSpan(Span* span) {
2095        SkASSERT(span->fWindValue > 0);
2096        if (--(span->fWindValue) == 0) {
2097            if (!span->fOppValue && !span->fDone) {
2098                span->fDone = true;
2099                ++fDoneSpans;
2100            }
2101        }
2102    }
2103
2104    bool bumpSpan(Span* span, int windDelta, int oppDelta) {
2105        SkASSERT(!span->fDone);
2106        span->fWindValue += windDelta;
2107        SkASSERT(span->fWindValue >= 0);
2108        span->fOppValue += oppDelta;
2109        SkASSERT(span->fOppValue >= 0);
2110        if (fXor) {
2111            span->fWindValue &= 1;
2112        }
2113        if (fOppXor) {
2114            span->fOppValue &= 1;
2115        }
2116        if (!span->fWindValue && !span->fOppValue) {
2117            span->fDone = true;
2118            ++fDoneSpans;
2119            return true;
2120        }
2121        return false;
2122    }
2123
2124    // OPTIMIZE
2125    // when the edges are initially walked, they don't automatically get the prior and next
2126    // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
2127    // and would additionally remove the need for similar checks in condition edges. It would
2128    // also allow intersection code to assume end of segment intersections (maybe?)
2129    bool complete() const {
2130        int count = fTs.count();
2131        return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
2132    }
2133
2134    bool done() const {
2135        SkASSERT(fDoneSpans <= fTs.count());
2136        return fDoneSpans == fTs.count();
2137    }
2138
2139    bool done(int min) const {
2140        return fTs[min].fDone;
2141    }
2142
2143    bool done(const Angle* angle) const {
2144        return done(SkMin32(angle->start(), angle->end()));
2145    }
2146
2147    bool equalPoints(int greaterTIndex, int lesserTIndex) {
2148        SkASSERT(greaterTIndex >= lesserTIndex);
2149        double greaterT = fTs[greaterTIndex].fT;
2150        double lesserT = fTs[lesserTIndex].fT;
2151        if (greaterT == lesserT) {
2152            return true;
2153        }
2154        if (!approximately_negative(greaterT - lesserT)) {
2155            return false;
2156        }
2157        return xyAtT(greaterTIndex) == xyAtT(lesserTIndex);
2158    }
2159
2160    /*
2161     The M and S variable name parts stand for the operators.
2162       Mi stands for Minuend (see wiki subtraction, analogous to difference)
2163       Su stands for Subtrahend
2164     The Opp variable name part designates that the value is for the Opposite operator.
2165     Opposite values result from combining coincident spans.
2166     */
2167
2168    Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
2169            bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMask) {
2170        const int startIndex = nextStart;
2171        const int endIndex = nextEnd;
2172        SkASSERT(startIndex != endIndex);
2173        const int count = fTs.count();
2174        SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2175        const int step = SkSign32(endIndex - startIndex);
2176        const int end = nextExactSpan(startIndex, step);
2177        SkASSERT(end >= 0);
2178        Span* endSpan = &fTs[end];
2179        Segment* other;
2180        if (isSimple(end)) {
2181        // mark the smaller of startIndex, endIndex done, and all adjacent
2182        // spans with the same T value (but not 'other' spans)
2183    #if DEBUG_WINDING
2184            SkDebugf("%s simple\n", __FUNCTION__);
2185    #endif
2186            int min = SkMin32(startIndex, endIndex);
2187            if (fTs[min].fDone) {
2188                return NULL;
2189            }
2190            markDoneBinary(min);
2191            other = endSpan->fOther;
2192            nextStart = endSpan->fOtherIndex;
2193            double startT = other->fTs[nextStart].fT;
2194            nextEnd = nextStart;
2195            do {
2196                nextEnd += step;
2197            }
2198            while (precisely_zero(startT - other->fTs[nextEnd].fT));
2199            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2200            return other;
2201        }
2202        // more than one viable candidate -- measure angles to find best
2203        SkTDArray<Angle> angles;
2204        SkASSERT(startIndex - endIndex != 0);
2205        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2206        addTwoAngles(startIndex, end, angles);
2207        buildAngles(end, angles, true);
2208        SkTDArray<Angle*> sorted;
2209        bool sortable = SortAngles(angles, sorted);
2210        int angleCount = angles.count();
2211        int firstIndex = findStartingEdge(sorted, startIndex, end);
2212        SkASSERT(firstIndex >= 0);
2213    #if DEBUG_SORT
2214        debugShowSort(__FUNCTION__, sorted, firstIndex);
2215    #endif
2216        if (!sortable) {
2217            unsortable = true;
2218            return NULL;
2219        }
2220        SkASSERT(sorted[firstIndex]->segment() == this);
2221    #if DEBUG_WINDING
2222        SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
2223                sorted[firstIndex]->sign());
2224    #endif
2225        int sumMiWinding = updateWinding(endIndex, startIndex);
2226        int sumSuWinding = updateOppWinding(endIndex, startIndex);
2227        if (operand()) {
2228            SkTSwap<int>(sumMiWinding, sumSuWinding);
2229        }
2230        int nextIndex = firstIndex + 1;
2231        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2232        const Angle* foundAngle = NULL;
2233        bool foundDone = false;
2234        // iterate through the angle, and compute everyone's winding
2235        Segment* nextSegment;
2236        do {
2237            SkASSERT(nextIndex != firstIndex);
2238            if (nextIndex == angleCount) {
2239                nextIndex = 0;
2240            }
2241            const Angle* nextAngle = sorted[nextIndex];
2242            nextSegment = nextAngle->segment();
2243            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
2244            bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2245                    nextAngle->end(), op, sumMiWinding, sumSuWinding,
2246                    maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
2247            if (activeAngle && (!foundAngle || foundDone)) {
2248                foundAngle = nextAngle;
2249                foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
2250            }
2251            if (nextSegment->done()) {
2252                continue;
2253            }
2254            if (nextSegment->windSum(nextAngle) != SK_MinS32) {
2255                continue;
2256            }
2257            Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
2258                    oppSumWinding, activeAngle, nextAngle);
2259            if (last) {
2260                *chase.append() = last;
2261#if DEBUG_WINDING
2262                SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2263                        last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2264#endif
2265            }
2266        } while (++nextIndex != lastIndex);
2267        markDoneBinary(SkMin32(startIndex, endIndex));
2268        if (!foundAngle) {
2269            return NULL;
2270        }
2271        nextStart = foundAngle->start();
2272        nextEnd = foundAngle->end();
2273        nextSegment = foundAngle->segment();
2274
2275    #if DEBUG_WINDING
2276        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2277                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2278     #endif
2279        return nextSegment;
2280    }
2281
2282    Segment* findNextWinding(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
2283            bool& unsortable) {
2284        const int startIndex = nextStart;
2285        const int endIndex = nextEnd;
2286        SkASSERT(startIndex != endIndex);
2287        const int count = fTs.count();
2288        SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2289        const int step = SkSign32(endIndex - startIndex);
2290        const int end = nextExactSpan(startIndex, step);
2291        SkASSERT(end >= 0);
2292        Span* endSpan = &fTs[end];
2293        Segment* other;
2294        if (isSimple(end)) {
2295        // mark the smaller of startIndex, endIndex done, and all adjacent
2296        // spans with the same T value (but not 'other' spans)
2297    #if DEBUG_WINDING
2298            SkDebugf("%s simple\n", __FUNCTION__);
2299    #endif
2300            int min = SkMin32(startIndex, endIndex);
2301            if (fTs[min].fDone) {
2302                return NULL;
2303            }
2304            markDoneUnary(min);
2305            other = endSpan->fOther;
2306            nextStart = endSpan->fOtherIndex;
2307            double startT = other->fTs[nextStart].fT;
2308            nextEnd = nextStart;
2309            do {
2310                nextEnd += step;
2311            }
2312            while (precisely_zero(startT - other->fTs[nextEnd].fT));
2313            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2314            return other;
2315        }
2316        // more than one viable candidate -- measure angles to find best
2317        SkTDArray<Angle> angles;
2318        SkASSERT(startIndex - endIndex != 0);
2319        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2320        addTwoAngles(startIndex, end, angles);
2321        buildAngles(end, angles, true);
2322        SkTDArray<Angle*> sorted;
2323        bool sortable = SortAngles(angles, sorted);
2324        int angleCount = angles.count();
2325        int firstIndex = findStartingEdge(sorted, startIndex, end);
2326        SkASSERT(firstIndex >= 0);
2327    #if DEBUG_SORT
2328        debugShowSort(__FUNCTION__, sorted, firstIndex);
2329    #endif
2330        if (!sortable) {
2331            unsortable = true;
2332            return NULL;
2333        }
2334        SkASSERT(sorted[firstIndex]->segment() == this);
2335    #if DEBUG_WINDING
2336        SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
2337                sorted[firstIndex]->sign());
2338    #endif
2339        int sumWinding = updateWinding(endIndex, startIndex);
2340        int nextIndex = firstIndex + 1;
2341        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2342        const Angle* foundAngle = NULL;
2343        bool foundDone = false;
2344        // iterate through the angle, and compute everyone's winding
2345        Segment* nextSegment;
2346        int activeCount = 0;
2347        do {
2348            SkASSERT(nextIndex != firstIndex);
2349            if (nextIndex == angleCount) {
2350                nextIndex = 0;
2351            }
2352            const Angle* nextAngle = sorted[nextIndex];
2353            nextSegment = nextAngle->segment();
2354            int maxWinding;
2355            bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
2356                    maxWinding, sumWinding);
2357            if (activeAngle) {
2358                ++activeCount;
2359                if (!foundAngle || (foundDone && activeCount & 1)) {
2360                    if (nextSegment->tiny(nextAngle)) {
2361                        unsortable = true;
2362                        return NULL;
2363                    }
2364                    foundAngle = nextAngle;
2365                    foundDone = nextSegment->done(nextAngle);
2366                }
2367            }
2368            if (nextSegment->done()) {
2369                continue;
2370            }
2371            if (nextSegment->windSum(nextAngle) != SK_MinS32) {
2372                continue;
2373            }
2374            Span* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle);
2375            if (last) {
2376                *chase.append() = last;
2377#if DEBUG_WINDING
2378                SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2379                        last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2380#endif
2381            }
2382        } while (++nextIndex != lastIndex);
2383        markDoneUnary(SkMin32(startIndex, endIndex));
2384        if (!foundAngle) {
2385            return NULL;
2386        }
2387        nextStart = foundAngle->start();
2388        nextEnd = foundAngle->end();
2389        nextSegment = foundAngle->segment();
2390    #if DEBUG_WINDING
2391        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2392                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2393     #endif
2394        return nextSegment;
2395    }
2396
2397    Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) {
2398        const int startIndex = nextStart;
2399        const int endIndex = nextEnd;
2400        SkASSERT(startIndex != endIndex);
2401        int count = fTs.count();
2402        SkASSERT(startIndex < endIndex ? startIndex < count - 1
2403                : startIndex > 0);
2404        int step = SkSign32(endIndex - startIndex);
2405        int end = nextExactSpan(startIndex, step);
2406        SkASSERT(end >= 0);
2407        Span* endSpan = &fTs[end];
2408        Segment* other;
2409        if (isSimple(end)) {
2410    #if DEBUG_WINDING
2411            SkDebugf("%s simple\n", __FUNCTION__);
2412    #endif
2413            int min = SkMin32(startIndex, endIndex);
2414            if (fTs[min].fDone) {
2415                return NULL;
2416            }
2417            markDone(min, 1);
2418            other = endSpan->fOther;
2419            nextStart = endSpan->fOtherIndex;
2420            double startT = other->fTs[nextStart].fT;
2421        #if 01 // FIXME: I don't know why the logic here is difference from the winding case
2422            SkDEBUGCODE(bool firstLoop = true;)
2423            if ((approximately_less_than_zero(startT) && step < 0)
2424                    || (approximately_greater_than_one(startT) && step > 0)) {
2425                step = -step;
2426                SkDEBUGCODE(firstLoop = false;)
2427            }
2428            do {
2429        #endif
2430                nextEnd = nextStart;
2431                do {
2432                    nextEnd += step;
2433                }
2434                 while (precisely_zero(startT - other->fTs[nextEnd].fT));
2435        #if 01
2436                if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
2437                    break;
2438                }
2439 #ifdef SK_DEBUG
2440                SkASSERT(firstLoop);
2441 #endif
2442                SkDEBUGCODE(firstLoop = false;)
2443                step = -step;
2444            } while (true);
2445        #endif
2446            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2447            return other;
2448        }
2449        SkTDArray<Angle> angles;
2450        SkASSERT(startIndex - endIndex != 0);
2451        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2452        addTwoAngles(startIndex, end, angles);
2453        buildAngles(end, angles, false);
2454        SkTDArray<Angle*> sorted;
2455        bool sortable = SortAngles(angles, sorted);
2456        if (!sortable) {
2457            unsortable = true;
2458    #if DEBUG_SORT
2459            debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0);
2460    #endif
2461            return NULL;
2462        }
2463        int angleCount = angles.count();
2464        int firstIndex = findStartingEdge(sorted, startIndex, end);
2465        SkASSERT(firstIndex >= 0);
2466    #if DEBUG_SORT
2467        debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
2468    #endif
2469        SkASSERT(sorted[firstIndex]->segment() == this);
2470        int nextIndex = firstIndex + 1;
2471        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2472        const Angle* foundAngle = NULL;
2473        bool foundDone = false;
2474        Segment* nextSegment;
2475        int activeCount = 0;
2476        do {
2477            SkASSERT(nextIndex != firstIndex);
2478            if (nextIndex == angleCount) {
2479                nextIndex = 0;
2480            }
2481            const Angle* nextAngle = sorted[nextIndex];
2482            nextSegment = nextAngle->segment();
2483            ++activeCount;
2484            if (!foundAngle || (foundDone && activeCount & 1)) {
2485                if (nextSegment->tiny(nextAngle)) {
2486                    unsortable = true;
2487                    return NULL;
2488                }
2489                foundAngle = nextAngle;
2490                foundDone = nextSegment->done(nextAngle);
2491            }
2492            if (nextSegment->done()) {
2493                continue;
2494            }
2495        } while (++nextIndex != lastIndex);
2496        markDone(SkMin32(startIndex, endIndex), 1);
2497        if (!foundAngle) {
2498            return NULL;
2499        }
2500        nextStart = foundAngle->start();
2501        nextEnd = foundAngle->end();
2502        nextSegment = foundAngle->segment();
2503    #if DEBUG_WINDING
2504        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2505                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2506     #endif
2507        return nextSegment;
2508    }
2509
2510    int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
2511        int angleCount = sorted.count();
2512        int firstIndex = -1;
2513        for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2514            const Angle* angle = sorted[angleIndex];
2515            if (angle->segment() == this && angle->start() == end &&
2516                    angle->end() == start) {
2517                firstIndex = angleIndex;
2518                break;
2519            }
2520        }
2521        return firstIndex;
2522    }
2523
2524    // FIXME: this is tricky code; needs its own unit test
2525    // note that fOtherIndex isn't computed yet, so it can't be used here
2526    void findTooCloseToCall() {
2527        int count = fTs.count();
2528        if (count < 3) { // require t=0, x, 1 at minimum
2529            return;
2530        }
2531        int matchIndex = 0;
2532        int moCount;
2533        Span* match;
2534        Segment* mOther;
2535        do {
2536            match = &fTs[matchIndex];
2537            mOther = match->fOther;
2538            // FIXME: allow quads, cubics to be near coincident?
2539            if (mOther->fVerb == SkPath::kLine_Verb) {
2540                moCount = mOther->fTs.count();
2541                if (moCount >= 3) {
2542                    break;
2543                }
2544            }
2545            if (++matchIndex >= count) {
2546                return;
2547            }
2548        } while (true); // require t=0, x, 1 at minimum
2549        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
2550        const SkPoint* matchPt = &xyAtT(match);
2551        // look for a pair of nearby T values that map to the same (x,y) value
2552        // if found, see if the pair of other segments share a common point. If
2553        // so, the span from here to there is coincident.
2554        for (int index = matchIndex + 1; index < count; ++index) {
2555            Span* test = &fTs[index];
2556            if (test->fDone) {
2557                continue;
2558            }
2559            Segment* tOther = test->fOther;
2560            if (tOther->fVerb != SkPath::kLine_Verb) {
2561                continue; // FIXME: allow quads, cubics to be near coincident?
2562            }
2563            int toCount = tOther->fTs.count();
2564            if (toCount < 3) { // require t=0, x, 1 at minimum
2565                continue;
2566            }
2567            const SkPoint* testPt = &xyAtT(test);
2568            if (*matchPt != *testPt) {
2569                matchIndex = index;
2570                moCount = toCount;
2571                match = test;
2572                mOther = tOther;
2573                matchPt = testPt;
2574                continue;
2575            }
2576            int moStart = -1;
2577            int moEnd = -1;
2578            double moStartT, moEndT;
2579            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
2580                Span& moSpan = mOther->fTs[moIndex];
2581                if (moSpan.fDone) {
2582                    continue;
2583                }
2584                if (moSpan.fOther == this) {
2585                    if (moSpan.fOtherT == match->fT) {
2586                        moStart = moIndex;
2587                        moStartT = moSpan.fT;
2588                    }
2589                    continue;
2590                }
2591                if (moSpan.fOther == tOther) {
2592                    if (tOther->windValueAt(moSpan.fOtherT) == 0) {
2593                        moStart = -1;
2594                        break;
2595                    }
2596                    SkASSERT(moEnd == -1);
2597                    moEnd = moIndex;
2598                    moEndT = moSpan.fT;
2599                }
2600            }
2601            if (moStart < 0 || moEnd < 0) {
2602                continue;
2603            }
2604            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
2605            if (approximately_equal(moStartT, moEndT)) {
2606                continue;
2607            }
2608            int toStart = -1;
2609            int toEnd = -1;
2610            double toStartT, toEndT;
2611            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
2612                Span& toSpan = tOther->fTs[toIndex];
2613                if (toSpan.fDone) {
2614                    continue;
2615                }
2616                if (toSpan.fOther == this) {
2617                    if (toSpan.fOtherT == test->fT) {
2618                        toStart = toIndex;
2619                        toStartT = toSpan.fT;
2620                    }
2621                    continue;
2622                }
2623                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
2624                    if (mOther->windValueAt(toSpan.fOtherT) == 0) {
2625                        moStart = -1;
2626                        break;
2627                    }
2628                    SkASSERT(toEnd == -1);
2629                    toEnd = toIndex;
2630                    toEndT = toSpan.fT;
2631                }
2632            }
2633            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
2634            if (toStart <= 0 || toEnd <= 0) {
2635                continue;
2636            }
2637            if (approximately_equal(toStartT, toEndT)) {
2638                continue;
2639            }
2640            // test to see if the segment between there and here is linear
2641            if (!mOther->isLinear(moStart, moEnd)
2642                    || !tOther->isLinear(toStart, toEnd)) {
2643                continue;
2644            }
2645            bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
2646            if (flipped) {
2647                mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
2648            } else {
2649                mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEndT);
2650            }
2651        }
2652    }
2653
2654 //   start here;
2655    // either:
2656    // a) mark spans with either end unsortable as done, or
2657    // b) rewrite findTop / findTopSegment / findTopContour to iterate further
2658    //    when encountering an unsortable span
2659
2660    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
2661    // and use more concise logic like the old edge walker code?
2662    // FIXME: this needs to deal with coincident edges
2663    Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable) {
2664        // iterate through T intersections and return topmost
2665        // topmost tangent from y-min to first pt is closer to horizontal
2666        SkASSERT(!done());
2667        int firstT = -1;
2668        SkPoint topPt;
2669        topPt.fY = SK_ScalarMax;
2670        int count = fTs.count();
2671        // see if either end is not done since we want smaller Y of the pair
2672        bool lastDone = true;
2673        bool lastUnsortable = false;
2674        for (int index = 0; index < count; ++index) {
2675            const Span& span = fTs[index];
2676            if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
2677                goto next;
2678            }
2679            if (!span.fDone | !lastDone) {
2680                const SkPoint& intercept = xyAtT(&span);
2681                if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
2682                        && topPt.fX > intercept.fX)) {
2683                    topPt = intercept;
2684                    firstT = index;
2685                }
2686            }
2687    next:
2688            lastDone = span.fDone;
2689            lastUnsortable = span.fUnsortableEnd;
2690        }
2691        SkASSERT(firstT >= 0);
2692        // sort the edges to find the leftmost
2693        int step = 1;
2694        int end = nextSpan(firstT, step);
2695        if (end == -1) {
2696            step = -1;
2697            end = nextSpan(firstT, step);
2698            SkASSERT(end != -1);
2699        }
2700        // if the topmost T is not on end, or is three-way or more, find left
2701        // look for left-ness from tLeft to firstT (matching y of other)
2702        SkTDArray<Angle> angles;
2703        SkASSERT(firstT - end != 0);
2704        addTwoAngles(end, firstT, angles);
2705        buildAngles(firstT, angles, true);
2706        SkTDArray<Angle*> sorted;
2707        bool sortable = SortAngles(angles, sorted);
2708    #if DEBUG_SORT
2709        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
2710    #endif
2711        if (onlySortable && !sortable) {
2712            unsortable = true;
2713            return NULL;
2714        }
2715        // skip edges that have already been processed
2716        firstT = -1;
2717        Segment* leftSegment;
2718        do {
2719            const Angle* angle = sorted[++firstT];
2720            SkASSERT(!onlySortable || !angle->unsortable());
2721            leftSegment = angle->segment();
2722            tIndex = angle->end();
2723            endIndex = angle->start();
2724        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
2725        SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
2726        return leftSegment;
2727    }
2728
2729    // FIXME: not crazy about this
2730    // when the intersections are performed, the other index is into an
2731    // incomplete array. as the array grows, the indices become incorrect
2732    // while the following fixes the indices up again, it isn't smart about
2733    // skipping segments whose indices are already correct
2734    // assuming we leave the code that wrote the index in the first place
2735    void fixOtherTIndex() {
2736        int iCount = fTs.count();
2737        for (int i = 0; i < iCount; ++i) {
2738            Span& iSpan = fTs[i];
2739            double oT = iSpan.fOtherT;
2740            Segment* other = iSpan.fOther;
2741            int oCount = other->fTs.count();
2742            for (int o = 0; o < oCount; ++o) {
2743                Span& oSpan = other->fTs[o];
2744                if (oT == oSpan.fT && this == oSpan.fOther) {
2745                    iSpan.fOtherIndex = o;
2746                    break;
2747                }
2748            }
2749        }
2750    }
2751
2752    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
2753        fDoneSpans = 0;
2754        fOperand = operand;
2755        fXor = evenOdd;
2756        fPts = pts;
2757        fVerb = verb;
2758    }
2759
2760    void initWinding(int start, int end) {
2761        int local = spanSign(start, end);
2762        int oppLocal = oppSign(start, end);
2763        (void) markAndChaseWinding(start, end, local, oppLocal);
2764        // OPTIMIZATION: the reverse mark and chase could skip the first marking
2765        (void) markAndChaseWinding(end, start, local, oppLocal);
2766    }
2767
2768    void initWinding(int start, int end, int winding, int oppWinding) {
2769        int local = spanSign(start, end);
2770        if (local * winding >= 0) {
2771            winding += local;
2772        }
2773        int oppLocal = oppSign(start, end);
2774        if (oppLocal * oppWinding >= 0) {
2775            oppWinding += oppLocal;
2776        }
2777        (void) markAndChaseWinding(start, end, winding, oppWinding);
2778    }
2779
2780/*
2781when we start with a vertical intersect, we try to use the dx to determine if the edge is to
2782the left or the right of vertical. This determines if we need to add the span's
2783sign or not. However, this isn't enough.
2784If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
2785If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
2786from has the same x direction as this span, the winding should change. If the dx is opposite, then
2787the same winding is shared by both.
2788*/
2789    void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
2790            SkScalar hitOppDx) {
2791        SkASSERT(hitDx || !winding);
2792        SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, tHit);
2793        SkASSERT(dx);
2794        int windVal = windValue(SkMin32(start, end));
2795    #if DEBUG_WINDING_AT_T
2796        SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
2797                hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
2798    #endif
2799        if (!winding) {
2800            winding = dx < 0 ? windVal : -windVal;
2801        } else if (winding * dx < 0) {
2802            int sideWind = winding + (dx < 0 ? windVal : -windVal);
2803            if (abs(winding) < abs(sideWind)) {
2804                winding = sideWind;
2805            }
2806        }
2807    #if DEBUG_WINDING_AT_T
2808        SkDebugf(" winding=%d\n", winding);
2809    #endif
2810        int oppLocal = oppSign(start, end);
2811        SkASSERT(hitOppDx || !oppWind || !oppLocal);
2812        int oppWindVal = oppValue(SkMin32(start, end));
2813        if (!oppWind) {
2814            oppWind = dx < 0 ? oppWindVal : -oppWindVal;
2815        } else if (hitOppDx * dx >= 0) {
2816            int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
2817            if (abs(oppWind) < abs(oppSideWind)) {
2818                oppWind = oppSideWind;
2819            }
2820        }
2821        (void) markAndChaseWinding(start, end, winding, oppWind);
2822    }
2823
2824    bool intersected() const {
2825        return fTs.count() > 0;
2826    }
2827
2828    bool isCanceled(int tIndex) const {
2829        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
2830    }
2831
2832    bool isConnected(int startIndex, int endIndex) const {
2833        return fTs[startIndex].fWindSum != SK_MinS32
2834                || fTs[endIndex].fWindSum != SK_MinS32;
2835    }
2836
2837    bool isHorizontal() const {
2838        return fBounds.fTop == fBounds.fBottom;
2839    }
2840
2841    bool isLinear(int start, int end) const {
2842        if (fVerb == SkPath::kLine_Verb) {
2843            return true;
2844        }
2845        if (fVerb == SkPath::kQuad_Verb) {
2846            SkPoint qPart[3];
2847            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
2848            return QuadIsLinear(qPart);
2849        } else {
2850            SkASSERT(fVerb == SkPath::kCubic_Verb);
2851            SkPoint cPart[4];
2852            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
2853            return CubicIsLinear(cPart);
2854        }
2855    }
2856
2857    // OPTIMIZE: successive calls could start were the last leaves off
2858    // or calls could specialize to walk forwards or backwards
2859    bool isMissing(double startT) const {
2860        size_t tCount = fTs.count();
2861        for (size_t index = 0; index < tCount; ++index) {
2862            if (approximately_zero(startT - fTs[index].fT)) {
2863                return false;
2864            }
2865        }
2866        return true;
2867    }
2868
2869    bool isSimple(int end) const {
2870        int count = fTs.count();
2871        if (count == 2) {
2872            return true;
2873        }
2874        double t = fTs[end].fT;
2875        if (approximately_less_than_zero(t)) {
2876            return !approximately_less_than_zero(fTs[1].fT);
2877        }
2878        if (approximately_greater_than_one(t)) {
2879            return !approximately_greater_than_one(fTs[count - 2].fT);
2880        }
2881        return false;
2882    }
2883
2884    bool isVertical() const {
2885        return fBounds.fLeft == fBounds.fRight;
2886    }
2887
2888    bool isVertical(int start, int end) const {
2889        return (*SegmentVertical[fVerb])(fPts, start, end);
2890    }
2891
2892    SkScalar leftMost(int start, int end) const {
2893        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
2894    }
2895
2896    // this span is excluded by the winding rule -- chase the ends
2897    // as long as they are unambiguous to mark connections as done
2898    // and give them the same winding value
2899    Span* markAndChaseDone(const Angle* angle, int winding) {
2900        int index = angle->start();
2901        int endIndex = angle->end();
2902        return markAndChaseDone(index, endIndex, winding);
2903    }
2904
2905    Span* markAndChaseDone(int index, int endIndex, int winding) {
2906        int step = SkSign32(endIndex - index);
2907        int min = SkMin32(index, endIndex);
2908        markDone(min, winding);
2909        Span* last;
2910        Segment* other = this;
2911        while ((other = other->nextChase(index, step, min, last))) {
2912            other->markDone(min, winding);
2913        }
2914        return last;
2915    }
2916
2917    Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding) {
2918        int index = angle->start();
2919        int endIndex = angle->end();
2920        int step = SkSign32(endIndex - index);
2921        int min = SkMin32(index, endIndex);
2922        markDoneBinary(min, winding, oppWinding);
2923        Span* last;
2924        Segment* other = this;
2925        while ((other = other->nextChase(index, step, min, last))) {
2926            other->markDoneBinary(min, winding, oppWinding);
2927        }
2928        return last;
2929    }
2930
2931    Span* markAndChaseDoneBinary(int index, int endIndex) {
2932        int step = SkSign32(endIndex - index);
2933        int min = SkMin32(index, endIndex);
2934        markDoneBinary(min);
2935        Span* last;
2936        Segment* other = this;
2937        while ((other = other->nextChase(index, step, min, last))) {
2938            if (other->done()) {
2939                return NULL;
2940            }
2941            other->markDoneBinary(min);
2942        }
2943        return last;
2944    }
2945
2946    Span* markAndChaseDoneUnary(int index, int endIndex) {
2947        int step = SkSign32(endIndex - index);
2948        int min = SkMin32(index, endIndex);
2949        markDoneUnary(min);
2950        Span* last;
2951        Segment* other = this;
2952        while ((other = other->nextChase(index, step, min, last))) {
2953            if (other->done()) {
2954                return NULL;
2955            }
2956            other->markDoneUnary(min);
2957        }
2958        return last;
2959    }
2960
2961    Span* markAndChaseDoneUnary(const Angle* angle, int winding) {
2962        int index = angle->start();
2963        int endIndex = angle->end();
2964        return markAndChaseDone(index, endIndex, winding);
2965    }
2966
2967    Span* markAndChaseWinding(const Angle* angle, const int winding) {
2968        int index = angle->start();
2969        int endIndex = angle->end();
2970        int step = SkSign32(endIndex - index);
2971        int min = SkMin32(index, endIndex);
2972        markWinding(min, winding);
2973        Span* last;
2974        Segment* other = this;
2975        while ((other = other->nextChase(index, step, min, last))) {
2976            if (other->fTs[min].fWindSum != SK_MinS32) {
2977                SkASSERT(other->fTs[min].fWindSum == winding);
2978                return NULL;
2979            }
2980            other->markWinding(min, winding);
2981        }
2982        return last;
2983    }
2984
2985    Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
2986        int min = SkMin32(index, endIndex);
2987        int step = SkSign32(endIndex - index);
2988        markWinding(min, winding, oppWinding);
2989        Span* last;
2990        Segment* other = this;
2991        while ((other = other->nextChase(index, step, min, last))) {
2992            if (other->fTs[min].fWindSum != SK_MinS32) {
2993                SkASSERT(other->fTs[min].fWindSum == winding);
2994                return NULL;
2995            }
2996            other->markWinding(min, winding, oppWinding);
2997        }
2998        return last;
2999    }
3000
3001    Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) {
3002        int start = angle->start();
3003        int end = angle->end();
3004        return markAndChaseWinding(start, end, winding, oppWinding);
3005    }
3006
3007    Span* markAngle(int maxWinding, int sumWinding, bool activeAngle, const Angle* angle) {
3008        SkASSERT(angle->segment() == this);
3009        if (useInnerWinding(maxWinding, sumWinding)) {
3010            maxWinding = sumWinding;
3011        }
3012        Span* last;
3013        if (activeAngle) {
3014            last = markAndChaseWinding(angle, maxWinding);
3015        } else {
3016            last = markAndChaseDoneUnary(angle, maxWinding);
3017        }
3018        return last;
3019    }
3020
3021    Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
3022            bool activeAngle, const Angle* angle) {
3023        SkASSERT(angle->segment() == this);
3024        if (useInnerWinding(maxWinding, sumWinding)) {
3025            maxWinding = sumWinding;
3026        }
3027        if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, oppSumWinding)) {
3028            oppMaxWinding = oppSumWinding;
3029        }
3030        Span* last;
3031        if (activeAngle) {
3032            last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3033        } else {
3034            last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
3035        }
3036        return last;
3037    }
3038
3039    // FIXME: this should also mark spans with equal (x,y)
3040    // This may be called when the segment is already marked done. While this
3041    // wastes time, it shouldn't do any more than spin through the T spans.
3042    // OPTIMIZATION: abort on first done found (assuming that this code is
3043    // always called to mark segments done).
3044    void markDone(int index, int winding) {
3045      //  SkASSERT(!done());
3046        SkASSERT(winding);
3047        double referenceT = fTs[index].fT;
3048        int lesser = index;
3049        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3050            markOneDone(__FUNCTION__, lesser, winding);
3051        }
3052        do {
3053            markOneDone(__FUNCTION__, index, winding);
3054        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3055    }
3056
3057    void markDoneBinary(int index, int winding, int oppWinding) {
3058      //  SkASSERT(!done());
3059        SkASSERT(winding || oppWinding);
3060        double referenceT = fTs[index].fT;
3061        int lesser = index;
3062        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3063            markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);
3064        }
3065        do {
3066            markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);
3067        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3068    }
3069
3070    void markDoneBinary(int index) {
3071        double referenceT = fTs[index].fT;
3072        int lesser = index;
3073        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3074            markOneDoneBinary(__FUNCTION__, lesser);
3075        }
3076        do {
3077            markOneDoneBinary(__FUNCTION__, index);
3078        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3079    }
3080
3081    void markDoneUnary(int index, int winding) {
3082      //  SkASSERT(!done());
3083        SkASSERT(winding);
3084        double referenceT = fTs[index].fT;
3085        int lesser = index;
3086        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3087            markOneDoneUnary(__FUNCTION__, lesser, winding);
3088        }
3089        do {
3090            markOneDoneUnary(__FUNCTION__, index, winding);
3091        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3092    }
3093
3094    void markDoneUnary(int index) {
3095        double referenceT = fTs[index].fT;
3096        int lesser = index;
3097        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3098            markOneDoneUnary(__FUNCTION__, lesser);
3099        }
3100        do {
3101            markOneDoneUnary(__FUNCTION__, index);
3102        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3103    }
3104
3105    void markOneDone(const char* funName, int tIndex, int winding) {
3106        Span* span = markOneWinding(funName, tIndex, winding);
3107        if (!span) {
3108            return;
3109        }
3110        span->fDone = true;
3111        fDoneSpans++;
3112    }
3113
3114    void markOneDoneBinary(const char* funName, int tIndex) {
3115        Span* span = verifyOneWinding(funName, tIndex);
3116        if (!span) {
3117            return;
3118        }
3119        span->fDone = true;
3120        fDoneSpans++;
3121    }
3122
3123    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) {
3124        Span* span = markOneWinding(funName, tIndex, winding, oppWinding);
3125        if (!span) {
3126            return;
3127        }
3128        span->fDone = true;
3129        fDoneSpans++;
3130    }
3131
3132    void markOneDoneUnary(const char* funName, int tIndex) {
3133        Span* span = verifyOneWindingU(funName, tIndex);
3134        if (!span) {
3135            return;
3136        }
3137        span->fDone = true;
3138        fDoneSpans++;
3139    }
3140
3141    void markOneDoneUnary(const char* funName, int tIndex, int winding) {
3142        Span* span = markOneWinding(funName, tIndex, winding);
3143        if (!span) {
3144            return;
3145        }
3146        span->fDone = true;
3147        fDoneSpans++;
3148    }
3149
3150    Span* markOneWinding(const char* funName, int tIndex, int winding) {
3151        Span& span = fTs[tIndex];
3152        if (span.fDone) {
3153            return NULL;
3154        }
3155    #if DEBUG_MARK_DONE
3156        debugShowNewWinding(funName, span, winding);
3157    #endif
3158        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3159   #ifdef SK_DEBUG
3160        SkASSERT(abs(winding) <= gDebugMaxWindSum);
3161   #endif
3162        span.fWindSum = winding;
3163        return &span;
3164    }
3165
3166    Span* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding) {
3167        Span& span = fTs[tIndex];
3168        if (span.fDone) {
3169            return NULL;
3170        }
3171    #if DEBUG_MARK_DONE
3172        debugShowNewWinding(funName, span, winding, oppWinding);
3173    #endif
3174        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3175   #ifdef SK_DEBUG
3176        SkASSERT(abs(winding) <= gDebugMaxWindSum);
3177   #endif
3178        span.fWindSum = winding;
3179        SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
3180   #ifdef SK_DEBUG
3181        SkASSERT(abs(oppWinding) <= gDebugMaxWindSum);
3182   #endif
3183        span.fOppSum = oppWinding;
3184        return &span;
3185    }
3186
3187    Span* verifyOneWinding(const char* funName, int tIndex) {
3188        Span& span = fTs[tIndex];
3189        if (span.fDone) {
3190            return NULL;
3191        }
3192    #if DEBUG_MARK_DONE
3193        debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
3194    #endif
3195        SkASSERT(span.fWindSum != SK_MinS32);
3196        SkASSERT(span.fOppSum != SK_MinS32);
3197        return &span;
3198    }
3199
3200    Span* verifyOneWindingU(const char* funName, int tIndex) {
3201        Span& span = fTs[tIndex];
3202        if (span.fDone) {
3203            return NULL;
3204        }
3205    #if DEBUG_MARK_DONE
3206        debugShowNewWinding(funName, span, span.fWindSum);
3207    #endif
3208        SkASSERT(span.fWindSum != SK_MinS32);
3209        return &span;
3210    }
3211
3212    // note that just because a span has one end that is unsortable, that's
3213    // not enough to mark it done. The other end may be sortable, allowing the
3214    // span to be added.
3215    // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
3216    void markUnsortable(int start, int end) {
3217        Span* span = &fTs[start];
3218        if (start < end) {
3219#if DEBUG_UNSORTABLE
3220            SkDebugf("%s start id=%d [%d] (%1.9g,%1.9g)\n", __FUNCTION__, fID, start,
3221                    xAtT(start), yAtT(start));
3222#endif
3223            span->fUnsortableStart = true;
3224        } else {
3225            --span;
3226#if DEBUG_UNSORTABLE
3227            SkDebugf("%s end id=%d [%d] (%1.9g,%1.9g) next:(%1.9g,%1.9g)\n", __FUNCTION__, fID,
3228                start - 1, xAtT(start - 1), yAtT(start - 1), xAtT(start), yAtT(start));
3229#endif
3230            span->fUnsortableEnd = true;
3231        }
3232        if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
3233            return;
3234        }
3235        span->fDone = true;
3236        fDoneSpans++;
3237    }
3238
3239    void markWinding(int index, int winding) {
3240    //    SkASSERT(!done());
3241        SkASSERT(winding);
3242        double referenceT = fTs[index].fT;
3243        int lesser = index;
3244        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3245            markOneWinding(__FUNCTION__, lesser, winding);
3246        }
3247        do {
3248            markOneWinding(__FUNCTION__, index, winding);
3249       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3250    }
3251
3252    void markWinding(int index, int winding, int oppWinding) {
3253    //    SkASSERT(!done());
3254        SkASSERT(winding || oppWinding);
3255        double referenceT = fTs[index].fT;
3256        int lesser = index;
3257        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3258            markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3259        }
3260        do {
3261            markOneWinding(__FUNCTION__, index, winding, oppWinding);
3262       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3263    }
3264
3265    void matchWindingValue(int tIndex, double t, bool borrowWind) {
3266        int nextDoorWind = SK_MaxS32;
3267        int nextOppWind = SK_MaxS32;
3268        if (tIndex > 0) {
3269            const Span& below = fTs[tIndex - 1];
3270            if (approximately_negative(t - below.fT)) {
3271                nextDoorWind = below.fWindValue;
3272                nextOppWind = below.fOppValue;
3273            }
3274        }
3275        if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3276            const Span& above = fTs[tIndex + 1];
3277            if (approximately_negative(above.fT - t)) {
3278                nextDoorWind = above.fWindValue;
3279                nextOppWind = above.fOppValue;
3280            }
3281        }
3282        if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3283            const Span& below = fTs[tIndex - 1];
3284            nextDoorWind = below.fWindValue;
3285            nextOppWind = below.fOppValue;
3286        }
3287        if (nextDoorWind != SK_MaxS32) {
3288            Span& newSpan = fTs[tIndex];
3289            newSpan.fWindValue = nextDoorWind;
3290            newSpan.fOppValue = nextOppWind;
3291            if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3292                newSpan.fDone = true;
3293                ++fDoneSpans;
3294            }
3295        }
3296    }
3297
3298    bool moreHorizontal(int index, int endIndex, bool& unsortable) const {
3299        // find bounds
3300        Bounds bounds;
3301        bounds.setPoint(xyAtT(index));
3302        bounds.add(xyAtT(endIndex));
3303        SkScalar width = bounds.width();
3304        SkScalar height = bounds.height();
3305        if (width > height) {
3306            if (approximately_negative(width)) {
3307                unsortable = true; // edge is too small to resolve meaningfully
3308            }
3309            return false;
3310        } else {
3311            if (approximately_negative(height)) {
3312                unsortable = true; // edge is too small to resolve meaningfully
3313            }
3314            return true;
3315        }
3316    }
3317
3318    // return span if when chasing, two or more radiating spans are not done
3319    // OPTIMIZATION: ? multiple spans is detected when there is only one valid
3320    // candidate and the remaining spans have windValue == 0 (canceled by
3321    // coincidence). The coincident edges could either be removed altogether,
3322    // or this code could be more complicated in detecting this case. Worth it?
3323    bool multipleSpans(int end) const {
3324        return end > 0 && end < fTs.count() - 1;
3325    }
3326
3327    bool nextCandidate(int& start, int& end) const {
3328        while (fTs[end].fDone) {
3329            if (fTs[end].fT == 1) {
3330                return false;
3331            }
3332            ++end;
3333        }
3334        start = end;
3335        end = nextExactSpan(start, 1);
3336        return true;
3337    }
3338
3339    Segment* nextChase(int& index, const int step, int& min, Span*& last) const {
3340        int end = nextExactSpan(index, step);
3341        SkASSERT(end >= 0);
3342        if (multipleSpans(end)) {
3343            last = &fTs[end];
3344            return NULL;
3345        }
3346        const Span& endSpan = fTs[end];
3347        Segment* other = endSpan.fOther;
3348        index = endSpan.fOtherIndex;
3349        int otherEnd = other->nextExactSpan(index, step);
3350        min = SkMin32(index, otherEnd);
3351        return other;
3352    }
3353
3354    // This has callers for two different situations: one establishes the end
3355    // of the current span, and one establishes the beginning of the next span
3356    // (thus the name). When this is looking for the end of the current span,
3357    // coincidence is found when the beginning Ts contain -step and the end
3358    // contains step. When it is looking for the beginning of the next, the
3359    // first Ts found can be ignored and the last Ts should contain -step.
3360    // OPTIMIZATION: probably should split into two functions
3361    int nextSpan(int from, int step) const {
3362        const Span& fromSpan = fTs[from];
3363        int count = fTs.count();
3364        int to = from;
3365        while (step > 0 ? ++to < count : --to >= 0) {
3366            const Span& span = fTs[to];
3367            if (approximately_zero(span.fT - fromSpan.fT)) {
3368                continue;
3369            }
3370            return to;
3371        }
3372        return -1;
3373    }
3374
3375    // FIXME
3376    // this returns at any difference in T, vs. a preset minimum. It may be
3377    // that all callers to nextSpan should use this instead.
3378    // OPTIMIZATION splitting this into separate loops for up/down steps
3379    // would allow using precisely_negative instead of precisely_zero
3380    int nextExactSpan(int from, int step) const {
3381        const Span& fromSpan = fTs[from];
3382        int count = fTs.count();
3383        int to = from;
3384        while (step > 0 ? ++to < count : --to >= 0) {
3385            const Span& span = fTs[to];
3386            if (precisely_zero(span.fT - fromSpan.fT)) {
3387                continue;
3388            }
3389            return to;
3390        }
3391        return -1;
3392    }
3393
3394    bool operand() const {
3395        return fOperand;
3396    }
3397
3398    int oppSign(const Angle* angle) const {
3399        SkASSERT(angle->segment() == this);
3400        return oppSign(angle->start(), angle->end());
3401    }
3402
3403    int oppSign(int startIndex, int endIndex) const {
3404        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue
3405                : fTs[endIndex].fOppValue;
3406#if DEBUG_WIND_BUMP
3407        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
3408#endif
3409        return result;
3410    }
3411
3412    int oppSum(int tIndex) const {
3413        return fTs[tIndex].fOppSum;
3414    }
3415
3416    int oppSum(const Angle* angle) const {
3417        int lesser = SkMin32(angle->start(), angle->end());
3418        return fTs[lesser].fOppSum;
3419    }
3420
3421    int oppValue(int tIndex) const {
3422        return fTs[tIndex].fOppValue;
3423    }
3424
3425    int oppValue(const Angle* angle) const {
3426        int lesser = SkMin32(angle->start(), angle->end());
3427        return fTs[lesser].fOppValue;
3428    }
3429
3430    const SkPoint* pts() const {
3431        return fPts;
3432    }
3433
3434    void reset() {
3435        init(NULL, (SkPath::Verb) -1, false, false);
3436        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
3437        fTs.reset();
3438    }
3439
3440    void setOppXor(bool isOppXor) {
3441        fOppXor = isOppXor;
3442    }
3443
3444    void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
3445        int deltaSum = spanSign(index, endIndex);
3446        maxWinding = sumWinding;
3447        sumWinding = sumWinding -= deltaSum;
3448    }
3449
3450    void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding,
3451            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
3452        int deltaSum = spanSign(index, endIndex);
3453        int oppDeltaSum = oppSign(index, endIndex);
3454        if (operand()) {
3455            maxWinding = sumSuWinding;
3456            sumWinding = sumSuWinding -= deltaSum;
3457            oppMaxWinding = sumMiWinding;
3458            oppSumWinding = sumMiWinding -= oppDeltaSum;
3459        } else {
3460            maxWinding = sumMiWinding;
3461            sumWinding = sumMiWinding -= deltaSum;
3462            oppMaxWinding = sumSuWinding;
3463            oppSumWinding = sumSuWinding -= oppDeltaSum;
3464        }
3465    }
3466
3467    // This marks all spans unsortable so that this info is available for early
3468    // exclusion in find top and others. This could be optimized to only mark
3469    // adjacent spans that unsortable. However, this makes it difficult to later
3470    // determine starting points for edge detection in find top and the like.
3471    static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
3472        bool sortable = true;
3473        int angleCount = angles.count();
3474        int angleIndex;
3475        angleList.setReserve(angleCount);
3476        for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3477            Angle& angle = angles[angleIndex];
3478            *angleList.append() = &angle;
3479            sortable &= !angle.unsortable();
3480        }
3481        if (sortable) {
3482            QSort<Angle>(angleList.begin(), angleList.end() - 1);
3483            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3484                if (angles[angleIndex].unsortable()) {
3485                    sortable = false;
3486                    break;
3487                }
3488            }
3489        }
3490        if (!sortable) {
3491            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3492                Angle& angle = angles[angleIndex];
3493                angle.segment()->markUnsortable(angle.start(), angle.end());
3494            }
3495        }
3496        return sortable;
3497    }
3498
3499    // OPTIMIZATION: mark as debugging only if used solely by tests
3500    const Span& span(int tIndex) const {
3501        return fTs[tIndex];
3502    }
3503
3504    int spanSign(const Angle* angle) const {
3505        SkASSERT(angle->segment() == this);
3506        return spanSign(angle->start(), angle->end());
3507    }
3508
3509    int spanSign(int startIndex, int endIndex) const {
3510        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue
3511                : fTs[endIndex].fWindValue;
3512#if DEBUG_WIND_BUMP
3513        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
3514#endif
3515        return result;
3516    }
3517
3518    // OPTIMIZATION: mark as debugging only if used solely by tests
3519    double t(int tIndex) const {
3520        return fTs[tIndex].fT;
3521    }
3522
3523    double tAtMid(int start, int end, double mid) const {
3524        return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
3525    }
3526
3527    bool tiny(const Angle* angle) const {
3528        int start = angle->start();
3529        int end = angle->end();
3530        const Span& mSpan = fTs[SkMin32(start, end)];
3531        return mSpan.fTiny;
3532    }
3533
3534    static void TrackOutside(SkTDArray<double>& outsideTs, double end,
3535            double start) {
3536        int outCount = outsideTs.count();
3537        if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) {
3538            *outsideTs.append() = end;
3539            *outsideTs.append() = start;
3540        }
3541    }
3542
3543    void undoneSpan(int& start, int& end) {
3544        size_t tCount = fTs.count();
3545        size_t index;
3546        for (index = 0; index < tCount; ++index) {
3547            if (!fTs[index].fDone) {
3548                break;
3549            }
3550        }
3551        SkASSERT(index < tCount - 1);
3552        start = index;
3553        double startT = fTs[index].fT;
3554        while (approximately_negative(fTs[++index].fT - startT))
3555            SkASSERT(index < tCount);
3556        SkASSERT(index < tCount);
3557        end = index;
3558    }
3559
3560    bool unsortable(int index) const {
3561        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
3562    }
3563
3564    void updatePts(const SkPoint pts[]) {
3565        fPts = pts;
3566    }
3567
3568    int updateOppWinding(int index, int endIndex) const {
3569        int lesser = SkMin32(index, endIndex);
3570        int oppWinding = oppSum(lesser);
3571        int oppSpanWinding = oppSign(index, endIndex);
3572        if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWinding)) {
3573            oppWinding -= oppSpanWinding;
3574        }
3575        return oppWinding;
3576    }
3577
3578    int updateOppWinding(const Angle* angle) const {
3579        int startIndex = angle->start();
3580        int endIndex = angle->end();
3581        return updateOppWinding(endIndex, startIndex);
3582    }
3583
3584    int updateOppWindingReverse(const Angle* angle) const {
3585        int startIndex = angle->start();
3586        int endIndex = angle->end();
3587        return updateOppWinding(startIndex, endIndex);
3588    }
3589
3590    int updateWinding(int index, int endIndex) const {
3591        int lesser = SkMin32(index, endIndex);
3592        int winding = windSum(lesser);
3593        int spanWinding = spanSign(index, endIndex);
3594        if (winding && useInnerWinding(winding - spanWinding, winding)) {
3595            winding -= spanWinding;
3596        }
3597        return winding;
3598    }
3599
3600    int updateWinding(const Angle* angle) const {
3601        int startIndex = angle->start();
3602        int endIndex = angle->end();
3603        return updateWinding(endIndex, startIndex);
3604    }
3605
3606    int updateWindingReverse(const Angle* angle) const {
3607        int startIndex = angle->start();
3608        int endIndex = angle->end();
3609        return updateWinding(startIndex, endIndex);
3610    }
3611
3612    SkPath::Verb verb() const {
3613        return fVerb;
3614    }
3615
3616    int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar& dx) const {
3617        if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard
3618            return SK_MinS32;
3619        }
3620        int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
3621        SkASSERT(winding != SK_MinS32);
3622        int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
3623    #if DEBUG_WINDING_AT_T
3624        SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
3625    #endif
3626        // see if a + change in T results in a +/- change in X (compute x'(T))
3627        dx = (*SegmentDXAtT[fVerb])(fPts, tHit);
3628        if (fVerb > SkPath::kLine_Verb && approximately_zero(dx)) {
3629            dx = fPts[2].fX - fPts[1].fX - dx;
3630        }
3631        if (dx == 0) {
3632    #if DEBUG_WINDING_AT_T
3633            SkDebugf(" dx=0 winding=SK_MinS32\n");
3634    #endif
3635            return SK_MinS32;
3636        }
3637        if (winding * dx > 0) { // if same signs, result is negative
3638            winding += dx > 0 ? -windVal : windVal;
3639        }
3640    #if DEBUG_WINDING_AT_T
3641        SkDebugf(" dx=%c winding=%d\n", dx > 0 ? '+' : '-', winding);
3642    #endif
3643        return winding;
3644    }
3645
3646    int windSum(int tIndex) const {
3647        return fTs[tIndex].fWindSum;
3648    }
3649
3650    int windSum(const Angle* angle) const {
3651        int start = angle->start();
3652        int end = angle->end();
3653        int index = SkMin32(start, end);
3654        return windSum(index);
3655    }
3656
3657    int windValue(int tIndex) const {
3658        return fTs[tIndex].fWindValue;
3659    }
3660
3661    int windValue(const Angle* angle) const {
3662        int start = angle->start();
3663        int end = angle->end();
3664        int index = SkMin32(start, end);
3665        return windValue(index);
3666    }
3667
3668    int windValueAt(double t) const {
3669        int count = fTs.count();
3670        for (int index = 0; index < count; ++index) {
3671            if (fTs[index].fT == t) {
3672                return fTs[index].fWindValue;
3673            }
3674        }
3675        SkASSERT(0);
3676        return 0;
3677    }
3678
3679    SkScalar xAtT(int index) const {
3680        return xAtT(&fTs[index]);
3681    }
3682
3683    SkScalar xAtT(const Span* span) const {
3684        return xyAtT(span).fX;
3685    }
3686
3687    const SkPoint& xyAtT(int index) const {
3688        return xyAtT(&fTs[index]);
3689    }
3690
3691    const SkPoint& xyAtT(const Span* span) const {
3692        if (SkScalarIsNaN(span->fPt.fX)) {
3693            if (span->fT == 0) {
3694                span->fPt = fPts[0];
3695            } else if (span->fT == 1) {
3696                span->fPt = fPts[fVerb];
3697            } else {
3698                (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt);
3699            }
3700        }
3701        return span->fPt;
3702    }
3703
3704    // used only by right angle winding finding
3705    void xyAtT(double mid, SkPoint& pt) const {
3706        (*SegmentXYAtT[fVerb])(fPts, mid, &pt);
3707    }
3708
3709    SkScalar yAtT(int index) const {
3710        return yAtT(&fTs[index]);
3711    }
3712
3713    SkScalar yAtT(const Span* span) const {
3714        return xyAtT(span).fY;
3715    }
3716
3717    void zeroCoincidentOpp(Span* oTest, int index) {
3718        Span* const test = &fTs[index];
3719        Span* end = test;
3720        do {
3721            end->fOppValue = 0;
3722            end = &fTs[++index];
3723        } while (approximately_negative(end->fT - test->fT));
3724    }
3725
3726    void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT, int oIndex) {
3727        Span* const oTest = &fTs[oIndex];
3728        Span* oEnd = oTest;
3729        const double startT = test->fT;
3730        const double oStartT = oTest->fT;
3731        double otherTMatch = (test->fT - startT) * tRatio + oStartT;
3732        while (!approximately_negative(oEndT - oEnd->fT)
3733                && approximately_negative(oEnd->fT - otherTMatch)) {
3734            oEnd->fOppValue = 0;
3735            oEnd = &fTs[++oIndex];
3736        }
3737    }
3738
3739    void zeroSpan(Span* span) {
3740        SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
3741        span->fWindValue = 0;
3742        span->fOppValue = 0;
3743        SkASSERT(!span->fDone);
3744        span->fDone = true;
3745        ++fDoneSpans;
3746    }
3747
3748#if DEBUG_DUMP
3749    void dump() const {
3750        const char className[] = "Segment";
3751        const int tab = 4;
3752        for (int i = 0; i < fTs.count(); ++i) {
3753            SkPoint out;
3754            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
3755            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
3756                    " otherT=%1.9g windSum=%d\n",
3757                    tab + sizeof(className), className, fID,
3758                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
3759                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
3760        }
3761        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
3762                tab + sizeof(className), className, fID,
3763                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
3764    }
3765#endif
3766
3767#if DEBUG_CONCIDENT
3768    // assert if pair has not already been added
3769     void debugAddTPair(double t, const Segment& other, double otherT) const {
3770        for (int i = 0; i < fTs.count(); ++i) {
3771            if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
3772                return;
3773            }
3774        }
3775        SkASSERT(0);
3776     }
3777#endif
3778
3779#if DEBUG_DUMP
3780    int debugID() const {
3781        return fID;
3782    }
3783#endif
3784
3785#if DEBUG_WINDING
3786    void debugShowSums() const {
3787        SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,
3788            fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);
3789        for (int i = 0; i < fTs.count(); ++i) {
3790            const Span& span = fTs[i];
3791            SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span));
3792            if (span.fWindSum == SK_MinS32) {
3793                SkDebugf("?");
3794            } else {
3795                SkDebugf("%d", span.fWindSum);
3796            }
3797            SkDebugf("]");
3798        }
3799        SkDebugf("\n");
3800    }
3801#endif
3802
3803#if DEBUG_CONCIDENT
3804    void debugShowTs() const {
3805        SkDebugf("%s id=%d", __FUNCTION__, fID);
3806        int lastWind = -1;
3807        int lastOpp = -1;
3808        double lastT = -1;
3809        int i;
3810        for (i = 0; i < fTs.count(); ++i) {
3811            bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
3812                    || lastOpp != fTs[i].fOppValue;
3813            if (change && lastWind >= 0) {
3814                SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
3815                        lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
3816            }
3817            if (change) {
3818                SkDebugf(" [o=%d", fTs[i].fOther->fID);
3819                lastWind = fTs[i].fWindValue;
3820                lastOpp = fTs[i].fOppValue;
3821                lastT = fTs[i].fT;
3822            } else {
3823                SkDebugf(",%d", fTs[i].fOther->fID);
3824            }
3825        }
3826        if (i <= 0) {
3827            return;
3828        }
3829        SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
3830                lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
3831        if (fOperand) {
3832            SkDebugf(" operand");
3833        }
3834        if (done()) {
3835            SkDebugf(" done");
3836        }
3837        SkDebugf("\n");
3838    }
3839#endif
3840
3841#if DEBUG_ACTIVE_SPANS
3842    void debugShowActiveSpans() const {
3843        if (done()) {
3844            return;
3845        }
3846#if DEBUG_ACTIVE_SPANS_SHORT_FORM
3847        int lastId = -1;
3848        double lastT = -1;
3849#endif
3850        for (int i = 0; i < fTs.count(); ++i) {
3851            if (fTs[i].fDone) {
3852                continue;
3853            }
3854#if DEBUG_ACTIVE_SPANS_SHORT_FORM
3855            if (lastId == fID && lastT == fTs[i].fT) {
3856                continue;
3857            }
3858            lastId = fID;
3859            lastT = fTs[i].fT;
3860#endif
3861            SkDebugf("%s id=%d", __FUNCTION__, fID);
3862            SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3863            for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3864                SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3865            }
3866            const Span* span = &fTs[i];
3867            SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,
3868                     xAtT(span), yAtT(span));
3869            const Segment* other = fTs[i].fOther;
3870            SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
3871                    other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
3872            if (fTs[i].fWindSum == SK_MinS32) {
3873                SkDebugf("?");
3874            } else {
3875                SkDebugf("%d", fTs[i].fWindSum);
3876            }
3877            SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
3878        }
3879    }
3880
3881    // This isn't useful yet -- but leaving it in for now in case i think of something
3882    // to use it for
3883    void validateActiveSpans() const {
3884        if (done()) {
3885            return;
3886        }
3887        int tCount = fTs.count();
3888        for (int index = 0; index < tCount; ++index) {
3889            if (fTs[index].fDone) {
3890                continue;
3891            }
3892            // count number of connections which are not done
3893            int first = index;
3894            double baseT = fTs[index].fT;
3895            while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) {
3896                --first;
3897            }
3898            int last = index;
3899            while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) {
3900                ++last;
3901            }
3902            int connections = 0;
3903            connections += first > 0 && !fTs[first - 1].fDone;
3904            for (int test = first; test <= last; ++test) {
3905                connections += !fTs[test].fDone;
3906                const Segment* other = fTs[test].fOther;
3907                int oIndex = fTs[test].fOtherIndex;
3908                connections += !other->fTs[oIndex].fDone;
3909                connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone;
3910            }
3911      //      SkASSERT(!(connections & 1));
3912        }
3913    }
3914#endif
3915
3916#if DEBUG_MARK_DONE
3917    void debugShowNewWinding(const char* fun, const Span& span, int winding) {
3918        const SkPoint& pt = xyAtT(&span);
3919        SkDebugf("%s id=%d", fun, fID);
3920        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3921        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3922            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3923        }
3924        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3925                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3926        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=",
3927                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding);
3928        if (span.fWindSum == SK_MinS32) {
3929            SkDebugf("?");
3930        } else {
3931            SkDebugf("%d", span.fWindSum);
3932        }
3933        SkDebugf(" windValue=%d\n", span.fWindValue);
3934    }
3935
3936    void debugShowNewWinding(const char* fun, const Span& span, int winding, int oppWinding) {
3937        const SkPoint& pt = xyAtT(&span);
3938        SkDebugf("%s id=%d", fun, fID);
3939        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3940        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
3941            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3942        }
3943        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3944                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3945        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d newOppSum=%d oppSum=",
3946                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
3947                winding, oppWinding);
3948        if (span.fOppSum == SK_MinS32) {
3949            SkDebugf("?");
3950        } else {
3951            SkDebugf("%d", span.fOppSum);
3952        }
3953        SkDebugf(" windSum=");
3954        if (span.fWindSum == SK_MinS32) {
3955            SkDebugf("?");
3956        } else {
3957            SkDebugf("%d", span.fWindSum);
3958        }
3959        SkDebugf(" windValue=%d\n", span.fWindValue);
3960    }
3961#endif
3962
3963#if DEBUG_SORT
3964    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first,
3965            const int contourWinding, const int oppContourWinding) const {
3966        SkASSERT(angles[first]->segment() == this);
3967        SkASSERT(angles.count() > 1);
3968        int lastSum = contourWinding;
3969        int oppLastSum = oppContourWinding;
3970        const Angle* firstAngle = angles[first];
3971        int windSum = lastSum - spanSign(firstAngle);
3972        int oppoSign = oppSign(firstAngle);
3973        int oppWindSum = oppLastSum - oppoSign;
3974        SkDebugf("%s %s contourWinding=%d oppContourWinding=%d sign=%d\n", fun, __FUNCTION__,
3975                contourWinding, oppContourWinding, spanSign(angles[first]));
3976        int index = first;
3977        bool firstTime = true;
3978        do {
3979            const Angle& angle = *angles[index];
3980            const Segment& segment = *angle.segment();
3981            int start = angle.start();
3982            int end = angle.end();
3983            const Span& sSpan = segment.fTs[start];
3984            const Span& eSpan = segment.fTs[end];
3985            const Span& mSpan = segment.fTs[SkMin32(start, end)];
3986            bool opp = segment.fOperand ^ fOperand;
3987            if (!firstTime) {
3988                oppoSign = segment.oppSign(&angle);
3989                if (opp) {
3990                    oppLastSum = oppWindSum;
3991                    oppWindSum -= segment.spanSign(&angle);
3992                    if (oppoSign) {
3993                        lastSum = windSum;
3994                        windSum -= oppoSign;
3995                    }
3996                } else {
3997                    lastSum = windSum;
3998                    windSum -= segment.spanSign(&angle);
3999                    if (oppoSign) {
4000                        oppLastSum = oppWindSum;
4001                        oppWindSum -= oppoSign;
4002                    }
4003                }
4004            }
4005            SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
4006                    " sign=%d windValue=%d windSum=",
4007                    __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "",
4008                    segment.fID, kLVerbStr[segment.fVerb],
4009                    start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
4010                    segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(),
4011                    mSpan.fWindValue);
4012            if (mSpan.fWindSum == SK_MinS32) {
4013                SkDebugf("?");
4014            } else {
4015                SkDebugf("%d", mSpan.fWindSum);
4016            }
4017            int last, wind;
4018            if (opp) {
4019                last = oppLastSum;
4020                wind = oppWindSum;
4021            } else {
4022                last = lastSum;
4023                wind = windSum;
4024            }
4025            if (!oppoSign) {
4026                SkDebugf(" %d->%d (max=%d)", last, wind,
4027                        useInnerWinding(last, wind) ? wind : last);
4028            } else {
4029                SkDebugf(" %d->%d (%d->%d)", last, wind, opp ? lastSum : oppLastSum,
4030                        opp ? windSum : oppWindSum);
4031            }
4032            SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp);
4033#if false && DEBUG_ANGLE
4034            angle.debugShow(segment.xyAtT(&sSpan));
4035#endif
4036            ++index;
4037            if (index == angles.count()) {
4038                index = 0;
4039            }
4040            if (firstTime) {
4041                firstTime = false;
4042            }
4043        } while (index != first);
4044    }
4045
4046    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first) {
4047        const Angle* firstAngle = angles[first];
4048        const Segment* segment = firstAngle->segment();
4049        int winding = segment->updateWinding(firstAngle);
4050        int oppWinding = segment->updateOppWinding(firstAngle);
4051        debugShowSort(fun, angles, first, winding, oppWinding);
4052    }
4053
4054#endif
4055
4056#if DEBUG_WINDING
4057    static char as_digit(int value) {
4058        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
4059    }
4060#endif
4061
4062#if DEBUG_SHOW_WINDING
4063    int debugShowWindingValues(int slotCount, int ofInterest) const {
4064        if (!(1 << fID & ofInterest)) {
4065            return 0;
4066        }
4067        int sum = 0;
4068        SkTDArray<char> slots;
4069        slots.setCount(slotCount * 2);
4070        memset(slots.begin(), ' ', slotCount * 2);
4071        for (int i = 0; i < fTs.count(); ++i) {
4072       //     if (!(1 << fTs[i].fOther->fID & ofInterest)) {
4073       //         continue;
4074       //     }
4075            sum += fTs[i].fWindValue;
4076            slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
4077            sum += fTs[i].fOppValue;
4078            slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
4079        }
4080        SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
4081                slots.begin() + slotCount);
4082        return sum;
4083    }
4084#endif
4085
4086private:
4087    const SkPoint* fPts;
4088    Bounds fBounds;
4089    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
4090    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
4091    int fDoneSpans; // quick check that segment is finished
4092    // OPTIMIZATION: force the following to be byte-sized
4093    SkPath::Verb fVerb;
4094    bool fOperand;
4095    bool fXor; // set if original contour had even-odd fill
4096    bool fOppXor; // set if opposite operand had even-odd fill
4097#if DEBUG_DUMP
4098    int fID;
4099#endif
4100};
4101
4102class Contour;
4103
4104struct Coincidence {
4105    Contour* fContours[2];
4106    int fSegments[2];
4107    double fTs[2][2];
4108};
4109
4110class Contour {
4111public:
4112    Contour() {
4113        reset();
4114#if DEBUG_DUMP
4115        fID = ++gContourID;
4116#endif
4117    }
4118
4119    bool operator<(const Contour& rh) const {
4120        return fBounds.fTop == rh.fBounds.fTop
4121                ? fBounds.fLeft < rh.fBounds.fLeft
4122                : fBounds.fTop < rh.fBounds.fTop;
4123    }
4124
4125    void addCoincident(int index, Contour* other, int otherIndex,
4126            const Intersections& ts, bool swap) {
4127        Coincidence& coincidence = *fCoincidences.append();
4128        coincidence.fContours[0] = this; // FIXME: no need to store
4129        coincidence.fContours[1] = other;
4130        coincidence.fSegments[0] = index;
4131        coincidence.fSegments[1] = otherIndex;
4132        if (fSegments[index].verb() == SkPath::kLine_Verb &&
4133                other->fSegments[otherIndex].verb() == SkPath::kLine_Verb) {
4134            // FIXME: coincident lines use legacy Ts instead of coincident Ts
4135            coincidence.fTs[swap][0] = ts.fT[0][0];
4136            coincidence.fTs[swap][1] = ts.fT[0][1];
4137            coincidence.fTs[!swap][0] = ts.fT[1][0];
4138            coincidence.fTs[!swap][1] = ts.fT[1][1];
4139        } else if (fSegments[index].verb() == SkPath::kQuad_Verb &&
4140                other->fSegments[otherIndex].verb() == SkPath::kQuad_Verb) {
4141            coincidence.fTs[swap][0] = ts.fCoincidentT[0][0];
4142            coincidence.fTs[swap][1] = ts.fCoincidentT[0][1];
4143            coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0];
4144            coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1];
4145        }
4146    }
4147
4148    void addCross(const Contour* crosser) {
4149#ifdef DEBUG_CROSS
4150        for (int index = 0; index < fCrosses.count(); ++index) {
4151            SkASSERT(fCrosses[index] != crosser);
4152        }
4153#endif
4154        *fCrosses.append() = crosser;
4155    }
4156
4157    void addCubic(const SkPoint pts[4]) {
4158        fSegments.push_back().addCubic(pts, fOperand, fXor);
4159        fContainsCurves = true;
4160    }
4161
4162    int addLine(const SkPoint pts[2]) {
4163        fSegments.push_back().addLine(pts, fOperand, fXor);
4164        return fSegments.count();
4165    }
4166
4167    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
4168        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
4169    }
4170
4171    int addQuad(const SkPoint pts[3]) {
4172        fSegments.push_back().addQuad(pts, fOperand, fXor);
4173        fContainsCurves = true;
4174        return fSegments.count();
4175    }
4176
4177    int addT(int segIndex, double newT, Contour* other, int otherIndex) {
4178        containsIntercepts();
4179        return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
4180    }
4181
4182    int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start) {
4183        return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start);
4184    }
4185
4186    const Bounds& bounds() const {
4187        return fBounds;
4188    }
4189
4190    void complete() {
4191        setBounds();
4192        fContainsIntercepts = false;
4193    }
4194
4195    void containsIntercepts() {
4196        fContainsIntercepts = true;
4197    }
4198
4199    bool crosses(const Contour* crosser) const {
4200        for (int index = 0; index < fCrosses.count(); ++index) {
4201            if (fCrosses[index] == crosser) {
4202                return true;
4203            }
4204        }
4205        return false;
4206    }
4207
4208    bool done() const {
4209        return fDone;
4210    }
4211
4212    const SkPoint& end() const {
4213        const Segment& segment = fSegments.back();
4214        return segment.pts()[segment.verb()];
4215    }
4216
4217    void findTooCloseToCall() {
4218        int segmentCount = fSegments.count();
4219        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
4220            fSegments[sIndex].findTooCloseToCall();
4221        }
4222    }
4223
4224    void fixOtherTIndex() {
4225        int segmentCount = fSegments.count();
4226        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
4227            fSegments[sIndex].fixOtherTIndex();
4228        }
4229    }
4230
4231    Segment* nonVerticalSegment(int& start, int& end) {
4232        int segmentCount = fSortedSegments.count();
4233        SkASSERT(segmentCount > 0);
4234        for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
4235            Segment* testSegment = fSortedSegments[sortedIndex];
4236            if (testSegment->done()) {
4237                continue;
4238            }
4239            start = end = 0;
4240            while (testSegment->nextCandidate(start, end)) {
4241                if (!testSegment->isVertical(start, end)) {
4242                    return testSegment;
4243                }
4244            }
4245        }
4246        return NULL;
4247    }
4248
4249    bool operand() const {
4250        return fOperand;
4251    }
4252
4253    void reset() {
4254        fSegments.reset();
4255        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
4256        fContainsCurves = fContainsIntercepts = fDone = false;
4257    }
4258
4259    void resolveCoincidence(SkTDArray<Contour*>& contourList) {
4260        int count = fCoincidences.count();
4261        for (int index = 0; index < count; ++index) {
4262            Coincidence& coincidence = fCoincidences[index];
4263            SkASSERT(coincidence.fContours[0] == this);
4264            int thisIndex = coincidence.fSegments[0];
4265            Segment& thisOne = fSegments[thisIndex];
4266            Contour* otherContour = coincidence.fContours[1];
4267            int otherIndex = coincidence.fSegments[1];
4268            Segment& other = otherContour->fSegments[otherIndex];
4269            if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
4270                continue;
4271            }
4272        #if DEBUG_CONCIDENT
4273            thisOne.debugShowTs();
4274            other.debugShowTs();
4275        #endif
4276            double startT = coincidence.fTs[0][0];
4277            double endT = coincidence.fTs[0][1];
4278            bool cancelers = false;
4279            if (startT > endT) {
4280                SkTSwap<double>(startT, endT);
4281                cancelers ^= true; // FIXME: just assign true
4282            }
4283            SkASSERT(!approximately_negative(endT - startT));
4284            double oStartT = coincidence.fTs[1][0];
4285            double oEndT = coincidence.fTs[1][1];
4286            if (oStartT > oEndT) {
4287                SkTSwap<double>(oStartT, oEndT);
4288                cancelers ^= true;
4289            }
4290            SkASSERT(!approximately_negative(oEndT - oStartT));
4291            bool opp = fOperand ^ otherContour->fOperand;
4292            if (cancelers && !opp) {
4293                // make sure startT and endT have t entries
4294                if (startT > 0 || oEndT < 1
4295                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
4296                    thisOne.addTPair(startT, other, oEndT, true);
4297                }
4298                if (oStartT > 0 || endT < 1
4299                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
4300                    other.addTPair(oStartT, thisOne, endT, true);
4301                }
4302                if (!thisOne.done() && !other.done()) {
4303                    thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
4304                }
4305            } else {
4306                if (startT > 0 || oStartT > 0
4307                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
4308                    thisOne.addTPair(startT, other, oStartT, true);
4309                }
4310                if (endT < 1 || oEndT < 1
4311                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
4312                    other.addTPair(oEndT, thisOne, endT, true);
4313                }
4314                if (!thisOne.done() && !other.done()) {
4315                    thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
4316                }
4317            }
4318        #if DEBUG_CONCIDENT
4319            thisOne.debugShowTs();
4320            other.debugShowTs();
4321        #endif
4322        #if DEBUG_SHOW_WINDING
4323            debugShowWindingValues(contourList);
4324        #endif
4325        }
4326    }
4327
4328    // first pass, add missing T values
4329    // second pass, determine winding values of overlaps
4330    void addCoincidentPoints() {
4331        int count = fCoincidences.count();
4332        for (int index = 0; index < count; ++index) {
4333            Coincidence& coincidence = fCoincidences[index];
4334            SkASSERT(coincidence.fContours[0] == this);
4335            int thisIndex = coincidence.fSegments[0];
4336            Segment& thisOne = fSegments[thisIndex];
4337            Contour* otherContour = coincidence.fContours[1];
4338            int otherIndex = coincidence.fSegments[1];
4339            Segment& other = otherContour->fSegments[otherIndex];
4340            if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
4341                // OPTIMIZATION: remove from array
4342                continue;
4343            }
4344        #if DEBUG_CONCIDENT
4345            thisOne.debugShowTs();
4346            other.debugShowTs();
4347        #endif
4348            double startT = coincidence.fTs[0][0];
4349            double endT = coincidence.fTs[0][1];
4350            bool cancelers;
4351            if ((cancelers = startT > endT)) {
4352                SkTSwap<double>(startT, endT);
4353            }
4354            SkASSERT(!approximately_negative(endT - startT));
4355            double oStartT = coincidence.fTs[1][0];
4356            double oEndT = coincidence.fTs[1][1];
4357            if (oStartT > oEndT) {
4358                SkTSwap<double>(oStartT, oEndT);
4359                cancelers ^= true;
4360            }
4361            SkASSERT(!approximately_negative(oEndT - oStartT));
4362            bool opp = fOperand ^ otherContour->fOperand;
4363            if (cancelers && !opp) {
4364                // make sure startT and endT have t entries
4365                if (startT > 0 || oEndT < 1
4366                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
4367                    thisOne.addTPair(startT, other, oEndT, true);
4368                }
4369                if (oStartT > 0 || endT < 1
4370                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
4371                    other.addTPair(oStartT, thisOne, endT, true);
4372                }
4373            } else {
4374                if (startT > 0 || oStartT > 0
4375                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
4376                    thisOne.addTPair(startT, other, oStartT, true);
4377                }
4378                if (endT < 1 || oEndT < 1
4379                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
4380                    other.addTPair(oEndT, thisOne, endT, true);
4381                }
4382            }
4383        #if DEBUG_CONCIDENT
4384            thisOne.debugShowTs();
4385            other.debugShowTs();
4386        #endif
4387        }
4388    }
4389
4390    void calcCoincidentWinding() {
4391        int count = fCoincidences.count();
4392        for (int index = 0; index < count; ++index) {
4393            Coincidence& coincidence = fCoincidences[index];
4394            SkASSERT(coincidence.fContours[0] == this);
4395            int thisIndex = coincidence.fSegments[0];
4396            Segment& thisOne = fSegments[thisIndex];
4397            if (thisOne.done()) {
4398                continue;
4399            }
4400            Contour* otherContour = coincidence.fContours[1];
4401            int otherIndex = coincidence.fSegments[1];
4402            Segment& other = otherContour->fSegments[otherIndex];
4403            if (other.done()) {
4404                continue;
4405            }
4406            double startT = coincidence.fTs[0][0];
4407            double endT = coincidence.fTs[0][1];
4408            bool cancelers;
4409            if ((cancelers = startT > endT)) {
4410                SkTSwap<double>(startT, endT);
4411            }
4412            SkASSERT(!approximately_negative(endT - startT));
4413            double oStartT = coincidence.fTs[1][0];
4414            double oEndT = coincidence.fTs[1][1];
4415            if (oStartT > oEndT) {
4416                SkTSwap<double>(oStartT, oEndT);
4417                cancelers ^= true;
4418            }
4419            SkASSERT(!approximately_negative(oEndT - oStartT));
4420            bool opp = fOperand ^ otherContour->fOperand;
4421            if (cancelers && !opp) {
4422                // make sure startT and endT have t entries
4423                if (!thisOne.done() && !other.done()) {
4424                    thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
4425                }
4426            } else {
4427                if (!thisOne.done() && !other.done()) {
4428                    thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
4429                }
4430            }
4431        #if DEBUG_CONCIDENT
4432            thisOne.debugShowTs();
4433            other.debugShowTs();
4434        #endif
4435        }
4436    }
4437
4438    SkTArray<Segment>& segments() {
4439        return fSegments;
4440    }
4441
4442    void setOperand(bool isOp) {
4443        fOperand = isOp;
4444    }
4445
4446    void setOppXor(bool isOppXor) {
4447        fOppXor = isOppXor;
4448        int segmentCount = fSegments.count();
4449        for (int test = 0; test < segmentCount; ++test) {
4450            fSegments[test].setOppXor(isOppXor);
4451        }
4452    }
4453
4454    void setXor(bool isXor) {
4455        fXor = isXor;
4456    }
4457
4458    void sortSegments() {
4459        int segmentCount = fSegments.count();
4460        fSortedSegments.setReserve(segmentCount);
4461        for (int test = 0; test < segmentCount; ++test) {
4462            *fSortedSegments.append() = &fSegments[test];
4463        }
4464        QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
4465        fFirstSorted = 0;
4466    }
4467
4468    const SkPoint& start() const {
4469        return fSegments.front().pts()[0];
4470    }
4471
4472    void toPath(PathWrapper& path) const {
4473        int segmentCount = fSegments.count();
4474        const SkPoint& pt = fSegments.front().pts()[0];
4475        path.deferredMove(pt);
4476        for (int test = 0; test < segmentCount; ++test) {
4477            fSegments[test].addCurveTo(0, 1, path, true);
4478        }
4479        path.close();
4480    }
4481
4482    void toPartialBackward(PathWrapper& path) const {
4483        int segmentCount = fSegments.count();
4484        for (int test = segmentCount - 1; test >= 0; --test) {
4485            fSegments[test].addCurveTo(1, 0, path, true);
4486        }
4487    }
4488
4489    void toPartialForward(PathWrapper& path) const {
4490        int segmentCount = fSegments.count();
4491        for (int test = 0; test < segmentCount; ++test) {
4492            fSegments[test].addCurveTo(0, 1, path, true);
4493        }
4494    }
4495
4496    void topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, Segment*& topStart) {
4497        int segmentCount = fSortedSegments.count();
4498        SkASSERT(segmentCount > 0);
4499        int sortedIndex = fFirstSorted;
4500        fDone = true; // may be cleared below
4501        for ( ; sortedIndex < segmentCount; ++sortedIndex) {
4502            Segment* testSegment = fSortedSegments[sortedIndex];
4503            if (testSegment->done()) {
4504                if (sortedIndex == fFirstSorted) {
4505                    ++fFirstSorted;
4506                }
4507                continue;
4508            }
4509            fDone = false;
4510            SkPoint testXY;
4511            testSegment->activeLeftTop(testXY);
4512            if (topStart) {
4513                if (testXY.fY < topLeft.fY) {
4514                    continue;
4515                }
4516                if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
4517                    continue;
4518                }
4519                if (bestXY.fY < testXY.fY) {
4520                    continue;
4521                }
4522                if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) {
4523                    continue;
4524                }
4525            }
4526            topStart = testSegment;
4527            bestXY = testXY;
4528        }
4529    }
4530
4531    Segment* undoneSegment(int& start, int& end) {
4532        int segmentCount = fSegments.count();
4533        for (int test = 0; test < segmentCount; ++test) {
4534            Segment* testSegment = &fSegments[test];
4535            if (testSegment->done()) {
4536                continue;
4537            }
4538            testSegment->undoneSpan(start, end);
4539            return testSegment;
4540        }
4541        return NULL;
4542    }
4543
4544    int updateSegment(int index, const SkPoint* pts) {
4545        Segment& segment = fSegments[index];
4546        segment.updatePts(pts);
4547        return segment.verb() + 1;
4548    }
4549
4550#if DEBUG_TEST
4551    SkTArray<Segment>& debugSegments() {
4552        return fSegments;
4553    }
4554#endif
4555
4556#if DEBUG_DUMP
4557    void dump() {
4558        int i;
4559        const char className[] = "Contour";
4560        const int tab = 4;
4561        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
4562        for (i = 0; i < fSegments.count(); ++i) {
4563            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
4564                    className, i);
4565            fSegments[i].dump();
4566        }
4567        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
4568                tab + sizeof(className), className,
4569                fBounds.fLeft, fBounds.fTop,
4570                fBounds.fRight, fBounds.fBottom);
4571        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
4572                className, fContainsIntercepts);
4573        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
4574                className, fContainsCurves);
4575    }
4576#endif
4577
4578#if DEBUG_ACTIVE_SPANS
4579    void debugShowActiveSpans() {
4580        for (int index = 0; index < fSegments.count(); ++index) {
4581            fSegments[index].debugShowActiveSpans();
4582        }
4583    }
4584
4585    void validateActiveSpans() {
4586        for (int index = 0; index < fSegments.count(); ++index) {
4587            fSegments[index].validateActiveSpans();
4588        }
4589    }
4590#endif
4591
4592#if DEBUG_SHOW_WINDING
4593    int debugShowWindingValues(int totalSegments, int ofInterest) {
4594        int count = fSegments.count();
4595        int sum = 0;
4596        for (int index = 0; index < count; ++index) {
4597            sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
4598        }
4599  //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
4600        return sum;
4601    }
4602
4603    static void debugShowWindingValues(SkTDArray<Contour*>& contourList) {
4604   //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
4605    //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
4606        int ofInterest = 1 << 5 | 1 << 8;
4607        int total = 0;
4608        int index;
4609        for (index = 0; index < contourList.count(); ++index) {
4610            total += contourList[index]->segments().count();
4611        }
4612        int sum = 0;
4613        for (index = 0; index < contourList.count(); ++index) {
4614            sum += contourList[index]->debugShowWindingValues(total, ofInterest);
4615        }
4616 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
4617    }
4618#endif
4619
4620protected:
4621    void setBounds() {
4622        int count = fSegments.count();
4623        if (count == 0) {
4624            SkDebugf("%s empty contour\n", __FUNCTION__);
4625            SkASSERT(0);
4626            // FIXME: delete empty contour?
4627            return;
4628        }
4629        fBounds = fSegments.front().bounds();
4630        for (int index = 1; index < count; ++index) {
4631            fBounds.add(fSegments[index].bounds());
4632        }
4633    }
4634
4635private:
4636    SkTArray<Segment> fSegments;
4637    SkTDArray<Segment*> fSortedSegments;
4638    int fFirstSorted;
4639    SkTDArray<Coincidence> fCoincidences;
4640    SkTDArray<const Contour*> fCrosses;
4641    Bounds fBounds;
4642    bool fContainsIntercepts;
4643    bool fContainsCurves;
4644    bool fDone;
4645    bool fOperand; // true for the second argument to a binary operator
4646    bool fXor;
4647    bool fOppXor;
4648#if DEBUG_DUMP
4649    int fID;
4650#endif
4651};
4652
4653class EdgeBuilder {
4654public:
4655
4656EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours)
4657    : fPath(path.nativePath())
4658    , fContours(contours)
4659{
4660    init();
4661}
4662
4663EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
4664    : fPath(&path)
4665    , fContours(contours)
4666{
4667    init();
4668}
4669
4670void init() {
4671    fCurrentContour = NULL;
4672    fOperand = false;
4673    fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
4674#if DEBUG_DUMP
4675    gContourID = 0;
4676    gSegmentID = 0;
4677#endif
4678    fSecondHalf = preFetch();
4679}
4680
4681void addOperand(const SkPath& path) {
4682    SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
4683    fPathVerbs.pop();
4684    fPath = &path;
4685    fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
4686    preFetch();
4687}
4688
4689void finish() {
4690    walk();
4691    complete();
4692    if (fCurrentContour && !fCurrentContour->segments().count()) {
4693        fContours.pop_back();
4694    }
4695    // correct pointers in contours since fReducePts may have moved as it grew
4696    int cIndex = 0;
4697    int extraCount = fExtra.count();
4698    SkASSERT(extraCount == 0 || fExtra[0] == -1);
4699    int eIndex = 0;
4700    int rIndex = 0;
4701    while (++eIndex < extraCount) {
4702        int offset = fExtra[eIndex];
4703        if (offset < 0) {
4704            ++cIndex;
4705            continue;
4706        }
4707        fCurrentContour = &fContours[cIndex];
4708        rIndex += fCurrentContour->updateSegment(offset - 1,
4709                &fReducePts[rIndex]);
4710    }
4711    fExtra.reset(); // we're done with this
4712}
4713
4714ShapeOpMask xorMask() const {
4715    return fXorMask[fOperand];
4716}
4717
4718protected:
4719
4720void complete() {
4721    if (fCurrentContour && fCurrentContour->segments().count()) {
4722        fCurrentContour->complete();
4723        fCurrentContour = NULL;
4724    }
4725}
4726
4727// FIXME:remove once we can access path pts directly
4728int preFetch() {
4729    SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed
4730    SkPoint pts[4];
4731    SkPath::Verb verb;
4732    do {
4733        verb = iter.next(pts);
4734        *fPathVerbs.append() = verb;
4735        if (verb == SkPath::kMove_Verb) {
4736            *fPathPts.append() = pts[0];
4737        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
4738            fPathPts.append(verb, &pts[1]);
4739        }
4740    } while (verb != SkPath::kDone_Verb);
4741    return fPathVerbs.count() - 1;
4742}
4743
4744void walk() {
4745    SkPath::Verb reducedVerb;
4746    uint8_t* verbPtr = fPathVerbs.begin();
4747    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
4748    const SkPoint* pointsPtr = fPathPts.begin();
4749    const SkPoint* finalCurveStart = NULL;
4750    const SkPoint* finalCurveEnd = NULL;
4751    SkPath::Verb verb;
4752    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
4753        switch (verb) {
4754            case SkPath::kMove_Verb:
4755                complete();
4756                if (!fCurrentContour) {
4757                    fCurrentContour = fContours.push_back_n(1);
4758                    fCurrentContour->setOperand(fOperand);
4759                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_Mask);
4760                    *fExtra.append() = -1; // start new contour
4761                }
4762                finalCurveEnd = pointsPtr++;
4763                goto nextVerb;
4764            case SkPath::kLine_Verb:
4765                // skip degenerate points
4766                if (pointsPtr[-1].fX != pointsPtr[0].fX
4767                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
4768                    fCurrentContour->addLine(&pointsPtr[-1]);
4769                }
4770                break;
4771            case SkPath::kQuad_Verb:
4772
4773                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
4774                if (reducedVerb == 0) {
4775                    break; // skip degenerate points
4776                }
4777                if (reducedVerb == 1) {
4778                    *fExtra.append() =
4779                            fCurrentContour->addLine(fReducePts.end() - 2);
4780                    break;
4781                }
4782                fCurrentContour->addQuad(&pointsPtr[-1]);
4783                break;
4784            case SkPath::kCubic_Verb:
4785                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
4786                if (reducedVerb == 0) {
4787                    break; // skip degenerate points
4788                }
4789                if (reducedVerb == 1) {
4790                    *fExtra.append() =
4791                            fCurrentContour->addLine(fReducePts.end() - 2);
4792                    break;
4793                }
4794                if (reducedVerb == 2) {
4795                    *fExtra.append() =
4796                            fCurrentContour->addQuad(fReducePts.end() - 3);
4797                    break;
4798                }
4799                fCurrentContour->addCubic(&pointsPtr[-1]);
4800                break;
4801            case SkPath::kClose_Verb:
4802                SkASSERT(fCurrentContour);
4803                if (finalCurveStart && finalCurveEnd
4804                        && *finalCurveStart != *finalCurveEnd) {
4805                    *fReducePts.append() = *finalCurveStart;
4806                    *fReducePts.append() = *finalCurveEnd;
4807                    *fExtra.append() =
4808                            fCurrentContour->addLine(fReducePts.end() - 2);
4809                }
4810                complete();
4811                goto nextVerb;
4812            default:
4813                SkDEBUGFAIL("bad verb");
4814                return;
4815        }
4816        finalCurveStart = &pointsPtr[verb - 1];
4817        pointsPtr += verb;
4818        SkASSERT(fCurrentContour);
4819    nextVerb:
4820        if (verbPtr == endOfFirstHalf) {
4821            fOperand = true;
4822        }
4823    }
4824}
4825
4826private:
4827    const SkPath* fPath;
4828    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
4829    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
4830    Contour* fCurrentContour;
4831    SkTArray<Contour>& fContours;
4832    SkTDArray<SkPoint> fReducePts; // segments created on the fly
4833    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
4834    ShapeOpMask fXorMask[2];
4835    int fSecondHalf;
4836    bool fOperand;
4837};
4838
4839class Work {
4840public:
4841    enum SegmentType {
4842        kHorizontalLine_Segment = -1,
4843        kVerticalLine_Segment = 0,
4844        kLine_Segment = SkPath::kLine_Verb,
4845        kQuad_Segment = SkPath::kQuad_Verb,
4846        kCubic_Segment = SkPath::kCubic_Verb,
4847    };
4848
4849    void addCoincident(Work& other, const Intersections& ts, bool swap) {
4850        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
4851    }
4852
4853    // FIXME: does it make sense to write otherIndex now if we're going to
4854    // fix it up later?
4855    void addOtherT(int index, double otherT, int otherIndex) {
4856        fContour->addOtherT(fIndex, index, otherT, otherIndex);
4857    }
4858
4859    // Avoid collapsing t values that are close to the same since
4860    // we walk ts to describe consecutive intersections. Since a pair of ts can
4861    // be nearly equal, any problems caused by this should be taken care
4862    // of later.
4863    // On the edge or out of range values are negative; add 2 to get end
4864    int addT(double newT, const Work& other) {
4865        return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
4866    }
4867
4868    int addUnsortableT(double newT, const Work& other, bool start) {
4869        return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start);
4870    }
4871
4872    bool advance() {
4873        return ++fIndex < fLast;
4874    }
4875
4876    SkScalar bottom() const {
4877        return bounds().fBottom;
4878    }
4879
4880    const Bounds& bounds() const {
4881        return fContour->segments()[fIndex].bounds();
4882    }
4883
4884#if !APPROXIMATE_CUBICS
4885    const SkPoint* cubic() const {
4886        return fCubic;
4887    }
4888#endif
4889
4890    void init(Contour* contour) {
4891        fContour = contour;
4892        fIndex = 0;
4893        fLast = contour->segments().count();
4894    }
4895
4896    bool isAdjacent(const Work& next) {
4897        return fContour == next.fContour && fIndex + 1 == next.fIndex;
4898    }
4899
4900    bool isFirstLast(const Work& next) {
4901        return fContour == next.fContour && fIndex == 0
4902                && next.fIndex == fLast - 1;
4903    }
4904
4905    SkScalar left() const {
4906        return bounds().fLeft;
4907    }
4908
4909#if !APPROXIMATE_CUBICS
4910    void promoteToCubic() {
4911        fCubic[0] = pts()[0];
4912        fCubic[2] = pts()[1];
4913        fCubic[3] = pts()[2];
4914        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
4915        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
4916        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
4917        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
4918    }
4919#endif
4920
4921    const SkPoint* pts() const {
4922        return fContour->segments()[fIndex].pts();
4923    }
4924
4925    SkScalar right() const {
4926        return bounds().fRight;
4927    }
4928
4929    ptrdiff_t segmentIndex() const {
4930        return fIndex;
4931    }
4932
4933    SegmentType segmentType() const {
4934        const Segment& segment = fContour->segments()[fIndex];
4935        SegmentType type = (SegmentType) segment.verb();
4936        if (type != kLine_Segment) {
4937            return type;
4938        }
4939        if (segment.isHorizontal()) {
4940            return kHorizontalLine_Segment;
4941        }
4942        if (segment.isVertical()) {
4943            return kVerticalLine_Segment;
4944        }
4945        return kLine_Segment;
4946    }
4947
4948    bool startAfter(const Work& after) {
4949        fIndex = after.fIndex;
4950        return advance();
4951    }
4952
4953    SkScalar top() const {
4954        return bounds().fTop;
4955    }
4956
4957    SkPath::Verb verb() const {
4958        return fContour->segments()[fIndex].verb();
4959    }
4960
4961    SkScalar x() const {
4962        return bounds().fLeft;
4963    }
4964
4965    bool xFlipped() const {
4966        return x() != pts()[0].fX;
4967    }
4968
4969    SkScalar y() const {
4970        return bounds().fTop;
4971    }
4972
4973    bool yFlipped() const {
4974        return y() != pts()[0].fY;
4975    }
4976
4977protected:
4978    Contour* fContour;
4979#if !APPROXIMATE_CUBICS
4980    SkPoint fCubic[4];
4981#endif
4982    int fIndex;
4983    int fLast;
4984};
4985
4986#if DEBUG_ADD_INTERSECTING_TS
4987static void debugShowLineIntersection(int pts, const Work& wt,
4988        const Work& wn, const double wtTs[2], const double wnTs[2]) {
4989    return;
4990    if (!pts) {
4991        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
4992                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
4993                wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY,
4994                wn.pts()[1].fX, wn.pts()[1].fY);
4995        return;
4996    }
4997    SkPoint wtOutPt, wnOutPt;
4998    LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
4999    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
5000    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
5001            __FUNCTION__,
5002            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
5003            wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
5004    if (pts == 2) {
5005        SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
5006    }
5007    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
5008            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
5009            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
5010    if (pts == 2) {
5011        SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
5012    }
5013    SkDebugf("\n");
5014}
5015
5016static void debugShowQuadLineIntersection(int pts, const Work& wt,
5017        const Work& wn, const double wtTs[2], const double wnTs[2]) {
5018    if (!pts) {
5019        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
5020                " (%1.9g,%1.9g %1.9g,%1.9g)\n",
5021                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
5022                wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
5023                wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY);
5024        return;
5025    }
5026    SkPoint wtOutPt, wnOutPt;
5027    QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
5028    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
5029    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
5030            __FUNCTION__,
5031            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
5032            wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
5033            wtOutPt.fX, wtOutPt.fY);
5034    if (pts == 2) {
5035        QuadXYAtT(wt.pts(), wtTs[1], &wtOutPt);
5036        SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY);
5037    }
5038    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
5039            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
5040            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
5041    if (pts == 2) {
5042        LineXYAtT(wn.pts(), wnTs[1], &wnOutPt);
5043        SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY);
5044    }
5045    SkDebugf("\n");
5046}
5047
5048// FIXME: show more than two intersection points
5049static void debugShowQuadIntersection(int pts, const Work& wt,
5050        const Work& wn, const double wtTs[2], const double wnTs[2]) {
5051    if (!pts) {
5052        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
5053                " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
5054                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
5055                wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
5056                wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
5057                wn.pts()[2].fX, wn.pts()[2].fY );
5058        return;
5059    }
5060    SkPoint wtOutPt, wnOutPt;
5061    QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
5062    QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt);
5063    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
5064            __FUNCTION__,
5065