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