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        if (firstT < 0) {
2911            unsortable = true;
2912            firstT = 0;
2913            while (fTs[firstT].fDone) {
2914                SkASSERT(firstT < fTs.count());
2915                ++firstT;
2916            }
2917            tIndex = firstT;
2918            endIndex = nextExactSpan(firstT, 1);
2919            return this;
2920        }
2921        // sort the edges to find the leftmost
2922        int step = 1;
2923        int end = nextSpan(firstT, step);
2924        if (end == -1) {
2925            step = -1;
2926            end = nextSpan(firstT, step);
2927            SkASSERT(end != -1);
2928        }
2929        // if the topmost T is not on end, or is three-way or more, find left
2930        // look for left-ness from tLeft to firstT (matching y of other)
2931        SkTDArray<Angle> angles;
2932        SkASSERT(firstT - end != 0);
2933        addTwoAngles(end, firstT, angles);
2934        buildAngles(firstT, angles, true);
2935        SkTDArray<Angle*> sorted;
2936        bool sortable = SortAngles(angles, sorted);
2937        int first = SK_MaxS32;
2938        SkScalar top = SK_ScalarMax;
2939        int count = sorted.count();
2940        for (int index = 0; index < count; ++index) {
2941            const Angle* angle = sorted[index];
2942            Segment* next = angle->segment();
2943            Bounds bounds;
2944            next->subDivideBounds(angle->end(), angle->start(), bounds);
2945            if (approximately_greater(top, bounds.fTop)) {
2946                top = bounds.fTop;
2947                first = index;
2948            }
2949        }
2950        SkASSERT(first < SK_MaxS32);
2951    #if DEBUG_SORT // || DEBUG_SWAP_TOP
2952        sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0);
2953    #endif
2954        if (onlySortable && !sortable) {
2955            unsortable = true;
2956            return NULL;
2957        }
2958        // skip edges that have already been processed
2959        firstT = first - 1;
2960        Segment* leftSegment;
2961        do {
2962            if (++firstT == count) {
2963                firstT = 0;
2964            }
2965            const Angle* angle = sorted[firstT];
2966            SkASSERT(!onlySortable || !angle->unsortable());
2967            leftSegment = angle->segment();
2968            tIndex = angle->end();
2969            endIndex = angle->start();
2970        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
2971        if (leftSegment->verb() >= SkPath::kQuad_Verb) {
2972            if (!leftSegment->clockwise(tIndex, endIndex)) {
2973                bool swap = leftSegment->verb() == SkPath::kQuad_Verb
2974                        || (!leftSegment->monotonic_in_y(tIndex, endIndex)
2975                        && !leftSegment->serpentine(tIndex, endIndex));
2976        #if DEBUG_SWAP_TOP
2977                SkDebugf("%s swap=%d serpentine=%d controls_contained_by_ends=%d\n", __FUNCTION__,
2978                        swap,
2979                        leftSegment->serpentine(tIndex, endIndex),
2980                        leftSegment->controls_contained_by_ends(tIndex, endIndex),
2981                        leftSegment->monotonic_in_y(tIndex, endIndex));
2982        #endif
2983                if (swap) {
2984        // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
2985        // sorted but merely the first not already processed (i.e., not done)
2986                    SkTSwap(tIndex, endIndex);
2987                }
2988            }
2989        }
2990        SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
2991        return leftSegment;
2992    }
2993
2994    // FIXME: not crazy about this
2995    // when the intersections are performed, the other index is into an
2996    // incomplete array. As the array grows, the indices become incorrect
2997    // while the following fixes the indices up again, it isn't smart about
2998    // skipping segments whose indices are already correct
2999    // assuming we leave the code that wrote the index in the first place
3000    void fixOtherTIndex() {
3001        int iCount = fTs.count();
3002        for (int i = 0; i < iCount; ++i) {
3003            Span& iSpan = fTs[i];
3004            double oT = iSpan.fOtherT;
3005            Segment* other = iSpan.fOther;
3006            int oCount = other->fTs.count();
3007            for (int o = 0; o < oCount; ++o) {
3008                Span& oSpan = other->fTs[o];
3009                if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
3010                    iSpan.fOtherIndex = o;
3011                    break;
3012                }
3013            }
3014        }
3015    }
3016
3017    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
3018        fDoneSpans = 0;
3019        fOperand = operand;
3020        fXor = evenOdd;
3021        fPts = pts;
3022        fVerb = verb;
3023    }
3024
3025    void initWinding(int start, int end) {
3026        int local = spanSign(start, end);
3027        int oppLocal = oppSign(start, end);
3028        (void) markAndChaseWinding(start, end, local, oppLocal);
3029        // OPTIMIZATION: the reverse mark and chase could skip the first marking
3030        (void) markAndChaseWinding(end, start, local, oppLocal);
3031    }
3032
3033    void initWinding(int start, int end, int winding, int oppWinding) {
3034        int local = spanSign(start, end);
3035        if (local * winding >= 0) {
3036            winding += local;
3037        }
3038        int oppLocal = oppSign(start, end);
3039        if (oppLocal * oppWinding >= 0) {
3040            oppWinding += oppLocal;
3041        }
3042        (void) markAndChaseWinding(start, end, winding, oppWinding);
3043    }
3044
3045/*
3046when we start with a vertical intersect, we try to use the dx to determine if the edge is to
3047the left or the right of vertical. This determines if we need to add the span's
3048sign or not. However, this isn't enough.
3049If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
3050If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
3051from has the same x direction as this span, the winding should change. If the dx is opposite, then
3052the same winding is shared by both.
3053*/
3054    void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
3055            SkScalar hitOppDx) {
3056        SkASSERT(hitDx || !winding);
3057        SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, tHit);
3058        SkASSERT(dx);
3059        int windVal = windValue(SkMin32(start, end));
3060    #if DEBUG_WINDING_AT_T
3061        SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
3062                hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3063    #endif
3064        if (!winding) {
3065            winding = dx < 0 ? windVal : -windVal;
3066        } else if (winding * dx < 0) {
3067            int sideWind = winding + (dx < 0 ? windVal : -windVal);
3068            if (abs(winding) < abs(sideWind)) {
3069                winding = sideWind;
3070            }
3071        }
3072    #if DEBUG_WINDING_AT_T
3073        SkDebugf(" winding=%d\n", winding);
3074    #endif
3075        int oppLocal = oppSign(start, end);
3076        SkASSERT(hitOppDx || !oppWind || !oppLocal);
3077        int oppWindVal = oppValue(SkMin32(start, end));
3078        if (!oppWind) {
3079            oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3080        } else if (hitOppDx * dx >= 0) {
3081            int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3082            if (abs(oppWind) < abs(oppSideWind)) {
3083                oppWind = oppSideWind;
3084            }
3085        }
3086        (void) markAndChaseWinding(start, end, winding, oppWind);
3087    }
3088
3089    bool intersected() const {
3090        return fTs.count() > 0;
3091    }
3092
3093    bool isCanceled(int tIndex) const {
3094        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
3095    }
3096
3097    bool isConnected(int startIndex, int endIndex) const {
3098        return fTs[startIndex].fWindSum != SK_MinS32
3099                || fTs[endIndex].fWindSum != SK_MinS32;
3100    }
3101
3102    bool isHorizontal() const {
3103        return fBounds.fTop == fBounds.fBottom;
3104    }
3105
3106    bool isLinear(int start, int end) const {
3107        if (fVerb == SkPath::kLine_Verb) {
3108            return true;
3109        }
3110        if (fVerb == SkPath::kQuad_Verb) {
3111            SkPoint qPart[3];
3112            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
3113            return QuadIsLinear(qPart);
3114        } else {
3115            SkASSERT(fVerb == SkPath::kCubic_Verb);
3116            SkPoint cPart[4];
3117            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
3118            return CubicIsLinear(cPart);
3119        }
3120    }
3121
3122    // OPTIMIZE: successive calls could start were the last leaves off
3123    // or calls could specialize to walk forwards or backwards
3124    bool isMissing(double startT) const {
3125        size_t tCount = fTs.count();
3126        for (size_t index = 0; index < tCount; ++index) {
3127            if (approximately_zero(startT - fTs[index].fT)) {
3128                return false;
3129            }
3130        }
3131        return true;
3132    }
3133
3134    bool isSimple(int end) const {
3135        int count = fTs.count();
3136        if (count == 2) {
3137            return true;
3138        }
3139        double t = fTs[end].fT;
3140        if (approximately_less_than_zero(t)) {
3141            return !approximately_less_than_zero(fTs[1].fT);
3142        }
3143        if (approximately_greater_than_one(t)) {
3144            return !approximately_greater_than_one(fTs[count - 2].fT);
3145        }
3146        return false;
3147    }
3148
3149    bool isVertical() const {
3150        return fBounds.fLeft == fBounds.fRight;
3151    }
3152
3153    bool isVertical(int start, int end) const {
3154        return (*SegmentVertical[fVerb])(fPts, start, end);
3155    }
3156
3157    SkScalar leftMost(int start, int end) const {
3158        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
3159    }
3160
3161    // this span is excluded by the winding rule -- chase the ends
3162    // as long as they are unambiguous to mark connections as done
3163    // and give them the same winding value
3164    Span* markAndChaseDone(const Angle* angle, int winding) {
3165        int index = angle->start();
3166        int endIndex = angle->end();
3167        return markAndChaseDone(index, endIndex, winding);
3168    }
3169
3170    Span* markAndChaseDone(int index, int endIndex, int winding) {
3171        int step = SkSign32(endIndex - index);
3172        int min = SkMin32(index, endIndex);
3173        markDone(min, winding);
3174        Span* last;
3175        Segment* other = this;
3176        while ((other = other->nextChase(index, step, min, last))) {
3177            other->markDone(min, winding);
3178        }
3179        return last;
3180    }
3181
3182    Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding) {
3183        int index = angle->start();
3184        int endIndex = angle->end();
3185        int step = SkSign32(endIndex - index);
3186        int min = SkMin32(index, endIndex);
3187        markDoneBinary(min, winding, oppWinding);
3188        Span* last;
3189        Segment* other = this;
3190        while ((other = other->nextChase(index, step, min, last))) {
3191            other->markDoneBinary(min, winding, oppWinding);
3192        }
3193        return last;
3194    }
3195
3196    Span* markAndChaseDoneBinary(int index, int endIndex) {
3197        int step = SkSign32(endIndex - index);
3198        int min = SkMin32(index, endIndex);
3199        markDoneBinary(min);
3200        Span* last;
3201        Segment* other = this;
3202        while ((other = other->nextChase(index, step, min, last))) {
3203            if (other->done()) {
3204                return NULL;
3205            }
3206            other->markDoneBinary(min);
3207        }
3208        return last;
3209    }
3210
3211    Span* markAndChaseDoneUnary(int index, int endIndex) {
3212        int step = SkSign32(endIndex - index);
3213        int min = SkMin32(index, endIndex);
3214        markDoneUnary(min);
3215        Span* last;
3216        Segment* other = this;
3217        while ((other = other->nextChase(index, step, min, last))) {
3218            if (other->done()) {
3219                return NULL;
3220            }
3221            other->markDoneUnary(min);
3222        }
3223        return last;
3224    }
3225
3226    Span* markAndChaseDoneUnary(const Angle* angle, int winding) {
3227        int index = angle->start();
3228        int endIndex = angle->end();
3229        return markAndChaseDone(index, endIndex, winding);
3230    }
3231
3232    Span* markAndChaseWinding(const Angle* angle, const int winding) {
3233        int index = angle->start();
3234        int endIndex = angle->end();
3235        int step = SkSign32(endIndex - index);
3236        int min = SkMin32(index, endIndex);
3237        markWinding(min, winding);
3238        Span* last;
3239        Segment* other = this;
3240        while ((other = other->nextChase(index, step, min, last))) {
3241            if (other->fTs[min].fWindSum != SK_MinS32) {
3242                SkASSERT(other->fTs[min].fWindSum == winding);
3243                return NULL;
3244            }
3245            other->markWinding(min, winding);
3246        }
3247        return last;
3248    }
3249
3250    Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3251        int min = SkMin32(index, endIndex);
3252        int step = SkSign32(endIndex - index);
3253        markWinding(min, winding, oppWinding);
3254        Span* last;
3255        Segment* other = this;
3256        while ((other = other->nextChase(index, step, min, last))) {
3257            if (other->fTs[min].fWindSum != SK_MinS32) {
3258                SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
3259                return NULL;
3260            }
3261            other->markWinding(min, winding, oppWinding);
3262        }
3263        return last;
3264    }
3265
3266    Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) {
3267        int start = angle->start();
3268        int end = angle->end();
3269        return markAndChaseWinding(start, end, winding, oppWinding);
3270    }
3271
3272    Span* markAngle(int maxWinding, int sumWinding, bool activeAngle, const Angle* angle) {
3273        SkASSERT(angle->segment() == this);
3274        if (useInnerWinding(maxWinding, sumWinding)) {
3275            maxWinding = sumWinding;
3276        }
3277        Span* last;
3278        if (activeAngle) {
3279            last = markAndChaseWinding(angle, maxWinding);
3280        } else {
3281            last = markAndChaseDoneUnary(angle, maxWinding);
3282        }
3283        return last;
3284    }
3285
3286    Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
3287            bool activeAngle, const Angle* angle) {
3288        SkASSERT(angle->segment() == this);
3289        if (useInnerWinding(maxWinding, sumWinding)) {
3290            maxWinding = sumWinding;
3291        }
3292        if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, oppSumWinding)) {
3293            oppMaxWinding = oppSumWinding;
3294        }
3295        Span* last;
3296        if (activeAngle) {
3297            last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3298        } else {
3299            last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
3300        }
3301        return last;
3302    }
3303
3304    // FIXME: this should also mark spans with equal (x,y)
3305    // This may be called when the segment is already marked done. While this
3306    // wastes time, it shouldn't do any more than spin through the T spans.
3307    // OPTIMIZATION: abort on first done found (assuming that this code is
3308    // always called to mark segments done).
3309    void markDone(int index, int winding) {
3310      //  SkASSERT(!done());
3311        SkASSERT(winding);
3312        double referenceT = fTs[index].fT;
3313        int lesser = index;
3314        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3315            markOneDone(__FUNCTION__, lesser, winding);
3316        }
3317        do {
3318            markOneDone(__FUNCTION__, index, winding);
3319        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3320    }
3321
3322    void markDoneBinary(int index, int winding, int oppWinding) {
3323      //  SkASSERT(!done());
3324        SkASSERT(winding || oppWinding);
3325        double referenceT = fTs[index].fT;
3326        int lesser = index;
3327        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3328            markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);
3329        }
3330        do {
3331            markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);
3332        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3333    }
3334
3335    void markDoneBinary(int index) {
3336        double referenceT = fTs[index].fT;
3337        int lesser = index;
3338        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3339            markOneDoneBinary(__FUNCTION__, lesser);
3340        }
3341        do {
3342            markOneDoneBinary(__FUNCTION__, index);
3343        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3344    }
3345
3346    void markDoneUnary(int index, int winding) {
3347      //  SkASSERT(!done());
3348        SkASSERT(winding);
3349        double referenceT = fTs[index].fT;
3350        int lesser = index;
3351        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3352            markOneDoneUnary(__FUNCTION__, lesser, winding);
3353        }
3354        do {
3355            markOneDoneUnary(__FUNCTION__, index, winding);
3356        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3357    }
3358
3359    void markDoneUnary(int index) {
3360        double referenceT = fTs[index].fT;
3361        int lesser = index;
3362        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3363            markOneDoneUnary(__FUNCTION__, lesser);
3364        }
3365        do {
3366            markOneDoneUnary(__FUNCTION__, index);
3367        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3368    }
3369
3370    void markOneDone(const char* funName, int tIndex, int winding) {
3371        Span* span = markOneWinding(funName, tIndex, winding);
3372        if (!span) {
3373            return;
3374        }
3375        span->fDone = true;
3376        fDoneSpans++;
3377    }
3378
3379    void markOneDoneBinary(const char* funName, int tIndex) {
3380        Span* span = verifyOneWinding(funName, tIndex);
3381        if (!span) {
3382            return;
3383        }
3384        span->fDone = true;
3385        fDoneSpans++;
3386    }
3387
3388    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) {
3389        Span* span = markOneWinding(funName, tIndex, winding, oppWinding);
3390        if (!span) {
3391            return;
3392        }
3393        span->fDone = true;
3394        fDoneSpans++;
3395    }
3396
3397    void markOneDoneUnary(const char* funName, int tIndex) {
3398        Span* span = verifyOneWindingU(funName, tIndex);
3399        if (!span) {
3400            return;
3401        }
3402        span->fDone = true;
3403        fDoneSpans++;
3404    }
3405