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