Simplify.cpp revision 64334352cc3f29f52dfa07225d65eb218d2fd830 
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 1
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
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 //               SkDebugf("*** %s quad is line\n", __FUNCTION__);
885                fTangent1.quadEndPoints(quad);
886            }
887            fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
888            } break;
889        case SkPath::kCubic_Verb: {
890            int nextC = 2;
891            CubicSubDivideHD(fPts, startT, endT, fCurvePart);
892            fTangent1.cubicEndPoints(fCurvePart, 0, 1);
893            if (dx() == 0 && dy() == 0) {
894                fTangent1.cubicEndPoints(fCurvePart, 0, 2);
895                nextC = 3;
896                if (dx() == 0 && dy() == 0) {
897 //                   SkDebugf("*** %s cubic is line\n", __FUNCTION__);
898                    fTangent1.cubicEndPoints(fCurvePart, 0, 3);
899                }
900            }
901            fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only
902            if (nextC == 2 && approximately_zero(fSide)) {
903                fSide = -fTangent1.pointDistance(fCurvePart[3]);
904            }
905            } break;
906        default:
907            SkASSERT(0);
908        }
909        fUnsortable = dx() == 0 && dy() == 0;
910        if (fUnsortable) {
911            return;
912        }
913        SkASSERT(fStart != fEnd);
914        int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
915        for (int index = fStart; index != fEnd; index += step) {
916#if 1
917            const Span& thisSpan = (*fSpans)[index];
918            const Span& nextSpan = (*fSpans)[index + step];
919            if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
920                continue;
921            }
922            fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
923#if DEBUG_UNSORTABLE
924            if (fUnsortable) {
925                SkPoint iPt, ePt;
926                (*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt);
927                (*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt);
928                SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
929                        index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
930            }
931#endif
932            return;
933#else
934            if ((*fSpans)[index].fUnsortableStart) {
935                fUnsortable = true;
936                return;
937            }
938#endif
939        }
940#if 1
941#if DEBUG_UNSORTABLE
942        SkPoint iPt, ePt;
943        (*SegmentXYAtT[fVerb])(fPts, startT, &iPt);
944        (*SegmentXYAtT[fVerb])(fPts, endT, &ePt);
945        SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
946            fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
947#endif
948        fUnsortable = true;
949#endif
950    }
951
952    Segment* segment() const {
953        return const_cast<Segment*>(fSegment);
954    }
955
956    int sign() const {
957        return SkSign32(fStart - fEnd);
958    }
959
960    const SkTDArray<Span>* spans() const {
961        return fSpans;
962    }
963
964    int start() const {
965        return fStart;
966    }
967
968    bool unsortable() const {
969        return fUnsortable;
970    }
971
972#if DEBUG_ANGLE
973    const SkPoint* pts() const {
974        return fPts;
975    }
976
977    SkPath::Verb verb() const {
978        return fVerb;
979    }
980
981    void debugShow(const SkPoint& a) const {
982        SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
983    }
984#endif
985
986private:
987    const SkPoint* fPts;
988    Cubic fCurvePart;
989    SkPath::Verb fVerb;
990    double fSide;
991    LineParameters fTangent1;
992    const SkTDArray<Span>* fSpans;
993    const Segment* fSegment;
994    int fStart;
995    int fEnd;
996    bool fReversed;
997    mutable bool fUnsortable; // this alone is editable by the less than operator
998};
999
1000// Bounds, unlike Rect, does not consider a line to be empty.
1001struct Bounds : public SkRect {
1002    static bool Intersects(const Bounds& a, const Bounds& b) {
1003        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
1004                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
1005    }
1006
1007    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
1008        if (left < fLeft) {
1009            fLeft = left;
1010        }
1011        if (top < fTop) {
1012            fTop = top;
1013        }
1014        if (right > fRight) {
1015            fRight = right;
1016        }
1017        if (bottom > fBottom) {
1018            fBottom = bottom;
1019        }
1020    }
1021
1022    void add(const Bounds& toAdd) {
1023        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
1024    }
1025
1026    void add(const SkPoint& pt) {
1027        if (pt.fX < fLeft) fLeft = pt.fX;
1028        if (pt.fY < fTop) fTop = pt.fY;
1029        if (pt.fX > fRight) fRight = pt.fX;
1030        if (pt.fY > fBottom) fBottom = pt.fY;
1031    }
1032
1033    bool isEmpty() {
1034        return fLeft > fRight || fTop > fBottom
1035                || (fLeft == fRight && fTop == fBottom)
1036                || sk_double_isnan(fLeft) || sk_double_isnan(fRight)
1037                || sk_double_isnan(fTop) || sk_double_isnan(fBottom);
1038    }
1039
1040    void setCubicBounds(const SkPoint a[4]) {
1041        _Rect dRect;
1042        MAKE_CONST_CUBIC(cubic, a);
1043        dRect.setBounds(cubic);
1044        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
1045                (float) dRect.bottom);
1046    }
1047
1048    void setQuadBounds(const SkPoint a[3]) {
1049        MAKE_CONST_QUAD(quad, a);
1050        _Rect dRect;
1051        dRect.setBounds(quad);
1052        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
1053                (float) dRect.bottom);
1054    }
1055
1056    void setPoint(const SkPoint& pt) {
1057        fLeft = fRight = pt.fX;
1058        fTop = fBottom = pt.fY;
1059    }
1060};
1061
1062// OPTIMIZATION: does the following also work, and is it any faster?
1063// return outerWinding * innerWinding > 0
1064//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
1065static bool useInnerWinding(int outerWinding, int innerWinding) {
1066    SkASSERT(outerWinding != SK_MaxS32);
1067    SkASSERT(innerWinding != SK_MaxS32);
1068    int absOut = abs(outerWinding);
1069    int absIn = abs(innerWinding);
1070    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
1071#if 0 && DEBUG_WINDING
1072    if (outerWinding * innerWinding < 0) {
1073        SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
1074                outerWinding, innerWinding, result ? "true" : "false");
1075    }
1076#endif
1077    return result;
1078}
1079
1080#define F (false)      // discard the edge
1081#define T (true)       // keep the edge
1082
1083static const bool gUnaryActiveEdge[2][2] = {
1084//  from=0  from=1
1085//  to=0,1  to=0,1
1086    {F, T}, {T, F},
1087};
1088
1089static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {
1090//                 miFrom=0                              miFrom=1
1091//         miTo=0            miTo=1              miTo=0             miTo=1
1092//    suFrom=0    1     suFrom=0     1      suFrom=0    1      suFrom=0    1
1093//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
1094    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
1095    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
1096    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
1097    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
1098};
1099
1100#undef F
1101#undef T
1102
1103// wrap path to keep track of whether the contour is initialized and non-empty
1104class PathWrapper {
1105public:
1106    PathWrapper(SkPath& path)
1107        : fPathPtr(&path)
1108        , fCloses(0)
1109        , fMoves(0)
1110    {
1111        init();
1112    }
1113
1114    void close() {
1115        if (!fHasMove) {
1116            return;
1117        }
1118        bool callClose = isClosed();
1119        lineTo();
1120        if (fEmpty) {
1121            return;
1122        }
1123        if (callClose) {
1124    #if DEBUG_PATH_CONSTRUCTION
1125            SkDebugf("path.close();\n");
1126    #endif
1127            fPathPtr->close();
1128            fCloses++;
1129        }
1130        init();
1131    }
1132
1133    void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
1134        lineTo();
1135        moveTo();
1136        fDefer[1] = pt3;
1137        nudge();
1138        fDefer[0] = fDefer[1];
1139#if DEBUG_PATH_CONSTRUCTION
1140        SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
1141                pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1142#endif
1143        fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1144        fEmpty = false;
1145    }
1146
1147    void deferredLine(const SkPoint& pt) {
1148        if (pt == fDefer[1]) {
1149            return;
1150        }
1151        if (changedSlopes(pt)) {
1152            lineTo();
1153            fDefer[0] = fDefer[1];
1154        }
1155        fDefer[1] = pt;
1156    }
1157
1158    void deferredMove(const SkPoint& pt) {
1159        fMoved = true;
1160        fHasMove = true;
1161        fEmpty = true;
1162        fDefer[0] = fDefer[1] = pt;
1163    }
1164
1165    void deferredMoveLine(const SkPoint& pt) {
1166        if (!fHasMove) {
1167            deferredMove(pt);
1168        }
1169        deferredLine(pt);
1170    }
1171
1172    bool hasMove() const {
1173        return fHasMove;
1174    }
1175
1176    void init() {
1177        fEmpty = true;
1178        fHasMove = false;
1179        fMoved = false;
1180    }
1181
1182    bool isClosed() const {
1183        return !fEmpty && fFirstPt == fDefer[1];
1184    }
1185
1186    void lineTo() {
1187        if (fDefer[0] == fDefer[1]) {
1188            return;
1189        }
1190        moveTo();
1191        nudge();
1192        fEmpty = false;
1193#if DEBUG_PATH_CONSTRUCTION
1194        SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
1195#endif
1196        fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);
1197        fDefer[0] = fDefer[1];
1198    }
1199
1200    const SkPath* nativePath() const {
1201        return fPathPtr;
1202    }
1203
1204    void nudge() {
1205        if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)
1206                || !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {
1207            return;
1208        }
1209        fDefer[1] = fFirstPt;
1210    }
1211
1212    void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
1213        lineTo();
1214        moveTo();
1215        fDefer[1] = pt2;
1216        nudge();
1217        fDefer[0] = fDefer[1];
1218#if DEBUG_PATH_CONSTRUCTION
1219        SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
1220                pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1221#endif
1222        fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1223        fEmpty = false;
1224    }
1225
1226    bool someAssemblyRequired() const {
1227        return fCloses < fMoves;
1228    }
1229
1230protected:
1231    bool changedSlopes(const SkPoint& pt) const {
1232        if (fDefer[0] == fDefer[1]) {
1233            return false;
1234        }
1235        SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;
1236        SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;
1237        SkScalar lineDx = pt.fX - fDefer[1].fX;
1238        SkScalar lineDy = pt.fY - fDefer[1].fY;
1239        return deferDx * lineDy != deferDy * lineDx;
1240    }
1241
1242    void moveTo() {
1243        if (!fMoved) {
1244            return;
1245        }
1246        fFirstPt = fDefer[0];
1247#if DEBUG_PATH_CONSTRUCTION
1248        SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);
1249#endif
1250        fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);
1251        fMoved = false;
1252        fMoves++;
1253    }
1254
1255private:
1256    SkPath* fPathPtr;
1257    SkPoint fDefer[2];
1258    SkPoint fFirstPt;
1259    int fCloses;
1260    int fMoves;
1261    bool fEmpty;
1262    bool fHasMove;
1263    bool fMoved;
1264};
1265
1266class Segment {
1267public:
1268    Segment() {
1269#if DEBUG_DUMP
1270        fID = ++gSegmentID;
1271#endif
1272    }
1273
1274    bool operator<(const Segment& rh) const {
1275        return fBounds.fTop < rh.fBounds.fTop;
1276    }
1277
1278    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
1279        if (activeAngleInner(index, done, angles)) {
1280            return true;
1281        }
1282        int lesser = index;
1283        while (--lesser >= 0 && equalPoints(index, lesser)) {
1284            if (activeAngleOther(lesser, done, angles)) {
1285                return true;
1286            }
1287        }
1288        lesser = index;
1289        do {
1290            if (activeAngleOther(index, done, angles)) {
1291                return true;
1292            }
1293        } while (++index < fTs.count() && equalPoints(index, lesser));
1294        return false;
1295    }
1296
1297    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
1298        Span* span = &fTs[index];
1299        Segment* other = span->fOther;
1300        int oIndex = span->fOtherIndex;
1301        return other->activeAngleInner(oIndex, done, angles);
1302    }
1303
1304    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
1305        int next = nextExactSpan(index, 1);
1306        if (next > 0) {
1307            Span& upSpan = fTs[index];
1308            if (upSpan.fWindValue || upSpan.fOppValue) {
1309                addAngle(angles, index, next);
1310                if (upSpan.fDone || upSpan.fUnsortableEnd) {
1311                    done++;
1312                } else if (upSpan.fWindSum != SK_MinS32) {
1313                    return true;
1314                }
1315            } else if (!upSpan.fDone) {
1316                upSpan.fDone = true;
1317                fDoneSpans++;
1318            }
1319        }
1320        int prev = nextExactSpan(index, -1);
1321        // edge leading into junction
1322        if (prev >= 0) {
1323            Span& downSpan = fTs[prev];
1324            if (downSpan.fWindValue || downSpan.fOppValue) {
1325                addAngle(angles, index, prev);
1326                if (downSpan.fDone) {
1327                    done++;
1328                 } else if (downSpan.fWindSum != SK_MinS32) {
1329                    return true;
1330                }
1331            } else if (!downSpan.fDone) {
1332                downSpan.fDone = true;
1333                fDoneSpans++;
1334            }
1335        }
1336        return false;
1337    }
1338
1339    SkPoint activeLeftTop(bool onlySortable, int* firstT) const {
1340        SkASSERT(!done());
1341        SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
1342        int count = fTs.count();
1343        // see if either end is not done since we want smaller Y of the pair
1344        bool lastDone = true;
1345        bool lastUnsortable = false;
1346        double lastT = -1;
1347        for (int index = 0; index < count; ++index) {
1348            const Span& span = fTs[index];
1349            if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
1350                goto next;
1351            }
1352            if (span.fDone && lastDone) {
1353                goto next;
1354            }
1355            if (approximately_negative(span.fT - lastT)) {
1356                goto next;
1357            }
1358            {
1359                const SkPoint& xy = xyAtT(&span);
1360                if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
1361                    topPt = xy;
1362                    if (firstT) {
1363                        *firstT = index;
1364                    }
1365                }
1366                if (fVerb != SkPath::kLine_Verb && !lastDone) {
1367                    SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT);
1368                    if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
1369                            && topPt.fX > curveTop.fX)) {
1370                        topPt = curveTop;
1371                        if (firstT) {
1372                            *firstT = index;
1373                        }
1374                    }
1375                }
1376                lastT = span.fT;
1377            }
1378    next:
1379            lastDone = span.fDone;
1380            lastUnsortable = span.fUnsortableEnd;
1381        }
1382        return topPt;
1383    }
1384
1385    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
1386        int sumMiWinding = updateWinding(endIndex, index);
1387        int sumSuWinding = updateOppWinding(endIndex, index);
1388        if (fOperand) {
1389            SkTSwap<int>(sumMiWinding, sumSuWinding);
1390        }
1391        int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1392        return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,
1393                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1394    }
1395
1396    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,
1397            int& sumMiWinding, int& sumSuWinding,
1398            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
1399        setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
1400                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
1401        bool miFrom;
1402        bool miTo;
1403        bool suFrom;
1404        bool suTo;
1405        if (operand()) {
1406            miFrom = (oppMaxWinding & xorMiMask) != 0;
1407            miTo = (oppSumWinding & xorMiMask) != 0;
1408            suFrom = (maxWinding & xorSuMask) != 0;
1409            suTo = (sumWinding & xorSuMask) != 0;
1410        } else {
1411            miFrom = (maxWinding & xorMiMask) != 0;
1412            miTo = (sumWinding & xorMiMask) != 0;
1413            suFrom = (oppMaxWinding & xorSuMask) != 0;
1414            suTo = (oppSumWinding & xorSuMask) != 0;
1415        }
1416        bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
1417#if DEBUG_ACTIVE_OP
1418        SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
1419                kShapeOpStr[op], miFrom, miTo, suFrom, suTo, result);
1420#endif
1421        SkASSERT(result != -1);
1422        return result;
1423    }
1424
1425    bool activeWinding(int index, int endIndex) {
1426        int sumWinding = updateWinding(endIndex, index);
1427        int maxWinding;
1428        return activeWinding(index, endIndex, maxWinding, sumWinding);
1429    }
1430
1431    bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
1432        setUpWinding(index, endIndex, maxWinding, sumWinding);
1433        bool from = maxWinding != 0;
1434        bool to = sumWinding  != 0;
1435        bool result = gUnaryActiveEdge[from][to];
1436        SkASSERT(result != -1);
1437        return result;
1438    }
1439
1440    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
1441        SkASSERT(start != end);
1442        Angle* angle = angles.append();
1443#if DEBUG_ANGLE
1444        if (angles.count() > 1 && !fTs[start].fTiny) {
1445            SkPoint angle0Pt, newPt;
1446            (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
1447                    (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
1448            (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
1449            SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX));
1450            SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY));
1451        }
1452#endif
1453        angle->set(fPts, fVerb, this, start, end, fTs);
1454    }
1455
1456    void addCancelOutsides(double tStart, double oStart, Segment& other,
1457            double oEnd) {
1458        int tIndex = -1;
1459        int tCount = fTs.count();
1460        int oIndex = -1;
1461        int oCount = other.fTs.count();
1462        do {
1463            ++tIndex;
1464        } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
1465        int tIndexStart = tIndex;
1466        do {
1467            ++oIndex;
1468        } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
1469        int oIndexStart = oIndex;
1470        double nextT;
1471        do {
1472            nextT = fTs[++tIndex].fT;
1473        } while (nextT < 1 && approximately_negative(nextT - tStart));
1474        double oNextT;
1475        do {
1476            oNextT = other.fTs[++oIndex].fT;
1477        } while (oNextT < 1 && approximately_negative(oNextT - oStart));
1478        // at this point, spans before and after are at:
1479        //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1480        // if tIndexStart == 0, no prior span
1481        // if nextT == 1, no following span
1482
1483        // advance the span with zero winding
1484        // if the following span exists (not past the end, non-zero winding)
1485        // connect the two edges
1486        if (!fTs[tIndexStart].fWindValue) {
1487            if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1488    #if DEBUG_CONCIDENT
1489                SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1490                        __FUNCTION__, fID, other.fID, tIndexStart - 1,
1491                        fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
1492                        xyAtT(tIndexStart).fY);
1493    #endif
1494                addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false,
1495                        fTs[tIndexStart].fPt);
1496            }
1497            if (nextT < 1 && fTs[tIndex].fWindValue) {
1498    #if DEBUG_CONCIDENT
1499                SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1500                        __FUNCTION__, fID, other.fID, tIndex,
1501                        fTs[tIndex].fT, xyAtT(tIndex).fX,
1502                        xyAtT(tIndex).fY);
1503    #endif
1504                addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
1505            }
1506        } else {
1507            SkASSERT(!other.fTs[oIndexStart].fWindValue);
1508            if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
1509    #if DEBUG_CONCIDENT
1510                SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1511                        __FUNCTION__, fID, other.fID, oIndexStart - 1,
1512                        other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
1513                        other.xyAtT(oIndexStart).fY);
1514                other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1515    #endif
1516            }
1517            if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
1518    #if DEBUG_CONCIDENT
1519                SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1520                        __FUNCTION__, fID, other.fID, oIndex,
1521                        other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
1522                        other.xyAtT(oIndex).fY);
1523                other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1524    #endif
1525            }
1526        }
1527    }
1528
1529    void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
1530            double oEnd) {
1531        // walk this to outsideTs[0]
1532        // walk other to outsideTs[1]
1533        // if either is > 0, add a pointer to the other, copying adjacent winding
1534        int tIndex = -1;
1535        int oIndex = -1;
1536        double tStart = outsideTs[0];
1537        double oStart = outsideTs[1];
1538        do {
1539            ++tIndex;
1540        } while (!approximately_negative(tStart - fTs[tIndex].fT));
1541        SkPoint ptStart = fTs[tIndex].fPt;
1542        do {
1543            ++oIndex;
1544        } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
1545        if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
1546            addTPair(tStart, other, oStart, false, ptStart);
1547        }
1548        tStart = fTs[tIndex].fT;
1549        oStart = other.fTs[oIndex].fT;
1550        do {
1551            double nextT;
1552            do {
1553                nextT = fTs[++tIndex].fT;
1554            } while (approximately_negative(nextT - tStart));
1555            tStart = nextT;
1556            ptStart = fTs[tIndex].fPt;
1557            do {
1558                nextT = other.fTs[++oIndex].fT;
1559            } while (approximately_negative(nextT - oStart));
1560            oStart = nextT;
1561            if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
1562                break;
1563            }
1564            addTPair(tStart, other, oStart, false, ptStart);
1565        } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
1566    }
1567
1568    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
1569        init(pts, SkPath::kCubic_Verb, operand, evenOdd);
1570        fBounds.setCubicBounds(pts);
1571    }
1572
1573    /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const {
1574        SkPoint edge[4];
1575        const SkPoint* ePtr;
1576        int lastT = fTs.count() - 1;
1577        if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
1578            ePtr = fPts;
1579        } else {
1580        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
1581            subDivide(start, end, edge);
1582            ePtr = edge;
1583        }
1584        if (active) {
1585            bool reverse = ePtr == fPts && start != 0;
1586            if (reverse) {
1587                path.deferredMoveLine(ePtr[fVerb]);
1588                switch (fVerb) {
1589                    case SkPath::kLine_Verb:
1590                        path.deferredLine(ePtr[0]);
1591                        break;
1592                    case SkPath::kQuad_Verb:
1593                        path.quadTo(ePtr[1], ePtr[0]);
1594                        break;
1595                    case SkPath::kCubic_Verb:
1596                        path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);
1597                        break;
1598                    default:
1599                        SkASSERT(0);
1600                }
1601       //         return ePtr[0];
1602           } else {
1603                path.deferredMoveLine(ePtr[0]);
1604                switch (fVerb) {
1605                    case SkPath::kLine_Verb:
1606                        path.deferredLine(ePtr[1]);
1607                        break;
1608                    case SkPath::kQuad_Verb:
1609                        path.quadTo(ePtr[1], ePtr[2]);
1610                        break;
1611                    case SkPath::kCubic_Verb:
1612                        path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);
1613                        break;
1614                    default:
1615                        SkASSERT(0);
1616                }
1617            }
1618        }
1619      //  return ePtr[fVerb];
1620    }
1621
1622    void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
1623        init(pts, SkPath::kLine_Verb, operand, evenOdd);
1624        fBounds.set(pts, 2);
1625    }
1626
1627#if 0
1628    const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {
1629        const SkPoint& pt = xyAtT(tIndex);
1630        if (active) {
1631            path.deferredMove(pt);
1632        }
1633        return pt;
1634    }
1635#endif
1636
1637    // add 2 to edge or out of range values to get T extremes
1638    void addOtherT(int index, double otherT, int otherIndex) {
1639        Span& span = fTs[index];
1640    #if PIN_ADD_T
1641        if (precisely_less_than_zero(otherT)) {
1642            otherT = 0;
1643        } else if (precisely_greater_than_one(otherT)) {
1644            otherT = 1;
1645        }
1646    #endif
1647        span.fOtherT = otherT;
1648        span.fOtherIndex = otherIndex;
1649    }
1650
1651    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
1652        init(pts, SkPath::kQuad_Verb, operand, evenOdd);
1653        fBounds.setQuadBounds(pts);
1654    }
1655
1656    // Defer all coincident edge processing until
1657    // after normal intersections have been computed
1658
1659// no need to be tricky; insert in normal T order
1660// resolve overlapping ts when considering coincidence later
1661
1662    // add non-coincident intersection. Resulting edges are sorted in T.
1663    int addT(Segment* other, const SkPoint& pt, double& newT) {
1664        // FIXME: in the pathological case where there is a ton of intercepts,
1665        //  binary search?
1666        int insertedAt = -1;
1667        size_t tCount = fTs.count();
1668    #if PIN_ADD_T
1669        // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
1670        if (precisely_less_than_zero(newT)) {
1671            newT = 0;
1672        } else if (precisely_greater_than_one(newT)) {
1673            newT = 1;
1674        }
1675    #endif
1676        for (size_t index = 0; index < tCount; ++index) {
1677            // OPTIMIZATION: if there are three or more identical Ts, then
1678            // the fourth and following could be further insertion-sorted so
1679            // that all the edges are clockwise or counterclockwise.
1680            // This could later limit segment tests to the two adjacent
1681            // neighbors, although it doesn't help with determining which
1682            // circular direction to go in.
1683            if (newT < fTs[index].fT) {
1684                insertedAt = index;
1685                break;
1686            }
1687        }
1688        Span* span;
1689        if (insertedAt >= 0) {
1690            span = fTs.insert(insertedAt);
1691        } else {
1692            insertedAt = tCount;
1693            span = fTs.append();
1694        }
1695        span->fT = newT;
1696        span->fOther = other;
1697        span->fPt = pt;
1698        span->fWindSum = SK_MinS32;
1699        span->fOppSum = SK_MinS32;
1700        span->fWindValue = 1;
1701        span->fOppValue = 0;
1702        span->fTiny = false;
1703        span->fLoop = false;
1704        if ((span->fDone = newT == 1)) {
1705            ++fDoneSpans;
1706        }
1707        span->fUnsortableStart = false;
1708        span->fUnsortableEnd = false;
1709        int less = -1;
1710        while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) {
1711#if 1
1712            if (span[less].fDone) {
1713                break;
1714            }
1715            double tInterval = newT - span[less].fT;
1716            if (precisely_negative(tInterval)) {
1717                break;
1718            }
1719            if (fVerb == SkPath::kCubic_Verb) {
1720                double tMid = newT - tInterval / 2;
1721                _Point midPt;
1722                CubicXYAtT(fPts, tMid, &midPt);
1723                if (!midPt.approximatelyEqual(xyAtT(span))) {
1724                    break;
1725                }
1726            }
1727            span[less].fTiny = true;
1728            span[less].fDone = true;
1729            if (approximately_negative(newT - span[less].fT)) {
1730                if (approximately_greater_than_one(newT)) {
1731                    span[less].fUnsortableStart = true;
1732                    span[less - 1].fUnsortableEnd = true;
1733                }
1734                if (approximately_less_than_zero(span[less].fT)) {
1735                    span[less + 1].fUnsortableStart = true;
1736                    span[less].fUnsortableEnd = true;
1737                }
1738            }
1739            ++fDoneSpans;
1740#else
1741            double tInterval = newT - span[less].fT;
1742            if (precisely_negative(tInterval)) {
1743                break;
1744            }
1745            if (fVerb == SkPath::kCubic_Verb) {
1746                double tMid = newT - tInterval / 2;
1747                _Point midPt;
1748                CubicXYAtT(fPts, tMid, &midPt);
1749                if (!midPt.approximatelyEqual(xyAtT(span))) {
1750                    break;
1751                }
1752            }
1753            SkASSERT(span[less].fDone == span->fDone);
1754            if (span[less].fT == 0) {
1755                span->fT = newT = 0;
1756            } else {
1757                setSpanT(less, newT);
1758            }
1759#endif
1760            --less;
1761        }
1762        int more = 1;
1763        while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) {
1764#if 1
1765            if (span[more - 1].fDone) {
1766                break;
1767            }
1768            double tEndInterval = span[more].fT - newT;
1769            if (precisely_negative(tEndInterval)) {
1770                break;
1771            }
1772            if (fVerb == SkPath::kCubic_Verb) {
1773                double tMid = newT - tEndInterval / 2;
1774                _Point midEndPt;
1775                CubicXYAtT(fPts, tMid, &midEndPt);
1776                if (!midEndPt.approximatelyEqual(xyAtT(span))) {
1777                    break;
1778                }
1779            }
1780            span[more - 1].fTiny = true;
1781            span[more - 1].fDone = true;
1782            if (approximately_negative(span[more].fT - newT)) {
1783                if (approximately_greater_than_one(span[more].fT)) {
1784                    span[more + 1].fUnsortableStart = true;
1785                    span[more].fUnsortableEnd = true;
1786                }
1787                if (approximately_less_than_zero(newT)) {
1788                    span[more].fUnsortableStart = true;
1789                    span[more - 1].fUnsortableEnd = true;
1790                }
1791            }
1792            ++fDoneSpans;
1793#else
1794            double tEndInterval = span[more].fT - newT;
1795            if (precisely_negative(tEndInterval)) {
1796                break;
1797            }
1798            if (fVerb == SkPath::kCubic_Verb) {
1799                double tMid = newT - tEndInterval / 2;
1800                _Point midEndPt;
1801                CubicXYAtT(fPts, tMid, &midEndPt);
1802                if (!midEndPt.approximatelyEqual(xyAtT(span))) {
1803                    break;
1804                }
1805            }
1806            SkASSERT(span[more - 1].fDone == span[more].fDone);
1807            if (newT == 0) {
1808                setSpanT(more, 0);
1809            } else {
1810                span->fT = newT = span[more].fT;
1811            }
1812#endif
1813            ++more;
1814        }
1815        return insertedAt;
1816    }
1817
1818    // set spans from start to end to decrement by one
1819    // note this walks other backwards
1820    // FIMXE: there's probably an edge case that can be constructed where
1821    // two span in one segment are separated by float epsilon on one span but
1822    // not the other, if one segment is very small. For this
1823    // case the counts asserted below may or may not be enough to separate the
1824    // spans. Even if the counts work out, what if the spans aren't correctly
1825    // sorted? It feels better in such a case to match the span's other span
1826    // pointer since both coincident segments must contain the same spans.
1827    void addTCancel(double startT, double endT, Segment& other,
1828            double oStartT, double oEndT) {
1829        SkASSERT(!approximately_negative(endT - startT));
1830        SkASSERT(!approximately_negative(oEndT - oStartT));
1831        bool binary = fOperand != other.fOperand;
1832        int index = 0;
1833        while (!approximately_negative(startT - fTs[index].fT)) {
1834            ++index;
1835        }
1836        int oIndex = other.fTs.count();
1837        while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
1838            ;
1839        double tRatio = (oEndT - oStartT) / (endT - startT);
1840        Span* test = &fTs[index];
1841        Span* oTest = &other.fTs[oIndex];
1842        SkTDArray<double> outsideTs;
1843        SkTDArray<double> oOutsideTs;
1844        do {
1845            bool decrement = test->fWindValue && oTest->fWindValue && !binary;
1846            bool track = test->fWindValue || oTest->fWindValue;
1847            double testT = test->fT;
1848            double oTestT = oTest->fT;
1849            Span* span = test;
1850            do {
1851                if (decrement) {
1852                    decrementSpan(span);
1853                } else if (track && span->fT < 1 && oTestT < 1) {
1854                    TrackOutside(outsideTs, span->fT, oTestT);
1855                }
1856                span = &fTs[++index];
1857            } while (approximately_negative(span->fT - testT));
1858            Span* oSpan = oTest;
1859            double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
1860            double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
1861            SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
1862            while (approximately_negative(otherTMatchStart - oSpan->fT)
1863                    && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
1864        #ifdef SK_DEBUG
1865                SkASSERT(originalWindValue == oSpan->fWindValue);
1866        #endif
1867                if (decrement) {
1868                    other.decrementSpan(oSpan);
1869                } else if (track && oSpan->fT < 1 && testT < 1) {
1870                    TrackOutside(oOutsideTs, oSpan->fT, testT);
1871                }
1872                if (!oIndex) {
1873                    break;
1874                }
1875                oSpan = &other.fTs[--oIndex];
1876            }
1877            test = span;
1878            oTest = oSpan;
1879        } while (!approximately_negative(endT - test->fT));
1880        SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
1881        // FIXME: determine if canceled edges need outside ts added
1882        if (!done() && outsideTs.count()) {
1883            double tStart = outsideTs[0];
1884            double oStart = outsideTs[1];
1885            addCancelOutsides(tStart, oStart, other, oEndT);
1886            int count = outsideTs.count();
1887            if (count > 2) {
1888                double tStart = outsideTs[count - 2];
1889                double oStart = outsideTs[count - 1];
1890                addCancelOutsides(tStart, oStart, other, oEndT);
1891            }
1892        }
1893        if (!other.done() && oOutsideTs.count()) {
1894            double tStart = oOutsideTs[0];
1895            double oStart = oOutsideTs[1];
1896            other.addCancelOutsides(tStart, oStart, *this, endT);
1897        }
1898    }
1899
1900    int addSelfT(Segment* other, const SkPoint& pt, double& newT) {
1901        int result = addT(other, pt, newT);
1902        Span* span = &fTs[result];
1903        span->fLoop = true;
1904        return result;
1905    }
1906
1907    int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) {
1908        int result = addT(other, pt, newT);
1909        Span* span = &fTs[result];
1910        if (start) {
1911            if (result > 0) {
1912                span[result - 1].fUnsortableEnd = true;
1913            }
1914            span[result].fUnsortableStart = true;
1915        } else {
1916            span[result].fUnsortableEnd = true;
1917            if (result + 1 < fTs.count()) {
1918                span[result + 1].fUnsortableStart = true;
1919            }
1920        }
1921        return result;
1922    }
1923
1924    int bumpCoincidentThis(const Span* oTest, bool opp, int index,
1925            SkTDArray<double>& outsideTs) {
1926        int oWindValue = oTest->fWindValue;
1927        int oOppValue = oTest->fOppValue;
1928        if (opp) {
1929            SkTSwap<int>(oWindValue, oOppValue);
1930        }
1931        Span* const test = &fTs[index];
1932        Span* end = test;
1933        const double oStartT = oTest->fT;
1934        do {
1935            if (bumpSpan(end, oWindValue, oOppValue)) {
1936                TrackOutside(outsideTs, end->fT, oStartT);
1937            }
1938            end = &fTs[++index];
1939        } while (approximately_negative(end->fT - test->fT));
1940        return index;
1941    }
1942
1943    // because of the order in which coincidences are resolved, this and other
1944    // may not have the same intermediate points. Compute the corresponding
1945    // intermediate T values (using this as the master, other as the follower)
1946    // and walk other conditionally -- hoping that it catches up in the end
1947    int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,
1948            SkTDArray<double>& oOutsideTs) {
1949        Span* const oTest = &fTs[oIndex];
1950        Span* oEnd = oTest;
1951        const double startT = test->fT;
1952        const double oStartT = oTest->fT;
1953        while (!approximately_negative(oEndT - oEnd->fT)
1954                && approximately_negative(oEnd->fT - oStartT)) {
1955            zeroSpan(oEnd);
1956            TrackOutside(oOutsideTs, oEnd->fT, startT);
1957            oEnd = &fTs[++oIndex];
1958        }
1959        return oIndex;
1960    }
1961
1962    // FIXME: need to test this case:
1963    // contourA has two segments that are coincident
1964    // contourB has two segments that are coincident in the same place
1965    // each ends up with +2/0 pairs for winding count
1966    // since logic below doesn't transfer count (only increments/decrements) can this be
1967    // resolved to +4/0 ?
1968
1969    // set spans from start to end to increment the greater by one and decrement
1970    // the lesser
1971    void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
1972        SkASSERT(!approximately_negative(endT - startT));
1973        SkASSERT(!approximately_negative(oEndT - oStartT));
1974        bool opp = fOperand ^ other.fOperand;
1975        int index = 0;
1976        while (!approximately_negative(startT - fTs[index].fT)) {
1977            ++index;
1978        }
1979        int oIndex = 0;
1980        while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
1981            ++oIndex;
1982        }
1983        Span* test = &fTs[index];
1984        Span* oTest = &other.fTs[oIndex];
1985        SkTDArray<double> outsideTs;
1986        SkTDArray<double> oOutsideTs;
1987        do {
1988            // if either span has an opposite value and the operands don't match, resolve first
1989     //       SkASSERT(!test->fDone || !oTest->fDone);
1990            if (test->fDone || oTest->fDone) {
1991                index = advanceCoincidentThis(oTest, opp, index);
1992                oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
1993            } else {
1994                index = bumpCoincidentThis(oTest, opp, index, outsideTs);
1995                oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
1996            }
1997            test = &fTs[index];
1998            oTest = &other.fTs[oIndex];
1999        } while (!approximately_negative(endT - test->fT));
2000        SkASSERT(approximately_negative(oTest->fT - oEndT));
2001        SkASSERT(approximately_negative(oEndT - oTest->fT));
2002        if (!done() && outsideTs.count()) {
2003            addCoinOutsides(outsideTs, other, oEndT);
2004        }
2005        if (!other.done() && oOutsideTs.count()) {
2006            other.addCoinOutsides(oOutsideTs, *this, endT);
2007        }
2008    }
2009
2010    // FIXME: this doesn't prevent the same span from being added twice
2011    // fix in caller, SkASSERT here?
2012    void addTPair(double t, Segment& other, double otherT, bool borrowWind, const SkPoint& pt) {
2013        int tCount = fTs.count();
2014        for (int tIndex = 0; tIndex < tCount; ++tIndex) {
2015            const Span& span = fTs[tIndex];
2016            if (!approximately_negative(span.fT - t)) {
2017                break;
2018            }
2019            if (approximately_negative(span.fT - t) && span.fOther == &other
2020                    && approximately_equal(span.fOtherT, otherT)) {
2021#if DEBUG_ADD_T_PAIR
2022                SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
2023                        __FUNCTION__, fID, t, other.fID, otherT);
2024#endif
2025                return;
2026            }
2027        }
2028#if DEBUG_ADD_T_PAIR
2029        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
2030                __FUNCTION__, fID, t, other.fID, otherT);
2031#endif
2032        int insertedAt = addT(&other, pt, t);
2033        int otherInsertedAt = other.addT(this, pt, otherT);
2034        addOtherT(insertedAt, otherT, otherInsertedAt);
2035        other.addOtherT(otherInsertedAt, t, insertedAt);
2036        matchWindingValue(insertedAt, t, borrowWind);
2037        other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
2038    }
2039
2040    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
2041        // add edge leading into junction
2042        int min = SkMin32(end, start);
2043        if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
2044            addAngle(angles, end, start);
2045        }
2046        // add edge leading away from junction
2047        int step = SkSign32(end - start);
2048        int tIndex = nextExactSpan(end, step);
2049        min = SkMin32(end, tIndex);
2050        if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
2051            addAngle(angles, end, tIndex);
2052        }
2053    }
2054
2055    int advanceCoincidentThis(const Span* oTest, bool opp, int index) {
2056        Span* const test = &fTs[index];
2057        Span* end = test;
2058        do {
2059            end = &fTs[++index];
2060        } while (approximately_negative(end->fT - test->fT));
2061        return index;
2062    }
2063
2064    int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {
2065        Span* const oTest = &fTs[oIndex];
2066        Span* oEnd = oTest;
2067        const double oStartT = oTest->fT;
2068        while (!approximately_negative(oEndT - oEnd->fT)
2069                && approximately_negative(oEnd->fT - oStartT)) {
2070            oEnd = &fTs[++oIndex];
2071        }
2072        return oIndex;
2073    }
2074
2075    bool betweenTs(int lesser, double testT, int greater) {
2076        if (lesser > greater) {
2077            SkTSwap<int>(lesser, greater);
2078        }
2079        return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
2080    }
2081
2082    const Bounds& bounds() const {
2083        return fBounds;
2084    }
2085
2086    void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {
2087        double referenceT = fTs[index].fT;
2088        int lesser = index;
2089        while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
2090                && precisely_negative(referenceT - fTs[lesser].fT)) {
2091            buildAnglesInner(lesser, angles);
2092        }
2093        do {
2094            buildAnglesInner(index, angles);
2095        } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
2096                && precisely_negative(fTs[index].fT - referenceT));
2097    }
2098
2099    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
2100        Span* span = &fTs[index];
2101        Segment* other = span->fOther;
2102    // if there is only one live crossing, and no coincidence, continue
2103    // in the same direction
2104    // if there is coincidence, the only choice may be to reverse direction
2105        // find edge on either side of intersection
2106        int oIndex = span->fOtherIndex;
2107        // if done == -1, prior span has already been processed
2108        int step = 1;
2109        int next = other->nextExactSpan(oIndex, step);
2110       if (next < 0) {
2111            step = -step;
2112            next = other->nextExactSpan(oIndex, step);
2113        }
2114        // add candidate into and away from junction
2115        other->addTwoAngles(next, oIndex, angles);
2116    }
2117
2118    int computeSum(int startIndex, int endIndex, bool binary) {
2119        SkTDArray<Angle> angles;
2120        addTwoAngles(startIndex, endIndex, angles);
2121        buildAngles(endIndex, angles, false);
2122        // OPTIMIZATION: check all angles to see if any have computed wind sum
2123        // before sorting (early exit if none)
2124        SkTDArray<Angle*> sorted;
2125        bool sortable = SortAngles(angles, sorted);
2126#if DEBUG_SORT
2127        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
2128#endif
2129        if (!sortable) {
2130            return SK_MinS32;
2131        }
2132        int angleCount = angles.count();
2133        const Angle* angle;
2134        const Segment* base;
2135        int winding;
2136        int oWinding;
2137        int firstIndex = 0;
2138        do {
2139            angle = sorted[firstIndex];
2140            base = angle->segment();
2141            winding = base->windSum(angle);
2142            if (winding != SK_MinS32) {
2143                oWinding = base->oppSum(angle);
2144                break;
2145            }
2146            if (++firstIndex == angleCount) {
2147                return SK_MinS32;
2148            }
2149        } while (true);
2150        // turn winding into contourWinding
2151        int spanWinding = base->spanSign(angle);
2152        bool inner = useInnerWinding(winding + spanWinding, winding);
2153    #if DEBUG_WINDING
2154        SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
2155            spanWinding, winding, angle->sign(), inner,
2156            inner ? winding + spanWinding : winding);
2157    #endif
2158        if (inner) {
2159            winding += spanWinding;
2160        }
2161    #if DEBUG_SORT
2162        base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
2163    #endif
2164        int nextIndex = firstIndex + 1;
2165        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2166        winding -= base->spanSign(angle);
2167        oWinding -= base->oppSign(angle);
2168        do {
2169            if (nextIndex == angleCount) {
2170                nextIndex = 0;
2171            }
2172            angle = sorted[nextIndex];
2173            Segment* segment = angle->segment();
2174            bool opp = base->fOperand ^ segment->fOperand;
2175            int maxWinding, oMaxWinding;
2176            int spanSign = segment->spanSign(angle);
2177            int oppoSign = segment->oppSign(angle);
2178            if (opp) {
2179                oMaxWinding = oWinding;
2180                oWinding -= spanSign;
2181                maxWinding = winding;
2182                if (oppoSign) {
2183                    winding -= oppoSign;
2184                }
2185            } else {
2186                maxWinding = winding;
2187                winding -= spanSign;
2188                oMaxWinding = oWinding;
2189                if (oppoSign) {
2190                    oWinding -= oppoSign;
2191                }
2192            }
2193            if (segment->windSum(angle) == SK_MinS32) {
2194                if (opp) {
2195                    if (useInnerWinding(oMaxWinding, oWinding)) {
2196                        oMaxWinding = oWinding;
2197                    }
2198                    if (oppoSign && useInnerWinding(maxWinding, winding)) {
2199                        maxWinding = winding;
2200                    }
2201                    (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
2202                } else {
2203                    if (useInnerWinding(maxWinding, winding)) {
2204                        maxWinding = winding;
2205                    }
2206                    if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
2207                        oMaxWinding = oWinding;
2208                    }
2209                    (void) segment->markAndChaseWinding(angle, maxWinding,
2210                            binary ? oMaxWinding : 0);
2211                }
2212            }
2213        } while (++nextIndex != lastIndex);
2214        int minIndex = SkMin32(startIndex, endIndex);
2215        return windSum(minIndex);
2216    }
2217
2218    int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething,
2219            double mid, bool opp, bool current) const {
2220        SkScalar bottom = fBounds.fBottom;
2221        int bestTIndex = -1;
2222        if (bottom <= bestY) {
2223            return bestTIndex;
2224        }
2225        SkScalar top = fBounds.fTop;
2226        if (top >= basePt.fY) {
2227            return bestTIndex;
2228        }
2229        if (fBounds.fLeft > basePt.fX) {
2230            return bestTIndex;
2231        }
2232        if (fBounds.fRight < basePt.fX) {
2233            return bestTIndex;
2234        }
2235        if (fBounds.fLeft == fBounds.fRight) {
2236            // if vertical, and directly above test point, wait for another one
2237            return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
2238        }
2239        // intersect ray starting at basePt with edge
2240        Intersections intersections;
2241        // OPTIMIZE: use specialty function that intersects ray with curve,
2242        // returning t values only for curve (we don't care about t on ray)
2243        int pts = (*VSegmentIntersect[fVerb])(fPts, top, bottom, basePt.fX, false, intersections);
2244        if (pts == 0 || (current && pts == 1)) {
2245            return bestTIndex;
2246        }
2247        if (current) {
2248            SkASSERT(pts > 1);
2249            int closestIdx = 0;
2250            double closest = fabs(intersections.fT[0][0] - mid);
2251            for (int idx = 1; idx < pts; ++idx) {
2252                double test = fabs(intersections.fT[0][idx] - mid);
2253                if (closest > test) {
2254                    closestIdx = idx;
2255                    closest = test;
2256                }
2257            }
2258            if (closestIdx < pts - 1) {
2259                intersections.fT[0][closestIdx] = intersections.fT[0][pts - 1];
2260            }
2261            --pts;
2262        }
2263        double bestT = -1;
2264        for (int index = 0; index < pts; ++index) {
2265            double foundT = intersections.fT[0][index];
2266            if (approximately_less_than_zero(foundT)
2267                        || approximately_greater_than_one(foundT)) {
2268                continue;
2269            }
2270            SkScalar testY = (*SegmentYAtT[fVerb])(fPts, foundT);
2271            if (approximately_negative(testY - bestY)
2272                    || approximately_negative(basePt.fY - testY)) {
2273                continue;
2274            }
2275            if (pts > 1 && fVerb == SkPath::kLine_Verb) {
2276                return SK_MinS32; // if the intersection is edge on, wait for another one
2277            }
2278            if (fVerb > SkPath::kLine_Verb) {
2279                SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, foundT);
2280                if (approximately_zero(dx)) {
2281                    return SK_MinS32; // hit vertical, wait for another one
2282                }
2283            }
2284            bestY = testY;
2285            bestT = foundT;
2286        }
2287        if (bestT < 0) {
2288            return bestTIndex;
2289        }
2290        SkASSERT(bestT >= 0);
2291        SkASSERT(bestT <= 1);
2292        int start;
2293        int end = 0;
2294        do {
2295            start = end;
2296            end = nextSpan(start, 1);
2297        } while (fTs[end].fT < bestT);
2298        // FIXME: see next candidate for a better pattern to find the next start/end pair
2299        while (start + 1 < end && fTs[start].fDone) {
2300            ++start;
2301        }
2302        if (!isCanceled(start)) {
2303            hitT = bestT;
2304            bestTIndex = start;
2305            hitSomething = true;
2306        }
2307        return bestTIndex;
2308    }
2309
2310    void decrementSpan(Span* span) {
2311        SkASSERT(span->fWindValue > 0);
2312        if (--(span->fWindValue) == 0) {
2313            if (!span->fOppValue && !span->fDone) {
2314                span->fDone = true;
2315                ++fDoneSpans;
2316            }
2317        }
2318    }
2319
2320    bool bumpSpan(Span* span, int windDelta, int oppDelta) {
2321        SkASSERT(!span->fDone);
2322        span->fWindValue += windDelta;
2323        SkASSERT(span->fWindValue >= 0);
2324        span->fOppValue += oppDelta;
2325        SkASSERT(span->fOppValue >= 0);
2326        if (fXor) {
2327            span->fWindValue &= 1;
2328        }
2329        if (fOppXor) {
2330            span->fOppValue &= 1;
2331        }
2332        if (!span->fWindValue && !span->fOppValue) {
2333            span->fDone = true;
2334            ++fDoneSpans;
2335            return true;
2336        }
2337        return false;
2338    }
2339
2340    // OPTIMIZE
2341    // when the edges are initially walked, they don't automatically get the prior and next
2342    // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
2343    // and would additionally remove the need for similar checks in condition edges. It would
2344    // also allow intersection code to assume end of segment intersections (maybe?)
2345    bool complete() const {
2346        int count = fTs.count();
2347        return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
2348    }
2349
2350    bool done() const {
2351        SkASSERT(fDoneSpans <= fTs.count());
2352        return fDoneSpans == fTs.count();
2353    }
2354
2355    bool done(int min) const {
2356        return fTs[min].fDone;
2357    }
2358
2359    bool done(const Angle* angle) const {
2360        return done(SkMin32(angle->start(), angle->end()));
2361    }
2362
2363    SkVector dxdy(int index) const {
2364        return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT);
2365    }
2366
2367    SkScalar dy(int index) const {
2368        return (*SegmentDYAtT[fVerb])(fPts, fTs[index].fT);
2369    }
2370
2371    bool equalPoints(int greaterTIndex, int lesserTIndex) {
2372        SkASSERT(greaterTIndex >= lesserTIndex);
2373        double greaterT = fTs[greaterTIndex].fT;
2374        double lesserT = fTs[lesserTIndex].fT;
2375        if (greaterT == lesserT) {
2376            return true;
2377        }
2378        if (!approximately_negative(greaterT - lesserT)) {
2379            return false;
2380        }
2381        return xyAtT(greaterTIndex) == xyAtT(lesserTIndex);
2382    }
2383
2384    /*
2385     The M and S variable name parts stand for the operators.
2386       Mi stands for Minuend (see wiki subtraction, analogous to difference)
2387       Su stands for Subtrahend
2388     The Opp variable name part designates that the value is for the Opposite operator.
2389     Opposite values result from combining coincident spans.
2390     */
2391
2392    Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
2393            bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMask) {
2394        const int startIndex = nextStart;
2395        const int endIndex = nextEnd;
2396        SkASSERT(startIndex != endIndex);
2397        const int count = fTs.count();
2398        SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2399        const int step = SkSign32(endIndex - startIndex);
2400        const int end = nextExactSpan(startIndex, step);
2401        SkASSERT(end >= 0);
2402        Span* endSpan = &fTs[end];
2403        Segment* other;
2404        if (isSimple(end)) {
2405        // mark the smaller of startIndex, endIndex done, and all adjacent
2406        // spans with the same T value (but not 'other' spans)
2407    #if DEBUG_WINDING
2408            SkDebugf("%s simple\n", __FUNCTION__);
2409    #endif
2410            int min = SkMin32(startIndex, endIndex);
2411            if (fTs[min].fDone) {
2412                return NULL;
2413            }
2414            markDoneBinary(min);
2415            other = endSpan->fOther;
2416            nextStart = endSpan->fOtherIndex;
2417            double startT = other->fTs[nextStart].fT;
2418            nextEnd = nextStart;
2419            do {
2420                nextEnd += step;
2421            }
2422            while (precisely_zero(startT - other->fTs[nextEnd].fT));
2423            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2424            return other;
2425        }
2426        // more than one viable candidate -- measure angles to find best
2427        SkTDArray<Angle> angles;
2428        SkASSERT(startIndex - endIndex != 0);
2429        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2430        addTwoAngles(startIndex, end, angles);
2431        buildAngles(end, angles, true);
2432        SkTDArray<Angle*> sorted;
2433        bool sortable = SortAngles(angles, sorted);
2434        int angleCount = angles.count();
2435        int firstIndex = findStartingEdge(sorted, startIndex, end);
2436        SkASSERT(firstIndex >= 0);
2437    #if DEBUG_SORT
2438        debugShowSort(__FUNCTION__, sorted, firstIndex);
2439    #endif
2440        if (!sortable) {
2441            unsortable = true;
2442            return NULL;
2443        }
2444        SkASSERT(sorted[firstIndex]->segment() == this);
2445    #if DEBUG_WINDING
2446        SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
2447                sorted[firstIndex]->sign());
2448    #endif
2449        int sumMiWinding = updateWinding(endIndex, startIndex);
2450        int sumSuWinding = updateOppWinding(endIndex, startIndex);
2451        if (operand()) {
2452            SkTSwap<int>(sumMiWinding, sumSuWinding);
2453        }
2454        int nextIndex = firstIndex + 1;
2455        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2456        const Angle* foundAngle = NULL;
2457        bool foundDone = false;
2458        // iterate through the angle, and compute everyone's winding
2459        Segment* nextSegment;
2460        int activeCount = 0;
2461        do {
2462            SkASSERT(nextIndex != firstIndex);
2463            if (nextIndex == angleCount) {
2464                nextIndex = 0;
2465            }
2466            const Angle* nextAngle = sorted[nextIndex];
2467            nextSegment = nextAngle->segment();
2468            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
2469            bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2470                    nextAngle->end(), op, sumMiWinding, sumSuWinding,
2471                    maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
2472            if (activeAngle) {
2473                ++activeCount;
2474                if (!foundAngle || (foundDone && activeCount & 1)) {
2475                    if (nextSegment->tiny(nextAngle)) {
2476                        unsortable = true;
2477                        return NULL;
2478                    }
2479                    foundAngle = nextAngle;
2480                    foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
2481                }
2482            }
2483            if (nextSegment->done()) {
2484                continue;
2485            }
2486            if (nextSegment->windSum(nextAngle) != SK_MinS32) {
2487                continue;
2488            }
2489            Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
2490                    oppSumWinding, activeAngle, nextAngle);
2491            if (last) {
2492                *chase.append() = last;
2493#if DEBUG_WINDING
2494                SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2495                        last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2496#endif
2497            }
2498        } while (++nextIndex != lastIndex);
2499        markDoneBinary(SkMin32(startIndex, endIndex));
2500        if (!foundAngle) {
2501            return NULL;
2502        }
2503        nextStart = foundAngle->start();
2504        nextEnd = foundAngle->end();
2505        nextSegment = foundAngle->segment();
2506
2507    #if DEBUG_WINDING
2508        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2509                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2510     #endif
2511        return nextSegment;
2512    }
2513
2514    Segment* findNextWinding(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
2515            bool& unsortable) {
2516        const int startIndex = nextStart;
2517        const int endIndex = nextEnd;
2518        SkASSERT(startIndex != endIndex);
2519        const int count = fTs.count();
2520        SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2521        const int step = SkSign32(endIndex - startIndex);
2522        const int end = nextExactSpan(startIndex, step);
2523        SkASSERT(end >= 0);
2524        Span* endSpan = &fTs[end];
2525        Segment* other;
2526        if (isSimple(end)) {
2527        // mark the smaller of startIndex, endIndex done, and all adjacent
2528        // spans with the same T value (but not 'other' spans)
2529    #if DEBUG_WINDING
2530            SkDebugf("%s simple\n", __FUNCTION__);
2531    #endif
2532            int min = SkMin32(startIndex, endIndex);
2533            if (fTs[min].fDone) {
2534                return NULL;
2535            }
2536            markDoneUnary(min);
2537            other = endSpan->fOther;
2538            nextStart = endSpan->fOtherIndex;
2539            double startT = other->fTs[nextStart].fT;
2540            nextEnd = nextStart;
2541            do {
2542                nextEnd += step;
2543            }
2544            while (precisely_zero(startT - other->fTs[nextEnd].fT));
2545            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2546            return other;
2547        }
2548        // more than one viable candidate -- measure angles to find best
2549        SkTDArray<Angle> angles;
2550        SkASSERT(startIndex - endIndex != 0);
2551        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2552        addTwoAngles(startIndex, end, angles);
2553        buildAngles(end, angles, true);
2554        SkTDArray<Angle*> sorted;
2555        bool sortable = SortAngles(angles, sorted);
2556        int angleCount = angles.count();
2557        int firstIndex = findStartingEdge(sorted, startIndex, end);
2558        SkASSERT(firstIndex >= 0);
2559    #if DEBUG_SORT
2560        debugShowSort(__FUNCTION__, sorted, firstIndex);
2561    #endif
2562        if (!sortable) {
2563            unsortable = true;
2564            return NULL;
2565        }
2566        SkASSERT(sorted[firstIndex]->segment() == this);
2567    #if DEBUG_WINDING
2568        SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
2569                sorted[firstIndex]->sign());
2570    #endif
2571        int sumWinding = updateWinding(endIndex, startIndex);
2572        int nextIndex = firstIndex + 1;
2573        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2574        const Angle* foundAngle = NULL;
2575        bool foundDone = false;
2576        // iterate through the angle, and compute everyone's winding
2577        Segment* nextSegment;
2578        int activeCount = 0;
2579        do {
2580            SkASSERT(nextIndex != firstIndex);
2581            if (nextIndex == angleCount) {
2582                nextIndex = 0;
2583            }
2584            const Angle* nextAngle = sorted[nextIndex];
2585            nextSegment = nextAngle->segment();
2586            int maxWinding;
2587            bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
2588                    maxWinding, sumWinding);
2589            if (activeAngle) {
2590                ++activeCount;
2591                if (!foundAngle || (foundDone && activeCount & 1)) {
2592                    if (nextSegment->tiny(nextAngle)) {
2593                        unsortable = true;
2594                        return NULL;
2595                    }
2596                    foundAngle = nextAngle;
2597                    foundDone = nextSegment->done(nextAngle);
2598                }
2599            }
2600            if (nextSegment->done()) {
2601                continue;
2602            }
2603            if (nextSegment->windSum(nextAngle) != SK_MinS32) {
2604                continue;
2605            }
2606            Span* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle);
2607            if (last) {
2608                *chase.append() = last;
2609#if DEBUG_WINDING
2610                SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
2611                        last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2612#endif
2613            }
2614        } while (++nextIndex != lastIndex);
2615        markDoneUnary(SkMin32(startIndex, endIndex));
2616        if (!foundAngle) {
2617            return NULL;
2618        }
2619        nextStart = foundAngle->start();
2620        nextEnd = foundAngle->end();
2621        nextSegment = foundAngle->segment();
2622    #if DEBUG_WINDING
2623        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2624                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2625     #endif
2626        return nextSegment;
2627    }
2628
2629    Segment* findNextXor(int& nextStart, int& nextEnd, bool& unsortable) {
2630        const int startIndex = nextStart;
2631        const int endIndex = nextEnd;
2632        SkASSERT(startIndex != endIndex);
2633        int count = fTs.count();
2634        SkASSERT(startIndex < endIndex ? startIndex < count - 1
2635                : startIndex > 0);
2636        int step = SkSign32(endIndex - startIndex);
2637        int end = nextExactSpan(startIndex, step);
2638        SkASSERT(end >= 0);
2639        Span* endSpan = &fTs[end];
2640        Segment* other;
2641        if (isSimple(end)) {
2642    #if DEBUG_WINDING
2643            SkDebugf("%s simple\n", __FUNCTION__);
2644    #endif
2645            int min = SkMin32(startIndex, endIndex);
2646            if (fTs[min].fDone) {
2647                return NULL;
2648            }
2649            markDone(min, 1);
2650            other = endSpan->fOther;
2651            nextStart = endSpan->fOtherIndex;
2652            double startT = other->fTs[nextStart].fT;
2653        #if 01 // FIXME: I don't know why the logic here is difference from the winding case
2654            SkDEBUGCODE(bool firstLoop = true;)
2655            if ((approximately_less_than_zero(startT) && step < 0)
2656                    || (approximately_greater_than_one(startT) && step > 0)) {
2657                step = -step;
2658                SkDEBUGCODE(firstLoop = false;)
2659            }
2660            do {
2661        #endif
2662                nextEnd = nextStart;
2663                do {
2664                    nextEnd += step;
2665                }
2666                 while (precisely_zero(startT - other->fTs[nextEnd].fT));
2667        #if 01
2668                if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
2669                    break;
2670                }
2671 #ifdef SK_DEBUG
2672                SkASSERT(firstLoop);
2673 #endif
2674                SkDEBUGCODE(firstLoop = false;)
2675                step = -step;
2676            } while (true);
2677        #endif
2678            SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
2679            return other;
2680        }
2681        SkTDArray<Angle> angles;
2682        SkASSERT(startIndex - endIndex != 0);
2683        SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2684        addTwoAngles(startIndex, end, angles);
2685        buildAngles(end, angles, false);
2686        SkTDArray<Angle*> sorted;
2687        bool sortable = SortAngles(angles, sorted);
2688        if (!sortable) {
2689            unsortable = true;
2690    #if DEBUG_SORT
2691            debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0);
2692    #endif
2693            return NULL;
2694        }
2695        int angleCount = angles.count();
2696        int firstIndex = findStartingEdge(sorted, startIndex, end);
2697        SkASSERT(firstIndex >= 0);
2698    #if DEBUG_SORT
2699        debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
2700    #endif
2701        SkASSERT(sorted[firstIndex]->segment() == this);
2702        int nextIndex = firstIndex + 1;
2703        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
2704        const Angle* foundAngle = NULL;
2705        bool foundDone = false;
2706        Segment* nextSegment;
2707        int activeCount = 0;
2708        do {
2709            SkASSERT(nextIndex != firstIndex);
2710            if (nextIndex == angleCount) {
2711                nextIndex = 0;
2712            }
2713            const Angle* nextAngle = sorted[nextIndex];
2714            nextSegment = nextAngle->segment();
2715            ++activeCount;
2716            if (!foundAngle || (foundDone && activeCount & 1)) {
2717                if (nextSegment->tiny(nextAngle)) {
2718                    unsortable = true;
2719                    return NULL;
2720                }
2721                foundAngle = nextAngle;
2722                foundDone = nextSegment->done(nextAngle);
2723            }
2724            if (nextSegment->done()) {
2725                continue;
2726            }
2727        } while (++nextIndex != lastIndex);
2728        markDone(SkMin32(startIndex, endIndex), 1);
2729        if (!foundAngle) {
2730            return NULL;
2731        }
2732        nextStart = foundAngle->start();
2733        nextEnd = foundAngle->end();
2734        nextSegment = foundAngle->segment();
2735    #if DEBUG_WINDING
2736        SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2737                __FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
2738     #endif
2739        return nextSegment;
2740    }
2741
2742    int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
2743        int angleCount = sorted.count();
2744        int firstIndex = -1;
2745        for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2746            const Angle* angle = sorted[angleIndex];
2747            if (angle->segment() == this && angle->start() == end &&
2748                    angle->end() == start) {
2749                firstIndex = angleIndex;
2750                break;
2751            }
2752        }
2753        return firstIndex;
2754    }
2755
2756    // FIXME: this is tricky code; needs its own unit test
2757    // note that fOtherIndex isn't computed yet, so it can't be used here
2758    void findTooCloseToCall() {
2759        int count = fTs.count();
2760        if (count < 3) { // require t=0, x, 1 at minimum
2761            return;
2762        }
2763        int matchIndex = 0;
2764        int moCount;
2765        Span* match;
2766        Segment* mOther;
2767        do {
2768            match = &fTs[matchIndex];
2769            mOther = match->fOther;
2770            // FIXME: allow quads, cubics to be near coincident?
2771            if (mOther->fVerb == SkPath::kLine_Verb) {
2772                moCount = mOther->fTs.count();
2773                if (moCount >= 3) {
2774                    break;
2775                }
2776            }
2777            if (++matchIndex >= count) {
2778                return;
2779            }
2780        } while (true); // require t=0, x, 1 at minimum
2781        // OPTIMIZATION: defer matchPt until qualifying toCount is found?
2782        const SkPoint* matchPt = &xyAtT(match);
2783        // look for a pair of nearby T values that map to the same (x,y) value
2784        // if found, see if the pair of other segments share a common point. If
2785        // so, the span from here to there is coincident.
2786        for (int index = matchIndex + 1; index < count; ++index) {
2787            Span* test = &fTs[index];
2788            if (test->fDone) {
2789                continue;
2790            }
2791            Segment* tOther = test->fOther;
2792            if (tOther->fVerb != SkPath::kLine_Verb) {
2793                continue; // FIXME: allow quads, cubics to be near coincident?
2794            }
2795            int toCount = tOther->fTs.count();
2796            if (toCount < 3) { // require t=0, x, 1 at minimum
2797                continue;
2798            }
2799            const SkPoint* testPt = &xyAtT(test);
2800            if (*matchPt != *testPt) {
2801                matchIndex = index;
2802                moCount = toCount;
2803                match = test;
2804                mOther = tOther;
2805                matchPt = testPt;
2806                continue;
2807            }
2808            int moStart = -1;
2809            int moEnd = -1;
2810            double moStartT, moEndT;
2811            for (int moIndex = 0; moIndex < moCount; ++moIndex) {
2812                Span& moSpan = mOther->fTs[moIndex];
2813                if (moSpan.fDone) {
2814                    continue;
2815                }
2816                if (moSpan.fOther == this) {
2817                    if (moSpan.fOtherT == match->fT) {
2818                        moStart = moIndex;
2819                        moStartT = moSpan.fT;
2820                    }
2821                    continue;
2822                }
2823                if (moSpan.fOther == tOther) {
2824                    if (tOther->windValueAt(moSpan.fOtherT) == 0) {
2825                        moStart = -1;
2826                        break;
2827                    }
2828                    SkASSERT(moEnd == -1);
2829                    moEnd = moIndex;
2830                    moEndT = moSpan.fT;
2831                }
2832            }
2833            if (moStart < 0 || moEnd < 0) {
2834                continue;
2835            }
2836            // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
2837            if (approximately_equal(moStartT, moEndT)) {
2838                continue;
2839            }
2840            int toStart = -1;
2841            int toEnd = -1;
2842            double toStartT, toEndT;
2843            for (int toIndex = 0; toIndex < toCount; ++toIndex) {
2844                Span& toSpan = tOther->fTs[toIndex];
2845                if (toSpan.fDone) {
2846                    continue;
2847                }
2848                if (toSpan.fOther == this) {
2849                    if (toSpan.fOtherT == test->fT) {
2850                        toStart = toIndex;
2851                        toStartT = toSpan.fT;
2852                    }
2853                    continue;
2854                }
2855                if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
2856                    if (mOther->windValueAt(toSpan.fOtherT) == 0) {
2857                        moStart = -1;
2858                        break;
2859                    }
2860                    SkASSERT(toEnd == -1);
2861                    toEnd = toIndex;
2862                    toEndT = toSpan.fT;
2863                }
2864            }
2865            // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
2866            if (toStart <= 0 || toEnd <= 0) {
2867                continue;
2868            }
2869            if (approximately_equal(toStartT, toEndT)) {
2870                continue;
2871            }
2872            // test to see if the segment between there and here is linear
2873            if (!mOther->isLinear(moStart, moEnd)
2874                    || !tOther->isLinear(toStart, toEnd)) {
2875                continue;
2876            }
2877            bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
2878            if (flipped) {
2879                mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
2880            } else {
2881                mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEndT);
2882            }
2883        }
2884    }
2885
2886    // FIXME: either:
2887    // a) mark spans with either end unsortable as done, or
2888    // b) rewrite findTop / findTopSegment / findTopContour to iterate further
2889    //    when encountering an unsortable span
2890
2891    // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
2892    // and use more concise logic like the old edge walker code?
2893    // FIXME: this needs to deal with coincident edges
2894    Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable) {
2895        // iterate through T intersections and return topmost
2896        // topmost tangent from y-min to first pt is closer to horizontal
2897        SkASSERT(!done());
2898        int firstT = -1;
2899        /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);
2900        SkASSERT(firstT >= 0);
2901        // sort the edges to find the leftmost
2902        int step = 1;
2903        int end = nextSpan(firstT, step);
2904        if (end == -1) {
2905            step = -1;
2906            end = nextSpan(firstT, step);
2907            SkASSERT(end != -1);
2908        }
2909        // if the topmost T is not on end, or is three-way or more, find left
2910        // look for left-ness from tLeft to firstT (matching y of other)
2911        SkTDArray<Angle> angles;
2912        SkASSERT(firstT - end != 0);
2913        addTwoAngles(end, firstT, angles);
2914        buildAngles(firstT, angles, true);
2915        SkTDArray<Angle*> sorted;
2916        bool sortable = SortAngles(angles, sorted);
2917    #if DEBUG_SORT
2918        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
2919    #endif
2920        if (onlySortable && !sortable) {
2921            unsortable = true;
2922            return NULL;
2923        }
2924        // skip edges that have already been processed
2925        firstT = -1;
2926        Segment* leftSegment;
2927        do {
2928            const Angle* angle = sorted[++firstT];
2929            SkASSERT(!onlySortable || !angle->unsortable());
2930            leftSegment = angle->segment();
2931            tIndex = angle->end();
2932            endIndex = angle->start();
2933        } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
2934        if (leftSegment->verb() >= SkPath::kQuad_Verb) {
2935            bool bumpsUp = leftSegment->bumpsUp(tIndex, endIndex);
2936            SkPoint xyE = leftSegment->xyAtT(endIndex);
2937            SkPoint xyS = leftSegment->xyAtT(tIndex);
2938            SkVector dxyE = leftSegment->dxdy(endIndex);
2939            SkVector dxyS = leftSegment->dxdy(tIndex);
2940            double cross = dxyE.cross(dxyS);
2941            bool bumpCheck = bumpsUp && xyE.fY < xyS.fY && dxyE.fX < 0;
2942            if (xyE == xyS){
2943                SkDebugf("%s ignore loops\n", __FUNCTION__);
2944                cross = 0;
2945            }
2946        #if DEBUG_SWAP_TOP
2947            SkDebugf("%s xyE=(%1.9g,%1.9g) xyS=(%1.9g,%1.9g)\n", __FUNCTION__,
2948                    xyE.fX, xyE.fY, xyS.fX, xyS.fY);
2949            SkDebugf("%s dxyE=(%1.9g,%1.9g) dxyS=(%1.9g,%1.9g) cross=%1.9g bumpsUp=%s\n",
2950                    __FUNCTION__,
2951                    dxyE.fX, dxyE.fY, dxyS.fX, dxyS.fY, cross, bumpsUp ? "true" : "false");
2952            if ((cross > 0) ^ bumpCheck) {
2953                leftSegment->bumpsUp(tIndex, endIndex);
2954                SkDebugf("%s cross bump disagree\n", __FUNCTION__);
2955            }
2956        #endif
2957            if (cross > 0 || bumpCheck) {
2958        #if DEBUG_SWAP_TOP
2959                SkDebugf("%s swap\n", __FUNCTION__);
2960        #endif
2961                SkTSwap(tIndex, endIndex);
2962            }
2963        }
2964        SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
2965        return leftSegment;
2966    }
2967
2968    // FIXME: not crazy about this
2969    // when the intersections are performed, the other index is into an
2970    // incomplete array. as the array grows, the indices become incorrect
2971    // while the following fixes the indices up again, it isn't smart about
2972    // skipping segments whose indices are already correct
2973    // assuming we leave the code that wrote the index in the first place
2974    void fixOtherTIndex() {
2975        int iCount = fTs.count();
2976        for (int i = 0; i < iCount; ++i) {
2977            Span& iSpan = fTs[i];
2978            double oT = iSpan.fOtherT;
2979            Segment* other = iSpan.fOther;
2980            int oCount = other->fTs.count();
2981            for (int o = 0; o < oCount; ++o) {
2982                Span& oSpan = other->fTs[o];
2983                if (oT == oSpan.fT && this == oSpan.fOther) {
2984                    iSpan.fOtherIndex = o;
2985                    break;
2986                }
2987            }
2988        }
2989    }
2990
2991    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
2992        fDoneSpans = 0;
2993        fOperand = operand;
2994        fXor = evenOdd;
2995        fPts = pts;
2996        fVerb = verb;
2997    }
2998
2999    void initWinding(int start, int end) {
3000        int local = spanSign(start, end);
3001        int oppLocal = oppSign(start, end);
3002        (void) markAndChaseWinding(start, end, local, oppLocal);
3003        // OPTIMIZATION: the reverse mark and chase could skip the first marking
3004        (void) markAndChaseWinding(end, start, local, oppLocal);
3005    }
3006
3007    void initWinding(int start, int end, int winding, int oppWinding) {
3008        int local = spanSign(start, end);
3009        if (local * winding >= 0) {
3010            winding += local;
3011        }
3012        int oppLocal = oppSign(start, end);
3013        if (oppLocal * oppWinding >= 0) {
3014            oppWinding += oppLocal;
3015        }
3016        (void) markAndChaseWinding(start, end, winding, oppWinding);
3017    }
3018
3019/*
3020when we start with a vertical intersect, we try to use the dx to determine if the edge is to
3021the left or the right of vertical. This determines if we need to add the span's
3022sign or not. However, this isn't enough.
3023If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
3024If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
3025from has the same x direction as this span, the winding should change. If the dx is opposite, then
3026the same winding is shared by both.
3027*/
3028    void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
3029            SkScalar hitOppDx) {
3030        SkASSERT(hitDx || !winding);
3031        SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, tHit);
3032        SkASSERT(dx);
3033        int windVal = windValue(SkMin32(start, end));
3034    #if DEBUG_WINDING_AT_T
3035        SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
3036                hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3037    #endif
3038        if (!winding) {
3039            winding = dx < 0 ? windVal : -windVal;
3040        } else if (winding * dx < 0) {
3041            int sideWind = winding + (dx < 0 ? windVal : -windVal);
3042            if (abs(winding) < abs(sideWind)) {
3043                winding = sideWind;
3044            }
3045        }
3046    #if DEBUG_WINDING_AT_T
3047        SkDebugf(" winding=%d\n", winding);
3048    #endif
3049        int oppLocal = oppSign(start, end);
3050        SkASSERT(hitOppDx || !oppWind || !oppLocal);
3051        int oppWindVal = oppValue(SkMin32(start, end));
3052        if (!oppWind) {
3053            oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3054        } else if (hitOppDx * dx >= 0) {
3055            int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3056            if (abs(oppWind) < abs(oppSideWind)) {
3057                oppWind = oppSideWind;
3058            }
3059        }
3060        (void) markAndChaseWinding(start, end, winding, oppWind);
3061    }
3062
3063    bool intersected() const {
3064        return fTs.count() > 0;
3065    }
3066
3067    bool isCanceled(int tIndex) const {
3068        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
3069    }
3070
3071    bool isConnected(int startIndex, int endIndex) const {
3072        return fTs[startIndex].fWindSum != SK_MinS32
3073                || fTs[endIndex].fWindSum != SK_MinS32;
3074    }
3075
3076    bool isHorizontal() const {
3077        return fBounds.fTop == fBounds.fBottom;
3078    }
3079
3080    bool isLinear(int start, int end) const {
3081        if (fVerb == SkPath::kLine_Verb) {
3082            return true;
3083        }
3084        if (fVerb == SkPath::kQuad_Verb) {
3085            SkPoint qPart[3];
3086            QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart);
3087            return QuadIsLinear(qPart);
3088        } else {
3089            SkASSERT(fVerb == SkPath::kCubic_Verb);
3090            SkPoint cPart[4];
3091            CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart);
3092            return CubicIsLinear(cPart);
3093        }
3094    }
3095
3096    // OPTIMIZE: successive calls could start were the last leaves off
3097    // or calls could specialize to walk forwards or backwards
3098    bool isMissing(double startT) const {
3099        size_t tCount = fTs.count();
3100        for (size_t index = 0; index < tCount; ++index) {
3101            if (approximately_zero(startT - fTs[index].fT)) {
3102                return false;
3103            }
3104        }
3105        return true;
3106    }
3107
3108    bool isSimple(int end) const {
3109        int count = fTs.count();
3110        if (count == 2) {
3111            return true;
3112        }
3113        double t = fTs[end].fT;
3114        if (approximately_less_than_zero(t)) {
3115            return !approximately_less_than_zero(fTs[1].fT);
3116        }
3117        if (approximately_greater_than_one(t)) {
3118            return !approximately_greater_than_one(fTs[count - 2].fT);
3119        }
3120        return false;
3121    }
3122
3123    bool isVertical() const {
3124        return fBounds.fLeft == fBounds.fRight;
3125    }
3126
3127    bool isVertical(int start, int end) const {
3128        return (*SegmentVertical[fVerb])(fPts, start, end);
3129    }
3130
3131    SkScalar leftMost(int start, int end) const {
3132        return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
3133    }
3134
3135    // this span is excluded by the winding rule -- chase the ends
3136    // as long as they are unambiguous to mark connections as done
3137    // and give them the same winding value
3138    Span* markAndChaseDone(const Angle* angle, int winding) {
3139        int index = angle->start();
3140        int endIndex = angle->end();
3141        return markAndChaseDone(index, endIndex, winding);
3142    }
3143
3144    Span* markAndChaseDone(int index, int endIndex, int winding) {
3145        int step = SkSign32(endIndex - index);
3146        int min = SkMin32(index, endIndex);
3147        markDone(min, winding);
3148        Span* last;
3149        Segment* other = this;
3150        while ((other = other->nextChase(index, step, min, last))) {
3151            other->markDone(min, winding);
3152        }
3153        return last;
3154    }
3155
3156    Span* markAndChaseDoneBinary(const Angle* angle, int winding, int oppWinding) {
3157        int index = angle->start();
3158        int endIndex = angle->end();
3159        int step = SkSign32(endIndex - index);
3160        int min = SkMin32(index, endIndex);
3161        markDoneBinary(min, winding, oppWinding);
3162        Span* last;
3163        Segment* other = this;
3164        while ((other = other->nextChase(index, step, min, last))) {
3165            other->markDoneBinary(min, winding, oppWinding);
3166        }
3167        return last;
3168    }
3169
3170    Span* markAndChaseDoneBinary(int index, int endIndex) {
3171        int step = SkSign32(endIndex - index);
3172        int min = SkMin32(index, endIndex);
3173        markDoneBinary(min);
3174        Span* last;
3175        Segment* other = this;
3176        while ((other = other->nextChase(index, step, min, last))) {
3177            if (other->done()) {
3178                return NULL;
3179            }
3180            other->markDoneBinary(min);
3181        }
3182        return last;
3183    }
3184
3185    Span* markAndChaseDoneUnary(int index, int endIndex) {
3186        int step = SkSign32(endIndex - index);
3187        int min = SkMin32(index, endIndex);
3188        markDoneUnary(min);
3189        Span* last;
3190        Segment* other = this;
3191        while ((other = other->nextChase(index, step, min, last))) {
3192            if (other->done()) {
3193                return NULL;
3194            }
3195            other->markDoneUnary(min);
3196        }
3197        return last;
3198    }
3199
3200    Span* markAndChaseDoneUnary(const Angle* angle, int winding) {
3201        int index = angle->start();
3202        int endIndex = angle->end();
3203        return markAndChaseDone(index, endIndex, winding);
3204    }
3205
3206    Span* markAndChaseWinding(const Angle* angle, const int winding) {
3207        int index = angle->start();
3208        int endIndex = angle->end();
3209        int step = SkSign32(endIndex - index);
3210        int min = SkMin32(index, endIndex);
3211        markWinding(min, winding);
3212        Span* last;
3213        Segment* other = this;
3214        while ((other = other->nextChase(index, step, min, last))) {
3215            if (other->fTs[min].fWindSum != SK_MinS32) {
3216                SkASSERT(other->fTs[min].fWindSum == winding);
3217                return NULL;
3218            }
3219            other->markWinding(min, winding);
3220        }
3221        return last;
3222    }
3223
3224    Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3225        int min = SkMin32(index, endIndex);
3226        int step = SkSign32(endIndex - index);
3227        markWinding(min, winding, oppWinding);
3228        Span* last;
3229        Segment* other = this;
3230        while ((other = other->nextChase(index, step, min, last))) {
3231            if (other->fTs[min].fWindSum != SK_MinS32) {
3232                SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
3233                return NULL;
3234            }
3235            other->markWinding(min, winding, oppWinding);
3236        }
3237        return last;
3238    }
3239
3240    Span* markAndChaseWinding(const Angle* angle, int winding, int oppWinding) {
3241        int start = angle->start();
3242        int end = angle->end();
3243        return markAndChaseWinding(start, end, winding, oppWinding);
3244    }
3245
3246    Span* markAngle(int maxWinding, int sumWinding, bool activeAngle, const Angle* angle) {
3247        SkASSERT(angle->segment() == this);
3248        if (useInnerWinding(maxWinding, sumWinding)) {
3249            maxWinding = sumWinding;
3250        }
3251        Span* last;
3252        if (activeAngle) {
3253            last = markAndChaseWinding(angle, maxWinding);
3254        } else {
3255            last = markAndChaseDoneUnary(angle, maxWinding);
3256        }
3257        return last;
3258    }
3259
3260    Span* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
3261            bool activeAngle, const Angle* angle) {
3262        SkASSERT(angle->segment() == this);
3263        if (useInnerWinding(maxWinding, sumWinding)) {
3264            maxWinding = sumWinding;
3265        }
3266        if (oppMaxWinding != oppSumWinding && useInnerWinding(oppMaxWinding, oppSumWinding)) {
3267            oppMaxWinding = oppSumWinding;
3268        }
3269        Span* last;
3270        if (activeAngle) {
3271            last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3272        } else {
3273            last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
3274        }
3275        return last;
3276    }
3277
3278    // FIXME: this should also mark spans with equal (x,y)
3279    // This may be called when the segment is already marked done. While this
3280    // wastes time, it shouldn't do any more than spin through the T spans.
3281    // OPTIMIZATION: abort on first done found (assuming that this code is
3282    // always called to mark segments done).
3283    void markDone(int index, int winding) {
3284      //  SkASSERT(!done());
3285        SkASSERT(winding);
3286        double referenceT = fTs[index].fT;
3287        int lesser = index;
3288        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3289            markOneDone(__FUNCTION__, lesser, winding);
3290        }
3291        do {
3292            markOneDone(__FUNCTION__, index, winding);
3293        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3294    }
3295
3296    void markDoneBinary(int index, int winding, int oppWinding) {
3297      //  SkASSERT(!done());
3298        SkASSERT(winding || oppWinding);
3299        double referenceT = fTs[index].fT;
3300        int lesser = index;
3301        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3302            markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);
3303        }
3304        do {
3305            markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);
3306        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3307    }
3308
3309    void markDoneBinary(int index) {
3310        double referenceT = fTs[index].fT;
3311        int lesser = index;
3312        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3313            markOneDoneBinary(__FUNCTION__, lesser);
3314        }
3315        do {
3316            markOneDoneBinary(__FUNCTION__, index);
3317        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3318    }
3319
3320    void markDoneUnary(int index, int winding) {
3321      //  SkASSERT(!done());
3322        SkASSERT(winding);
3323        double referenceT = fTs[index].fT;
3324        int lesser = index;
3325        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3326            markOneDoneUnary(__FUNCTION__, lesser, winding);
3327        }
3328        do {
3329            markOneDoneUnary(__FUNCTION__, index, winding);
3330        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3331    }
3332
3333    void markDoneUnary(int index) {
3334        double referenceT = fTs[index].fT;
3335        int lesser = index;
3336        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3337            markOneDoneUnary(__FUNCTION__, lesser);
3338        }
3339        do {
3340            markOneDoneUnary(__FUNCTION__, index);
3341        } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3342    }
3343
3344    void markOneDone(const char* funName, int tIndex, int winding) {
3345        Span* span = markOneWinding(funName, tIndex, winding);
3346        if (!span) {
3347            return;
3348        }
3349        span->fDone = true;
3350        fDoneSpans++;
3351    }
3352
3353    void markOneDoneBinary(const char* funName, int tIndex) {
3354        Span* span = verifyOneWinding(funName, tIndex);
3355        if (!span) {
3356            return;
3357        }
3358        span->fDone = true;
3359        fDoneSpans++;
3360    }
3361
3362    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) {
3363        Span* span = markOneWinding(funName, tIndex, winding, oppWinding);
3364        if (!span) {
3365            return;
3366        }
3367        span->fDone = true;
3368        fDoneSpans++;
3369    }
3370
3371    void markOneDoneUnary(const char* funName, int tIndex) {
3372        Span* span = verifyOneWindingU(funName, tIndex);
3373        if (!span) {
3374            return;
3375        }
3376        span->fDone = true;
3377        fDoneSpans++;
3378    }
3379
3380    void markOneDoneUnary(const char* funName, int tIndex, int winding) {
3381        Span* span = markOneWinding(funName, tIndex, winding);
3382        if (!span) {
3383            return;
3384        }
3385        span->fDone = true;
3386        fDoneSpans++;
3387    }
3388
3389    Span* markOneWinding(const char* funName, int tIndex, int winding) {
3390        Span& span = fTs[tIndex];
3391        if (span.fDone) {
3392            return NULL;
3393        }
3394    #if DEBUG_MARK_DONE
3395        debugShowNewWinding(funName, span, winding);
3396    #endif
3397        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3398   #ifdef SK_DEBUG
3399        SkASSERT(abs(winding) <= gDebugMaxWindSum);
3400   #endif
3401        span.fWindSum = winding;
3402        return &span;
3403    }
3404
3405    Span* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding) {
3406        Span& span = fTs[tIndex];
3407        if (span.fDone) {
3408            return NULL;
3409        }
3410    #if DEBUG_MARK_DONE
3411        debugShowNewWinding(funName, span, winding, oppWinding);
3412    #endif
3413        SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3414   #ifdef SK_DEBUG
3415        SkASSERT(abs(winding) <= gDebugMaxWindSum);
3416   #endif
3417        span.fWindSum = winding;
3418        SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
3419   #ifdef SK_DEBUG
3420        SkASSERT(abs(oppWinding) <= gDebugMaxWindSum);
3421   #endif
3422        span.fOppSum = oppWinding;
3423        return &span;
3424    }
3425
3426    bool bumpsUp(int tStart, int tEnd) const {
3427        SkPoint edge[4];
3428        subDivide(tStart, tEnd, edge);
3429        switch (fVerb) {
3430            case SkPath::kLine_Verb:
3431                SkASSERT(0); // shouldn't call in for lines
3432                return true;
3433            case SkPath::kQuad_Verb:
3434                return approximately_greater(edge[0].fY, edge[1].fY)
3435                        && approximately_lesser(edge[1].fY, edge[2].fY);
3436            case SkPath::kCubic_Verb:
3437                return (approximately_greater(edge[0].fY, edge[1].fY)
3438                        && approximately_lesser(edge[1].fY, edge[3].fY))
3439                        || (approximately_greater(edge[0].fY, edge[2].fY)
3440                        && approximately_lesser(edge[2].fY, edge[3].fY));
3441            default:
3442                SkASSERT(0);
3443                return false;
3444        }
3445    }
3446
3447    Span* verifyOneWinding(const char* funName, int tIndex) {
3448        Span& span = fTs[tIndex];
3449        if (span.fDone) {
3450            return NULL;
3451        }
3452    #if DEBUG_MARK_DONE
3453        debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
3454    #endif
3455        SkASSERT(span.fWindSum != SK_MinS32);
3456        SkASSERT(span.fOppSum != SK_MinS32);
3457        return &span;
3458    }
3459
3460    Span* verifyOneWindingU(const char* funName, int tIndex) {
3461        Span& span = fTs[tIndex];
3462        if (span.fDone) {
3463            return NULL;
3464        }
3465    #if DEBUG_MARK_DONE
3466        debugShowNewWinding(funName, span, span.fWindSum);
3467    #endif
3468        SkASSERT(span.fWindSum != SK_MinS32);
3469        return &span;
3470    }
3471
3472    // note that just because a span has one end that is unsortable, that's
3473    // not enough to mark it done. The other end may be sortable, allowing the
3474    // span to be added.
3475    // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
3476    void markUnsortable(int start, int end) {
3477        Span* span = &fTs[start];
3478        if (start < end) {
3479#if DEBUG_UNSORTABLE
3480            SkDebugf("%s start id=%d [%d] (%1.9g,%1.9g)\n", __FUNCTION__, fID, start,
3481                    xAtT(start), yAtT(start));
3482#endif
3483            span->fUnsortableStart = true;
3484        } else {
3485            --span;
3486#if DEBUG_UNSORTABLE
3487            SkDebugf("%s end id=%d [%d] (%1.9g,%1.9g) next:(%1.9g,%1.9g)\n", __FUNCTION__, fID,
3488                start - 1, xAtT(start - 1), yAtT(start - 1), xAtT(start), yAtT(start));
3489#endif
3490            span->fUnsortableEnd = true;
3491        }
3492        if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
3493            return;
3494        }
3495        span->fDone = true;
3496        fDoneSpans++;
3497    }
3498
3499    void markWinding(int index, int winding) {
3500    //    SkASSERT(!done());
3501        SkASSERT(winding);
3502        double referenceT = fTs[index].fT;
3503        int lesser = index;
3504        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3505            markOneWinding(__FUNCTION__, lesser, winding);
3506        }
3507        do {
3508            markOneWinding(__FUNCTION__, index, winding);
3509       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3510    }
3511
3512    void markWinding(int index, int winding, int oppWinding) {
3513    //    SkASSERT(!done());
3514        SkASSERT(winding || oppWinding);
3515        double referenceT = fTs[index].fT;
3516        int lesser = index;
3517        while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3518            markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3519        }
3520        do {
3521            markOneWinding(__FUNCTION__, index, winding, oppWinding);
3522       } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3523    }
3524
3525    void matchWindingValue(int tIndex, double t, bool borrowWind) {
3526        int nextDoorWind = SK_MaxS32;
3527        int nextOppWind = SK_MaxS32;
3528        if (tIndex > 0) {
3529            const Span& below = fTs[tIndex - 1];
3530            if (approximately_negative(t - below.fT)) {
3531                nextDoorWind = below.fWindValue;
3532                nextOppWind = below.fOppValue;
3533            }
3534        }
3535        if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3536            const Span& above = fTs[tIndex + 1];
3537            if (approximately_negative(above.fT - t)) {
3538                nextDoorWind = above.fWindValue;
3539                nextOppWind = above.fOppValue;
3540            }
3541        }
3542        if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3543            const Span& below = fTs[tIndex - 1];
3544            nextDoorWind = below.fWindValue;
3545            nextOppWind = below.fOppValue;
3546        }
3547        if (nextDoorWind != SK_MaxS32) {
3548            Span& newSpan = fTs[tIndex];
3549            newSpan.fWindValue = nextDoorWind;
3550            newSpan.fOppValue = nextOppWind;
3551            if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3552                newSpan.fDone = true;
3553                ++fDoneSpans;
3554            }
3555        }
3556    }
3557
3558    bool moreHorizontal(int index, int endIndex, bool& unsortable) const {
3559        // find bounds
3560        Bounds bounds;
3561        bounds.setPoint(xyAtT(index));
3562        bounds.add(xyAtT(endIndex));
3563        SkScalar width = bounds.width();
3564        SkScalar height = bounds.height();
3565        if (width > height) {
3566            if (approximately_negative(width)) {
3567                unsortable = true; // edge is too small to resolve meaningfully
3568            }
3569            return false;
3570        } else {
3571            if (approximately_negative(height)) {
3572                unsortable = true; // edge is too small to resolve meaningfully
3573            }
3574            return true;
3575        }
3576    }
3577
3578    // return span if when chasing, two or more radiating spans are not done
3579    // OPTIMIZATION: ? multiple spans is detected when there is only one valid
3580    // candidate and the remaining spans have windValue == 0 (canceled by
3581    // coincidence). The coincident edges could either be removed altogether,
3582    // or this code could be more complicated in detecting this case. Worth it?
3583    bool multipleSpans(int end) const {
3584        return end > 0 && end < fTs.count() - 1;
3585    }
3586
3587    bool nextCandidate(int& start, int& end) const {
3588        while (fTs[end].fDone) {
3589            if (fTs[end].fT == 1) {
3590                return false;
3591            }
3592            ++end;
3593        }
3594        start = end;
3595        end = nextExactSpan(start, 1);
3596        return true;
3597    }
3598
3599    Segment* nextChase(int& index, const int step, int& min, Span*& last) const {
3600        int end = nextExactSpan(index, step);
3601        SkASSERT(end >= 0);
3602        if (multipleSpans(end)) {
3603            last = &fTs[end];
3604            return NULL;
3605        }
3606        const Span& endSpan = fTs[end];
3607        Segment* other = endSpan.fOther;
3608        index = endSpan.fOtherIndex;
3609        SkASSERT(index >= 0);
3610        int otherEnd = other->nextExactSpan(index, step);
3611        SkASSERT(otherEnd >= 0);
3612        min = SkMin32(index, otherEnd);
3613        return other;
3614    }
3615
3616    // This has callers for two different situations: one establishes the end
3617    // of the current span, and one establishes the beginning of the next span
3618    // (thus the name). When this is looking for the end of the current span,
3619    // coincidence is found when the beginning Ts contain -step and the end
3620    // contains step. When it is looking for the beginning of the next, the
3621    // first Ts found can be ignored and the last Ts should contain -step.
3622    // OPTIMIZATION: probably should split into two functions
3623    int nextSpan(int from, int step) const {
3624        const Span& fromSpan = fTs[from];
3625        int count = fTs.count();
3626        int to = from;
3627        while (step > 0 ? ++to < count : --to >= 0) {
3628            const Span& span = fTs[to];
3629            if (approximately_zero(span.fT - fromSpan.fT)) {
3630                continue;
3631            }
3632            return to;
3633        }
3634        return -1;
3635    }
3636
3637    // FIXME
3638    // this returns at any difference in T, vs. a preset minimum. It may be
3639    // that all callers to nextSpan should use this instead.
3640    // OPTIMIZATION splitting this into separate loops for up/down steps
3641    // would allow using precisely_negative instead of precisely_zero
3642    int nextExactSpan(int from, int step) const {
3643        const Span& fromSpan = fTs[from];
3644        int count = fTs.count();
3645        int to = from;
3646        while (step > 0 ? ++to < count : --to >= 0) {
3647            const Span& span = fTs[to];
3648            if (precisely_zero(span.fT - fromSpan.fT)) {
3649                continue;
3650            }
3651            return to;
3652        }
3653        return -1;
3654    }
3655
3656    bool operand() const {
3657        return fOperand;
3658    }
3659
3660    int oppSign(const Angle* angle) const {
3661        SkASSERT(angle->segment() == this);
3662        return oppSign(angle->start(), angle->end());
3663    }
3664
3665    int oppSign(int startIndex, int endIndex) const {
3666        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue
3667                : fTs[endIndex].fOppValue;
3668#if DEBUG_WIND_BUMP
3669        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
3670#endif
3671        return result;
3672    }
3673
3674    int oppSum(int tIndex) const {
3675        return fTs[tIndex].fOppSum;
3676    }
3677
3678    int oppSum(const Angle* angle) const {
3679        int lesser = SkMin32(angle->start(), angle->end());
3680        return fTs[lesser].fOppSum;
3681    }
3682
3683    int oppValue(int tIndex) const {
3684        return fTs[tIndex].fOppValue;
3685    }
3686
3687    int oppValue(const Angle* angle) const {
3688        int lesser = SkMin32(angle->start(), angle->end());
3689        return fTs[lesser].fOppValue;
3690    }
3691
3692    const SkPoint* pts() const {
3693        return fPts;
3694    }
3695
3696    void reset() {
3697        init(NULL, (SkPath::Verb) -1, false, false);
3698        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
3699        fTs.reset();
3700    }
3701
3702    void setOppXor(bool isOppXor) {
3703        fOppXor = isOppXor;
3704    }
3705
3706    void setSpanT(int index, double t) {
3707        Span& span = fTs[index];
3708        span.fT = t;
3709        span.fOther->fTs[span.fOtherIndex].fOtherT = t;
3710    }
3711
3712    void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
3713        int deltaSum = spanSign(index, endIndex);
3714        maxWinding = sumWinding;
3715        sumWinding = sumWinding -= deltaSum;
3716    }
3717
3718    void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding,
3719            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
3720        int deltaSum = spanSign(index, endIndex);
3721        int oppDeltaSum = oppSign(index, endIndex);
3722        if (operand()) {
3723            maxWinding = sumSuWinding;
3724            sumWinding = sumSuWinding -= deltaSum;
3725            oppMaxWinding = sumMiWinding;
3726            oppSumWinding = sumMiWinding -= oppDeltaSum;
3727        } else {
3728            maxWinding = sumMiWinding;
3729            sumWinding = sumMiWinding -= deltaSum;
3730            oppMaxWinding = sumSuWinding;
3731            oppSumWinding = sumSuWinding -= oppDeltaSum;
3732        }
3733    }
3734
3735    // This marks all spans unsortable so that this info is available for early
3736    // exclusion in find top and others. This could be optimized to only mark
3737    // adjacent spans that unsortable. However, this makes it difficult to later
3738    // determine starting points for edge detection in find top and the like.
3739    static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
3740        bool sortable = true;
3741        int angleCount = angles.count();
3742        int angleIndex;
3743        angleList.setReserve(angleCount);
3744        for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3745            Angle& angle = angles[angleIndex];
3746            *angleList.append() = &angle;
3747            sortable &= !angle.unsortable();
3748        }
3749        if (sortable) {
3750            QSort<Angle>(angleList.begin(), angleList.end() - 1);
3751            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3752                if (angles[angleIndex].unsortable()) {
3753                    sortable = false;
3754                    break;
3755                }
3756            }
3757        }
3758        if (!sortable) {
3759            for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
3760                Angle& angle = angles[angleIndex];
3761                angle.segment()->markUnsortable(angle.start(), angle.end());
3762            }
3763        }
3764        return sortable;
3765    }
3766
3767    // OPTIMIZATION: mark as debugging only if used solely by tests
3768    const Span& span(int tIndex) const {
3769        return fTs[tIndex];
3770    }
3771
3772    int spanSign(const Angle* angle) const {
3773        SkASSERT(angle->segment() == this);
3774        return spanSign(angle->start(), angle->end());
3775    }
3776
3777    int spanSign(int startIndex, int endIndex) const {
3778        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue
3779                : fTs[endIndex].fWindValue;
3780#if DEBUG_WIND_BUMP
3781        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
3782#endif
3783        return result;
3784    }
3785
3786    void subDivide(int start, int end, SkPoint edge[4]) const {
3787        edge[0] = fTs[start].fPt;
3788        edge[fVerb] = fTs[end].fPt;
3789        if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) {
3790            _Point sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[fVerb].fX, edge[fVerb].fY }};
3791            if (fVerb == SkPath::kQuad_Verb) {
3792                MAKE_CONST_QUAD(aQuad, fPts);
3793                edge[1] = sub_divide(aQuad, sub[0], sub[1], fTs[start].fT, fTs[end].fT).asSkPoint();
3794            } else {
3795                MAKE_CONST_CUBIC(aCubic, fPts);
3796                sub_divide(aCubic, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub);
3797                edge[1] = sub[0].asSkPoint();
3798                edge[2] = sub[1].asSkPoint();
3799            }
3800        }
3801    }
3802
3803    // OPTIMIZATION: mark as debugging only if used solely by tests
3804    double t(int tIndex) const {
3805        return fTs[tIndex].fT;
3806    }
3807
3808    double tAtMid(int start, int end, double mid) const {
3809        return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
3810    }
3811
3812    bool tiny(const Angle* angle) const {
3813        int start = angle->start();
3814        int end = angle->end();
3815        const Span& mSpan = fTs[SkMin32(start, end)];
3816        return mSpan.fTiny;
3817    }
3818
3819    static void TrackOutside(SkTDArray<double>& outsideTs, double end,
3820            double start) {
3821        int outCount = outsideTs.count();
3822        if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) {
3823            *outsideTs.append() = end;
3824            *outsideTs.append() = start;
3825        }
3826    }
3827
3828    void undoneSpan(int& start, int& end) {
3829        size_t tCount = fTs.count();
3830        size_t index;
3831        for (index = 0; index < tCount; ++index) {
3832            if (!fTs[index].fDone) {
3833                break;
3834            }
3835        }
3836        SkASSERT(index < tCount - 1);
3837        start = index;
3838        double startT = fTs[index].fT;
3839        while (approximately_negative(fTs[++index].fT - startT))
3840            SkASSERT(index < tCount);
3841        SkASSERT(index < tCount);
3842        end = index;
3843    }
3844
3845    bool unsortable(int index) const {
3846        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
3847    }
3848
3849    void updatePts(const SkPoint pts[]) {
3850        fPts = pts;
3851    }
3852
3853    int updateOppWinding(int index, int endIndex) const {
3854        int lesser = SkMin32(index, endIndex);
3855        int oppWinding = oppSum(lesser);
3856        int oppSpanWinding = oppSign(index, endIndex);
3857        if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWinding)
3858                && oppWinding != SK_MaxS32) {
3859            oppWinding -= oppSpanWinding;
3860        }
3861        return oppWinding;
3862    }
3863
3864    int updateOppWinding(const Angle* angle) const {
3865        int startIndex = angle->start();
3866        int endIndex = angle->end();
3867        return updateOppWinding(endIndex, startIndex);
3868    }
3869
3870    int updateOppWindingReverse(const Angle* angle) const {
3871        int startIndex = angle->start();
3872        int endIndex = angle->end();
3873        return updateOppWinding(startIndex, endIndex);
3874    }
3875
3876    int updateWinding(int index, int endIndex) const {
3877        int lesser = SkMin32(index, endIndex);
3878        int winding = windSum(lesser);
3879        int spanWinding = spanSign(index, endIndex);
3880        if (winding && useInnerWinding(winding - spanWinding, winding) && winding != SK_MaxS32) {
3881            winding -= spanWinding;
3882        }
3883        return winding;
3884    }
3885
3886    int updateWinding(const Angle* angle) const {
3887        int startIndex = angle->start();
3888        int endIndex = angle->end();
3889        return updateWinding(endIndex, startIndex);
3890    }
3891
3892    int updateWindingReverse(const Angle* angle) const {
3893        int startIndex = angle->start();
3894        int endIndex = angle->end();
3895        return updateWinding(startIndex, endIndex);
3896    }
3897
3898    SkPath::Verb verb() const {
3899        return fVerb;
3900    }
3901
3902    int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar& dx) const {
3903        if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard
3904            return SK_MinS32;
3905        }
3906        int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
3907        SkASSERT(winding != SK_MinS32);
3908        int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
3909    #if DEBUG_WINDING_AT_T
3910        SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
3911    #endif
3912        // see if a + change in T results in a +/- change in X (compute x'(T))
3913        dx = (*SegmentDXAtT[fVerb])(fPts, tHit);
3914        if (fVerb > SkPath::kLine_Verb && approximately_zero(dx)) {
3915            dx = fPts[2].fX - fPts[1].fX - dx;
3916        }
3917        if (dx == 0) {
3918    #if DEBUG_WINDING_AT_T
3919            SkDebugf(" dx=0 winding=SK_MinS32\n");
3920    #endif
3921            return SK_MinS32;
3922        }
3923        if (winding * dx > 0) { // if same signs, result is negative
3924            winding += dx > 0 ? -windVal : windVal;
3925        }
3926    #if DEBUG_WINDING_AT_T
3927        SkDebugf(" dx=%c winding=%d\n", dx > 0 ? '+' : '-', winding);
3928    #endif
3929        return winding;
3930    }
3931
3932    int windSum(int tIndex) const {
3933        return fTs[tIndex].fWindSum;
3934    }
3935
3936    int windSum(const Angle* angle) const {
3937        int start = angle->start();
3938        int end = angle->end();
3939        int index = SkMin32(start, end);
3940        return windSum(index);
3941    }
3942
3943    int windValue(int tIndex) const {
3944        return fTs[tIndex].fWindValue;
3945    }
3946
3947    int windValue(const Angle* angle) const {
3948        int start = angle->start();
3949        int end = angle->end();
3950        int index = SkMin32(start, end);
3951        return windValue(index);
3952    }
3953
3954    int windValueAt(double t) const {
3955        int count = fTs.count();
3956        for (int index = 0; index < count; ++index) {
3957            if (fTs[index].fT == t) {
3958                return fTs[index].fWindValue;
3959            }
3960        }
3961        SkASSERT(0);
3962        return 0;
3963    }
3964
3965    SkScalar xAtT(int index) const {
3966        return xAtT(&fTs[index]);
3967    }
3968
3969    SkScalar xAtT(const Span* span) const {
3970        return xyAtT(span).fX;
3971    }
3972
3973    const SkPoint& xyAtT(int index) const {
3974        return xyAtT(&fTs[index]);
3975    }
3976
3977    const SkPoint& xyAtT(const Span* span) const {
3978        if (SkScalarIsNaN(span->fPt.fX)) {
3979            SkASSERT(0); // make sure this path is never used
3980            if (span->fT == 0) {
3981                span->fPt = fPts[0];
3982            } else if (span->fT == 1) {
3983                span->fPt = fPts[fVerb];
3984            } else {
3985                (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt);
3986            }
3987        }
3988        return span->fPt;
3989    }
3990
3991    // used only by right angle winding finding
3992    void xyAtT(double mid, SkPoint& pt) const {
3993        (*SegmentXYAtT[fVerb])(fPts, mid, &pt);
3994    }
3995
3996    SkScalar yAtT(int index) const {
3997        return yAtT(&fTs[index]);
3998    }
3999
4000    SkScalar yAtT(const Span* span) const {
4001        return xyAtT(span).fY;
4002    }
4003
4004    void zeroCoincidentOpp(Span* oTest, int index) {
4005        Span* const test = &fTs[index];
4006        Span* end = test;
4007        do {
4008            end->fOppValue = 0;
4009            end = &fTs[++index];
4010        } while (approximately_negative(end->fT - test->fT));
4011    }
4012
4013    void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT, int oIndex) {
4014        Span* const oTest = &fTs[oIndex];
4015        Span* oEnd = oTest;
4016        const double startT = test->fT;
4017        const double oStartT = oTest->fT;
4018        double otherTMatch = (test->fT - startT) * tRatio + oStartT;
4019        while (!approximately_negative(oEndT - oEnd->fT)
4020                && approximately_negative(oEnd->fT - otherTMatch)) {
4021            oEnd->fOppValue = 0;
4022            oEnd = &fTs[++oIndex];
4023        }
4024    }
4025
4026    void zeroSpan(Span* span) {
4027        SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
4028        span->fWindValue = 0;
4029        span->fOppValue = 0;
4030        SkASSERT(!span->fDone);
4031        span->fDone = true;
4032        ++fDoneSpans;
4033    }
4034
4035#if DEBUG_DUMP
4036    void dump() const {
4037        const char className[] = "Segment";
4038        const int tab = 4;
4039        for (int i = 0; i < fTs.count(); ++i) {
4040            SkPoint out;
4041            (*SegmentXYAtT[fVerb])(fPts, t(i), &out);
4042            SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
4043                    " otherT=%1.9g windSum=%d\n",
4044                    tab + sizeof(className), className, fID,
4045                    kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
4046                    fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
4047        }
4048        SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
4049                tab + sizeof(className), className, fID,
4050                fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
4051    }
4052#endif
4053
4054#if DEBUG_CONCIDENT
4055    // SkASSERT if pair has not already been added
4056     void debugAddTPair(double t, const Segment& other, double otherT) const {
4057        for (int i = 0; i < fTs.count(); ++i) {
4058            if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
4059                return;
4060            }
4061        }
4062        SkASSERT(0);
4063     }
4064#endif
4065
4066#if DEBUG_DUMP
4067    int debugID() const {
4068        return fID;
4069    }
4070#endif
4071
4072#if DEBUG_WINDING
4073    void debugShowSums() const {
4074        SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,
4075            fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);
4076        for (int i = 0; i < fTs.count(); ++i) {
4077            const Span& span = fTs[i];
4078            SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span));
4079            if (span.fWindSum == SK_MinS32) {
4080                SkDebugf("?");
4081            } else {
4082                SkDebugf("%d", span.fWindSum);
4083            }
4084            SkDebugf("]");
4085        }
4086        SkDebugf("\n");
4087    }
4088#endif
4089
4090#if DEBUG_CONCIDENT
4091    void debugShowTs() const {
4092        SkDebugf("%s id=%d", __FUNCTION__, fID);
4093        int lastWind = -1;
4094        int lastOpp = -1;
4095        double lastT = -1;
4096        int i;
4097        for (i = 0; i < fTs.count(); ++i) {
4098            bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
4099                    || lastOpp != fTs[i].fOppValue;
4100            if (change && lastWind >= 0) {
4101                SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
4102                        lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
4103            }
4104            if (change) {
4105                SkDebugf(" [o=%d", fTs[i].fOther->fID);
4106                lastWind = fTs[i].fWindValue;
4107                lastOpp = fTs[i].fOppValue;
4108                lastT = fTs[i].fT;
4109            } else {
4110                SkDebugf(",%d", fTs[i].fOther->fID);
4111            }
4112        }
4113        if (i <= 0) {
4114            return;
4115        }
4116        SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
4117                lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
4118        if (fOperand) {
4119            SkDebugf(" operand");
4120        }
4121        if (done()) {
4122            SkDebugf(" done");
4123        }
4124        SkDebugf("\n");
4125    }
4126#endif
4127
4128#if DEBUG_ACTIVE_SPANS
4129    void debugShowActiveSpans() const {
4130        if (done()) {
4131            return;
4132        }
4133#if DEBUG_ACTIVE_SPANS_SHORT_FORM
4134        int lastId = -1;
4135        double lastT = -1;
4136#endif
4137        for (int i = 0; i < fTs.count(); ++i) {
4138            SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther->
4139                    fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]);
4140            if (fTs[i].fDone) {
4141                continue;
4142            }
4143#if DEBUG_ACTIVE_SPANS_SHORT_FORM
4144            if (lastId == fID && lastT == fTs[i].fT) {
4145                continue;
4146            }
4147            lastId = fID;
4148            lastT = fTs[i].fT;
4149#endif
4150            SkDebugf("%s id=%d", __FUNCTION__, fID);
4151            SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
4152            for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
4153                SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
4154            }
4155            const Span* span = &fTs[i];
4156            SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,
4157                     xAtT(span), yAtT(span));
4158            int iEnd = i + 1;
4159            while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
4160                ++iEnd;
4161            }
4162            SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
4163            const Segment* other = fTs[i].fOther;
4164            SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
4165                    other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
4166            if (fTs[i].fWindSum == SK_MinS32) {
4167                SkDebugf("?");
4168            } else {
4169                SkDebugf("%d", fTs[i].fWindSum);
4170            }
4171            SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
4172        }
4173    }
4174
4175    // This isn't useful yet -- but leaving it in for now in case i think of something
4176    // to use it for
4177    void validateActiveSpans() const {
4178        if (done()) {
4179            return;
4180        }
4181        int tCount = fTs.count();
4182        for (int index = 0; index < tCount; ++index) {
4183            if (fTs[index].fDone) {
4184                continue;
4185            }
4186            // count number of connections which are not done
4187            int first = index;
4188            double baseT = fTs[index].fT;
4189            while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) {
4190                --first;
4191            }
4192            int last = index;
4193            while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) {
4194                ++last;
4195            }
4196            int connections = 0;
4197            connections += first > 0 && !fTs[first - 1].fDone;
4198            for (int test = first; test <= last; ++test) {
4199                connections += !fTs[test].fDone;
4200                const Segment* other = fTs[test].fOther;
4201                int oIndex = fTs[test].fOtherIndex;
4202                connections += !other->fTs[oIndex].fDone;
4203                connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone;
4204            }
4205      //      SkASSERT(!(connections & 1));
4206        }
4207    }
4208#endif
4209
4210#if DEBUG_MARK_DONE
4211    void debugShowNewWinding(const char* fun, const Span& span, int winding) {
4212        const SkPoint& pt = xyAtT(&span);
4213        SkDebugf("%s id=%d", fun, fID);
4214        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
4215        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
4216            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
4217        }
4218        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
4219                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
4220        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=",
4221                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
4222                (&span)[1].fT, winding);
4223        if (span.fWindSum == SK_MinS32) {
4224            SkDebugf("?");
4225        } else {
4226            SkDebugf("%d", span.fWindSum);
4227        }
4228        SkDebugf(" windValue=%d\n", span.fWindValue);
4229    }
4230
4231    void debugShowNewWinding(const char* fun, const Span& span, int winding, int oppWinding) {
4232        const SkPoint& pt = xyAtT(&span);
4233        SkDebugf("%s id=%d", fun, fID);
4234        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
4235        for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
4236            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
4237        }
4238        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
4239                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
4240        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=",
4241                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
4242                (&span)[1].fT, winding, oppWinding);
4243        if (span.fOppSum == SK_MinS32) {
4244            SkDebugf("?");
4245        } else {
4246            SkDebugf("%d", span.fOppSum);
4247        }
4248        SkDebugf(" windSum=");
4249        if (span.fWindSum == SK_MinS32) {
4250            SkDebugf("?");
4251        } else {
4252            SkDebugf("%d", span.fWindSum);
4253        }
4254        SkDebugf(" windValue=%d\n", span.fWindValue);
4255    }
4256#endif
4257
4258#if DEBUG_SORT
4259    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first,
4260            const int contourWinding, const int oppContourWinding) const {
4261        if (--gDebugSortCount < 0) {
4262            return;
4263        }
4264        SkASSERT(angles[first]->segment() == this);
4265        SkASSERT(angles.count() > 1);
4266        int lastSum = contourWinding;
4267        int oppLastSum = oppContourWinding;
4268        const Angle* firstAngle = angles[first];
4269        int windSum = lastSum - spanSign(firstAngle);
4270        int oppoSign = oppSign(firstAngle);
4271        int oppWindSum = oppLastSum - oppoSign;
4272        #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \
4273            else snprintf(x##Str, sizeof(x##Str), "%d", x)
4274        WIND_AS_STRING(contourWinding);
4275        WIND_AS_STRING(oppContourWinding);
4276        SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,
4277                contourWindingStr, oppContourWindingStr, spanSign(angles[first]));
4278        int index = first;
4279        bool firstTime = true;
4280        do {
4281            const Angle& angle = *angles[index];
4282            const Segment& segment = *angle.segment();
4283            int start = angle.start();
4284            int end = angle.end();
4285            const Span& sSpan = segment.fTs[start];
4286            const Span& eSpan = segment.fTs[end];
4287            const Span& mSpan = segment.fTs[SkMin32(start, end)];
4288            bool opp = segment.fOperand ^ fOperand;
4289            if (!firstTime) {
4290                oppoSign = segment.oppSign(&angle);
4291                if (opp) {
4292                    oppLastSum = oppWindSum;
4293                    oppWindSum -= segment.spanSign(&angle);
4294                    if (oppoSign) {
4295                        lastSum = windSum;
4296                        windSum -= oppoSign;
4297                    }
4298                } else {
4299                    lastSum = windSum;
4300                    windSum -= segment.spanSign(&angle);
4301                    if (oppoSign) {
4302                        oppLastSum = oppWindSum;
4303                        oppWindSum -= oppoSign;
4304                    }
4305                }
4306            }
4307            SkDebugf("%s [%d] %s", __FUNCTION__, index,
4308                    angle.unsortable() ? "*** UNSORTABLE *** " : "");
4309        #if COMPACT_DEBUG_SORT
4310            SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)",
4311                    segment.fID, kLVerbStr[segment.fVerb],
4312                    start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
4313                    segment.xAtT(&eSpan), segment.yAtT(&eSpan));
4314        #else
4315            switch (segment.fVerb) {
4316                case SkPath::kLine_Verb:
4317                    SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));
4318                    break;
4319                case SkPath::kQuad_Verb:
4320                    SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));
4321                    break;
4322                case SkPath::kCubic_Verb:
4323                    SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts));
4324                    break;
4325            }
4326            SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);
4327        #endif
4328            SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue);
4329            winding_printf(mSpan.fWindSum);
4330            int last, wind;
4331            if (opp) {
4332                last = oppLastSum;
4333                wind = oppWindSum;
4334            } else {
4335                last = lastSum;
4336                wind = windSum;
4337            }
4338            bool useInner = valid_wind(last) && valid_wind(wind) && useInnerWinding(last, wind);
4339            WIND_AS_STRING(last);
4340            WIND_AS_STRING(wind);
4341            WIND_AS_STRING(lastSum);
4342            WIND_AS_STRING(oppLastSum);
4343            WIND_AS_STRING(windSum);
4344            WIND_AS_STRING(oppWindSum);
4345            #undef WIND_AS_STRING
4346            if (!oppoSign) {
4347                SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr);
4348            } else {
4349                SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,
4350                        opp ? windSumStr : oppWindSumStr);
4351            }
4352            SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp);
4353#if false && DEBUG_ANGLE
4354            angle.debugShow(segment.xyAtT(&sSpan));
4355#endif
4356            ++index;
4357            if (index == angles.count()) {
4358                index = 0;
4359            }
4360            if (firstTime) {
4361                firstTime = false;
4362            }
4363        } while (index != first);
4364    }
4365
4366    void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first) {
4367        const Angle* firstAngle = angles[first];
4368        const Segment* segment = firstAngle->segment();
4369        int winding = segment->updateWinding(firstAngle);
4370        int oppWinding = segment->updateOppWinding(firstAngle);
4371        debugShowSort(fun, angles, first, winding, oppWinding);
4372    }
4373
4374#endif
4375
4376#if DEBUG_WINDING
4377    static char as_digit(int value) {
4378        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
4379    }
4380#endif
4381
4382#if DEBUG_SHOW_WINDING
4383    int debugShowWindingValues(int slotCount, int ofInterest) const {
4384        if (!(1 << fID & ofInterest)) {
4385            return 0;
4386        }
4387        int sum = 0;
4388        SkTDArray<char> slots;
4389        slots.setCount(slotCount * 2);
4390        memset(slots.begin(), ' ', slotCount * 2);
4391        for (int i = 0; i < fTs.count(); ++i) {
4392       //     if (!(1 << fTs[i].fOther->fID & ofInterest)) {
4393       //         continue;
4394       //     }
4395            sum += fTs[i].fWindValue;
4396            slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
4397            sum += fTs[i].fOppValue;
4398            slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
4399        }
4400        SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
4401                slots.begin() + slotCount);
4402        return sum;
4403    }
4404#endif
4405
4406private:
4407    const SkPoint* fPts;
4408    Bounds fBounds;
4409    SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
4410    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
4411    int fDoneSpans; // quick check that segment is finished
4412    // OPTIMIZATION: force the following to be byte-sized
4413    SkPath::Verb fVerb;
4414    bool fOperand;
4415    bool fXor; // set if original contour had even-odd fill
4416    bool fOppXor; // set if opposite operand had even-odd fill
4417#if DEBUG_DUMP
4418    int fID;
4419#endif
4420};
4421
4422class Contour;
4423
4424struct Coincidence {
4425    Contour* fContours[2];
4426    int fSegments[2];
4427    double fTs[2][2];
4428    SkPoint fPts[2];
4429};
4430
4431class Contour {
4432public:
4433    Contour() {
4434        reset();
4435#if DEBUG_DUMP
4436        fID = ++gContourID;
4437#endif
4438    }
4439
4440    bool operator<(const Contour& rh) const {
4441        return fBounds.fTop == rh.fBounds.fTop
4442                ? fBounds.fLeft < rh.fBounds.fLeft
4443                : fBounds.fTop < rh.fBounds.fTop;
4444    }
4445
4446    void addCoincident(int index, Contour* other, int otherIndex,
4447            const Intersections& ts, bool swap) {
4448        Coincidence& coincidence = *fCoincidences.append();
4449        coincidence.fContours[0] = this; // FIXME: no need to store
4450        coincidence.fContours[1] = other;
4451        coincidence.fSegments[0] = index;
4452        coincidence.fSegments[1] = otherIndex;
4453        coincidence.fTs[swap][0] = ts.fT[0][0];
4454        coincidence.fTs[swap][1] = ts.fT[0][1];
4455        coincidence.fTs[!swap][0] = ts.fT[1][0];
4456        coincidence.fTs[!swap][1] = ts.fT[1][1];
4457        coincidence.fPts[0] = ts.fPt[0].asSkPoint();
4458        coincidence.fPts[1] = ts.fPt[1].asSkPoint();
4459    }
4460
4461    void addCross(const Contour* crosser) {
4462#ifdef DEBUG_CROSS
4463        for (int index = 0; index < fCrosses.count(); ++index) {
4464            SkASSERT(fCrosses[index] != crosser);
4465        }
4466#endif
4467        *fCrosses.append() = crosser;
4468    }
4469
4470    void addCubic(const SkPoint pts[4]) {
4471        fSegments.push_back().addCubic(pts, fOperand, fXor);
4472        fContainsCurves = fContainsCubics = true;
4473    }
4474
4475    int addLine(const SkPoint pts[2]) {
4476        fSegments.push_back().addLine(pts, fOperand, fXor);
4477        return fSegments.count();
4478    }
4479
4480    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
4481        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
4482    }
4483
4484    int addQuad(const SkPoint pts[3]) {
4485        fSegments.push_back().addQuad(pts, fOperand, fXor);
4486        fContainsCurves = true;
4487        return fSegments.count();
4488    }
4489
4490    int addT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, double& newT) {
4491        setContainsIntercepts();
4492        return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
4493    }
4494
4495    int addSelfT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, double& newT) {
4496        setContainsIntercepts();
4497        return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT);
4498    }
4499
4500    int addUnsortableT(int segIndex, Contour* other, int otherIndex, bool start,
4501            const SkPoint& pt, double& newT) {
4502        return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT);
4503    }
4504
4505    const Bounds& bounds() const {
4506        return fBounds;
4507    }
4508
4509    void complete() {
4510        setBounds();
4511        fContainsIntercepts = false;
4512    }
4513
4514    bool containsCubics() const {
4515        return fContainsCubics;
4516    }
4517
4518    bool crosses(const Contour* crosser) const {
4519        for (int index = 0; index < fCrosses.count(); ++index) {
4520            if (fCrosses[index] == crosser) {
4521                return true;
4522            }
4523        }
4524        return false;
4525    }
4526
4527    bool done() const {
4528        return fDone;
4529    }
4530
4531    const SkPoint& end() const {
4532        const Segment& segment = fSegments.back();
4533        return segment.pts()[segment.verb()];
4534    }
4535
4536    void findTooCloseToCall() {
4537        int segmentCount = fSegments.count();
4538        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
4539            fSegments[sIndex].findTooCloseToCall();
4540        }
4541    }
4542
4543    void fixOtherTIndex() {
4544        int segmentCount = fSegments.count();
4545        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
4546            fSegments[sIndex].fixOtherTIndex();
4547        }
4548    }
4549
4550    Segment* nonVerticalSegment(int& start, int& end) {
4551        int segmentCount = fSortedSegments.count();
4552        SkASSERT(segmentCount > 0);
4553        for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
4554            Segment* testSegment = fSortedSegments[sortedIndex];
4555            if (testSegment->done()) {
4556                continue;
4557            }
4558            start = end = 0;
4559            while (testSegment->nextCandidate(start, end)) {
4560                if (!testSegment->isVertical(start, end)) {
4561                    return testSegment;
4562                }
4563            }
4564        }
4565        return NULL;
4566    }
4567
4568    bool operand() const {
4569        return fOperand;
4570    }
4571
4572    void reset() {
4573        fSegments.reset();
4574        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
4575        fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;
4576    }
4577
4578    void resolveCoincidence(SkTDArray<Contour*>& contourList) {
4579        int count = fCoincidences.count();
4580        for (int index = 0; index < count; ++index) {
4581            Coincidence& coincidence = fCoincidences[index];
4582            SkASSERT(coincidence.fContours[0] == this);
4583            int thisIndex = coincidence.fSegments[0];
4584            Segment& thisOne = fSegments[thisIndex];
4585            Contour* otherContour = coincidence.fContours[1];
4586            int otherIndex = coincidence.fSegments[1];
4587            Segment& other = otherContour->fSegments[otherIndex];
4588            if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
4589                continue;
4590            }
4591        #if DEBUG_CONCIDENT
4592            thisOne.debugShowTs();
4593            other.debugShowTs();
4594        #endif
4595            double startT = coincidence.fTs[0][0];
4596            double endT = coincidence.fTs[0][1];
4597            bool cancelers = false;
4598            if (startT > endT) {
4599                SkTSwap<double>(startT, endT);
4600                cancelers ^= true; // FIXME: just assign true
4601            }
4602            SkASSERT(!approximately_negative(endT - startT));
4603            double oStartT = coincidence.fTs[1][0];
4604            double oEndT = coincidence.fTs[1][1];
4605            if (oStartT > oEndT) {
4606                SkTSwap<double>(oStartT, oEndT);
4607                cancelers ^= true;
4608            }
4609            SkASSERT(!approximately_negative(oEndT - oStartT));
4610            bool opp = fOperand ^ otherContour->fOperand;
4611            if (cancelers && !opp) {
4612                // make sure startT and endT have t entries
4613                if (startT > 0 || oEndT < 1
4614                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
4615                    thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
4616                }
4617                if (oStartT > 0 || endT < 1
4618                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
4619                    other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
4620                }
4621                if (!thisOne.done() && !other.done()) {
4622                    thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
4623                }
4624            } else {
4625                if (startT > 0 || oStartT > 0
4626                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
4627                    thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
4628                }
4629                if (endT < 1 || oEndT < 1
4630                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
4631                    other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
4632                }
4633                if (!thisOne.done() && !other.done()) {
4634                    thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
4635                }
4636            }
4637        #if DEBUG_CONCIDENT
4638            thisOne.debugShowTs();
4639            other.debugShowTs();
4640        #endif
4641        #if DEBUG_SHOW_WINDING
4642            debugShowWindingValues(contourList);
4643        #endif
4644        }
4645    }
4646
4647    // first pass, add missing T values
4648    // second pass, determine winding values of overlaps
4649    void addCoincidentPoints() {
4650        int count = fCoincidences.count();
4651        for (int index = 0; index < count; ++index) {
4652            Coincidence& coincidence = fCoincidences[index];
4653            SkASSERT(coincidence.fContours[0] == this);
4654            int thisIndex = coincidence.fSegments[0];
4655            Segment& thisOne = fSegments[thisIndex];
4656            Contour* otherContour = coincidence.fContours[1];
4657            int otherIndex = coincidence.fSegments[1];
4658            Segment& other = otherContour->fSegments[otherIndex];
4659            if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
4660                // OPTIMIZATION: remove from array
4661                continue;
4662            }
4663        #if DEBUG_CONCIDENT
4664            thisOne.debugShowTs();
4665            other.debugShowTs();
4666        #endif
4667            double startT = coincidence.fTs[0][0];
4668            double endT = coincidence.fTs[0][1];
4669            bool cancelers;
4670            if ((cancelers = startT > endT)) {
4671                SkTSwap(startT, endT);
4672                SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
4673            }
4674            SkASSERT(!approximately_negative(endT - startT));
4675            double oStartT = coincidence.fTs[1][0];
4676            double oEndT = coincidence.fTs[1][1];
4677            if (oStartT > oEndT) {
4678                SkTSwap<double>(oStartT, oEndT);
4679                cancelers ^= true;
4680            }
4681            SkASSERT(!approximately_negative(oEndT - oStartT));
4682            bool opp = fOperand ^ otherContour->fOperand;
4683            if (cancelers && !opp) {
4684                // make sure startT and endT have t entries
4685                if (startT > 0 || oEndT < 1
4686                        || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
4687                    thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
4688                }
4689                if (oStartT > 0 || endT < 1
4690                        || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
4691                    other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
4692                }
4693            } else {
4694                if (startT > 0 || oStartT > 0
4695                        || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
4696                    thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
4697                }
4698                if (endT < 1 || oEndT < 1
4699                        || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
4700                    other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
4701                }
4702            }
4703        #if DEBUG_CONCIDENT
4704            thisOne.debugShowTs();
4705            other.debugShowTs();
4706        #endif
4707        }
4708    }
4709
4710    void calcCoincidentWinding() {
4711        int count = fCoincidences.count();
4712        for (int index = 0; index < count; ++index) {
4713            Coincidence& coincidence = fCoincidences[index];
4714            SkASSERT(coincidence.fContours[0] == this);
4715            int thisIndex = coincidence.fSegments[0];
4716            Segment& thisOne = fSegments[thisIndex];
4717            if (thisOne.done()) {
4718                continue;
4719            }
4720            Contour* otherContour = coincidence.fContours[1];
4721            int otherIndex = coincidence.fSegments[1];
4722            Segment& other = otherContour->fSegments[otherIndex];
4723            if (other.done()) {
4724                continue;
4725            }
4726            double startT = coincidence.fTs[0][0];
4727            double endT = coincidence.fTs[0][1];
4728            bool cancelers;
4729            if ((cancelers = startT > endT)) {
4730                SkTSwap<double>(startT, endT);
4731            }
4732            SkASSERT(!approximately_negative(endT - startT));
4733            double oStartT = coincidence.fTs[1][0];
4734            double oEndT = coincidence.fTs[1][1];
4735            if (oStartT > oEndT) {
4736                SkTSwap<double>(oStartT, oEndT);
4737                cancelers ^= true;
4738            }
4739            SkASSERT(!approximately_negative(oEndT - oStartT));
4740            bool opp = fOperand ^ otherContour->fOperand;
4741            if (cancelers && !opp) {
4742                // make sure startT and endT have t entries
4743                if (!thisOne.done() && !other.done()) {
4744                    thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
4745                }
4746            } else {
4747                if (!thisOne.done() && !other.done()) {
4748                    thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
4749                }
4750            }
4751        #if DEBUG_CONCIDENT
4752            thisOne.debugShowTs();
4753            other.debugShowTs();
4754        #endif
4755        }
4756    }
4757
4758    SkTArray<Segment>& segments() {
4759        return fSegments;
4760    }
4761
4762    void setContainsIntercepts() {
4763        fContainsIntercepts = true;
4764    }
4765
4766    void setOperand(bool isOp) {
4767        fOperand = isOp;
4768    }
4769
4770    void setOppXor(bool isOppXor) {
4771        fOppXor = isOppXor;
4772        int segmentCount = fSegments.count();
4773        for (int test = 0; test < segmentCount; ++test) {
4774            fSegments[test].setOppXor(isOppXor);
4775        }
4776    }
4777
4778    void setXor(bool isXor) {
4779        fXor = isXor;
4780    }
4781
4782    void sortSegments() {
4783        int segmentCount = fSegments.count();
4784        fSortedSegments.setReserve(segmentCount);
4785        for (int test = 0; test < segmentCount; ++test) {
4786            *fSortedSegments.append() = &fSegments[test];
4787        }
4788        QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
4789        fFirstSorted = 0;
4790    }
4791
4792    const SkPoint& start() const {
4793        return fSegments.front().pts()[0];
4794    }
4795
4796    void toPath(PathWrapper& path) const {
4797        int segmentCount = fSegments.count();
4798        const SkPoint& pt = fSegments.front().pts()[0];
4799        path.deferredMove(pt);
4800        for (int test = 0; test < segmentCount; ++test) {
4801            fSegments[test].addCurveTo(0, 1, path, true);
4802        }
4803        path.close();
4804    }
4805
4806    void toPartialBackward(PathWrapper& path) const {
4807        int segmentCount = fSegments.count();
4808        for (int test = segmentCount - 1; test >= 0; --test) {
4809            fSegments[test].addCurveTo(1, 0, path, true);
4810        }
4811    }
4812
4813    void toPartialForward(PathWrapper& path) const {
4814        int segmentCount = fSegments.count();
4815        for (int test = 0; test < segmentCount; ++test) {
4816            fSegments[test].addCurveTo(0, 1, path, true);
4817        }
4818    }
4819
4820    void topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, Segment*& topStart) {
4821        int segmentCount = fSortedSegments.count();
4822        SkASSERT(segmentCount > 0);
4823        int sortedIndex = fFirstSorted;
4824        fDone = true; // may be cleared below
4825        for ( ; sortedIndex < segmentCount; ++sortedIndex) {
4826            Segment* testSegment = fSortedSegments[sortedIndex];
4827            if (testSegment->done()) {
4828                if (sortedIndex == fFirstSorted) {
4829                    ++fFirstSorted;
4830                }
4831                continue;
4832            }
4833            fDone = false;
4834            SkPoint testXY = testSegment->activeLeftTop(true, NULL);
4835            if (topStart) {
4836                if (testXY.fY < topLeft.fY) {
4837                    continue;
4838                }
4839                if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
4840                    continue;
4841                }
4842                if (bestXY.fY < testXY.fY) {
4843                    continue;
4844                }
4845                if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) {
4846                    continue;
4847                }
4848            }
4849            topStart = testSegment;
4850            bestXY = testXY;
4851        }
4852    }
4853
4854    Segment* undoneSegment(int& start, int& end) {
4855        int segmentCount = fSegments.count();
4856        for (int test = 0; test < segmentCount; ++test) {
4857            Segment* testSegment = &fSegments[test];
4858            if (testSegment->done()) {
4859                continue;
4860            }
4861            testSegment->undoneSpan(start, end);
4862            return testSegment;
4863        }
4864        return NULL;
4865    }
4866
4867    int updateSegment(int index, const SkPoint* pts) {
4868        Segment& segment = fSegments[index];
4869        segment.updatePts(pts);
4870        return segment.verb() + 1;
4871    }
4872
4873#if DEBUG_TEST
4874    SkTArray<Segment>& debugSegments() {
4875        return fSegments;
4876    }
4877#endif
4878
4879#if DEBUG_DUMP
4880    void dump() {
4881        int i;
4882        const char className[] = "Contour";
4883        const int tab = 4;
4884        SkDebugf("%s %p (contour=%d)\n", className, this, fID);
4885        for (i = 0; i < fSegments.count(); ++i) {
4886            SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
4887                    className, i);
4888            fSegments[i].dump();
4889        }
4890        SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
4891                tab + sizeof(className), className,
4892                fBounds.fLeft, fBounds.fTop,
4893                fBounds.fRight, fBounds.fBottom);
4894        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
4895                className, fContainsIntercepts);
4896        SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
4897                className, fContainsCurves);
4898    }
4899#endif
4900
4901#if DEBUG_ACTIVE_SPANS
4902    void debugShowActiveSpans() {
4903        for (int index = 0; index < fSegments.count(); ++index) {
4904            fSegments[index].debugShowActiveSpans();
4905        }
4906    }
4907
4908    void validateActiveSpans() {
4909        for (int index = 0; index < fSegments.count(); ++index) {
4910            fSegments[index].validateActiveSpans();
4911        }
4912    }
4913#endif
4914
4915#if DEBUG_SHOW_WINDING
4916    int debugShowWindingValues(int totalSegments, int ofInterest) {
4917        int count = fSegments.count();
4918        int sum = 0;
4919        for (int index = 0; index < count; ++index) {
4920            sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
4921        }
4922  //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
4923        return sum;
4924    }
4925
4926    static void debugShowWindingValues(SkTDArray<Contour*>& contourList) {
4927   //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
4928    //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
4929        int ofInterest = 1 << 5 | 1 << 8;
4930        int total = 0;
4931        int index;
4932        for (index = 0; index < contourList.count(); ++index) {
4933            total += contourList[index]->segments().count();
4934        }
4935        int sum = 0;
4936        for (index = 0; index < contourList.count(); ++index) {
4937            sum += contourList[index]->debugShowWindingValues(total, ofInterest);
4938        }
4939 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
4940    }
4941#endif
4942
4943protected:
4944    void setBounds() {
4945        int count = fSegments.count();
4946        if (count == 0) {
4947            SkDebugf("%s empty contour\n", __FUNCTION__);
4948            SkASSERT(0);
4949            // FIXME: delete empty contour?
4950            return;
4951        }
4952        fBounds = fSegments.front().bounds();
4953        for (int index = 1; index < count; ++index) {
4954            fBounds.add(fSegments[index].bounds());
4955        }
4956    }
4957
4958private:
4959    SkTArray<Segment> fSegments;
4960    SkTDArray<Segment*> fSortedSegments;
4961    int fFirstSorted;
4962    SkTDArray<Coincidence> fCoincidences;
4963    SkTDArray<const Contour*> fCrosses;
4964    Bounds fBounds;
4965    bool fContainsIntercepts; // FIXME: is this used by anybody?
4966    bool fContainsCubics;
4967    bool fContainsCurves;
4968    bool fDone;
4969    bool fOperand; // true for the second argument to a binary operator
4970    bool fXor;
4971    bool fOppXor;
4972#if DEBUG_DUMP
4973    int fID;
4974#endif
4975};
4976
4977class EdgeBuilder {
4978public:
4979
4980EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours)
4981    : fPath(path.nativePath())
4982    , fContours(contours)
4983{
4984    init();
4985}
4986
4987EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours)
4988    : fPath(&path)
4989    , fContours(contours)
4990{
4991    init();
4992}
4993
4994void init() {
4995    fCurrentContour = NULL;
4996    fOperand = false;
4997    fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
4998#if DEBUG_DUMP
4999    gContourID = 0;
5000    gSegmentID = 0;
5001#endif
5002    fSecondHalf = preFetch();
5003}
5004
5005void addOperand(const SkPath& path) {
5006    SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
5007    fPathVerbs.pop();
5008    fPath = &path;
5009    fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask;
5010    preFetch();
5011}
5012
5013void finish() {
5014    walk();
5015    complete();
5016    if (fCurrentContour && !fCurrentContour->segments().count()) {
5017        fContours.pop_back();
5018    }
5019    // correct pointers in contours since fReducePts may have moved as it grew
5020    int cIndex = 0;
5021    int extraCount = fExtra.count();
5022    SkASSERT(extraCount == 0 || fExtra[0] == -1);
5023    int eIndex = 0;
5024    int rIndex = 0;
5025    while (++eIndex < extraCount) {
5026        int offset = fExtra[eIndex];
5027        if (offset < 0) {
5028            ++cIndex;
5029            continue;
5030        }
5031        fCurrentContour = &fContours[cIndex];
5032        rIndex += fCurrentContour->updateSegment(offset - 1,
5033                &fReducePts[rIndex]);
5034    }
5035    fExtra.reset(); // we're done with this
5036}
5037
5038ShapeOpMask xorMask() const {
5039    return fXorMask[fOperand];
5040}
5041
5042protected:
5043
5044void complete() {
5045    if (fCurrentContour && fCurrentContour->segments().count()) {
5046        fCurrentContour->complete();
5047        fCurrentContour = NULL;
5048    }
5049}
5050
5051// FIXME:remove once we can access path pts directly
5052int preFetch() {
5053    SkPath::RawIter iter(*fPath); // FIXME: access path directly when allowed
5054    SkPoint pts[4];
5055    SkPath::Verb verb;
5056    do {
5057        verb = iter.next(pts);
5058        *fPathVerbs.append() = verb;
5059        if (verb == SkPath::kMove_Verb) {
5060            *fPathPts.append() = pts[0];
5061        } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
5062            fPathPts.append(verb, &pts[1]);
5063        }
5064    } while (verb != SkPath::kDone_Verb);
5065    return fPathVerbs.count() - 1;
5066}
5067
5068void walk() {
5069    SkPath::Verb reducedVerb;
5070    uint8_t* verbPtr = fPathVerbs.begin();
5071    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
5072    const SkPoint* pointsPtr = fPathPts.begin();
5073    const SkPoint* finalCurveStart = NULL;
5074    const SkPoint* finalCurveEnd = NULL;
5075    SkPath::Verb verb;
5076    while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) {
5077        switch (verb) {
5078            case SkPath::kMove_Verb:
5079                complete();
5080                if (!fCurrentContour) {
5081                    fCurrentContour = fContours.push_back_n(1);
5082                    fCurrentContour->setOperand(fOperand);
5083                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_Mask);
5084                    *fExtra.append() = -1; // start new contour
5085                }
5086                finalCurveEnd = pointsPtr++;
5087                goto nextVerb;
5088            case SkPath::kLine_Verb:
5089                // skip degenerate points
5090                if (pointsPtr[-1].fX != pointsPtr[0].fX
5091                        || pointsPtr[-1].fY != pointsPtr[0].fY) {
5092                    fCurrentContour->addLine(&pointsPtr[-1]);
5093                }
5094                break;
5095            case SkPath::kQuad_Verb:
5096
5097                reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts);
5098                if (reducedVerb == 0) {
5099                    break; // skip degenerate points
5100                }
5101                if (reducedVerb == 1) {
5102                    *fExtra.append() =
5103                            fCurrentContour->addLine(fReducePts.end() - 2);
5104                    break;
5105                }
5106                fCurrentContour->addQuad(&pointsPtr[-1]);
5107                break;
5108            case SkPath::kCubic_Verb:
5109                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
5110                if (reducedVerb == 0) {
5111                    break; // skip degenerate points
5112                }
5113                if (reducedVerb == 1) {
5114                    *fExtra.append() =
5115                            fCurrentContour->addLine(fReducePts.end() - 2);
5116                    break;
5117                }
5118                if (reducedVerb == 2) {
5119                    *fExtra.append() =
5120                            fCurrentContour->addQuad(fReducePts.end() - 3);
5121                    break;
5122                }
5123                fCurrentContour->addCubic(&pointsPtr[-1]);
5124                break;
5125            case SkPath::kClose_Verb:
5126                SkASSERT(fCurrentContour);
5127                if (finalCurveStart && finalCurveEnd
5128                        && *finalCurveStart != *finalCurveEnd) {
5129                    *fReducePts.append() = *finalCurveStart;
5130                    *fReducePts.append() = *finalCurveEnd;
5131                    *fExtra.append() =
5132                            fCurrentContour->addLine(fReducePts.end() - 2);
5133                }
5134                complete();
5135                goto nextVerb;
5136            default:
5137                SkDEBUGFAIL("bad verb");
5138                return;
5139        }
5140        finalCurveStart = &pointsPtr[verb - 1];
5141        pointsPtr += verb;
5142        SkASSERT(fCurrentContour);
5143    nextVerb:
5144        if (verbPtr == endOfFirstHalf) {
5145            fOperand = true;
5146        }
5147    }
5148}
5149
5150private:
5151    const SkPath* fPath;
5152    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
5153    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
5154    Contour* fCurrentContour;
5155    SkTArray<Contour>& fContours;
5156    SkTDArray<SkPoint> fReducePts; // segments created on the fly
5157    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
5158    ShapeOpMask fXorMask[2];
5159    int fSecondHalf;
5160    bool fOperand;
5161};
5162
5163class Work {
5164public:
5165    enum SegmentType {
5166        kHorizontalLine_Segment = -1,
5167        kVerticalLine_Segment = 0,
5168        kLine_Segment = SkPath::kLine_Verb,
5169        kQuad_Segment = SkPath::kQuad_Verb,
5170        kCubic_Segment = SkPath::kCubic_Verb,
5171    };
5172
5173    void addCoincident(Work& other, const Intersections& ts, bool swap) {
5174        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
5175    }
5176
5177    // FIXME: does it make sense to write otherIndex now if we're going to
5178    // fix it up later?
5179    void addOtherT(int index, double otherT, int otherIndex) {
5180        fContour->addOtherT(fIndex, index, otherT, otherIndex);
5181    }
5182
5183    // Avoid collapsing t values that are close to the same since
5184    // we walk ts to describe consecutive intersections. Since a pair of ts can
5185    // be nearly equal, any problems caused by this should be taken care
5186    // of later.
5187    // On the edge or out of range values are negative; add 2 to get end
5188    int addT(const Work& other, const SkPoint& pt, double& newT) {
5189        return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
5190    }
5191
5192    int addSelfT(const Work& other, const SkPoint& pt, double& newT) {
5193        return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT);
5194    }
5195
5196    int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) {
5197        return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT);
5198    }
5199
5200    bool advance() {
5201        return ++fIndex < fLast;
5202    }
5203
5204    SkScalar bottom() const {
5205        return bounds().fBottom;
5206    }
5207
5208    const Bounds& bounds() const {
5209        return fContour->segments()[fIndex].bounds();
5210    }
5211
5212#if !APPROXIMATE_CUBICS
5213    const SkPoint* cubic() const {
5214        return fCubic;
5215    }
5216#endif
5217
5218    void init(Contour* contour) {
5219        fContour = contour;
5220        fIndex = 0;
5221        fLast = contour->segments().count();
5222    }
5223
5224    bool isAdjacent(const Work& next) {
5225        return fContour == next.fContour && fIndex + 1 == next.fIndex;
5226    }
5227
5228    bool isFirstLast(const Work& next) {
5229        return fContour == next.fContour && fIndex == 0
5230                && next.fIndex == fLast - 1;
5231    }
5232
5233    SkScalar left() const {
5234        return bounds().fLeft;
5235    }
5236
5237#if !APPROXIMATE_CUBICS
5238    void promoteToCubic() {
5239        fCubic[0] = pts()[0];
5240        fCubic[2] = pts()[1];
5241        fCubic[3] = pts()[2];
5242        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
5243        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
5244        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
5245        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
5246    }
5247#endif
5248
5249    const SkPoint* pts() const {
5250        return fContour->segments()[fIndex].pts();
5251    }
5252
5253    SkScalar right() const {
5254        return bounds().fRight;
5255    }
5256
5257    ptrdiff_t segmentIndex() const {
5258        return fIndex;
5259    }
5260
5261    SegmentType segmentType() const {
5262        const Segment& segment = fContour->segments()[fIndex];
5263        SegmentType type = (SegmentType) segment.verb();
5264        if (type != kLine_Segment) {
5265            return type;
5266        }
5267        if (segment.isHorizontal()) {
5268            return kHorizontalLine_Segment;
5269        }
5270        if (segment.isVertical()) {
5271            return kVerticalLine_Segment;
5272        }
5273        return kLine_Segment;
5274    }
5275
5276    bool startAfter(const Work& after) {
5277        fIndex = after.fIndex;
5278        return advance();
5279    }
5280
5281    SkScalar top() const {
5282        return bounds().fTop;
5283    }
5284
5285    SkPath::Verb verb() const {
5286        return fContour->segments()[fIndex].verb();
5287    }
5288
5289    SkScalar x() const {
5290        return bounds().fLeft;
5291    }
5292
5293    bool xFlipped() const {
5294        return x() != pts()[0].fX;
5295    }
5296
5297    SkScalar y() const {
5298        return bounds().fTop;
5299    }
5300
5301    bool yFlipped() const {
5302        return y() != pts()[0].fY;
5303    }
5304
5305protected:
5306    Contour* fContour;
5307#if !APPROXIMATE_CUBICS
5308    SkPoint fCubic[4];
5309#endif
5310    int fIndex;
5311    int fLast;
5312};
5313
5314#if DEBUG_ADD_INTERSECTING_TS
5315
5316static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn,
5317        const Intersections& i) {
5318    SkASSERT(i.used() == pts);
5319    if (!pts) {
5320        SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
5321                __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5322        return;
5323    }
5324    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5325            i.fT[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5326    if (pts == 2) {
5327        SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i.fT[0][1], PT_DEBUG_DATA(i, 1));
5328    }
5329    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5330    if (pts == 2) {
5331        SkDebugf(" " T_DEBUG_STR(wnTs, 1), i.fT[1][1]);
5332    }
5333    SkDebugf("\n");
5334}
5335
5336static void debugShowQuadLineIntersection(int pts, const Work& wt,
5337        const Work& wn, const Intersections& i) {
5338    SkASSERT(i.used() == pts);
5339    if (!pts) {
5340        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
5341                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5342        return;
5343    }
5344    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5345            i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5346    for (int n = 1; n < pts; ++n) {
5347        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5348    }
5349    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5350    for (int n = 1; n < pts; ++n) {
5351        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5352    }
5353    SkDebugf("\n");
5354}
5355
5356static void debugShowQuadIntersection(int pts, const Work& wt,
5357        const Work& wn, const Intersections& i) {
5358    SkASSERT(i.used() == pts);
5359    if (!pts) {
5360        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
5361                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
5362        return;
5363    }
5364    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5365            i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5366    for (int n = 1; n < pts; ++n) {
5367        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5368    }
5369    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts()));
5370    for (int n = 1; n < pts; ++n) {
5371        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5372    }
5373    SkDebugf("\n");
5374}
5375
5376static void debugShowCubicLineIntersection(int pts, const Work& wt,
5377        const Work& wn, const Intersections& i) {
5378    SkASSERT(i.used() == pts);
5379    if (!pts) {
5380        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
5381                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5382        return;
5383    }
5384    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5385            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5386    for (int n = 1; n < pts; ++n) {
5387        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5388    }
5389    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5390    for (int n = 1; n < pts; ++n) {
5391        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5392    }
5393    SkDebugf("\n");
5394}
5395
5396static void debugShowCubicQuadIntersection(int pts, const Work& wt,
5397        const Work& wn, const Intersections& i) {
5398    SkASSERT(i.used() == pts);
5399    if (!pts) {
5400        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
5401                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
5402        return;
5403    }
5404    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5405            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5406    for (int n = 1; n < pts; ++n) {
5407        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5408    }
5409    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts()));
5410    for (int n = 1; n < pts; ++n) {
5411        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5412    }
5413    SkDebugf("\n");
5414}
5415
5416static void debugShowCubicIntersection(int pts, const Work& wt,
5417        const Work& wn, const Intersections& i) {
5418    SkASSERT(i.used() == pts);
5419    if (!pts) {
5420        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
5421                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
5422        return;
5423    }
5424    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5425            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5426    for (int n = 1; n < pts; ++n) {
5427        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5428    }
5429    SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i.fT[1][0], CUBIC_DEBUG_DATA(wn.pts()));
5430    for (int n = 1; n < pts; ++n) {
5431        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5432    }
5433    SkDebugf("\n");
5434}
5435
5436static void debugShowCubicIntersection(int pts, const Work& wt, const Intersections& i) {
5437    SkASSERT(i.used() == pts);
5438    if (!pts) {
5439        SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,
5440                CUBIC_DEBUG_DATA(wt.pts()));
5441        return;
5442    }
5443    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5444            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5445    SkDebugf(" " T_DEBUG_STR(wtTs, 1), i.fT[1][0]);
5446    SkDebugf("\n");
5447}
5448
5449#else
5450static void debugShowLineIntersection(int , const Work& , const Work& , const Intersections& ) {
5451}
5452
5453static void debugShowQuadLineIntersection(int , const Work& , const Work& , const Intersections& ) {
5454}
5455
5456static void debugShowQuadIntersection(int , const Work& , const Work& , const Intersections& ) {
5457}
5458
5459static void debugShowCubicLineIntersection(int , const Work& , const Work& ,
5460        const Intersections& ) {
5461}
5462
5463static void debugShowCubicQuadIntersection(int , const Work& , const Work& ,
5464        const Intersections& ) {
5465}
5466
5467static void debugShowCubicIntersection(int , const Work& , const Work& , const Intersections& ) {
5468}
5469
5470static void debugShowCubicIntersection(int , const Work& , const Intersections& ) {
5471}
5472#endif
5473
5474static bool addIntersectTs(Contour* test, Contour* next) {
5475
5476    if (test != next) {
5477        if (test->bounds().fBottom < next->bounds().fTop) {
5478            return false;
5479        }
5480        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
5481            return true;
5482        }
5483    }
5484    Work wt;
5485    wt.init(test);
5486    bool foundCommonContour = test == next;
5487    do {
5488        Work wn;
5489        wn.init(next);
5490        if (test == next && !wn.startAfter(wt)) {
5491            continue;
5492        }
5493        do {
5494            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
5495                continue;
5496            }
5497            int pts;
5498            Intersections ts;
5499            bool swap = false;
5500            switch (wt.segmentType()) {
5501                case Work::kHorizontalLine_Segment:
5502                    swap = true;
5503                    switch (wn.segmentType()) {
5504                        case Work::kHorizontalLine_Segment:
5505                        case Work::kVerticalLine_Segment:
5506                        case Work::kLine_Segment: {
5507                            pts = HLineIntersect(wn.pts(), wt.left(),
5508                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5509                            debugShowLineIntersection(pts, wt, wn, ts);
5510                            break;
5511                        }
5512                        case Work::kQuad_Segment: {
5513                            pts = HQuadIntersect(wn.pts(), wt.left(),
5514                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5515                            break;
5516                        }
5517                        case Work::kCubic_Segment: {
5518                            pts = HCubicIntersect(wn.pts(), wt.left(),
5519                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5520                            debugShowCubicLineIntersection(pts, wn, wt, ts);
5521                            break;
5522                        }
5523                        default:
5524                            SkASSERT(0);
5525                    }
5526                    break;
5527                case Work::kVerticalLine_Segment:
5528                    swap = true;
5529                    switch (wn.segmentType()) {
5530                        case Work::kHorizontalLine_Segment:
5531                        case Work::kVerticalLine_Segment:
5532                        case Work::kLine_Segment: {
5533                            pts = VLineIntersect(wn.pts(), wt.top(),
5534                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5535                            debugShowLineIntersection(pts, wt, wn, ts);
5536                            break;
5537                        }
5538                        case Work::kQuad_Segment: {
5539                            pts = VQuadIntersect(wn.pts(), wt.top(),
5540                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5541                            break;
5542                        }
5543                        case Work::kCubic_Segment: {
5544                            pts = VCubicIntersect(wn.pts(), wt.top(),
5545                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5546                            debugShowCubicLineIntersection(pts, wn, wt, ts);
5547                            break;
5548                        }
5549                        default:
5550                            SkASSERT(0);
5551                    }
5552                    break;
5553                case Work::kLine_Segment:
5554                    switch (wn.segmentType()) {
5555                        case Work::kHorizontalLine_Segment:
5556                            pts = HLineIntersect(wt.pts(), wn.left(),
5557                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5558                            debugShowLineIntersection(pts, wt, wn, ts);
5559                            break;
5560                        case Work::kVerticalLine_Segment:
5561                            pts = VLineIntersect(wt.pts(), wn.top(),
5562                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5563                            debugShowLineIntersection(pts, wt, wn, ts);
5564                            break;
5565                        case Work::kLine_Segment: {
5566                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
5567                            debugShowLineIntersection(pts, wt, wn, ts);
5568                            break;
5569                        }
5570                        case Work::kQuad_Segment: {
5571                            swap = true;
5572                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
5573                            debugShowQuadLineIntersection(pts, wn, wt, ts);
5574                            break;
5575                        }
5576                        case Work::kCubic_Segment: {
5577                            swap = true;
5578                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
5579                            debugShowCubicLineIntersection(pts, wn, wt,  ts);
5580                            break;
5581                        }
5582                        default:
5583                            SkASSERT(0);
5584                    }
5585                    break;
5586                case Work::kQuad_Segment:
5587                    switch (wn.segmentType()) {
5588                        case Work::kHorizontalLine_Segment:
5589                            pts = HQuadIntersect(wt.pts(), wn.left(),
5590                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5591                            break;
5592                        case Work::kVerticalLine_Segment:
5593                            pts = VQuadIntersect(wt.pts(), wn.top(),
5594                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5595                            break;
5596                        case Work::kLine_Segment: {
5597                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
5598                            debugShowQuadLineIntersection(pts, wt, wn, ts);
5599                            break;
5600                        }
5601                        case Work::kQuad_Segment: {
5602                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
5603                            debugShowQuadIntersection(pts, wt, wn, ts);
5604                            break;
5605                        }
5606                        case Work::kCubic_Segment: {
5607                    #if APPROXIMATE_CUBICS
5608                            swap = true;
5609                            pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts);
5610                            debugShowCubicQuadIntersection(pts, wn, wt, ts);
5611                    #else
5612                            wt.promoteToCubic();
5613                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
5614                            debugShowCubicIntersection(pts, wt, wn, ts);
5615                    #endif
5616                            break;
5617                        }
5618                        default:
5619                            SkASSERT(0);
5620                    }
5621                    break;
5622                case Work::kCubic_Segment:
5623                    switch (wn.segmentType()) {
5624                        case Work::kHorizontalLine_Segment:
5625                            pts = HCubicIntersect(wt.pts(), wn.left(),
5626                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5627                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5628                            break;
5629                        case Work::kVerticalLine_Segment:
5630                            pts = VCubicIntersect(wt.pts(), wn.top(),
5631                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5632                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5633                            break;
5634                        case Work::kLine_Segment: {
5635                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
5636                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5637                            break;
5638                        }
5639                        case Work::kQuad_Segment: {
5640                    #if APPROXIMATE_CUBICS
5641                            pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts);
5642                            debugShowCubicQuadIntersection(pts, wt, wn, ts);
5643                    #else
5644                            wn.promoteToCubic();
5645                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
5646                            debugShowCubicIntersection(pts, wt, wn, ts);
5647                    #endif
5648                            break;
5649                        }
5650                        case Work::kCubic_Segment: {
5651                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
5652                            debugShowCubicIntersection(pts, wt, wn, ts);
5653                            break;
5654                        }
5655                        default:
5656                            SkASSERT(0);
5657                    }
5658                    break;
5659                default:
5660                    SkASSERT(0);
5661            }
5662            if (!foundCommonContour && pts > 0) {
5663                test->addCross(next);
5664                next->addCross(test);
5665                foundCommonContour = true;
5666            }
5667            // in addition to recording T values, record matching segment
5668            if (ts.unsortable()) {
5669                bool start = true;
5670                for (int pt = 0; pt < ts.used(); ++pt) {
5671                    // FIXME: if unsortable, the other points to the original. This logic is
5672                    // untested downstream.
5673                    SkPoint point = ts.fPt[pt].asSkPoint();
5674                    int testTAt = wt.addUnsortableT(wt, start, point, ts.fT[swap][pt]);
5675                    wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt);
5676                    testTAt = wn.addUnsortableT(wn, start ^ ts.fFlip, point, ts.fT[!swap][pt]);
5677                    wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt);
5678                    start ^= true;
5679                }
5680                continue;
5681            }
5682            if (pts == 2) {
5683                if (wn.segmentType() <= Work::kLine_Segment
5684                        && wt.segmentType() <= Work::kLine_Segment) {
5685                    wt.addCoincident(wn, ts, swap);
5686                    continue;
5687                }
5688                if (wn.segmentType() >= Work::kQuad_Segment
5689                        && wt.segmentType() >= Work::kQuad_Segment
5690                        && ts.fIsCoincident[0]) {
5691                    SkASSERT(ts.coincidentUsed() == 2);
5692                    wt.addCoincident(wn, ts, swap);
5693                    continue;
5694                }
5695
5696            }
5697            for (int pt = 0; pt < pts; ++pt) {
5698                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
5699                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
5700                SkPoint point = ts.fPt[pt].asSkPoint();
5701                int testTAt = wt.addT(wn, point, ts.fT[swap][pt]);
5702                int nextTAt = wn.addT(wt, point, ts.fT[!swap][pt]);
5703                wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
5704                wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
5705            }
5706        } while (wn.advance());
5707    } while (wt.advance());
5708    return true;
5709}
5710
5711static void addSelfIntersectTs(Contour* test) {
5712    Work wt;
5713    wt.init(test);
5714    do {
5715        if (wt.segmentType() != Work::kCubic_Segment) {
5716            continue;
5717        }
5718        Intersections ts;
5719        int pts = CubicIntersect(wt.pts(), ts);
5720        debugShowCubicIntersection(pts, wt, ts);
5721        if (!pts) {
5722            continue;
5723        }
5724        SkASSERT(pts == 1);
5725        SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1);
5726        SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1);
5727        SkPoint point = ts.fPt[0].asSkPoint();
5728        int testTAt = wt.addSelfT(wt, point, ts.fT[0][0]);
5729        int nextTAt = wt.addT(wt, point, ts.fT[1][0]);
5730        wt.addOtherT(testTAt, ts.fT[1][0], nextTAt);
5731        wt.addOtherT(nextTAt, ts.fT[0][0], testTAt);
5732    } while (wt.advance());
5733}
5734
5735// resolve any coincident pairs found while intersecting, and
5736// see if coincidence is formed by clipping non-concident segments
5737static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {
5738    int contourCount = contourList.count();
5739#if ONE_PASS_COINCIDENCE_CHECK
5740    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5741        Contour* contour = contourList[cIndex];
5742        contour->resolveCoincidence(contourList);
5743    }
5744#else
5745    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5746        Contour* contour = contourList[cIndex];
5747        contour->addCoincidentPoints();
5748    }
5749    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5750        Contour* contour = contourList[cIndex];
5751        contour->calcCoincidentWinding();
5752    }
5753#endif
5754    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5755        Contour* contour = contourList[cIndex];
5756        contour->findTooCloseToCall();
5757    }
5758}
5759
5760static int contourRangeCheckY(SkTDArray<Contour*>& contourList,  Segment*& current, int& index,
5761        int& endIndex, double& bestHit, SkScalar& bestDx, bool& tryAgain, double& mid, bool opp) {
5762    SkPoint basePt;
5763    double tAtMid = current->tAtMid(index, endIndex, mid);
5764    current->xyAtT(tAtMid, basePt);
5765    int contourCount = contourList.count();
5766    SkScalar bestY = SK_ScalarMin;
5767    Segment* bestSeg = NULL;
5768    int bestTIndex;
5769    bool bestOpp;
5770    bool hitSomething = false;
5771    for (int cTest = 0; cTest < contourCount; ++cTest) {
5772        Contour* contour = contourList[cTest];
5773        bool testOpp = contour->operand() ^ current->operand() ^ opp;
5774        if (basePt.fY < contour->bounds().fTop) {
5775            continue;
5776        }
5777        if (bestY > contour->bounds().fBottom) {
5778            continue;
5779        }
5780        int segmentCount = contour->segments().count();
5781        for (int test = 0; test < segmentCount; ++test) {
5782            Segment* testSeg = &contour->segments()[test];
5783            SkScalar testY = bestY;
5784            double testHit;
5785            int testTIndex = testSeg->crossedSpanY(basePt, testY, testHit, hitSomething, tAtMid,
5786                    testOpp, testSeg == current);
5787            if (testTIndex < 0) {
5788                if (testTIndex == SK_MinS32) {
5789                    hitSomething = true;
5790                    bestSeg = NULL;
5791                    goto abortContours; // vertical encountered, return and try different point
5792                }
5793                continue;
5794            }
5795            if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
5796                double baseT = current->t(index);
5797                double endT = current->t(endIndex);
5798                double newMid = (testHit - baseT) / (endT - baseT);
5799#if DEBUG_WINDING
5800                SkPoint midXY, newXY;
5801                double midT = current->tAtMid(index, endIndex, mid);
5802                current->xyAtT(midT, midXY);
5803                double newMidT = current->tAtMid(index, endIndex, newMid);
5804                current->xyAtT(newMidT, newXY);
5805                SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
5806                        " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
5807                        current->debugID(), mid, newMid,
5808                        baseT, current->xAtT(index), current->yAtT(index),
5809                        baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
5810                        baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
5811                        endT, current->xAtT(endIndex), current->yAtT(endIndex));
5812#endif
5813                mid = newMid * 2; // calling loop with divide by 2 before continuing
5814                return SK_MinS32;
5815            }
5816            bestSeg = testSeg;
5817            bestHit = testHit;
5818            bestOpp = testOpp;
5819            bestTIndex = testTIndex;
5820            bestY = testY;
5821        }
5822    }
5823abortContours:
5824    int result;
5825    if (!bestSeg) {
5826        result = hitSomething ? SK_MinS32 : 0;
5827    } else {
5828        if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
5829            current = bestSeg;
5830            index = bestTIndex;
5831            endIndex = bestSeg->nextSpan(bestTIndex, 1);
5832            SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
5833            tryAgain = true;
5834            return 0;
5835        }
5836        result = bestSeg->windingAtT(bestHit, bestTIndex, bestOpp, bestDx);
5837        SkASSERT(bestDx);
5838    }
5839    double baseT = current->t(index);
5840    double endT = current->t(endIndex);
5841    bestHit = baseT + mid * (endT - baseT);
5842    return result;
5843}
5844
5845static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
5846    int contourCount = contourList.count();
5847    Segment* result;
5848    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5849        Contour* contour = contourList[cIndex];
5850        result = contour->undoneSegment(start, end);
5851        if (result) {
5852            return result;
5853        }
5854    }
5855    return NULL;
5856}
5857
5858#define OLD_FIND_CHASE 1
5859
5860static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {
5861    while (chase.count()) {
5862        Span* span;
5863        chase.pop(&span);
5864        const Span& backPtr = span->fOther->span(span->fOtherIndex);
5865        Segment* segment = backPtr.fOther;
5866        tIndex = backPtr.fOtherIndex;
5867        SkTDArray<Angle> angles;
5868        int done = 0;
5869        if (segment->activeAngle(tIndex, done, angles)) {
5870            Angle* last = angles.end() - 1;
5871            tIndex = last->start();
5872            endIndex = last->end();
5873   #if TRY_ROTATE
5874            *chase.insert(0) = span;
5875   #else
5876            *chase.append() = span;
5877   #endif
5878            return last->segment();
5879        }
5880        if (done == angles.count()) {
5881            continue;
5882        }
5883        SkTDArray<Angle*> sorted;
5884        bool sortable = Segment::SortAngles(angles, sorted);
5885        int angleCount = sorted.count();
5886#if DEBUG_SORT
5887        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
5888#endif
5889        if (!sortable) {
5890            continue;
5891        }
5892        // find first angle, initialize winding to computed fWindSum
5893        int firstIndex = -1;
5894        const Angle* angle;
5895#if OLD_FIND_CHASE
5896        int winding;
5897        do {
5898            angle = sorted[++firstIndex];
5899            segment = angle->segment();
5900            winding = segment->windSum(angle);
5901        } while (winding == SK_MinS32);
5902        int spanWinding = segment->spanSign(angle->start(), angle->end());
5903    #if DEBUG_WINDING
5904        SkDebugf("%s winding=%d spanWinding=%d\n",
5905                __FUNCTION__, winding, spanWinding);
5906    #endif
5907        // turn span winding into contour winding
5908        if (spanWinding * winding < 0) {
5909            winding += spanWinding;
5910        }
5911    #if DEBUG_SORT
5912        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);
5913    #endif
5914        // we care about first sign and whether wind sum indicates this
5915        // edge is inside or outside. Maybe need to pass span winding
5916        // or first winding or something into this function?
5917        // advance to first undone angle, then return it and winding
5918        // (to set whether edges are active or not)
5919        int nextIndex = firstIndex + 1;
5920        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5921        angle = sorted[firstIndex];
5922        winding -= angle->segment()->spanSign(angle);
5923#else
5924        do {
5925            angle = sorted[++firstIndex];
5926            segment = angle->segment();
5927        } while (segment->windSum(angle) == SK_MinS32);
5928    #if DEBUG_SORT
5929        segment->debugShowSort(__FUNCTION__, sorted, firstIndex);
5930    #endif
5931        int sumWinding = segment->updateWindingReverse(angle);
5932        int nextIndex = firstIndex + 1;
5933        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5934        Segment* first = NULL;
5935#endif
5936        do {
5937            SkASSERT(nextIndex != firstIndex);
5938            if (nextIndex == angleCount) {
5939                nextIndex = 0;
5940            }
5941            angle = sorted[nextIndex];
5942            segment = angle->segment();
5943#if OLD_FIND_CHASE
5944            int maxWinding = winding;
5945            winding -= segment->spanSign(angle);
5946    #if DEBUG_SORT
5947            SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
5948                    segment->debugID(), maxWinding, winding, angle->sign());
5949    #endif
5950            tIndex = angle->start();
5951            endIndex = angle->end();
5952            int lesser = SkMin32(tIndex, endIndex);
5953            const Span& nextSpan = segment->span(lesser);
5954            if (!nextSpan.fDone) {
5955#if 1
5956            // FIXME: this be wrong? assign startWinding if edge is in
5957            // same direction. If the direction is opposite, winding to
5958            // assign is flipped sign or +/- 1?
5959                if (useInnerWinding(maxWinding, winding)) {
5960                    maxWinding = winding;
5961                }
5962                segment->markAndChaseWinding(angle, maxWinding, 0);
5963#endif
5964                break;
5965            }
5966#else
5967            int start = angle->start();
5968            int end = angle->end();
5969            int maxWinding;
5970            segment->setUpWinding(start, end, maxWinding, sumWinding);
5971            if (!segment->done(angle)) {
5972                if (!first) {
5973                    first = segment;
5974                    tIndex = start;
5975                    endIndex = end;
5976                }
5977                (void) segment->markAngle(maxWinding, sumWinding, true, angle);
5978            }
5979#endif
5980        } while (++nextIndex != lastIndex);
5981   #if TRY_ROTATE
5982        *chase.insert(0) = span;
5983   #else
5984        *chase.append() = span;
5985   #endif
5986        return segment;
5987    }
5988    return NULL;
5989}
5990
5991#if DEBUG_ACTIVE_SPANS
5992static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
5993    int index;
5994    for (index = 0; index < contourList.count(); ++ index) {
5995        contourList[index]->debugShowActiveSpans();
5996    }
5997    for (index = 0; index < contourList.count(); ++ index) {
5998        contourList[index]->validateActiveSpans();
5999    }
6000}
6001#endif
6002
6003static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
6004        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool onlySortable) {
6005    Segment* result;
6006    do {
6007        SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
6008        int contourCount = contourList.count();
6009        Segment* topStart = NULL;
6010        done = true;
6011        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
6012            Contour* contour = contourList[cIndex];
6013            if (contour->done()) {
6014                continue;
6015            }
6016            const Bounds& bounds = contour->bounds();
6017            if (bounds.fBottom < topLeft.fY) {
6018                done = false;
6019                continue;
6020            }
6021            if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) {
6022                done = false;
6023                continue;
6024            }
6025            contour->topSortableSegment(topLeft, bestXY, topStart);
6026            if (!contour->done()) {
6027                done = false;
6028            }
6029        }
6030        if (!topStart) {
6031            return NULL;
6032        }
6033        topLeft = bestXY;
6034        result = topStart->findTop(index, endIndex, unsortable, onlySortable);
6035    } while (!result);
6036    return result;
6037}
6038
6039static int rightAngleWinding(SkTDArray<Contour*>& contourList,
6040        Segment*& current, int& index, int& endIndex, double& tHit, SkScalar& hitDx, bool& tryAgain,
6041        bool opp) {
6042    double test = 0.9;
6043    int contourWinding;
6044    do {
6045        contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
6046                tryAgain, test, opp);
6047        if (contourWinding != SK_MinS32 || tryAgain) {
6048            return contourWinding;
6049        }
6050        test /= 2;
6051    } while (!approximately_negative(test));
6052    SkASSERT(0); // should be OK to comment out, but interested when this hits
6053    return contourWinding;
6054}
6055
6056static void skipVertical(SkTDArray<Contour*>& contourList,
6057        Segment*& current, int& index, int& endIndex) {
6058    if (!current->isVertical(index, endIndex)) {
6059        return;
6060    }
6061    int contourCount = contourList.count();
6062    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
6063        Contour* contour = contourList[cIndex];
6064        if (contour->done()) {
6065            continue;
6066        }
6067        current = contour->nonVerticalSegment(index, endIndex);
6068        if (current) {
6069            return;
6070        }
6071    }
6072}
6073
6074static Segment* findSortableTop(SkTDArray<Contour*>& contourList, bool& firstContour, int& index,
6075        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool binary) {
6076    Segment* current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, done,
6077            true);
6078    if (!current) {
6079        return NULL;
6080    }
6081    if (firstContour) {
6082        current->initWinding(index, endIndex);
6083        firstContour = false;
6084        return current;
6085    }
6086    int minIndex = SkMin32(index, endIndex);
6087    int sumWinding = current->windSum(minIndex);
6088    if (sumWinding != SK_MinS32) {
6089        return current;
6090    }
6091    sumWinding = current->computeSum(index, endIndex, binary);
6092    if (sumWinding != SK_MinS32) {
6093        return current;
6094    }
6095    int contourWinding;
6096    int oppContourWinding = 0;
6097    // the simple upward projection of the unresolved points hit unsortable angles
6098    // shoot rays at right angles to the segment to find its winding, ignoring angle cases
6099    bool tryAgain;
6100    double tHit;
6101    SkScalar hitDx = 0;
6102    SkScalar hitOppDx = 0;
6103    do {
6104        // if current is vertical, find another candidate which is not
6105        // if only remaining candidates are vertical, then they can be marked done
6106        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
6107        skipVertical(contourList, current, index, endIndex);
6108        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
6109        tryAgain = false;
6110        contourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitDx,
6111                tryAgain, false);
6112        if (tryAgain) {
6113            continue;
6114        }
6115        if (!binary) {
6116            break;
6117        }
6118        oppContourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitOppDx,
6119                tryAgain, true);
6120    } while (tryAgain);
6121
6122    current->initWinding(index, endIndex, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx);
6123    return current;
6124}
6125
6126// rewrite that abandons keeping local track of winding
6127static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
6128    bool firstContour = true;
6129    bool unsortable = false;
6130    bool topUnsortable = false;
6131    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
6132    do {
6133        int index, endIndex;
6134        bool topDone;
6135        Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft,
6136                topUnsortable, topDone, false);
6137        if (!current) {
6138            if (topUnsortable || !topDone) {
6139                topUnsortable = false;
6140                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
6141                topLeft.fX = topLeft.fY = SK_ScalarMin;
6142                continue;
6143            }
6144            break;
6145        }
6146        SkTDArray<Span*> chaseArray;
6147        do {
6148            if (current->activeWinding(index, endIndex)) {
6149                do {
6150            #if DEBUG_ACTIVE_SPANS
6151                    if (!unsortable && current->done()) {
6152                        debugShowActiveSpans(contourList);
6153                    }
6154            #endif
6155                    SkASSERT(unsortable || !current->done());
6156                    int nextStart = index;
6157                    int nextEnd = endIndex;
6158                    Segment* next = current->findNextWinding(chaseArray, nextStart, nextEnd,
6159                            unsortable);
6160                    if (!next) {
6161                        if (!unsortable && simple.hasMove()
6162                                && current->verb() != SkPath::kLine_Verb
6163                                && !simple.isClosed()) {
6164                            current->addCurveTo(index, endIndex, simple, true);
6165                            SkASSERT(simple.isClosed());
6166                        }
6167                        break;
6168                    }
6169        #if DEBUG_FLOW
6170            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
6171                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
6172                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
6173        #endif
6174                    current->addCurveTo(index, endIndex, simple, true);
6175                    current = next;
6176                    index = nextStart;
6177                    endIndex = nextEnd;
6178                } while (!simple.isClosed() && (!unsortable
6179                        || !current->done(SkMin32(index, endIndex))));
6180                if (current->activeWinding(index, endIndex) && !simple.isClosed()) {
6181                    SkASSERT(unsortable);
6182                    int min = SkMin32(index, endIndex);
6183                    if (!current->done(min)) {
6184                        current->addCurveTo(index, endIndex, simple, true);
6185                        current->markDoneUnary(min);
6186                    }
6187                }
6188                simple.close();
6189            } else {
6190                Span* last = current->markAndChaseDoneUnary(index, endIndex);
6191                if (last && !last->fLoop) {
6192                    *chaseArray.append() = last;
6193                }
6194            }
6195            current = findChase(chaseArray, index, endIndex);
6196        #if DEBUG_ACTIVE_SPANS
6197            debugShowActiveSpans(contourList);
6198        #endif
6199            if (!current) {
6200                break;
6201            }
6202        } while (true);
6203    } while (true);
6204    return simple.someAssemblyRequired();
6205}
6206
6207// returns true if all edges were processed
6208static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
6209    Segment* current;
6210    int start, end;
6211    bool unsortable = false;
6212    bool closable = true;
6213    while ((current = findUndone(contourList, start, end))) {
6214        do {
6215    #if DEBUG_ACTIVE_SPANS
6216            if (!unsortable && current->done()) {
6217                debugShowActiveSpans(contourList);
6218            }
6219    #endif
6220            SkASSERT(unsortable || !current->done());
6221            int nextStart = start;
6222            int nextEnd = end;
6223            Segment* next = current->findNextXor(nextStart, nextEnd, unsortable);
6224            if (!next) {
6225                if (!unsortable && simple.hasMove()
6226                        && current->verb() != SkPath::kLine_Verb
6227                        && !simple.isClosed()) {
6228                    current->addCurveTo(start, end, simple, true);
6229                    SkASSERT(simple.isClosed());
6230                }
6231                break;
6232            }
6233        #if DEBUG_FLOW
6234            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
6235                    current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
6236                    current->xyAtT(end).fX, current->xyAtT(end).fY);
6237        #endif
6238            current->addCurveTo(start, end, simple, true);
6239            current = next;
6240            start = nextStart;
6241            end = nextEnd;
6242        } while (!simple.isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
6243        if (!simple.isClosed()) {
6244            SkASSERT(unsortable);
6245            int min = SkMin32(start, end);
6246            if (!current->done(min)) {
6247                current->addCurveTo(start, end, simple, true);
6248                current->markDone(min, 1);
6249            }
6250            closable = false;
6251        }
6252        simple.close();
6253    #if DEBUG_ACTIVE_SPANS
6254        debugShowActiveSpans(contourList);
6255    #endif
6256    }
6257    return closable;
6258}
6259
6260static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
6261    int contourCount = contourList.count();
6262    for (int cTest = 0; cTest < contourCount; ++cTest) {
6263        Contour* contour = contourList[cTest];
6264        contour->fixOtherTIndex();
6265    }
6266}
6267
6268static void sortSegments(SkTDArray<Contour*>& contourList) {
6269    int contourCount = contourList.count();
6270    for (int cTest = 0; cTest < contourCount; ++cTest) {
6271        Contour* contour = contourList[cTest];
6272        contour->sortSegments();
6273    }
6274}
6275
6276static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& list,
6277        bool evenOdd, bool oppEvenOdd) {
6278    int count = contours.count();
6279    if (count == 0) {
6280        return;
6281    }
6282    for (int index = 0; index < count; ++index) {
6283        Contour& contour = contours[index];
6284        contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
6285        *list.append() = &contour;
6286    }
6287    QSort<Contour>(list.begin(), list.end() - 1);
6288}
6289
6290static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) {
6291    return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY);
6292}
6293
6294static bool lessThan(SkTDArray<double>& distances, const int one, const int two) {
6295    return distances[one] < distances[two];
6296}
6297    /*
6298        check start and end of each contour
6299        if not the same, record them
6300        match them up
6301        connect closest
6302        reassemble contour pieces into new path
6303    */
6304static void assemble(const PathWrapper& path, PathWrapper& simple) {
6305#if DEBUG_PATH_CONSTRUCTION
6306    SkDebugf("%s\n", __FUNCTION__);
6307#endif
6308    SkTArray<Contour> contours;
6309    EdgeBuilder builder(path, contours);
6310    builder.finish();
6311    int count = contours.count();
6312    int outer;
6313    SkTDArray<int> runs; // indices of partial contours
6314    for (outer = 0; outer < count; ++outer) {
6315        const Contour& eContour = contours[outer];
6316        const SkPoint& eStart = eContour.start();
6317        const SkPoint& eEnd = eContour.end();
6318#if DEBUG_ASSEMBLE
6319        SkDebugf("%s contour", __FUNCTION__);
6320        if (!approximatelyEqual(eStart, eEnd)) {
6321            SkDebugf("[%d]", runs.count());
6322        } else {
6323            SkDebugf("   ");
6324        }
6325        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
6326                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
6327#endif
6328        if (approximatelyEqual(eStart, eEnd)) {
6329            eContour.toPath(simple);
6330            continue;
6331        }
6332        *runs.append() = outer;
6333    }
6334    count = runs.count();
6335    if (count == 0) {
6336        return;
6337    }
6338    SkTDArray<int> sLink, eLink;
6339    sLink.setCount(count);
6340    eLink.setCount(count);
6341    int rIndex, iIndex;
6342    for (rIndex = 0; rIndex < count; ++rIndex) {
6343        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
6344    }
6345    SkTDArray<double> distances;
6346    const int ends = count * 2; // all starts and ends
6347    const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2
6348    distances.setCount(entries);
6349    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
6350        outer = runs[rIndex >> 1];
6351        const Contour& oContour = contours[outer];
6352        const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
6353        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
6354                * ends - rIndex - 1;
6355        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
6356            int inner = runs[iIndex >> 1];
6357            const Contour& iContour = contours[inner];
6358            const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
6359            double dx = iPt.fX - oPt.fX;
6360            double dy = iPt.fY - oPt.fY;
6361            double dist = dx * dx + dy * dy;
6362            distances[row + iIndex] = dist; // oStart distance from iStart
6363        }
6364    }
6365    SkTDArray<int> sortedDist;
6366    sortedDist.setCount(entries);
6367    for (rIndex = 0; rIndex < entries; ++rIndex) {
6368        sortedDist[rIndex] = rIndex;
6369    }
6370    QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end() - 1, lessThan);
6371    int remaining = count; // number of start/end pairs
6372    for (rIndex = 0; rIndex < entries; ++rIndex) {
6373        int pair = sortedDist[rIndex];
6374        int row = pair / ends;
6375        int col = pair - row * ends;
6376        int thingOne = row < col ? row : ends - row - 2;
6377        int ndxOne = thingOne >> 1;
6378        bool endOne = thingOne & 1;
6379        int* linkOne = endOne ? eLink.begin() : sLink.begin();
6380        if (linkOne[ndxOne] != SK_MaxS32) {
6381            continue;
6382        }
6383        int thingTwo = row < col ? col : ends - row + col - 1;
6384        int ndxTwo = thingTwo >> 1;
6385        bool endTwo = thingTwo & 1;
6386        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
6387        if (linkTwo[ndxTwo] != SK_MaxS32) {
6388            continue;
6389        }
6390        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
6391        bool flip = endOne == endTwo;
6392        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
6393        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
6394        if (!--remaining) {
6395            break;
6396        }
6397    }
6398    SkASSERT(!remaining);
6399#if DEBUG_ASSEMBLE
6400    for (rIndex = 0; rIndex < count; ++rIndex) {
6401        int s = sLink[rIndex];
6402        int e = eLink[rIndex];
6403        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
6404                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
6405    }
6406#endif
6407    rIndex = 0;
6408    do {
6409        bool forward = true;
6410        bool first = true;
6411        int sIndex = sLink[rIndex];
6412        SkASSERT(sIndex != SK_MaxS32);
6413        sLink[rIndex] = SK_MaxS32;
6414        int eIndex;
6415        if (sIndex < 0) {
6416            eIndex = sLink[~sIndex];
6417            sLink[~sIndex] = SK_MaxS32;
6418        } else {
6419            eIndex = eLink[sIndex];
6420            eLink[sIndex] = SK_MaxS32;
6421        }
6422        SkASSERT(eIndex != SK_MaxS32);
6423#if DEBUG_ASSEMBLE
6424        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
6425                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
6426                    eIndex < 0 ? ~eIndex : eIndex);
6427#endif
6428        do {
6429            outer = runs[rIndex];
6430            const Contour& contour = contours[outer];
6431            if (first) {
6432                first = false;
6433                const SkPoint* startPtr = &contour.start();
6434                simple.deferredMove(startPtr[0]);
6435            }
6436            if (forward) {
6437                contour.toPartialForward(simple);
6438            } else {
6439                contour.toPartialBackward(simple);
6440            }
6441#if DEBUG_ASSEMBLE
6442            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
6443                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
6444                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
6445#endif
6446            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
6447                simple.close();
6448                break;
6449            }
6450            if (forward) {
6451                eIndex = eLink[rIndex];
6452                SkASSERT(eIndex != SK_MaxS32);
6453                eLink[rIndex] = SK_MaxS32;
6454                if (eIndex >= 0) {
6455                    SkASSERT(sLink[eIndex] == rIndex);
6456                    sLink[eIndex] = SK_MaxS32;
6457                } else {
6458                    SkASSERT(eLink[~eIndex] == ~rIndex);
6459                    eLink[~eIndex] = SK_MaxS32;
6460                }
6461            } else {
6462                eIndex = sLink[rIndex];
6463                SkASSERT(eIndex != SK_MaxS32);
6464                sLink[rIndex] = SK_MaxS32;
6465                if (eIndex >= 0) {
6466                    SkASSERT(eLink[eIndex] == rIndex);
6467                    eLink[eIndex] = SK_MaxS32;
6468                } else {
6469                    SkASSERT(sLink[~eIndex] == ~rIndex);
6470                    sLink[~eIndex] = SK_MaxS32;
6471                }
6472            }
6473            rIndex = eIndex;
6474            if (rIndex < 0) {
6475                forward ^= 1;
6476                rIndex = ~rIndex;
6477            }
6478        } while (true);
6479        for (rIndex = 0; rIndex < count; ++rIndex) {
6480            if (sLink[rIndex] != SK_MaxS32) {
6481                break;
6482            }
6483        }
6484    } while (rIndex < count);
6485#if DEBUG_ASSEMBLE
6486    for (rIndex = 0; rIndex < count; ++rIndex) {
6487       SkASSERT(sLink[rIndex] == SK_MaxS32);
6488       SkASSERT(eLink[rIndex] == SK_MaxS32);
6489    }
6490#endif
6491}
6492
6493void simplifyx(const SkPath& path, SkPath& result) {
6494#if DEBUG_SORT
6495    gDebugSortCount = gDebugSortCountDefault;
6496#endif
6497    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
6498    result.reset();
6499    result.setFillType(SkPath::kEvenOdd_FillType);
6500    PathWrapper simple(result);
6501
6502    // turn path into list of segments
6503    SkTArray<Contour> contours;
6504    EdgeBuilder builder(path, contours);
6505    builder.finish();
6506    SkTDArray<Contour*> contourList;
6507    makeContourList(contours, contourList, false, false);
6508    Contour** currentPtr = contourList.begin();
6509    if (!currentPtr) {
6510        return;
6511    }
6512    Contour** listEnd = contourList.end();
6513    // find all intersections between segments
6514    do {
6515        Contour** nextPtr = currentPtr;
6516        Contour* current = *currentPtr++;
6517        if (current->containsCubics()) {
6518            addSelfIntersectTs(current);
6519        }
6520        Contour* next;
6521        do {
6522            next = *nextPtr++;
6523        } while (addIntersectTs(current, next) && nextPtr != listEnd);
6524    } while (currentPtr != listEnd);
6525    // eat through coincident edges
6526    coincidenceCheck(contourList, 0);
6527    fixOtherTIndex(contourList);
6528    sortSegments(contourList);
6529#if DEBUG_ACTIVE_SPANS
6530    debugShowActiveSpans(contourList);
6531#endif
6532    // construct closed contours
6533    if (builder.xorMask() == kWinding_Mask ? bridgeWinding(contourList, simple)
6534                : !bridgeXor(contourList, simple))
6535    { // if some edges could not be resolved, assemble remaining fragments
6536        SkPath temp;
6537        temp.setFillType(SkPath::kEvenOdd_FillType);
6538        PathWrapper assembled(temp);
6539        assemble(simple, assembled);
6540        result = *assembled.nativePath();
6541    }
6542}
6543