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