Simplify.cpp revision 7ff5c841bf669826b4cbd708ae1a6b3527f15dca 
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 = QuadReduceOrder(&pointsPtr[-1], fReducePts);
5043                if (reducedVerb == 0) {
5044                    break; // skip degenerate points
5045                }
5046                if (reducedVerb == 1) {
5047                    *fExtra.append() =
5048                            fCurrentContour->addLine(fReducePts.end() - 2);
5049                    break;
5050                }
5051                fCurrentContour->addQuad(&pointsPtr[-1]);
5052                break;
5053            case SkPath::kCubic_Verb:
5054                reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts);
5055                if (reducedVerb == 0) {
5056                    break; // skip degenerate points
5057                }
5058                if (reducedVerb == 1) {
5059                    *fExtra.append() =
5060                            fCurrentContour->addLine(fReducePts.end() - 2);
5061                    break;
5062                }
5063                if (reducedVerb == 2) {
5064                    *fExtra.append() =
5065                            fCurrentContour->addQuad(fReducePts.end() - 3);
5066                    break;
5067                }
5068                fCurrentContour->addCubic(&pointsPtr[-1]);
5069                break;
5070            case SkPath::kClose_Verb:
5071                SkASSERT(fCurrentContour);
5072                if (finalCurveStart && finalCurveEnd
5073                        && *finalCurveStart != *finalCurveEnd) {
5074                    *fReducePts.append() = *finalCurveStart;
5075                    *fReducePts.append() = *finalCurveEnd;
5076                    *fExtra.append() =
5077                            fCurrentContour->addLine(fReducePts.end() - 2);
5078                }
5079                complete();
5080                goto nextVerb;
5081            default:
5082                SkDEBUGFAIL("bad verb");
5083                return;
5084        }
5085        finalCurveStart = &pointsPtr[verb - 1];
5086        pointsPtr += verb;
5087        SkASSERT(fCurrentContour);
5088    nextVerb:
5089        if (verbPtr == endOfFirstHalf) {
5090            fOperand = true;
5091        }
5092    }
5093}
5094
5095private:
5096    const SkPath* fPath;
5097    SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead
5098    SkTDArray<uint8_t> fPathVerbs; // FIXME: remove
5099    Contour* fCurrentContour;
5100    SkTArray<Contour>& fContours;
5101    SkTDArray<SkPoint> fReducePts; // segments created on the fly
5102    SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour
5103    ShapeOpMask fXorMask[2];
5104    int fSecondHalf;
5105    bool fOperand;
5106};
5107
5108class Work {
5109public:
5110    enum SegmentType {
5111        kHorizontalLine_Segment = -1,
5112        kVerticalLine_Segment = 0,
5113        kLine_Segment = SkPath::kLine_Verb,
5114        kQuad_Segment = SkPath::kQuad_Verb,
5115        kCubic_Segment = SkPath::kCubic_Verb,
5116    };
5117
5118    void addCoincident(Work& other, const Intersections& ts, bool swap) {
5119        fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
5120    }
5121
5122    // FIXME: does it make sense to write otherIndex now if we're going to
5123    // fix it up later?
5124    void addOtherT(int index, double otherT, int otherIndex) {
5125        fContour->addOtherT(fIndex, index, otherT, otherIndex);
5126    }
5127
5128    // Avoid collapsing t values that are close to the same since
5129    // we walk ts to describe consecutive intersections. Since a pair of ts can
5130    // be nearly equal, any problems caused by this should be taken care
5131    // of later.
5132    // On the edge or out of range values are negative; add 2 to get end
5133    int addT(const Work& other, const SkPoint& pt, double& newT) {
5134        return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
5135    }
5136
5137    int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) {
5138        return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT);
5139    }
5140
5141    bool advance() {
5142        return ++fIndex < fLast;
5143    }
5144
5145    SkScalar bottom() const {
5146        return bounds().fBottom;
5147    }
5148
5149    const Bounds& bounds() const {
5150        return fContour->segments()[fIndex].bounds();
5151    }
5152
5153#if !APPROXIMATE_CUBICS
5154    const SkPoint* cubic() const {
5155        return fCubic;
5156    }
5157#endif
5158
5159    void init(Contour* contour) {
5160        fContour = contour;
5161        fIndex = 0;
5162        fLast = contour->segments().count();
5163    }
5164
5165    bool isAdjacent(const Work& next) {
5166        return fContour == next.fContour && fIndex + 1 == next.fIndex;
5167    }
5168
5169    bool isFirstLast(const Work& next) {
5170        return fContour == next.fContour && fIndex == 0
5171                && next.fIndex == fLast - 1;
5172    }
5173
5174    SkScalar left() const {
5175        return bounds().fLeft;
5176    }
5177
5178#if !APPROXIMATE_CUBICS
5179    void promoteToCubic() {
5180        fCubic[0] = pts()[0];
5181        fCubic[2] = pts()[1];
5182        fCubic[3] = pts()[2];
5183        fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3;
5184        fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3;
5185        fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3;
5186        fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3;
5187    }
5188#endif
5189
5190    const SkPoint* pts() const {
5191        return fContour->segments()[fIndex].pts();
5192    }
5193
5194    SkScalar right() const {
5195        return bounds().fRight;
5196    }
5197
5198    ptrdiff_t segmentIndex() const {
5199        return fIndex;
5200    }
5201
5202    SegmentType segmentType() const {
5203        const Segment& segment = fContour->segments()[fIndex];
5204        SegmentType type = (SegmentType) segment.verb();
5205        if (type != kLine_Segment) {
5206            return type;
5207        }
5208        if (segment.isHorizontal()) {
5209            return kHorizontalLine_Segment;
5210        }
5211        if (segment.isVertical()) {
5212            return kVerticalLine_Segment;
5213        }
5214        return kLine_Segment;
5215    }
5216
5217    bool startAfter(const Work& after) {
5218        fIndex = after.fIndex;
5219        return advance();
5220    }
5221
5222    SkScalar top() const {
5223        return bounds().fTop;
5224    }
5225
5226    SkPath::Verb verb() const {
5227        return fContour->segments()[fIndex].verb();
5228    }
5229
5230    SkScalar x() const {
5231        return bounds().fLeft;
5232    }
5233
5234    bool xFlipped() const {
5235        return x() != pts()[0].fX;
5236    }
5237
5238    SkScalar y() const {
5239        return bounds().fTop;
5240    }
5241
5242    bool yFlipped() const {
5243        return y() != pts()[0].fY;
5244    }
5245
5246protected:
5247    Contour* fContour;
5248#if !APPROXIMATE_CUBICS
5249    SkPoint fCubic[4];
5250#endif
5251    int fIndex;
5252    int fLast;
5253};
5254
5255#if DEBUG_ADD_INTERSECTING_TS
5256
5257#if DEBUG_AS_C_CODE
5258#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
5259#define QUAD_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
5260#define LINE_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"
5261#define PT_DEBUG_STR "{{%1.17g,%1.17g}}"
5262#else
5263#define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
5264#define QUAD_DEBUG_STR  "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
5265#define LINE_DEBUG_STR  "(%1.9g,%1.9g %1.9g,%1.9g)"
5266#define PT_DEBUG_STR "(%1.9g,%1.9g)"
5267#endif
5268#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
5269#define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
5270#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
5271#define QUAD_DEBUG_DATA(q)  q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
5272#define LINE_DEBUG_DATA(l)  l[0].fX, l[0].fY, l[1].fX, l[1].fY
5273#define PT_DEBUG_DATA(i, n) i.fPt[n].x, i.fPt[n].y
5274
5275static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn,
5276        const Intersections& i) {
5277    SkASSERT(i.used() == pts);
5278    if (!pts) {
5279        SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
5280                __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5281        return;
5282    }
5283    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5284            i.fT[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5285    if (pts == 2) {
5286        SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i.fT[0][1], PT_DEBUG_DATA(i, 1));
5287    }
5288    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5289    if (pts == 2) {
5290        SkDebugf(" " T_DEBUG_STR(wnTs, 1), i.fT[1][1]);
5291    }
5292    SkDebugf("\n");
5293}
5294
5295static void debugShowQuadLineIntersection(int pts, const Work& wt,
5296        const Work& wn, const Intersections& i) {
5297    SkASSERT(i.used() == pts);
5298    if (!pts) {
5299        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
5300                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5301        return;
5302    }
5303    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5304            i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5305    for (int n = 1; n < pts; ++n) {
5306        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5307    }
5308    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5309    for (int n = 1; n < pts; ++n) {
5310        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5311    }
5312    SkDebugf("\n");
5313}
5314
5315static void debugShowQuadIntersection(int pts, const Work& wt,
5316        const Work& wn, const Intersections& i) {
5317    SkASSERT(i.used() == pts);
5318    if (!pts) {
5319        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
5320                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
5321        return;
5322    }
5323    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5324            i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5325    for (int n = 1; n < pts; ++n) {
5326        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5327    }
5328    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts()));
5329    for (int n = 1; n < pts; ++n) {
5330        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5331    }
5332    SkDebugf("\n");
5333}
5334
5335static void debugShowCubicLineIntersection(int pts, const Work& wt,
5336        const Work& wn, const Intersections& i) {
5337    SkASSERT(i.used() == pts);
5338    if (!pts) {
5339        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
5340                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
5341        return;
5342    }
5343    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5344            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5345    for (int n = 1; n < pts; ++n) {
5346        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5347    }
5348    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts()));
5349    for (int n = 1; n < pts; ++n) {
5350        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5351    }
5352    SkDebugf("\n");
5353}
5354
5355static void debugShowCubicQuadIntersection(int pts, const Work& wt,
5356        const Work& wn, const Intersections& i) {
5357    SkASSERT(i.used() == pts);
5358    if (!pts) {
5359        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
5360                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
5361        return;
5362    }
5363    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5364            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5365    for (int n = 1; n < pts; ++n) {
5366        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5367    }
5368    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts()));
5369    for (int n = 1; n < pts; ++n) {
5370        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5371    }
5372    SkDebugf("\n");
5373}
5374
5375static void debugShowCubicIntersection(int pts, const Work& wt,
5376        const Work& wn, const Intersections& i) {
5377    SkASSERT(i.used() == pts);
5378    if (!pts) {
5379        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
5380                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
5381        return;
5382    }
5383    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5384            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5385    for (int n = 1; n < pts; ++n) {
5386        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n));
5387    }
5388    SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i.fT[1][0], CUBIC_DEBUG_DATA(wn.pts()));
5389    for (int n = 1; n < pts; ++n) {
5390        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]);
5391    }
5392    SkDebugf("\n");
5393}
5394
5395static void debugShowCubicIntersection(int pts, const Work& wt, const Intersections& i) {
5396    SkASSERT(i.used() == pts);
5397    if (!pts) {
5398        SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,
5399                CUBIC_DEBUG_DATA(wt.pts()));
5400        return;
5401    }
5402    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
5403            i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
5404    SkDebugf(" " T_DEBUG_STR(wtTs, 1), i.fT[1][0]);
5405    SkDebugf("\n");
5406}
5407
5408#undef CUBIC_DEBUG_STR
5409#undef QUAD_DEBUG_STR
5410#undef LINE_DEBUG_STR
5411#undef PT_DEBUG_STR
5412#undef T_DEBUG_STR
5413#undef CUBIC_DEBUG_DATA
5414#undef QUAD_DEBUG_DATA
5415#undef LINE_DEBUG_DATA
5416#undef PT_DEBUG_DATA
5417
5418#else
5419static void debugShowLineIntersection(int , const Work& , const Work& , const Intersections& ) {
5420}
5421
5422static void debugShowQuadLineIntersection(int , const Work& , const Work& , const Intersections& ) {
5423}
5424
5425static void debugShowQuadIntersection(int , const Work& , const Work& , const Intersections& ) {
5426}
5427
5428static void debugShowCubicLineIntersection(int , const Work& , const Work& ,
5429        const Intersections& ) {
5430}
5431
5432static void debugShowCubicQuadIntersection(int , const Work& , const Work& ,
5433        const Intersections& ) {
5434}
5435
5436static void debugShowCubicIntersection(int , const Work& , const Work& , const Intersections& ) {
5437}
5438
5439static void debugShowCubicIntersection(int , const Work& , const Intersections& ) {
5440}
5441#endif
5442
5443static bool addIntersectTs(Contour* test, Contour* next) {
5444
5445    if (test != next) {
5446        if (test->bounds().fBottom < next->bounds().fTop) {
5447            return false;
5448        }
5449        if (!Bounds::Intersects(test->bounds(), next->bounds())) {
5450            return true;
5451        }
5452    }
5453    Work wt;
5454    wt.init(test);
5455    bool foundCommonContour = test == next;
5456    do {
5457        Work wn;
5458        wn.init(next);
5459        if (test == next && !wn.startAfter(wt)) {
5460            continue;
5461        }
5462        do {
5463            if (!Bounds::Intersects(wt.bounds(), wn.bounds())) {
5464                continue;
5465            }
5466            int pts;
5467            Intersections ts;
5468            bool swap = false;
5469            switch (wt.segmentType()) {
5470                case Work::kHorizontalLine_Segment:
5471                    swap = true;
5472                    switch (wn.segmentType()) {
5473                        case Work::kHorizontalLine_Segment:
5474                        case Work::kVerticalLine_Segment:
5475                        case Work::kLine_Segment: {
5476                            pts = HLineIntersect(wn.pts(), wt.left(),
5477                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5478                            debugShowLineIntersection(pts, wt, wn, ts);
5479                            break;
5480                        }
5481                        case Work::kQuad_Segment: {
5482                            pts = HQuadIntersect(wn.pts(), wt.left(),
5483                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5484                            break;
5485                        }
5486                        case Work::kCubic_Segment: {
5487                            pts = HCubicIntersect(wn.pts(), wt.left(),
5488                                    wt.right(), wt.y(), wt.xFlipped(), ts);
5489                            debugShowCubicLineIntersection(pts, wn, wt, ts);
5490                            break;
5491                        }
5492                        default:
5493                            SkASSERT(0);
5494                    }
5495                    break;
5496                case Work::kVerticalLine_Segment:
5497                    swap = true;
5498                    switch (wn.segmentType()) {
5499                        case Work::kHorizontalLine_Segment:
5500                        case Work::kVerticalLine_Segment:
5501                        case Work::kLine_Segment: {
5502                            pts = VLineIntersect(wn.pts(), wt.top(),
5503                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5504                            debugShowLineIntersection(pts, wt, wn, ts);
5505                            break;
5506                        }
5507                        case Work::kQuad_Segment: {
5508                            pts = VQuadIntersect(wn.pts(), wt.top(),
5509                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5510                            break;
5511                        }
5512                        case Work::kCubic_Segment: {
5513                            pts = VCubicIntersect(wn.pts(), wt.top(),
5514                                    wt.bottom(), wt.x(), wt.yFlipped(), ts);
5515                            debugShowCubicLineIntersection(pts, wn, wt, ts);
5516                            break;
5517                        }
5518                        default:
5519                            SkASSERT(0);
5520                    }
5521                    break;
5522                case Work::kLine_Segment:
5523                    switch (wn.segmentType()) {
5524                        case Work::kHorizontalLine_Segment:
5525                            pts = HLineIntersect(wt.pts(), wn.left(),
5526                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5527                            debugShowLineIntersection(pts, wt, wn, ts);
5528                            break;
5529                        case Work::kVerticalLine_Segment:
5530                            pts = VLineIntersect(wt.pts(), wn.top(),
5531                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5532                            debugShowLineIntersection(pts, wt, wn, ts);
5533                            break;
5534                        case Work::kLine_Segment: {
5535                            pts = LineIntersect(wt.pts(), wn.pts(), ts);
5536                            debugShowLineIntersection(pts, wt, wn, ts);
5537                            break;
5538                        }
5539                        case Work::kQuad_Segment: {
5540                            swap = true;
5541                            pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
5542                            debugShowQuadLineIntersection(pts, wn, wt, ts);
5543                            break;
5544                        }
5545                        case Work::kCubic_Segment: {
5546                            swap = true;
5547                            pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
5548                            debugShowCubicLineIntersection(pts, wn, wt,  ts);
5549                            break;
5550                        }
5551                        default:
5552                            SkASSERT(0);
5553                    }
5554                    break;
5555                case Work::kQuad_Segment:
5556                    switch (wn.segmentType()) {
5557                        case Work::kHorizontalLine_Segment:
5558                            pts = HQuadIntersect(wt.pts(), wn.left(),
5559                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5560                            break;
5561                        case Work::kVerticalLine_Segment:
5562                            pts = VQuadIntersect(wt.pts(), wn.top(),
5563                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5564                            break;
5565                        case Work::kLine_Segment: {
5566                            pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
5567                            debugShowQuadLineIntersection(pts, wt, wn, ts);
5568                            break;
5569                        }
5570                        case Work::kQuad_Segment: {
5571                            pts = QuadIntersect(wt.pts(), wn.pts(), ts);
5572                            debugShowQuadIntersection(pts, wt, wn, ts);
5573                            break;
5574                        }
5575                        case Work::kCubic_Segment: {
5576                    #if APPROXIMATE_CUBICS
5577                            swap = true;
5578                            pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts);
5579                            debugShowCubicQuadIntersection(pts, wn, wt, ts);
5580                    #else
5581                            wt.promoteToCubic();
5582                            pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
5583                            debugShowCubicIntersection(pts, wt, wn, ts);
5584                    #endif
5585                            break;
5586                        }
5587                        default:
5588                            SkASSERT(0);
5589                    }
5590                    break;
5591                case Work::kCubic_Segment:
5592                    switch (wn.segmentType()) {
5593                        case Work::kHorizontalLine_Segment:
5594                            pts = HCubicIntersect(wt.pts(), wn.left(),
5595                                    wn.right(), wn.y(), wn.xFlipped(), ts);
5596                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5597                            break;
5598                        case Work::kVerticalLine_Segment:
5599                            pts = VCubicIntersect(wt.pts(), wn.top(),
5600                                    wn.bottom(), wn.x(), wn.yFlipped(), ts);
5601                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5602                            break;
5603                        case Work::kLine_Segment: {
5604                            pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
5605                            debugShowCubicLineIntersection(pts, wt, wn, ts);
5606                            break;
5607                        }
5608                        case Work::kQuad_Segment: {
5609                    #if APPROXIMATE_CUBICS
5610                            pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts);
5611                            debugShowCubicQuadIntersection(pts, wt, wn, ts);
5612                    #else
5613                            wn.promoteToCubic();
5614                            pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
5615                            debugShowCubicIntersection(pts, wt, wn, ts);
5616                    #endif
5617                            break;
5618                        }
5619                        case Work::kCubic_Segment: {
5620                            pts = CubicIntersect(wt.pts(), wn.pts(), ts);
5621                            debugShowCubicIntersection(pts, wt, wn, ts);
5622                            break;
5623                        }
5624                        default:
5625                            SkASSERT(0);
5626                    }
5627                    break;
5628                default:
5629                    SkASSERT(0);
5630            }
5631            if (!foundCommonContour && pts > 0) {
5632                test->addCross(next);
5633                next->addCross(test);
5634                foundCommonContour = true;
5635            }
5636            // in addition to recording T values, record matching segment
5637            if (ts.unsortable()) {
5638                bool start = true;
5639                for (int pt = 0; pt < ts.used(); ++pt) {
5640                    // FIXME: if unsortable, the other points to the original. This logic is
5641                    // untested downstream.
5642                    SkPoint point = ts.fPt[pt].asSkPoint();
5643                    int testTAt = wt.addUnsortableT(wt, start, point, ts.fT[swap][pt]);
5644                    wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt);
5645                    testTAt = wn.addUnsortableT(wn, start ^ ts.fFlip, point, ts.fT[!swap][pt]);
5646                    wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt);
5647                    start ^= true;
5648                }
5649                continue;
5650            }
5651            if (pts == 2) {
5652                if (wn.segmentType() <= Work::kLine_Segment
5653                        && wt.segmentType() <= Work::kLine_Segment) {
5654                    wt.addCoincident(wn, ts, swap);
5655                    continue;
5656                }
5657                if (wn.segmentType() >= Work::kQuad_Segment
5658                        && wt.segmentType() >= Work::kQuad_Segment
5659                        && ts.fIsCoincident[0]) {
5660                    SkASSERT(ts.coincidentUsed() == 2);
5661                    wt.addCoincident(wn, ts, swap);
5662                    continue;
5663                }
5664
5665            }
5666            for (int pt = 0; pt < pts; ++pt) {
5667                SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
5668                SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
5669                SkPoint point = ts.fPt[pt].asSkPoint();
5670                int testTAt = wt.addT(wn, point, ts.fT[swap][pt]);
5671                int nextTAt = wn.addT(wt, point, ts.fT[!swap][pt]);
5672                wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
5673                wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
5674            }
5675        } while (wn.advance());
5676    } while (wt.advance());
5677    return true;
5678}
5679
5680static void addSelfIntersectTs(Contour* test) {
5681    Work wt;
5682    wt.init(test);
5683    do {
5684        if (wt.segmentType() != Work::kCubic_Segment) {
5685            continue;
5686        }
5687        Intersections ts;
5688        int pts = CubicIntersect(wt.pts(), ts);
5689        debugShowCubicIntersection(pts, wt, ts);
5690        if (!pts) {
5691            continue;
5692        }
5693        SkASSERT(pts == 1);
5694        SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1);
5695        SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1);
5696        SkPoint point = ts.fPt[0].asSkPoint();
5697        int testTAt = wt.addT(wt, point, ts.fT[0][0]);
5698        int nextTAt = wt.addT(wt, point, ts.fT[1][0]);
5699        wt.addOtherT(testTAt, ts.fT[1][0], nextTAt);
5700        wt.addOtherT(nextTAt, ts.fT[0][0], testTAt);
5701    } while (wt.advance());
5702}
5703
5704// resolve any coincident pairs found while intersecting, and
5705// see if coincidence is formed by clipping non-concident segments
5706static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {
5707    int contourCount = contourList.count();
5708#if ONE_PASS_COINCIDENCE_CHECK
5709    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5710        Contour* contour = contourList[cIndex];
5711        contour->resolveCoincidence(contourList);
5712    }
5713#else
5714    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5715        Contour* contour = contourList[cIndex];
5716        contour->addCoincidentPoints();
5717    }
5718    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5719        Contour* contour = contourList[cIndex];
5720        contour->calcCoincidentWinding();
5721    }
5722#endif
5723    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5724        Contour* contour = contourList[cIndex];
5725        contour->findTooCloseToCall();
5726    }
5727}
5728
5729static int contourRangeCheckY(SkTDArray<Contour*>& contourList,  Segment*& current, int& index,
5730        int& endIndex, double& bestHit, SkScalar& bestDx, bool& tryAgain, double& mid, bool opp) {
5731    SkPoint basePt;
5732    double tAtMid = current->tAtMid(index, endIndex, mid);
5733    current->xyAtT(tAtMid, basePt);
5734    int contourCount = contourList.count();
5735    SkScalar bestY = SK_ScalarMin;
5736    Segment* bestSeg = NULL;
5737    int bestTIndex;
5738    bool bestOpp;
5739    bool hitSomething = false;
5740    for (int cTest = 0; cTest < contourCount; ++cTest) {
5741        Contour* contour = contourList[cTest];
5742        bool testOpp = contour->operand() ^ current->operand() ^ opp;
5743        if (basePt.fY < contour->bounds().fTop) {
5744            continue;
5745        }
5746        if (bestY > contour->bounds().fBottom) {
5747            continue;
5748        }
5749        int segmentCount = contour->segments().count();
5750        for (int test = 0; test < segmentCount; ++test) {
5751            Segment* testSeg = &contour->segments()[test];
5752            SkScalar testY = bestY;
5753            double testHit;
5754            int testTIndex = testSeg->crossedSpanY(basePt, testY, testHit, hitSomething, tAtMid,
5755                    testOpp, testSeg == current);
5756            if (testTIndex < 0) {
5757                if (testTIndex == SK_MinS32) {
5758                    hitSomething = true;
5759                    bestSeg = NULL;
5760                    goto abortContours; // vertical encountered, return and try different point
5761                }
5762                continue;
5763            }
5764            if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
5765                double baseT = current->t(index);
5766                double endT = current->t(endIndex);
5767                double newMid = (testHit - baseT) / (endT - baseT);
5768#if DEBUG_WINDING
5769                SkPoint midXY, newXY;
5770                double midT = current->tAtMid(index, endIndex, mid);
5771                current->xyAtT(midT, midXY);
5772                double newMidT = current->tAtMid(index, endIndex, newMid);
5773                current->xyAtT(newMidT, newXY);
5774                SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
5775                        " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
5776                        current->debugID(), mid, newMid,
5777                        baseT, current->xAtT(index), current->yAtT(index),
5778                        baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
5779                        baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
5780                        endT, current->xAtT(endIndex), current->yAtT(endIndex));
5781#endif
5782                mid = newMid * 2; // calling loop with divide by 2 before continuing
5783                return SK_MinS32;
5784            }
5785            bestSeg = testSeg;
5786            bestHit = testHit;
5787            bestOpp = testOpp;
5788            bestTIndex = testTIndex;
5789            bestY = testY;
5790        }
5791    }
5792abortContours:
5793    int result;
5794    if (!bestSeg) {
5795        result = hitSomething ? SK_MinS32 : 0;
5796    } else {
5797        if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
5798            current = bestSeg;
5799            index = bestTIndex;
5800            endIndex = bestSeg->nextSpan(bestTIndex, 1);
5801            SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
5802            tryAgain = true;
5803            return 0;
5804        }
5805        result = bestSeg->windingAtT(bestHit, bestTIndex, bestOpp, bestDx);
5806        SkASSERT(bestDx);
5807    }
5808    double baseT = current->t(index);
5809    double endT = current->t(endIndex);
5810    bestHit = baseT + mid * (endT - baseT);
5811    return result;
5812}
5813
5814static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
5815    int contourCount = contourList.count();
5816    Segment* result;
5817    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5818        Contour* contour = contourList[cIndex];
5819        result = contour->undoneSegment(start, end);
5820        if (result) {
5821            return result;
5822        }
5823    }
5824    return NULL;
5825}
5826
5827#define OLD_FIND_CHASE 1
5828
5829static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {
5830    while (chase.count()) {
5831        Span* span;
5832        chase.pop(&span);
5833        const Span& backPtr = span->fOther->span(span->fOtherIndex);
5834        Segment* segment = backPtr.fOther;
5835        tIndex = backPtr.fOtherIndex;
5836        SkTDArray<Angle> angles;
5837        int done = 0;
5838        if (segment->activeAngle(tIndex, done, angles)) {
5839            Angle* last = angles.end() - 1;
5840            tIndex = last->start();
5841            endIndex = last->end();
5842   #if TRY_ROTATE
5843            *chase.insert(0) = span;
5844   #else
5845            *chase.append() = span;
5846   #endif
5847            return last->segment();
5848        }
5849        if (done == angles.count()) {
5850            continue;
5851        }
5852        SkTDArray<Angle*> sorted;
5853        bool sortable = Segment::SortAngles(angles, sorted);
5854        int angleCount = sorted.count();
5855#if DEBUG_SORT
5856        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
5857#endif
5858        if (!sortable) {
5859            continue;
5860        }
5861        // find first angle, initialize winding to computed fWindSum
5862        int firstIndex = -1;
5863        const Angle* angle;
5864#if OLD_FIND_CHASE
5865        int winding;
5866        do {
5867            angle = sorted[++firstIndex];
5868            segment = angle->segment();
5869            winding = segment->windSum(angle);
5870        } while (winding == SK_MinS32);
5871        int spanWinding = segment->spanSign(angle->start(), angle->end());
5872    #if DEBUG_WINDING
5873        SkDebugf("%s winding=%d spanWinding=%d\n",
5874                __FUNCTION__, winding, spanWinding);
5875    #endif
5876        // turn span winding into contour winding
5877        if (spanWinding * winding < 0) {
5878            winding += spanWinding;
5879        }
5880    #if DEBUG_SORT
5881        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);
5882    #endif
5883        // we care about first sign and whether wind sum indicates this
5884        // edge is inside or outside. Maybe need to pass span winding
5885        // or first winding or something into this function?
5886        // advance to first undone angle, then return it and winding
5887        // (to set whether edges are active or not)
5888        int nextIndex = firstIndex + 1;
5889        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5890        angle = sorted[firstIndex];
5891        winding -= angle->segment()->spanSign(angle);
5892#else
5893        do {
5894            angle = sorted[++firstIndex];
5895            segment = angle->segment();
5896        } while (segment->windSum(angle) == SK_MinS32);
5897    #if DEBUG_SORT
5898        segment->debugShowSort(__FUNCTION__, sorted, firstIndex);
5899    #endif
5900        int sumWinding = segment->updateWindingReverse(angle);
5901        int nextIndex = firstIndex + 1;
5902        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
5903        Segment* first = NULL;
5904#endif
5905        do {
5906            SkASSERT(nextIndex != firstIndex);
5907            if (nextIndex == angleCount) {
5908                nextIndex = 0;
5909            }
5910            angle = sorted[nextIndex];
5911            segment = angle->segment();
5912#if OLD_FIND_CHASE
5913            int maxWinding = winding;
5914            winding -= segment->spanSign(angle);
5915    #if DEBUG_SORT
5916            SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
5917                    segment->debugID(), maxWinding, winding, angle->sign());
5918    #endif
5919            tIndex = angle->start();
5920            endIndex = angle->end();
5921            int lesser = SkMin32(tIndex, endIndex);
5922            const Span& nextSpan = segment->span(lesser);
5923            if (!nextSpan.fDone) {
5924#if 1
5925            // FIXME: this be wrong? assign startWinding if edge is in
5926            // same direction. If the direction is opposite, winding to
5927            // assign is flipped sign or +/- 1?
5928                if (useInnerWinding(maxWinding, winding)) {
5929                    maxWinding = winding;
5930                }
5931                segment->markAndChaseWinding(angle, maxWinding, 0);
5932#endif
5933                break;
5934            }
5935#else
5936            int start = angle->start();
5937            int end = angle->end();
5938            int maxWinding;
5939            segment->setUpWinding(start, end, maxWinding, sumWinding);
5940            if (!segment->done(angle)) {
5941                if (!first) {
5942                    first = segment;
5943                    tIndex = start;
5944                    endIndex = end;
5945                }
5946                (void) segment->markAngle(maxWinding, sumWinding, true, angle);
5947            }
5948#endif
5949        } while (++nextIndex != lastIndex);
5950   #if TRY_ROTATE
5951        *chase.insert(0) = span;
5952   #else
5953        *chase.append() = span;
5954   #endif
5955        return segment;
5956    }
5957    return NULL;
5958}
5959
5960#if DEBUG_ACTIVE_SPANS
5961static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
5962    int index;
5963    for (index = 0; index < contourList.count(); ++ index) {
5964        contourList[index]->debugShowActiveSpans();
5965    }
5966    for (index = 0; index < contourList.count(); ++ index) {
5967        contourList[index]->validateActiveSpans();
5968    }
5969}
5970#endif
5971
5972static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
5973        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool onlySortable) {
5974    Segment* result;
5975    do {
5976        SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
5977        int contourCount = contourList.count();
5978        Segment* topStart = NULL;
5979        done = true;
5980        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
5981            Contour* contour = contourList[cIndex];
5982            if (contour->done()) {
5983                continue;
5984            }
5985            const Bounds& bounds = contour->bounds();
5986            if (bounds.fBottom < topLeft.fY) {
5987                done = false;
5988                continue;
5989            }
5990            if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) {
5991                done = false;
5992                continue;
5993            }
5994            contour->topSortableSegment(topLeft, bestXY, topStart);
5995            if (!contour->done()) {
5996                done = false;
5997            }
5998        }
5999        if (!topStart) {
6000            return NULL;
6001        }
6002        topLeft = bestXY;
6003        result = topStart->findTop(index, endIndex, unsortable, onlySortable);
6004    } while (!result);
6005    return result;
6006}
6007
6008static int rightAngleWinding(SkTDArray<Contour*>& contourList,
6009        Segment*& current, int& index, int& endIndex, double& tHit, SkScalar& hitDx, bool& tryAgain,
6010        bool opp) {
6011    double test = 0.9;
6012    int contourWinding;
6013    do {
6014        contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
6015                tryAgain, test, opp);
6016        if (contourWinding != SK_MinS32 || tryAgain) {
6017            return contourWinding;
6018        }
6019        test /= 2;
6020    } while (!approximately_negative(test));
6021    SkASSERT(0); // should be OK to comment out, but interested when this hits
6022    return contourWinding;
6023}
6024
6025static void skipVertical(SkTDArray<Contour*>& contourList,
6026        Segment*& current, int& index, int& endIndex) {
6027    if (!current->isVertical(index, endIndex)) {
6028        return;
6029    }
6030    int contourCount = contourList.count();
6031    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
6032        Contour* contour = contourList[cIndex];
6033        if (contour->done()) {
6034            continue;
6035        }
6036        current = contour->nonVerticalSegment(index, endIndex);
6037        if (current) {
6038            return;
6039        }
6040    }
6041}
6042
6043static Segment* findSortableTop(SkTDArray<Contour*>& contourList, bool& firstContour, int& index,
6044        int& endIndex, SkPoint& topLeft, bool& unsortable, bool& done, bool binary) {
6045    Segment* current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, done,
6046            true);
6047    if (!current) {
6048        return NULL;
6049    }
6050    if (firstContour) {
6051        current->initWinding(index, endIndex);
6052        firstContour = false;
6053        return current;
6054    }
6055    int minIndex = SkMin32(index, endIndex);
6056    int sumWinding = current->windSum(minIndex);
6057    if (sumWinding != SK_MinS32) {
6058        return current;
6059    }
6060    sumWinding = current->computeSum(index, endIndex, binary);
6061    if (sumWinding != SK_MinS32) {
6062        return current;
6063    }
6064    int contourWinding;
6065    int oppContourWinding = 0;
6066    // the simple upward projection of the unresolved points hit unsortable angles
6067    // shoot rays at right angles to the segment to find its winding, ignoring angle cases
6068    bool tryAgain;
6069    double tHit;
6070    SkScalar hitDx = 0;
6071    SkScalar hitOppDx = 0;
6072    do {
6073        // if current is vertical, find another candidate which is not
6074        // if only remaining candidates are vertical, then they can be marked done
6075        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
6076        skipVertical(contourList, current, index, endIndex);
6077        SkASSERT(index != endIndex && index >= 0 && endIndex >= 0);
6078        tryAgain = false;
6079        contourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitDx,
6080                tryAgain, false);
6081        if (tryAgain) {
6082            continue;
6083        }
6084        if (!binary) {
6085            break;
6086        }
6087        oppContourWinding = rightAngleWinding(contourList, current, index, endIndex, tHit, hitOppDx,
6088                tryAgain, true);
6089    } while (tryAgain);
6090
6091    current->initWinding(index, endIndex, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx);
6092    return current;
6093}
6094
6095// rewrite that abandons keeping local track of winding
6096static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
6097    bool firstContour = true;
6098    bool unsortable = false;
6099    bool topUnsortable = false;
6100    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
6101    do {
6102        int index, endIndex;
6103        bool topDone;
6104        Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft,
6105                topUnsortable, topDone, false);
6106        if (!current) {
6107            if (topUnsortable || !topDone) {
6108                topUnsortable = false;
6109                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
6110                topLeft.fX = topLeft.fY = SK_ScalarMin;
6111                continue;
6112            }
6113            break;
6114        }
6115        SkTDArray<Span*> chaseArray;
6116        do {
6117            if (current->activeWinding(index, endIndex)) {
6118                do {
6119            #if DEBUG_ACTIVE_SPANS
6120                    if (!unsortable && current->done()) {
6121                        debugShowActiveSpans(contourList);
6122                    }
6123            #endif
6124                    SkASSERT(unsortable || !current->done());
6125                    int nextStart = index;
6126                    int nextEnd = endIndex;
6127                    Segment* next = current->findNextWinding(chaseArray, nextStart, nextEnd,
6128                            unsortable);
6129                    if (!next) {
6130                        if (!unsortable && simple.hasMove()
6131                                && current->verb() != SkPath::kLine_Verb
6132                                && !simple.isClosed()) {
6133                            current->addCurveTo(index, endIndex, simple, true);
6134                            SkASSERT(simple.isClosed());
6135                        }
6136                        break;
6137                    }
6138        #if DEBUG_FLOW
6139            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
6140                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
6141                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
6142        #endif
6143                    current->addCurveTo(index, endIndex, simple, true);
6144                    current = next;
6145                    index = nextStart;
6146                    endIndex = nextEnd;
6147                } while (!simple.isClosed() && (!unsortable
6148                        || !current->done(SkMin32(index, endIndex))));
6149                if (current->activeWinding(index, endIndex) && !simple.isClosed()) {
6150                    SkASSERT(unsortable);
6151                    int min = SkMin32(index, endIndex);
6152                    if (!current->done(min)) {
6153                        current->addCurveTo(index, endIndex, simple, true);
6154                        current->markDoneUnary(min);
6155                    }
6156                }
6157                simple.close();
6158            } else {
6159                Span* last = current->markAndChaseDoneUnary(index, endIndex);
6160                if (last) {
6161                    *chaseArray.append() = last;
6162                }
6163            }
6164            current = findChase(chaseArray, index, endIndex);
6165        #if DEBUG_ACTIVE_SPANS
6166            debugShowActiveSpans(contourList);
6167        #endif
6168            if (!current) {
6169                break;
6170            }
6171        } while (true);
6172    } while (true);
6173    return simple.someAssemblyRequired();
6174}
6175
6176// returns true if all edges were processed
6177static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
6178    Segment* current;
6179    int start, end;
6180    bool unsortable = false;
6181    bool closable = true;
6182    while ((current = findUndone(contourList, start, end))) {
6183        do {
6184    #if DEBUG_ACTIVE_SPANS
6185            if (!unsortable && current->done()) {
6186                debugShowActiveSpans(contourList);
6187            }
6188    #endif
6189            SkASSERT(unsortable || !current->done());
6190            int nextStart = start;
6191            int nextEnd = end;
6192            Segment* next = current->findNextXor(nextStart, nextEnd, unsortable);
6193            if (!next) {
6194                if (!unsortable && simple.hasMove()
6195                        && current->verb() != SkPath::kLine_Verb
6196                        && !simple.isClosed()) {
6197                    current->addCurveTo(start, end, simple, true);
6198                    SkASSERT(simple.isClosed());
6199                }
6200                break;
6201            }
6202        #if DEBUG_FLOW
6203            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
6204                    current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
6205                    current->xyAtT(end).fX, current->xyAtT(end).fY);
6206        #endif
6207            current->addCurveTo(start, end, simple, true);
6208            current = next;
6209            start = nextStart;
6210            end = nextEnd;
6211        } while (!simple.isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
6212        if (!simple.isClosed()) {
6213            SkASSERT(unsortable);
6214            int min = SkMin32(start, end);
6215            if (!current->done(min)) {
6216                current->addCurveTo(start, end, simple, true);
6217                current->markDone(min, 1);
6218            }
6219            closable = false;
6220        }
6221        simple.close();
6222    #if DEBUG_ACTIVE_SPANS
6223        debugShowActiveSpans(contourList);
6224    #endif
6225    }
6226    return closable;
6227}
6228
6229static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
6230    int contourCount = contourList.count();
6231    for (int cTest = 0; cTest < contourCount; ++cTest) {
6232        Contour* contour = contourList[cTest];
6233        contour->fixOtherTIndex();
6234    }
6235}
6236
6237static void sortSegments(SkTDArray<Contour*>& contourList) {
6238    int contourCount = contourList.count();
6239    for (int cTest = 0; cTest < contourCount; ++cTest) {
6240        Contour* contour = contourList[cTest];
6241        contour->sortSegments();
6242    }
6243}
6244
6245static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& list,
6246        bool evenOdd, bool oppEvenOdd) {
6247    int count = contours.count();
6248    if (count == 0) {
6249        return;
6250    }
6251    for (int index = 0; index < count; ++index) {
6252        Contour& contour = contours[index];
6253        contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
6254        *list.append() = &contour;
6255    }
6256    QSort<Contour>(list.begin(), list.end() - 1);
6257}
6258
6259static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) {
6260    return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY);
6261}
6262
6263static bool lessThan(SkTDArray<double>& distances, const int one, const int two) {
6264    return distances[one] < distances[two];
6265}
6266    /*
6267        check start and end of each contour
6268        if not the same, record them
6269        match them up
6270        connect closest
6271        reassemble contour pieces into new path
6272    */
6273static void assemble(const PathWrapper& path, PathWrapper& simple) {
6274#if DEBUG_PATH_CONSTRUCTION
6275    SkDebugf("%s\n", __FUNCTION__);
6276#endif
6277    SkTArray<Contour> contours;
6278    EdgeBuilder builder(path, contours);
6279    builder.finish();
6280    int count = contours.count();
6281    int outer;
6282    SkTDArray<int> runs; // indices of partial contours
6283    for (outer = 0; outer < count; ++outer) {
6284        const Contour& eContour = contours[outer];
6285        const SkPoint& eStart = eContour.start();
6286        const SkPoint& eEnd = eContour.end();
6287#if DEBUG_ASSEMBLE
6288        SkDebugf("%s contour", __FUNCTION__);
6289        if (!approximatelyEqual(eStart, eEnd)) {
6290            SkDebugf("[%d]", runs.count());
6291        } else {
6292            SkDebugf("   ");
6293        }
6294        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
6295                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
6296#endif
6297        if (approximatelyEqual(eStart, eEnd)) {
6298            eContour.toPath(simple);
6299            continue;
6300        }
6301        *runs.append() = outer;
6302    }
6303    count = runs.count();
6304    if (count == 0) {
6305        return;
6306    }
6307    SkTDArray<int> sLink, eLink;
6308    sLink.setCount(count);
6309    eLink.setCount(count);
6310    int rIndex, iIndex;
6311    for (rIndex = 0; rIndex < count; ++rIndex) {
6312        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
6313    }
6314    SkTDArray<double> distances;
6315    const int ends = count * 2; // all starts and ends
6316    const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2
6317    distances.setCount(entries);
6318    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
6319        outer = runs[rIndex >> 1];
6320        const Contour& oContour = contours[outer];
6321        const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
6322        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
6323                * ends - rIndex - 1;
6324        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
6325            int inner = runs[iIndex >> 1];
6326            const Contour& iContour = contours[inner];
6327            const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
6328            double dx = iPt.fX - oPt.fX;
6329            double dy = iPt.fY - oPt.fY;
6330            double dist = dx * dx + dy * dy;
6331            distances[row + iIndex] = dist; // oStart distance from iStart
6332        }
6333    }
6334    SkTDArray<int> sortedDist;
6335    sortedDist.setCount(entries);
6336    for (rIndex = 0; rIndex < entries; ++rIndex) {
6337        sortedDist[rIndex] = rIndex;
6338    }
6339    QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end() - 1, lessThan);
6340    int remaining = count; // number of start/end pairs
6341    for (rIndex = 0; rIndex < entries; ++rIndex) {
6342        int pair = sortedDist[rIndex];
6343        int row = pair / ends;
6344        int col = pair - row * ends;
6345        int thingOne = row < col ? row : ends - row - 2;
6346        int ndxOne = thingOne >> 1;
6347        bool endOne = thingOne & 1;
6348        int* linkOne = endOne ? eLink.begin() : sLink.begin();
6349        if (linkOne[ndxOne] != SK_MaxS32) {
6350            continue;
6351        }
6352        int thingTwo = row < col ? col : ends - row + col - 1;
6353        int ndxTwo = thingTwo >> 1;
6354        bool endTwo = thingTwo & 1;
6355        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
6356        if (linkTwo[ndxTwo] != SK_MaxS32) {
6357            continue;
6358        }
6359        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
6360        bool flip = endOne == endTwo;
6361        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
6362        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
6363        if (!--remaining) {
6364            break;
6365        }
6366    }
6367    SkASSERT(!remaining);
6368#if DEBUG_ASSEMBLE
6369    for (rIndex = 0; rIndex < count; ++rIndex) {
6370        int s = sLink[rIndex];
6371        int e = eLink[rIndex];
6372        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
6373                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
6374    }
6375#endif
6376    rIndex = 0;
6377    do {
6378        bool forward = true;
6379        bool first = true;
6380        int sIndex = sLink[rIndex];
6381        SkASSERT(sIndex != SK_MaxS32);
6382        sLink[rIndex] = SK_MaxS32;
6383        int eIndex;
6384        if (sIndex < 0) {
6385            eIndex = sLink[~sIndex];
6386            sLink[~sIndex] = SK_MaxS32;
6387        } else {
6388            eIndex = eLink[sIndex];
6389            eLink[sIndex] = SK_MaxS32;
6390        }
6391        SkASSERT(eIndex != SK_MaxS32);
6392#if DEBUG_ASSEMBLE
6393        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
6394                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
6395                    eIndex < 0 ? ~eIndex : eIndex);
6396#endif
6397        do {
6398            outer = runs[rIndex];
6399            const Contour& contour = contours[outer];
6400            if (first) {
6401                first = false;
6402                const SkPoint* startPtr = &contour.start();
6403                simple.deferredMove(startPtr[0]);
6404            }
6405            if (forward) {
6406                contour.toPartialForward(simple);
6407            } else {
6408                contour.toPartialBackward(simple);
6409            }
6410#if DEBUG_ASSEMBLE
6411            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
6412                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
6413                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
6414#endif
6415            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
6416                simple.close();
6417                break;
6418            }
6419            if (forward) {
6420                eIndex = eLink[rIndex];
6421                SkASSERT(eIndex != SK_MaxS32);
6422                eLink[rIndex] = SK_MaxS32;
6423                if (eIndex >= 0) {
6424                    SkASSERT(sLink[eIndex] == rIndex);
6425                    sLink[eIndex] = SK_MaxS32;
6426                } else {
6427                    SkASSERT(eLink[~eIndex] == ~rIndex);
6428                    eLink[~eIndex] = SK_MaxS32;
6429                }
6430            } else {
6431                eIndex = sLink[rIndex];
6432                SkASSERT(eIndex != SK_MaxS32);
6433                sLink[rIndex] = SK_MaxS32;
6434                if (eIndex >= 0) {
6435                    SkASSERT(eLink[eIndex] == rIndex);
6436                    eLink[eIndex] = SK_MaxS32;
6437                } else {
6438                    SkASSERT(sLink[~eIndex] == ~rIndex);
6439                    sLink[~eIndex] = SK_MaxS32;
6440                }
6441            }
6442            rIndex = eIndex;
6443            if (rIndex < 0) {
6444                forward ^= 1;
6445                rIndex = ~rIndex;
6446            }
6447        } while (true);
6448        for (rIndex = 0; rIndex < count; ++rIndex) {
6449            if (sLink[rIndex] != SK_MaxS32) {
6450                break;
6451            }
6452        }
6453    } while (rIndex < count);
6454#if DEBUG_ASSEMBLE
6455    for (rIndex = 0; rIndex < count; ++rIndex) {
6456       SkASSERT(sLink[rIndex] == SK_MaxS32);
6457       SkASSERT(eLink[rIndex] == SK_MaxS32);
6458    }
6459#endif
6460}
6461
6462void simplifyx(const SkPath& path, SkPath& result) {
6463#if DEBUG_SORT
6464    gDebugSortCount = gDebugSortCountDefault;
6465#endif
6466    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
6467    result.reset();
6468    result.setFillType(SkPath::kEvenOdd_FillType);
6469    PathWrapper simple(result);
6470
6471    // turn path into list of segments
6472    SkTArray<Contour> contours;
6473    EdgeBuilder builder(path, contours);
6474    builder.finish();
6475    SkTDArray<Contour*> contourList;
6476    makeContourList(contours, contourList, false, false);
6477    Contour** currentPtr = contourList.begin();
6478    if (!currentPtr) {
6479        return;
6480    }
6481    Contour** listEnd = contourList.end();
6482    // find all intersections between segments
6483    do {
6484        Contour** nextPtr = currentPtr;
6485        Contour* current = *currentPtr++;
6486        if (current->containsCubics()) {
6487            addSelfIntersectTs(current);
6488        }
6489        Contour* next;
6490        do {
6491            next = *nextPtr++;
6492        } while (addIntersectTs(current, next) && nextPtr != listEnd);
6493    } while (currentPtr != listEnd);
6494    // eat through coincident edges
6495    coincidenceCheck(contourList, 0);
6496    fixOtherTIndex(contourList);
6497    sortSegments(contourList);
6498#if DEBUG_ACTIVE_SPANS
6499    debugShowActiveSpans(contourList);
6500#endif
6501    // construct closed contours
6502    if (builder.xorMask() == kWinding_Mask ? bridgeWinding(contourList, simple)
6503                : !bridgeXor(contourList, simple))
6504    { // if some edges could not be resolved, assemble remaining fragments
6505        SkPath temp;
6506        temp.setFillType(SkPath::kEvenOdd_FillType);
6507        PathWrapper assembled(temp);
6508        assemble(simple, assembled);
6509        result = *assembled.nativePath();
6510    }
6511}
6512