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