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