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