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