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