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