1fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com/*
2fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com * Copyright 2012 Google Inc.
3fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com *
4fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be
5fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com * found in the LICENSE file.
6fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com */
7b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com#include "Simplify.h"
8fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
9fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#undef SkASSERT
10fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
11fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
1215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// Terminology:
1315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// A Path contains one of more Contours
1415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// A Contour is made up of Segment array
15b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com// A Segment is described by a Verb and a Point array with 2, 3, or 4 points
16b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com// A Verb is one of Line, Quad(ratic), or Cubic
1715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// A Segment contains a Span array
1815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// A Span is describes a portion of a Segment using starting and ending T
1915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// T values range from 0 to 1, where 0 is the first Point in the Segment
2047580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com// An Edge is a Segment generated from a Span
2115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
22fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com// FIXME: remove once debugging is complete
2347580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#ifdef SK_DEBUG
2447580694fbe974a065caf7c39c3d2075708c2018caryclark@google.comint gDebugMaxWindSum = SK_MaxS32;
2547580694fbe974a065caf7c39c3d2075708c2018caryclark@google.comint gDebugMaxWindValue = SK_MaxS32;
2647580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#endif
2747580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com
28f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#define PIN_ADD_T 0
290b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com#define TRY_ROTATE 1
308f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#define ONE_PASS_COINCIDENCE_CHECK 0
3173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#define APPROXIMATE_CUBICS 1
32d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define COMPACT_DEBUG_SORT 0
33a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com
3447580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_UNUSED 0 // set to expose unused functions
3545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
3631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com#if FORCE_RELEASE || defined SK_RELEASE
37fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
3847580694fbe974a065caf7c39c3d2075708c2018caryclark@google.comconst bool gRunTestsInOneThread = false;
39fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
40beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#define DEBUG_ACTIVE_OP 0
4147580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_ACTIVE_SPANS 0
424eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
43fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0
4447580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_ADD_T_PAIR 0
45c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com#define DEBUG_ANGLE 0
467ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#define DEBUG_AS_C_CODE 1
47e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com#define DEBUG_ASSEMBLE 0
4847580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_CONCIDENT 0
498dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#define DEBUG_CROSS 0
50e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com#define DEBUG_FLOW 0
5147580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_MARK_DONE 0
52f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#define DEBUG_PATH_CONSTRUCTION 0
53729e1c46cea63dfaa6e4a05608b8f3be41e19dcecaryclark@google.com#define DEBUG_SHOW_WINDING 0
54c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#define DEBUG_SORT 0
555e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#define DEBUG_SWAP_TOP 0
568f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#define DEBUG_UNSORTABLE 0
57afe56de6361a81eef537ddd8f6d5626c8546d4c7caryclark@google.com#define DEBUG_WIND_BUMP 0
588dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#define DEBUG_WINDING 0
598f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#define DEBUG_WINDING_AT_T 0
60fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
61fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#else
62fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
6347580694fbe974a065caf7c39c3d2075708c2018caryclark@google.comconst bool gRunTestsInOneThread = true;
64fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
65beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#define DEBUG_ACTIVE_OP 1
66c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com#define DEBUG_ACTIVE_SPANS 1
671304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
686aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 1
696aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com#define DEBUG_ADD_T_PAIR 1
703350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com#define DEBUG_ANGLE 1
714aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#define DEBUG_AS_C_CODE 1
72e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com#define DEBUG_ASSEMBLE 1
733350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com#define DEBUG_CONCIDENT 1
74534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com#define DEBUG_CROSS 0
75e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com#define DEBUG_FLOW 1
763350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com#define DEBUG_MARK_DONE 1
7765f9f0a1664a9cb38157ccfbcc3e0e936af0a58ecaryclark@google.com#define DEBUG_PATH_CONSTRUCTION 1
78729e1c46cea63dfaa6e4a05608b8f3be41e19dcecaryclark@google.com#define DEBUG_SHOW_WINDING 0
7947580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_SORT 1
8047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com#define DEBUG_SWAP_TOP 1
818f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#define DEBUG_UNSORTABLE 1
82afe56de6361a81eef537ddd8f6d5626c8546d4c7caryclark@google.com#define DEBUG_WIND_BUMP 0
8347580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#define DEBUG_WINDING 1
848f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#define DEBUG_WINDING_AT_T 1
85fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
86fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#endif
87fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
88beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \
89beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com        DEBUG_PATH_CONSTRUCTION)
90027de226c144d9e6b7a76acb2e904952b5620a5ecaryclark@google.com
91d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#if DEBUG_AS_C_CODE
92d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
93d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define QUAD_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
94d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define LINE_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"
95d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define PT_DEBUG_STR "{{%1.17g,%1.17g}}"
96d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#else
97d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
98d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define QUAD_DEBUG_STR  "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
99d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define LINE_DEBUG_STR  "(%1.9g,%1.9g %1.9g,%1.9g)"
100d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define PT_DEBUG_STR "(%1.9g,%1.9g)"
101d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#endif
102d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
103d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
104d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
105d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define QUAD_DEBUG_DATA(q)  q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
106d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define LINE_DEBUG_DATA(l)  l[0].fX, l[0].fY, l[1].fX, l[1].fY
107d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define PT_DEBUG_DATA(i, n) i.fPt[n].x, i.fPt[n].y
108d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com
109fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#if DEBUG_DUMP
110fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
11165f9f0a1664a9cb38157ccfbcc3e0e936af0a58ecaryclark@google.com// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
112fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int gContourID;
113fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int gSegmentID;
114fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#endif
115fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
1161304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com#if DEBUG_SORT || DEBUG_SWAP_TOP
1174aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.comstatic int gDebugSortCountDefault = SK_MaxS32;
118c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.comstatic int gDebugSortCount;
119c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#endif
120c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com
1215e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#if DEBUG_ACTIVE_OP
1225e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.comstatic const char* kShapeOpStr[] = {"diff", "sect", "union", "xor"};
1235e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#endif
1245e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com
1258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#ifndef DEBUG_TEST
1268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#define DEBUG_TEST 0
1278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#endif
1288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
12932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com#define MAKE_CONST_LINE(line, pts) \
13032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}
13132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com#define MAKE_CONST_QUAD(quad, pts) \
13232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
13332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            {pts[2].fX, pts[2].fY}}
13432546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com#define MAKE_CONST_CUBIC(cubic, pts) \
13532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
13632546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            {pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}
13732546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com
138fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2],
139fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        Intersections& intersections) {
14032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
14132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(bLine, b);
14245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return intersect(aLine, bLine, intersections);
143fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
144fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
145fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
146fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        Intersections& intersections) {
14732546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
14832546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(bLine, b);
1493350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    return intersect(aQuad, bLine, intersections);
150fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
151fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
15232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.comstatic int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],
153fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        Intersections& intersections) {
15432546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
15532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(bLine, b);
15673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    return intersect(aCubic, bLine, intersections);
157fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
158fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
159fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
160fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        Intersections& intersections) {
16132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
16232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(bQuad, b);
163235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#define TRY_QUARTIC_SOLUTION 1
164235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#if TRY_QUARTIC_SOLUTION
165235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    intersect2(aQuad, bQuad, intersections);
166235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#else
167fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    intersect(aQuad, bQuad, intersections);
168235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#endif
16945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return intersections.fUsed;
170fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
171fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
17273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#if APPROXIMATE_CUBICS
17373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3],
174fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        Intersections& intersections) {
17532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
17673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    MAKE_CONST_QUAD(bQuad, b);
17773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    return intersect(aCubic, bQuad, intersections);
17873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com}
17973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#endif
18073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com
18173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) {
18273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
18332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(bCubic, b);
18473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#if APPROXIMATE_CUBICS
18545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    intersect3(aCubic, bCubic, intersections);
18673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#else
187fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    intersect(aCubic, bCubic, intersections);
18873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#endif
18945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return intersections.fUsed;
190fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
191fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
192c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.comstatic int CubicIntersect(const SkPoint a[4], Intersections& intersections) {
193c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
194c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com    return intersect(aCubic, intersections);
195c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com}
196c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com
197fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
198fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkScalar y, bool flipped, Intersections& intersections) {
19932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
200fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return horizontalIntersect(aLine, left, right, y, flipped, intersections);
201fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
202fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
203fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
204fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkScalar y, bool flipped, Intersections& intersections) {
20532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
206fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
207fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
208fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
209fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
210fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkScalar y, bool flipped, Intersections& intersections) {
21132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
212fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
213fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
214fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
215e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.comstatic int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,
216e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        SkScalar , SkScalar , bool , Intersections& ) = {
217e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    NULL,
218e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    HLineIntersect,
219e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    HQuadIntersect,
220e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    HCubicIntersect
221e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com};
222e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
2238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
2248dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkScalar x, bool flipped, Intersections& intersections) {
22532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
2268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
2278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com}
2288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
2298dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
2308dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkScalar x, bool flipped, Intersections& intersections) {
23132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
2328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
2338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com}
2348dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
2358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
2368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkScalar x, bool flipped, Intersections& intersections) {
23732546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
2388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
239fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
240fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
2418dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
2428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkScalar , SkScalar , bool , Intersections& ) = {
2438dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    NULL,
2448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    VLineIntersect,
2458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    VQuadIntersect,
2468dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    VCubicIntersect
2478dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com};
2488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
249fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
25032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(line, a);
251fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x, y;
252fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(line, t, x, y);
253fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fX = SkDoubleToScalar(x);
254fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fY = SkDoubleToScalar(y);
255fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
256fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
257f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, _Point* out) {
258f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    MAKE_CONST_LINE(line, a);
259f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    xy_at_t(line, t, out->x, out->y);
260f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com}
261f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
262fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
26332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(quad, a);
264fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x, y;
265fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(quad, t, x, y);
266fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fX = SkDoubleToScalar(x);
267fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fY = SkDoubleToScalar(y);
268fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
269fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
2706aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.comstatic void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {
2716aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    MAKE_CONST_QUAD(quad, a);
2726aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    xy_at_t(quad, t, out->x, out->y);
2736aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com}
2746aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com
275fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
27632546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
277fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x, y;
278fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(cubic, t, x, y);
279fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fX = SkDoubleToScalar(x);
280fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    out->fY = SkDoubleToScalar(y);
281fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
282fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
283f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic void CubicXYAtT(const SkPoint a[4], double t, _Point* out) {
284f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
285f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    xy_at_t(cubic, t, out->x, out->y);
286f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com}
287f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
288fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
289fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    NULL,
290fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    LineXYAtT,
291fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    QuadXYAtT,
292fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    CubicXYAtT
293fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com};
294fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
295f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic void (* const SegmentXYAtT2[])(const SkPoint [], double , _Point* ) = {
296f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    NULL,
297f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    LineXYAtT,
298f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    QuadXYAtT,
299f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    CubicXYAtT
300f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com};
301f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
302fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar LineXAtT(const SkPoint a[2], double t) {
30332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
304fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x;
305fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(aLine, t, x, *(double*) 0);
306fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(x);
307fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
308fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
309fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar QuadXAtT(const SkPoint a[3], double t) {
31032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(quad, a);
311fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x;
312fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(quad, t, x, *(double*) 0);
313fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(x);
314fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
315fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
316fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar CubicXAtT(const SkPoint a[4], double t) {
31732546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
318fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x;
319fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(cubic, t, x, *(double*) 0);
320fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(x);
321fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
322fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
323fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
324fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    NULL,
325fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    LineXAtT,
326fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    QuadXAtT,
327fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    CubicXAtT
328fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com};
329fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
330fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar LineYAtT(const SkPoint a[2], double t) {
33132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
332fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double y;
333fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(aLine, t, *(double*) 0, y);
334fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(y);
335fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
336fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
337fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar QuadYAtT(const SkPoint a[3], double t) {
33832546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(quad, a);
339fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double y;
340fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(quad, t, *(double*) 0, y);
341fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(y);
342fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
343fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
344fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar CubicYAtT(const SkPoint a[4], double t) {
34532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
346fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double y;
347fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(cubic, t, *(double*) 0, y);
348fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return SkDoubleToScalar(y);
349fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
350fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
351fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
352fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    NULL,
353fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    LineYAtT,
354fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    QuadYAtT,
355fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    CubicYAtT
356fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com};
357fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
3588dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic SkScalar LineDXAtT(const SkPoint a[2], double ) {
3598dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return a[1].fX - a[0].fX;
3608dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com}
3618dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
3628dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic SkScalar QuadDXAtT(const SkPoint a[3], double t) {
36332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(quad, a);
36405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com    double x = dx_at_t(quad, t);
3658dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return SkDoubleToScalar(x);
3668dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com}
3678dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
3688dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic SkScalar CubicDXAtT(const SkPoint a[4], double t) {
36932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
37005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com    double x = dx_at_t(cubic, t);
3718dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    return SkDoubleToScalar(x);
3728dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com}
3738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
3748dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comstatic SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
3758dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    NULL,
3768dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    LineDXAtT,
3778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    QuadDXAtT,
3788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    CubicDXAtT
3798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com};
3808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
381e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.comstatic SkScalar LineDYAtT(const SkPoint a[2], double ) {
382e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    return a[1].fY - a[0].fY;
383e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com}
384e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
385e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.comstatic SkScalar QuadDYAtT(const SkPoint a[3], double t) {
386e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    MAKE_CONST_QUAD(quad, a);
38705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com    double y = dy_at_t(quad, t);
388e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    return SkDoubleToScalar(y);
389e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com}
390e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
391e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.comstatic SkScalar CubicDYAtT(const SkPoint a[4], double t) {
392e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
39305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com    double y = dy_at_t(cubic, t);
394e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    return SkDoubleToScalar(y);
395e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com}
396e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
397e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.comstatic SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {
398e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    NULL,
399e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    LineDYAtT,
400e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    QuadDYAtT,
401e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    CubicDYAtT
402e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com};
403e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
4047ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.comstatic SkVector LineDXDYAtT(const SkPoint a[2], double ) {
40545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return a[1] - a[0];
40645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}
40745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
4087ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.comstatic SkVector QuadDXDYAtT(const SkPoint a[3], double t) {
40945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    MAKE_CONST_QUAD(quad, a);
4107ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    _Vector v = dxdy_at_t(quad, t);
4117ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    return v.asSkVector();
41245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}
41345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
4147ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.comstatic SkVector CubicDXDYAtT(const SkPoint a[4], double t) {
41545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
4167ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    _Vector v = dxdy_at_t(cubic, t);
4177ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    return v.asSkVector();
41845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}
41945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
4207ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.comstatic SkVector (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {
42145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    NULL,
42245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    LineDXDYAtT,
42345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    QuadDXDYAtT,
42445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    CubicDXDYAtT
42545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com};
42645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
427fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT,
428fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkPoint sub[2]) {
42932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
430fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    _Line dst;
431fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub_divide(aLine, startT, endT, dst);
432fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
433fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
434fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
435fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
436fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
437fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
438fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void QuadSubDivide(const SkPoint a[3], double startT, double endT,
439fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkPoint sub[3]) {
44032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
441fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    Quadratic dst;
442fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub_divide(aQuad, startT, endT, dst);
443fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
444fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
445fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
446fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
447fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[2].fX = SkDoubleToScalar(dst[2].x);
448fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[2].fY = SkDoubleToScalar(dst[2].y);
449fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
450fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
451fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void CubicSubDivide(const SkPoint a[4], double startT, double endT,
452fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkPoint sub[4]) {
45332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
454fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    Cubic dst;
455fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub_divide(aCubic, startT, endT, dst);
456fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
457fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
458fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
459fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
460fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[2].fX = SkDoubleToScalar(dst[2].x);
461fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[2].fY = SkDoubleToScalar(dst[2].y);
462fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[3].fX = SkDoubleToScalar(dst[3].x);
463fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    sub[3].fY = SkDoubleToScalar(dst[3].y);
464fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
465fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
466b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comstatic void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
467b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        SkPoint []) = {
468b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    NULL,
469b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    LineSubDivide,
470b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    QuadSubDivide,
471b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    CubicSubDivide
472b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com};
473b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com
474aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.comstatic void LineSubDivideHD(const SkPoint a[2], double startT, double endT, _Line& dst) {
47532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
4763350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    sub_divide(aLine, startT, endT, dst);
4773350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com}
4783350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com
479aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.comstatic void QuadSubDivideHD(const SkPoint a[3], double startT, double endT, Quadratic& dst) {
48032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
4813350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    sub_divide(aQuad, startT, endT, dst);
4823350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com}
4833350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com
484aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.comstatic void CubicSubDivideHD(const SkPoint a[4], double startT, double endT, Cubic& dst) {
48532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
4863350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    sub_divide(aCubic, startT, endT, dst);
4873350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com}
4883350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com
48945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic SkPoint QuadTop(const SkPoint a[3], double startT, double endT) {
49045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    MAKE_CONST_QUAD(quad, a);
49145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    _Point topPt = top(quad, startT, endT);
49245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return topPt.asSkPoint();
49345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}
49445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
49545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic SkPoint CubicTop(const SkPoint a[3], double startT, double endT) {
49645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    MAKE_CONST_CUBIC(cubic, a);
49745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    _Point topPt = top(cubic, startT, endT);
49845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return topPt.asSkPoint();
49945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}
50045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
50145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic SkPoint (* SegmentTop[])(const SkPoint[], double , double ) = {
50245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    NULL,
50345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    NULL,
50445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    QuadTop,
50545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    CubicTop
50645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com};
50745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com
50865f9f0a1664a9cb38157ccfbcc3e0e936af0a58ecaryclark@google.com#if DEBUG_UNUSED
509fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void QuadSubBounds(const SkPoint a[3], double startT, double endT,
510fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkRect& bounds) {
511fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    SkPoint dst[3];
512fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    QuadSubDivide(a, startT, endT, dst);
513fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bounds.fLeft = bounds.fRight = dst[0].fX;
514fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bounds.fTop = bounds.fBottom = dst[0].fY;
515fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    for (int index = 1; index < 3; ++index) {
516fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        bounds.growToInclude(dst[index].fX, dst[index].fY);
517fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
518fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
519fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
520fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic void CubicSubBounds(const SkPoint a[4], double startT, double endT,
521fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkRect& bounds) {
522fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    SkPoint dst[4];
523fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    CubicSubDivide(a, startT, endT, dst);
524fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bounds.fLeft = bounds.fRight = dst[0].fX;
525fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bounds.fTop = bounds.fBottom = dst[0].fY;
526fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    for (int index = 1; index < 4; ++index) {
527fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        bounds.growToInclude(dst[index].fX, dst[index].fY);
528fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
529fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
53065f9f0a1664a9cb38157ccfbcc3e0e936af0a58ecaryclark@google.com#endif
531fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
53215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comstatic SkPath::Verb QuadReduceOrder(const SkPoint a[3],
533fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkTDArray<SkPoint>& reducePts) {
53432546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
535fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    Quadratic dst;
53647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com    int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);
53724bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com    if (order == 2) { // quad became line
53824bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        for (int index = 0; index < order; ++index) {
53924bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            SkPoint* pt = reducePts.append();
54024bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            pt->fX = SkDoubleToScalar(dst[index].x);
54124bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            pt->fY = SkDoubleToScalar(dst[index].y);
54224bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        }
543fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
544fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return (SkPath::Verb) (order - 1);
545fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
546fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
547fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkPath::Verb CubicReduceOrder(const SkPoint a[4],
548fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkTDArray<SkPoint>& reducePts) {
54932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
550fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    Cubic dst;
55147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill);
55224bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com    if (order == 2 || order == 3) { // cubic became line or quad
55324bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        for (int index = 0; index < order; ++index) {
55424bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            SkPoint* pt = reducePts.append();
55524bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            pt->fX = SkDoubleToScalar(dst[index].x);
55624bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com            pt->fY = SkDoubleToScalar(dst[index].y);
55724bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        }
558fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
559fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    return (SkPath::Verb) (order - 1);
560fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
561fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
56215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comstatic bool QuadIsLinear(const SkPoint a[3]) {
56332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
56415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    return isLinear(aQuad, 0, 2);
56515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com}
56615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
56715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comstatic bool CubicIsLinear(const SkPoint a[4]) {
56832546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
56915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    return isLinear(aCubic, 0, 3);
57015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com}
57115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
572fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
57332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_LINE(aLine, a);
574fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    double x[2];
575fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    xy_at_t(aLine, startT, x[0], *(double*) 0);
576495f8e435b677f28913cd2adc8caa8d3d766dd17caryclark@google.com    xy_at_t(aLine, endT, x[1], *(double*) 0);
577495f8e435b677f28913cd2adc8caa8d3d766dd17caryclark@google.com    return SkMinScalar((float) x[0], (float) x[1]);
578fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
579fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
580fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
58132546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
582b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    return (float) leftMostT(aQuad, startT, endT);
583fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
584fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
585fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
58632546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
587b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    return (float) leftMostT(aCubic, startT, endT);
588fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com}
589fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
590fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstatic SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
591fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    NULL,
592fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    LineLeftMost,
593fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    QuadLeftMost,
594fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    CubicLeftMost
595fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com};
596fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
5976aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com#if 0 // currently unused
598235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comstatic int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
599235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        Intersections& intersections) {
600235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
601235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    MAKE_CONST_LINE(bLine, b);
602235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    return intersectRay(aQuad, bLine, intersections);
603235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com}
6046aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com#endif
6056aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com
606f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic int QuadRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) {
6076aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    MAKE_CONST_QUAD(aQuad, a);
6086aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    return intersectRay(aQuad, bLine, intersections);
6096aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com}
610235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com
611f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic int CubicRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) {
612f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    MAKE_CONST_CUBIC(aCubic, a);
613f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    return intersectRay(aCubic, bLine, intersections);
614f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com}
615f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
616f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comstatic int (* const SegmentRayIntersect[])(const SkPoint [], const _Line& , Intersections&) = {
617f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    NULL,
618f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    NULL,
619f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    QuadRayIntersect,
620f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    CubicRayIntersect
621f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com};
622f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
623f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
624f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com
625db0b3e099f888213535c4ad4c785b84544309033caryclark@google.comstatic bool LineVertical(const SkPoint a[2], double startT, double endT) {
626db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    MAKE_CONST_LINE(aLine, a);
627db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    double x[2];
628db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    xy_at_t(aLine, startT, x[0], *(double*) 0);
629db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    xy_at_t(aLine, endT, x[1], *(double*) 0);
6306d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com    return AlmostEqualUlps((float) x[0], (float) x[1]);
631db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com}
632db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com
633db0b3e099f888213535c4ad4c785b84544309033caryclark@google.comstatic bool QuadVertical(const SkPoint a[3], double startT, double endT) {
634db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    SkPoint dst[3];
635db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    QuadSubDivide(a, startT, endT, dst);
6366d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
637db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com}
638db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com
639db0b3e099f888213535c4ad4c785b84544309033caryclark@google.comstatic bool CubicVertical(const SkPoint a[4], double startT, double endT) {
640db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    SkPoint dst[4];
641db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    CubicSubDivide(a, startT, endT, dst);
6426d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com    return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
6436d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com            && AlmostEqualUlps(dst[2].fX, dst[3].fX);
644db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com}
645db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com
646db0b3e099f888213535c4ad4c785b84544309033caryclark@google.comstatic bool (* const SegmentVertical[])(const SkPoint [], double , double) = {
647db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    NULL,
648db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    LineVertical,
649db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    QuadVertical,
650db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    CubicVertical
651db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com};
652db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com
653b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comclass Segment;
654b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com
6556aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.comstruct Span {
6566aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    Segment* fOther;
6576aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    mutable SkPoint fPt; // lazily computed as needed
6586aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    double fT;
6596aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    double fOtherT; // value at fOther[fOtherIndex].fT
6606aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    int fOtherIndex;  // can't be used during intersection
66131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com    int fWindSum; // accumulated from contours surrounding this one.
66231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com    int fOppSum; // for binary operators: the opposite winding sum
6636aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
66457cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
6656aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    bool fDone; // if set, this span to next higher T has been processed
666c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    bool fUnsortableStart; // set when start is part of an unsortable pair
667c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    bool fUnsortableEnd; // set when end is part of an unsortable pair
668f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool fTiny; // if set, span may still be considered once for edge following
6694aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com    bool fLoop; // set when a cubic loops back to this point
6706aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com};
6716aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com
67215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// sorting angles
67315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com// given angles of {dx dy ddx ddy dddx dddy} sort them
67415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comclass Angle {
67515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.compublic:
676b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // FIXME: this is bogus for quads and cubics
677b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // if the quads and cubics' line from end pt to ctrl pt are coincident,
678b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // there's no obvious way to determine the curve ordering from the
679b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // derivatives alone. In particular, if one quadratic's coincident tangent
680b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // is longer than the other curve, the final control point can place the
681b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // longer curve on either side of the shorter one.
682b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
683b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    // may provide some help, but nothing has been figured out yet.
6844f55d39a175afe70c1231eb7389790633210106fskia.committer@gmail.com
68532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    /*(
68632546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    for quads and cubics, set up a parameterized line (e.g. LineParameters )
68732546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    for points [0] to [1]. See if point [2] is on that line, or on one side
68832546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    or the other. If it both quads' end points are on the same side, choose
68932546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    the shorter tangent. If the tangents are equal, choose the better second
69032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    tangent angle
6914f55d39a175afe70c1231eb7389790633210106fskia.committer@gmail.com
6926aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    maybe I could set up LineParameters lazily
69332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com    */
69415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    bool operator<(const Angle& rh) const {
695235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double y = dy();
696235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double ry = rh.dy();
697235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
698235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            return y < 0;
699b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        }
700235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double x = dx();
701235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double rx = rh.dx();
702235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        if (y == 0 && ry == 0 && x * rx < 0) {
703235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            return x < rx;
70415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        }
7056aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double x_ry = x * ry;
7066aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double rx_y = rx * y;
7076aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double cmp = x_ry - rx_y;
708c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com        if (!approximately_zero(cmp)) {
70915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            return cmp < 0;
71015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        }
711d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        if (approximately_zero(x_ry) && approximately_zero(rx_y)
712d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com                && !approximately_zero_squared(cmp)) {
713d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com            return cmp < 0;
714d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        }
715c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        // at this point, the initial tangent line is coincident
71686adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com        // see if edges curl away from each other
71731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
71831143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                || !approximately_zero(rh.fSide))) {
719c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // FIXME: running demo will trigger this assertion
720c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // (don't know if commenting out will trigger further assertion or not)
721c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // commenting it out allows demo to run in release, though
722c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com     //       SkASSERT(fSide != rh.fSide);
723c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            return fSide < rh.fSide;
724c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        }
7256aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        // see if either curve can be lengthened and try the tangent compare again
7266aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
7276aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com                && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
7286aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            Angle longer = *this;
7296aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            Angle rhLonger = rh;
7306aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            if (longer.lengthen() | rhLonger.lengthen()) {
7316aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com                return longer < rhLonger;
7326aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            }
7338f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com    #if 0
734a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            // what if we extend in the other direction?
735a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            longer = *this;
736a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            rhLonger = rh;
737a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            if (longer.reverseLengthen() | rhLonger.reverseLengthen()) {
738a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com                return longer < rhLonger;
739a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            }
7408f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com    #endif
741b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        }
742185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
74331143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                || (rh.fVerb == SkPath::kLine_Verb
74431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                && approximately_zero(rx) && approximately_zero(ry))) {
745185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            // See general unsortable comment below. This case can happen when
746185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            // one line has a non-zero change in t but no change in x and y.
747185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            fUnsortable = true;
748185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            rh.fUnsortable = true;
749185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            return this < &rh; // even with no solution, return a stable sort
750185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        }
751e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
752e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com                || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
753e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com            fUnsortable = true;
754e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com            rh.fUnsortable = true;
755e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com            return this < &rh; // even with no solution, return a stable sort
756e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        }
757f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com        SkASSERT(fVerb >= SkPath::kQuad_Verb);
758f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com        SkASSERT(rh.fVerb >= SkPath::kQuad_Verb);
759c1ad0226087e10b1f300b5a45e3d6fdb23b8d1b8skia.committer@gmail.com        // FIXME: until I can think of something better, project a ray from the
760d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        // end of the shorter tangent to midway between the end points
761d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        // through both curves and use the resulting angle to sort
762235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
763235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double len = fTangent1.normalSquared();
764235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        double rlen = rh.fTangent1.normalSquared();
7656aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        _Line ray;
766235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        Intersections i, ri;
767d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        int roots, rroots;
768d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        bool flip = false;
769d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        do {
770f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            bool useThis = (len < rlen) ^ flip;
771f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            const Cubic& part = useThis ? fCurvePart : rh.fCurvePart;
772f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
773f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
774f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com                part[2] : part[1];
775f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            ray[1].x = (part[0].x + part[partVerb].x) / 2;
776f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            ray[1].y = (part[0].y + part[partVerb].y) / 2;
777d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com            SkASSERT(ray[0] != ray[1]);
778f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            roots = (*SegmentRayIntersect[fVerb])(fPts, ray, i);
779f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            rroots = (*SegmentRayIntersect[rh.fVerb])(rh.fPts, ray, ri);
780d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        } while ((roots == 0 || rroots == 0) && (flip ^= true));
781c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        if (roots == 0 || rroots == 0) {
782c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // FIXME: we don't have a solution in this case. The interim solution
783c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // is to mark the edges as unsortable, exclude them from this and
784c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            // future computations, and allow the returned path to be fragmented
785c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            fUnsortable = true;
786c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            rh.fUnsortable = true;
787c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            return this < &rh; // even with no solution, return a stable sort
788c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        }
7896aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        _Point loc;
7906aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double best = SK_ScalarInfinity;
7916aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double dx, dy, dist;
792235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        int index;
793235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        for (index = 0; index < roots; ++index) {
794f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            (*SegmentXYAtT2[fVerb])(fPts, i.fT[0][index], &loc);
7956aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            dx = loc.x - ray[0].x;
7966aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            dy = loc.y - ray[0].y;
797235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            dist = dx * dx + dy * dy;
798235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            if (best > dist) {
799235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com                best = dist;
800235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            }
801235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        }
802235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        for (index = 0; index < rroots; ++index) {
803f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            (*SegmentXYAtT2[rh.fVerb])(rh.fPts, ri.fT[0][index], &loc);
8046aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            dx = loc.x - ray[0].x;
8056aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            dy = loc.y - ray[0].y;
806235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            dist = dx * dx + dy * dy;
807235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            if (best > dist) {
808235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com                return fSide < 0;
809235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            }
810235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        }
811235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        return fSide > 0;
812b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    }
813d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
81447580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com    double dx() const {
815235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        return fTangent1.dx();
81647580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com    }
817b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com
8187db7c6bba9e9a61ad574a1d60b65bce4563beee5caryclark@google.com    double dy() const {
819235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        return fTangent1.dy();
8207db7c6bba9e9a61ad574a1d60b65bce4563beee5caryclark@google.com    }
8217db7c6bba9e9a61ad574a1d60b65bce4563beee5caryclark@google.com
822b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    int end() const {
823b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        return fEnd;
82415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    }
82515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
82688f7d0cb09707355bc9079d4b0569537e8048fa9caryclark@google.com    bool isHorizontal() const {
827235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        return dy() == 0 && fVerb == SkPath::kLine_Verb;
82888f7d0cb09707355bc9079d4b0569537e8048fa9caryclark@google.com    }
829a27096b4740775ae141fd0abaf456d706065c5eeskia.committer@gmail.com
8306aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    bool lengthen() {
8316aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        int newEnd = fEnd;
8326aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
8336aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            fEnd = newEnd;
8346aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            setSpans();
8356aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            return true;
8366aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        }
8376aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        return false;
8386aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    }
8396aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com
840a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com    bool reverseLengthen() {
841a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        if (fReversed) {
842a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            return false;
843a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        }
844a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        int newEnd = fStart;
845a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
846a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            fEnd = newEnd;
847a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            fReversed = true;
848a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            setSpans();
849a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            return true;
850a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        }
851a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        return false;
852a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com    }
853a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com
8543350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
8556aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            int start, int end, const SkTDArray<Span>& spans) {
8563350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        fSegment = segment;
8573350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        fStart = start;
8583350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        fEnd = end;
859235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        fPts = orig;
860235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        fVerb = verb;
8616aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        fSpans = &spans;
862a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        fReversed = false;
863c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        fUnsortable = false;
8646aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        setSpans();
8656aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    }
866439cb51451ef6f55f65dab90eb7f91acf67ea8feskia.committer@gmail.com
8678f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com
8686aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    void setSpans() {
8696aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double startT = (*fSpans)[fStart].fT;
8706aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        double endT = (*fSpans)[fEnd].fT;
8716aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        switch (fVerb) {
87232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com        case SkPath::kLine_Verb:
87332546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            _Line l;
8746aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            LineSubDivideHD(fPts, startT, endT, l);
87532546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            // OPTIMIZATION: for pure line compares, we never need fTangent1.c
87632546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            fTangent1.lineEndPoints(l);
877235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            fSide = 0;
87832546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com            break;
879f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com        case SkPath::kQuad_Verb: {
880f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            Quadratic& quad = (Quadratic&)fCurvePart;
881f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            QuadSubDivideHD(fPts, startT, endT, quad);
882f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            fTangent1.quadEndPoints(quad, 0, 1);
883aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com            if (dx() == 0 && dy() == 0) {
884f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com                fTangent1.quadEndPoints(quad);
885aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com            }
886f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
887f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            } break;
88886adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com        case SkPath::kCubic_Verb: {
88986adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com            int nextC = 2;
890f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            CubicSubDivideHD(fPts, startT, endT, fCurvePart);
891f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            fTangent1.cubicEndPoints(fCurvePart, 0, 1);
892aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com            if (dx() == 0 && dy() == 0) {
893f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com                fTangent1.cubicEndPoints(fCurvePart, 0, 2);
89486adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com                nextC = 3;
895aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com                if (dx() == 0 && dy() == 0) {
896f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com                    fTangent1.cubicEndPoints(fCurvePart, 0, 3);
897aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com                }
898aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com            }
899f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com            fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only
90086adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com            if (nextC == 2 && approximately_zero(fSide)) {
901f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com                fSide = -fTangent1.pointDistance(fCurvePart[3]);
90286adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com            }
90386adc0d414496185972a7191aca904e9e7223d7dcaryclark@google.com            } break;
904235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        default:
905235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com            SkASSERT(0);
9063350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        }
907db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        fUnsortable = dx() == 0 && dy() == 0;
908f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (fUnsortable) {
909f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
910f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
911f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkASSERT(fStart != fEnd);
912f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
913f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        for (int index = fStart; index != fEnd; index += step) {
9148f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#if 1
9158f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            const Span& thisSpan = (*fSpans)[index];
9168f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            const Span& nextSpan = (*fSpans)[index + step];
91747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com            if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
9188f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                continue;
919f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            }
9208f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
9218f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#if DEBUG_UNSORTABLE
9228f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            if (fUnsortable) {
9238f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                SkPoint iPt, ePt;
9248f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                (*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt);
9258f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                (*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt);
9268f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
9278f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                        index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
9288f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            }
9298f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#endif
9308f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            return;
9318f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#else
9328f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            if ((*fSpans)[index].fUnsortableStart) {
933f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                fUnsortable = true;
934f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                return;
935f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            }
936e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com#endif
937f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
9388f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#if 1
9398f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#if DEBUG_UNSORTABLE
9408f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        SkPoint iPt, ePt;
9418f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        (*SegmentXYAtT[fVerb])(fPts, startT, &iPt);
9428f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        (*SegmentXYAtT[fVerb])(fPts, endT, &ePt);
9438f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
9448f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
9458f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#endif
9468f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        fUnsortable = true;
9478f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com#endif
9483350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com    }
94988f7d0cb09707355bc9079d4b0569537e8048fa9caryclark@google.com
9501577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com    Segment* segment() const {
9518dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        return const_cast<Segment*>(fSegment);
952b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    }
953d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
954b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    int sign() const {
955495f8e435b677f28913cd2adc8caa8d3d766dd17caryclark@google.com        return SkSign32(fStart - fEnd);
956b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    }
957d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
958c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    const SkTDArray<Span>* spans() const {
959c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        return fSpans;
960c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    }
961c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com
962b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    int start() const {
963b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        return fStart;
96415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    }
96520c301bd1aa4578c6d0abb23ac2c72b5fbb436dbskia.committer@gmail.com
966c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    bool unsortable() const {
967c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        return fUnsortable;
968c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    }
96915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
970c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com#if DEBUG_ANGLE
9716aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    const SkPoint* pts() const {
9726aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        return fPts;
9736aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    }
9746aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com
9756aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    SkPath::Verb verb() const {
9766aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        return fVerb;
9776aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    }
978439cb51451ef6f55f65dab90eb7f91acf67ea8feskia.committer@gmail.com
979c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com    void debugShow(const SkPoint& a) const {
9806aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
981c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com    }
982c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com#endif
983c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com
98415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comprivate:
985235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    const SkPoint* fPts;
986f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com    Cubic fCurvePart;
987235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    SkPath::Verb fVerb;
988235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    double fSide;
989235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com    LineParameters fTangent1;
9906aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com    const SkTDArray<Span>* fSpans;
9918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    const Segment* fSegment;
992b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    int fStart;
993b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    int fEnd;
994a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com    bool fReversed;
995c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com    mutable bool fUnsortable; // this alone is editable by the less than operator
99615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com};
99715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
9988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com// Bounds, unlike Rect, does not consider a line to be empty.
999fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comstruct Bounds : public SkRect {
1000fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    static bool Intersects(const Bounds& a, const Bounds& b) {
1001fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
1002fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
1003fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1004fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
10058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
10068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (left < fLeft) {
10078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            fLeft = left;
10088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
10098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (top < fTop) {
10108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            fTop = top;
10118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
10128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (right > fRight) {
10138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            fRight = right;
10148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
10158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (bottom > fBottom) {
10168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            fBottom = bottom;
10178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
10188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
10198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
10208dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    void add(const Bounds& toAdd) {
10218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
10228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
1023c7b4be7f110bc7b487c3c3f28d82877584e74c2fskia.committer@gmail.com
1024e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    void add(const SkPoint& pt) {
1025e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        if (pt.fX < fLeft) fLeft = pt.fX;
1026e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        if (pt.fY < fTop) fTop = pt.fY;
1027e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        if (pt.fX > fRight) fRight = pt.fX;
1028e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        if (pt.fY > fBottom) fBottom = pt.fY;
1029e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    }
1030e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
1031fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bool isEmpty() {
1032fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        return fLeft > fRight || fTop > fBottom
1033235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com                || (fLeft == fRight && fTop == fBottom)
1034beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com                || sk_double_isnan(fLeft) || sk_double_isnan(fRight)
1035beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com                || sk_double_isnan(fTop) || sk_double_isnan(fBottom);
1036fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
103703682beb8c1c5dfe714933e9419e1412b33c932dskia.committer@gmail.com
1038fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    void setCubicBounds(const SkPoint a[4]) {
1039fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        _Rect dRect;
104032546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com        MAKE_CONST_CUBIC(cubic, a);
1041fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        dRect.setBounds(cubic);
1042b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
1043b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com                (float) dRect.bottom);
1044fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1045fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
10461304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    void setLineBounds(const SkPoint a[2]) {
10471304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com        setPoint(a[0]);
10481304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com        add(a[1]);
10491304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    }
10501304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com
1051fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    void setQuadBounds(const SkPoint a[3]) {
105232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com        MAKE_CONST_QUAD(quad, a);
1053fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        _Rect dRect;
1054fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        dRect.setBounds(quad);
1055b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        set((float) dRect.left, (float) dRect.top, (float) dRect.right,
1056b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com                (float) dRect.bottom);
1057fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1058e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com
1059e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    void setPoint(const SkPoint& pt) {
1060e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        fLeft = fRight = pt.fX;
1061e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com        fTop = fBottom = pt.fY;
1062e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com    }
1063fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com};
1064fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com
10651304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.comstatic void (Bounds::*setSegmentBounds[])(const SkPoint[]) = {
10661304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    NULL,
10671304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    &Bounds::setLineBounds,
10681304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    &Bounds::setQuadBounds,
10691304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com    &Bounds::setCubicBounds
10701304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com};
10711304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com
10727ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com// OPTIMIZATION: does the following also work, and is it any faster?
10737ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com// return outerWinding * innerWinding > 0
10747ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com//      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
10752ddff9388694263c7be9347de7eb768cd0847997caryclark@google.comstatic bool useInnerWinding(int outerWinding, int innerWinding) {
1076c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com    SkASSERT(outerWinding != SK_MaxS32);
1077c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com    SkASSERT(innerWinding != SK_MaxS32);
10782ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    int absOut = abs(outerWinding);
10792ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    int absIn = abs(innerWinding);
10802ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
10815e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#if 0 && DEBUG_WINDING
1082c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com    if (outerWinding * innerWinding < 0) {
108324bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
10842ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com                outerWinding, innerWinding, result ? "true" : "false");
10852ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    }
1086c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#endif
10872ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    return result;
10882ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com}
10892ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com
10909f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com#define F (false)      // discard the edge
10919f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com#define T (true)       // keep the edge
10929f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com
1093d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.comstatic const bool gUnaryActiveEdge[2][2] = {
1094d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com//  from=0  from=1
1095d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com//  to=0,1  to=0,1
1096d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    {F, T}, {T, F},
1097d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com};
1098d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com
10999f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.comstatic const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {
11009f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com//                 miFrom=0                              miFrom=1
11019f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com//         miTo=0            miTo=1              miTo=0             miTo=1
11029f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com//    suFrom=0    1     suFrom=0     1      suFrom=0    1      suFrom=0    1
11039f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com//   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
11049f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com    {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
11059f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com    {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
11069f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com    {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
11079f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com    {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
1108235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com};
1109235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com
11109f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com#undef F
11119f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com#undef T
1112235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com
1113f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com// wrap path to keep track of whether the contour is initialized and non-empty
1114f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.comclass PathWrapper {
1115f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.compublic:
1116f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    PathWrapper(SkPath& path)
1117f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        : fPathPtr(&path)
1118d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        , fCloses(0)
1119d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        , fMoves(0)
1120f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    {
1121f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        init();
1122f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1123f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1124f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void close() {
1125f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (!fHasMove) {
1126f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
1127f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1128f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        bool callClose = isClosed();
1129f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        lineTo();
1130f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (fEmpty) {
1131f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
1132f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1133f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (callClose) {
1134f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #if DEBUG_PATH_CONSTRUCTION
1135f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            SkDebugf("path.close();\n");
1136f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #endif
1137f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            fPathPtr->close();
1138d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com            fCloses++;
1139f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1140f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        init();
1141f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1142f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1143f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
1144f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        lineTo();
1145f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        moveTo();
114685ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fDefer[1] = pt3;
114785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        nudge();
114885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fDefer[0] = fDefer[1];
1149f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#if DEBUG_PATH_CONSTRUCTION
1150f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
115185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com                pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1152f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#endif
115385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
1154f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fEmpty = false;
1155f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1156f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1157f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void deferredLine(const SkPoint& pt) {
1158f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (pt == fDefer[1]) {
1159f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
1160f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1161f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (changedSlopes(pt)) {
1162f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            lineTo();
1163f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            fDefer[0] = fDefer[1];
1164f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1165f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fDefer[1] = pt;
1166f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1167f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1168f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void deferredMove(const SkPoint& pt) {
1169f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fMoved = true;
1170f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fHasMove = true;
1171f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fEmpty = true;
1172f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fDefer[0] = fDefer[1] = pt;
1173f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1174549c93ef979aeb4dcb65b3d0fca4b58e8ab62227skia.committer@gmail.com
1175f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void deferredMoveLine(const SkPoint& pt) {
1176f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (!fHasMove) {
1177f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            deferredMove(pt);
1178f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1179f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        deferredLine(pt);
1180f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1181549c93ef979aeb4dcb65b3d0fca4b58e8ab62227skia.committer@gmail.com
1182f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool hasMove() const {
1183f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        return fHasMove;
1184f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1185f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1186f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void init() {
1187f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fEmpty = true;
1188f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fHasMove = false;
1189f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fMoved = false;
1190f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1191f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1192f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool isClosed() const {
1193f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        return !fEmpty && fFirstPt == fDefer[1];
1194f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1195549c93ef979aeb4dcb65b3d0fca4b58e8ab62227skia.committer@gmail.com
1196f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void lineTo() {
1197f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (fDefer[0] == fDefer[1]) {
1198f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
1199f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1200f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        moveTo();
120185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        nudge();
1202f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fEmpty = false;
1203f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#if DEBUG_PATH_CONSTRUCTION
1204f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
1205f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#endif
1206f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);
1207f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fDefer[0] = fDefer[1];
1208f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1209f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1210f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    const SkPath* nativePath() const {
1211f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        return fPathPtr;
1212f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1213cdcb2ce2744c7e5c47453328dbf292edee79ab37skia.committer@gmail.com
121485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com    void nudge() {
121585ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)
121685ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com                || !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {
121785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com            return;
121885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        }
121985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fDefer[1] = fFirstPt;
122085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com    }
1221f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1222f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
1223f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        lineTo();
1224f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        moveTo();
122585ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fDefer[1] = pt2;
122685ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        nudge();
122785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fDefer[0] = fDefer[1];
1228f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#if DEBUG_PATH_CONSTRUCTION
1229f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
123085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com                pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1231f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#endif
123285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com        fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
1233f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fEmpty = false;
1234f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
12357a03d86a3d9adcb13432fbd82039725149487c97skia.committer@gmail.com
1236d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    bool someAssemblyRequired() const {
1237d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        return fCloses < fMoves;
1238d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    }
1239f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1240f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.comprotected:
1241f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool changedSlopes(const SkPoint& pt) const {
1242f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (fDefer[0] == fDefer[1]) {
1243f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return false;
1244549c93ef979aeb4dcb65b3d0fca4b58e8ab62227skia.committer@gmail.com        }
1245f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;
1246f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;
1247f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkScalar lineDx = pt.fX - fDefer[1].fX;
1248f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkScalar lineDy = pt.fY - fDefer[1].fY;
1249f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        return deferDx * lineDy != deferDy * lineDx;
1250f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1251f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1252f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    void moveTo() {
1253f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (!fMoved) {
1254f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            return;
1255f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
1256f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fFirstPt = fDefer[0];
1257f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#if DEBUG_PATH_CONSTRUCTION
1258f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);
1259f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#endif
1260f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);
1261f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        fMoved = false;
1262d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        fMoves++;
1263f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    }
1264f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1265f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.comprivate:
1266f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    SkPath* fPathPtr;
1267f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    SkPoint fDefer[2];
1268f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    SkPoint fFirstPt;
1269d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    int fCloses;
1270d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    int fMoves;
1271f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool fEmpty;
1272f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool fHasMove;
1273f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    bool fMoved;
1274f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com};
1275f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com
1276fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comclass Segment {
1277fa0588ff672564af1c235a63589573829035a60bcaryclark@google.compublic:
1278fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    Segment() {
1279fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#if DEBUG_DUMP
1280fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fID = ++gSegmentID;
1281fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#endif
1282fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
128324c29d91caa4eaa31f9e77bad614627a252df35eskia.committer@gmail.com
1284fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com    bool operator<(const Segment& rh) const {
1285fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com        return fBounds.fTop < rh.fBounds.fTop;
1286fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com    }
1287fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com
12884eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
12899764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        if (activeAngleInner(index, done, angles)) {
12909764cc6c109dba208592fe5f16447b8439375746caryclark@google.com            return true;
12919764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        }
1292fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        int lesser = index;
1293db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        while (--lesser >= 0 && equalPoints(index, lesser)) {
12949764cc6c109dba208592fe5f16447b8439375746caryclark@google.com            if (activeAngleOther(lesser, done, angles)) {
1295fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com                return true;
1296fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com            }
1297fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        }
1298db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        lesser = index;
1299fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        do {
13009764cc6c109dba208592fe5f16447b8439375746caryclark@google.com            if (activeAngleOther(index, done, angles)) {
1301fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com                return true;
1302fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com            }
1303db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        } while (++index < fTs.count() && equalPoints(index, lesser));
1304fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        return false;
1305fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com    }
1306fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com
13074eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
1308fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        Span* span = &fTs[index];
1309fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        Segment* other = span->fOther;
1310fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        int oIndex = span->fOtherIndex;
13119764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        return other->activeAngleInner(oIndex, done, angles);
13129764cc6c109dba208592fe5f16447b8439375746caryclark@google.com    }
1313d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
13144eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
1315fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com        int next = nextExactSpan(index, 1);
13169764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        if (next > 0) {
13174eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            Span& upSpan = fTs[index];
13184eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            if (upSpan.fWindValue || upSpan.fOppValue) {
1319210acafc5207765e12474064aa01640d5af92770caryclark@google.com                addAngle(angles, index, next);
1320f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                if (upSpan.fDone || upSpan.fUnsortableEnd) {
1321210acafc5207765e12474064aa01640d5af92770caryclark@google.com                    done++;
1322210acafc5207765e12474064aa01640d5af92770caryclark@google.com                } else if (upSpan.fWindSum != SK_MinS32) {
1323210acafc5207765e12474064aa01640d5af92770caryclark@google.com                    return true;
1324210acafc5207765e12474064aa01640d5af92770caryclark@google.com                }
13254eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            } else if (!upSpan.fDone) {
13264eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                upSpan.fDone = true;
13274eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                fDoneSpans++;
13289764cc6c109dba208592fe5f16447b8439375746caryclark@google.com            }
1329fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        }
1330fb51afb03e76c5701fffaa847584a8b7b2c18a7ecaryclark@google.com        int prev = nextExactSpan(index, -1);
1331fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com        // edge leading into junction
13329764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        if (prev >= 0) {
13334eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            Span& downSpan = fTs[prev];
13344eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            if (downSpan.fWindValue || downSpan.fOppValue) {
1335210acafc5207765e12474064aa01640d5af92770caryclark@google.com                addAngle(angles, index, prev);
1336210acafc5207765e12474064aa01640d5af92770caryclark@google.com                if (downSpan.fDone) {
1337210acafc5207765e12474064aa01640d5af92770caryclark@google.com                    done++;
1338210acafc5207765e12474064aa01640d5af92770caryclark@google.com                 } else if (downSpan.fWindSum != SK_MinS32) {
1339210acafc5207765e12474064aa01640d5af92770caryclark@google.com                    return true;
1340210acafc5207765e12474064aa01640d5af92770caryclark@google.com                }
13414eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            } else if (!downSpan.fDone) {
13424eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                downSpan.fDone = true;
13434eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                fDoneSpans++;
13449764cc6c109dba208592fe5f16447b8439375746caryclark@google.com            }
13459764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        }
13469764cc6c109dba208592fe5f16447b8439375746caryclark@google.com        return false;
1347fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com    }
1348fa4a6e964691ff9a88bc047418abe2d4324dfcaecaryclark@google.com
134945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    SkPoint activeLeftTop(bool onlySortable, int* firstT) const {
13508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkASSERT(!done());
135145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
13528dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        int count = fTs.count();
135345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        // see if either end is not done since we want smaller Y of the pair
13548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        bool lastDone = true;
1355f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        bool lastUnsortable = false;
135645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        double lastT = -1;
13578dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        for (int index = 0; index < count; ++index) {
1358f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            const Span& span = fTs[index];
135945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
1360f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                goto next;
1361f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            }
136245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            if (span.fDone && lastDone) {
136345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                goto next;
136445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            }
136545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            if (approximately_negative(span.fT - lastT)) {
136645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                goto next;
136745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            }
136845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            {
136945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                const SkPoint& xy = xyAtT(&span);
137045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
137145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    topPt = xy;
137245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    if (firstT) {
137345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                        *firstT = index;
137445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    }
1375f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                }
137645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                if (fVerb != SkPath::kLine_Verb && !lastDone) {
137745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT);
137845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
137945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                            && topPt.fX > curveTop.fX)) {
138045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                        topPt = curveTop;
138145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                        if (firstT) {
138245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                            *firstT = index;
138345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                        }
138445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                    }
13858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                }
138645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                lastT = span.fT;
13878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            }
1388f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    next:
1389f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            lastDone = span.fDone;
1390f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            lastUnsortable = span.fUnsortableEnd;
13918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
139245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        return topPt;
13938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
13948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
13957fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
13967fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        int sumMiWinding = updateWinding(endIndex, index);
13977fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        int sumSuWinding = updateOppWinding(endIndex, index);
13987fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        if (fOperand) {
13997fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com            SkTSwap<int>(sumMiWinding, sumSuWinding);
14007fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        }
14017fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
14027fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,
14039f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
14047fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com    }
1405c7b4be7f110bc7b487c3c3f28d82877584e74c2fskia.committer@gmail.com
14069f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,
1407c3d7d90973528527131c72549b10c2a21300e0acskia.committer@gmail.com            int& sumMiWinding, int& sumSuWinding,
14087fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com            int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
14097fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
14107fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com                maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
14119f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        bool miFrom;
14129f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        bool miTo;
14139f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        bool suFrom;
14149f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        bool suTo;
14157fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        if (operand()) {
14169f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            miFrom = (oppMaxWinding & xorMiMask) != 0;
14179f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            miTo = (oppSumWinding & xorMiMask) != 0;
14189f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            suFrom = (maxWinding & xorSuMask) != 0;
14199f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            suTo = (sumWinding & xorSuMask) != 0;
14207fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        } else {
14219f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            miFrom = (maxWinding & xorMiMask) != 0;
14229f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            miTo = (sumWinding & xorMiMask) != 0;
14239f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            suFrom = (oppMaxWinding & xorSuMask) != 0;
14249f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com            suTo = (oppSumWinding & xorSuMask) != 0;
14257fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com        }
14269f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
1427beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#if DEBUG_ACTIVE_OP
1428beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com        SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
1429beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com                kShapeOpStr[op], miFrom, miTo, suFrom, suTo, result);
1430beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#endif
14319f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        SkASSERT(result != -1);
14329f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com        return result;
14337fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com    }
14347fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com
1435d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    bool activeWinding(int index, int endIndex) {
1436d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        int sumWinding = updateWinding(endIndex, index);
1437d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        int maxWinding;
1438d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        return activeWinding(index, endIndex, maxWinding, sumWinding);
1439d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    }
1440d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com
1441d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
1442d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        setUpWinding(index, endIndex, maxWinding, sumWinding);
1443d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        bool from = maxWinding != 0;
1444d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        bool to = sumWinding  != 0;
1445d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        bool result = gUnaryActiveEdge[from][to];
1446d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        SkASSERT(result != -1);
1447d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com        return result;
1448d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com    }
1449d0deb4fa612a44adb941025af52c5179c5d11cd7caryclark@google.com
14508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
1451b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        SkASSERT(start != end);
14523350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        Angle* angle = angles.append();
14536aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com#if DEBUG_ANGLE
145431143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        if (angles.count() > 1 && !fTs[start].fTiny) {
14556aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            SkPoint angle0Pt, newPt;
14566aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
14576aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com                    (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
14586aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
14596d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com            SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX));
14606d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com            SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY));
14616aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        }
14623350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com#endif
14636aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com        angle->set(fPts, fVerb, this, start, end, fTs);
1464fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1465a833b5c40d0516237e0889fce8af44880423fc20caryclark@google.com
14662ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    void addCancelOutsides(double tStart, double oStart, Segment& other,
1467cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            double oEnd) {
1468cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int tIndex = -1;
1469cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int tCount = fTs.count();
1470cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int oIndex = -1;
1471cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int oCount = other.fTs.count();
1472cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1473cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            ++tIndex;
14743350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
1475cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int tIndexStart = tIndex;
1476cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1477cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            ++oIndex;
14783350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
1479cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int oIndexStart = oIndex;
1480cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        double nextT;
1481cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1482cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            nextT = fTs[++tIndex].fT;
14833350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (nextT < 1 && approximately_negative(nextT - tStart));
1484cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        double oNextT;
1485cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1486cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            oNextT = other.fTs[++oIndex].fT;
14873350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (oNextT < 1 && approximately_negative(oNextT - oStart));
1488cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // at this point, spans before and after are at:
1489cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
1490cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // if tIndexStart == 0, no prior span
1491cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // if nextT == 1, no following span
1492d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1493cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // advance the span with zero winding
1494cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // if the following span exists (not past the end, non-zero winding)
1495cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // connect the two edges
1496cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        if (!fTs[tIndexStart].fWindValue) {
1497cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
1498cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #if DEBUG_CONCIDENT
1499cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1500cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        __FUNCTION__, fID, other.fID, tIndexStart - 1,
150127c449af06cd1d05db441593d08b84f3530fba52caryclark@google.com                        fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
150227c449af06cd1d05db441593d08b84f3530fba52caryclark@google.com                        xyAtT(tIndexStart).fY);
1503cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #endif
150445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false,
150545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                        fTs[tIndexStart].fPt);
1506cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            }
1507cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            if (nextT < 1 && fTs[tIndex].fWindValue) {
1508cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #if DEBUG_CONCIDENT
1509cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1510cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        __FUNCTION__, fID, other.fID, tIndex,
1511cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        fTs[tIndex].fT, xyAtT(tIndex).fX,
1512cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        xyAtT(tIndex).fY);
1513cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #endif
151445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com                addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
1515cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            }
1516cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        } else {
1517cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            SkASSERT(!other.fTs[oIndexStart].fWindValue);
1518cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
1519cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #if DEBUG_CONCIDENT
1520cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1521cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        __FUNCTION__, fID, other.fID, oIndexStart - 1,
152227c449af06cd1d05db441593d08b84f3530fba52caryclark@google.com                        other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
152327c449af06cd1d05db441593d08b84f3530fba52caryclark@google.com                        other.xyAtT(oIndexStart).fY);
152427c449af06cd1d05db441593d08b84f3530fba52caryclark@google.com                other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
1525cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #endif
1526cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            }
1527cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
1528cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #if DEBUG_CONCIDENT
1529cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
1530cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        __FUNCTION__, fID, other.fID, oIndex,
1531cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
1532cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        other.xyAtT(oIndex).fY);
1533cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
1534cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    #endif
1535cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            }
1536cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        }
1537cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    }
1538d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1539cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
1540cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            double oEnd) {
1541cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // walk this to outsideTs[0]
1542cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // walk other to outsideTs[1]
1543cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        // if either is > 0, add a pointer to the other, copying adjacent winding
1544cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int tIndex = -1;
1545cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        int oIndex = -1;
1546cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        double tStart = outsideTs[0];
1547cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        double oStart = outsideTs[1];
1548cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1549cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            ++tIndex;
15503350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(tStart - fTs[tIndex].fT));
155145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        SkPoint ptStart = fTs[tIndex].fPt;
1552cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1553cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            ++oIndex;
15543350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
15554eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
155645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            addTPair(tStart, other, oStart, false, ptStart);
1557cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        }
1558cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        tStart = fTs[tIndex].fT;
1559cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        oStart = other.fTs[oIndex].fT;
1560cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        do {
1561cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            double nextT;
1562cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            do {
1563cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                nextT = fTs[++tIndex].fT;
15643350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com            } while (approximately_negative(nextT - tStart));
1565cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            tStart = nextT;
156645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            ptStart = fTs[tIndex].fPt;
1567cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            do {
1568cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                nextT = other.fTs[++oIndex].fT;
15693350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com            } while (approximately_negative(nextT - oStart));
1570cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            oStart = nextT;
15714eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
1572cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                break;
1573cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            }
157445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com            addTPair(tStart, other, oStart, false, ptStart);
15753350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
1576cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    }
1577d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
15784eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
15794eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        init(pts, SkPath::kCubic_Verb, operand, evenOdd);
1580fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fBounds.setCubicBounds(pts);
1581fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1582549c93ef979aeb4dcb65b3d0fca4b58e8ab62227skia.committer@gmail.com
1583f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const {
15841577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com        SkPoint edge[4];
1585f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        const SkPoint* ePtr;
1586f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        int lastT = fTs.count() - 1;
1587f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
1588f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            ePtr = fPts;
1589f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        } else {
15908dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
1591c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            subDivide(start, end, edge);
1592f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            ePtr = edge;
1593f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
15948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (active) {
1595f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            bool reverse = ePtr == fPts && start != 0;
1596f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            if (reverse) {
1597f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                path.deferredMoveLine(ePtr[fVerb]);
1598f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                switch (fVerb) {
1599f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kLine_Verb:
1600f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.deferredLine(ePtr[0]);
1601f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1602f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kQuad_Verb:
1603f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.quadTo(ePtr[1], ePtr[0]);
1604f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1605f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kCubic_Verb:
1606f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);
1607f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1608f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    default:
1609f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        SkASSERT(0);
1610f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                }
1611f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com       //         return ePtr[0];
1612f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com           } else {
1613f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                path.deferredMoveLine(ePtr[0]);
1614f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                switch (fVerb) {
1615f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kLine_Verb:
1616f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.deferredLine(ePtr[1]);
1617f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1618f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kQuad_Verb:
1619f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.quadTo(ePtr[1], ePtr[2]);
1620f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1621f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    case SkPath::kCubic_Verb:
1622f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);
1623f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        break;
1624f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                    default:
1625f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                        SkASSERT(0);
1626f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com                }
16278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            }
16281577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com        }
1629f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com      //  return ePtr[fVerb];
16301577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com    }
16311577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com
16324eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
16334eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        init(pts, SkPath::kLine_Verb, operand, evenOdd);
1634fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fBounds.set(pts, 2);
1635fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1636a833b5c40d0516237e0889fce8af44880423fc20caryclark@google.com
1637f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#if 0
1638f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {
16398dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        const SkPoint& pt = xyAtT(tIndex);
16408dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (active) {
1641f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            path.deferredMove(pt);
16428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
164388f7d0cb09707355bc9079d4b0569537e8048fa9caryclark@google.com        return pt;
16441577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com    }
1645f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com#endif
16461577e8f9c5bc8436cc71d3438c6d0b9f02c38338caryclark@google.com
1647fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    // add 2 to edge or out of range values to get T extremes
1648b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    void addOtherT(int index, double otherT, int otherIndex) {
1649b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        Span& span = fTs[index];
1650f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #if PIN_ADD_T
1651185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        if (precisely_less_than_zero(otherT)) {
1652185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            otherT = 0;
1653185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        } else if (precisely_greater_than_one(otherT)) {
1654185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com            otherT = 1;
1655185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        }
1656f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #endif
1657b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        span.fOtherT = otherT;
1658b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        span.fOtherIndex = otherIndex;
1659fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1660a833b5c40d0516237e0889fce8af44880423fc20caryclark@google.com
16614eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
16624eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        init(pts, SkPath::kQuad_Verb, operand, evenOdd);
1663fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fBounds.setQuadBounds(pts);
1664fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1665d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
16668dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // Defer all coincident edge processing until
16678dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // after normal intersections have been computed
16688dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
16698dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com// no need to be tricky; insert in normal T order
16708dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com// resolve overlapping ts when considering coincidence later
1671a833b5c40d0516237e0889fce8af44880423fc20caryclark@google.com
16728dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // add non-coincident intersection. Resulting edges are sorted in T.
16737ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    int addT(Segment* other, const SkPoint& pt, double& newT) {
167415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        // FIXME: in the pathological case where there is a ton of intercepts,
167515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        //  binary search?
167615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        int insertedAt = -1;
167715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        size_t tCount = fTs.count();
1678f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #if PIN_ADD_T
1679c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com        // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
1680185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        if (precisely_less_than_zero(newT)) {
1681c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com            newT = 0;
1682185c7c47983dde02b5542cf45fe3fc58a3ecb055caryclark@google.com        } else if (precisely_greater_than_one(newT)) {
1683c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com            newT = 1;
1684c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com        }
1685f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com    #endif
16868dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        for (size_t index = 0; index < tCount; ++index) {
168715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // OPTIMIZATION: if there are three or more identical Ts, then
168815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // the fourth and following could be further insertion-sorted so
168915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // that all the edges are clockwise or counterclockwise.
169015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // This could later limit segment tests to the two adjacent
169115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // neighbors, although it doesn't help with determining which
169215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            // circular direction to go in.
16938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            if (newT < fTs[index].fT) {
16948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                insertedAt = index;
16958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                break;
169615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com            }
169715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        }
16988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        Span* span;
16998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (insertedAt >= 0) {
17008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            span = fTs.insert(insertedAt);
17018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        } else {
17028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            insertedAt = tCount;
17038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            span = fTs.append();
17048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
170515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        span->fT = newT;
17068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        span->fOther = other;
170745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com        span->fPt = pt;
17088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        span->fWindSum = SK_MinS32;
170931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        span->fOppSum = SK_MinS32;
17108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        span->fWindValue = 1;
171157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        span->fOppValue = 0;
1712f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        span->fTiny = false;
17134aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com        span->fLoop = false;
17148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if ((span->fDone = newT == 1)) {
171565f9f0a1664a9cb38157ccfbcc3e0e936af0a58ecaryclark@google.com            ++fDoneSpans;
1716d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        }
1717c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        span->fUnsortableStart = false;
1718c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        span->fUnsortableEnd = false;
17198f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        int less = -1;
17207ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com        while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) {
17217ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#if 1
17227ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (span[less].fDone) {
17237ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                break;
17247ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
1725c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            double tInterval = newT - span[less].fT;
1726c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            if (precisely_negative(tInterval)) {
1727c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                break;
1728c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            }
1729c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            if (fVerb == SkPath::kCubic_Verb) {
1730c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                double tMid = newT - tInterval / 2;
1731c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                _Point midPt;
1732c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                CubicXYAtT(fPts, tMid, &midPt);
1733c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                if (!midPt.approximatelyEqual(xyAtT(span))) {
1734c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                    break;
1735c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                }
1736c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            }
17378f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            span[less].fTiny = true;
17388f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            span[less].fDone = true;
17398f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            if (approximately_negative(newT - span[less].fT)) {
17400b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                if (approximately_greater_than_one(newT)) {
17418f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[less].fUnsortableStart = true;
17428f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[less - 1].fUnsortableEnd = true;
17430b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                }
17448f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                if (approximately_less_than_zero(span[less].fT)) {
17458f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[less + 1].fUnsortableStart = true;
17468f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[less].fUnsortableEnd = true;
17470b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                }
17480b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com            }
1749f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            ++fDoneSpans;
17507ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#else
17517ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            double tInterval = newT - span[less].fT;
17527ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (precisely_negative(tInterval)) {
17537ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                break;
17547ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
17557ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (fVerb == SkPath::kCubic_Verb) {
17567ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                double tMid = newT - tInterval / 2;
17577ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                _Point midPt;
17587ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                CubicXYAtT(fPts, tMid, &midPt);
17597ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                if (!midPt.approximatelyEqual(xyAtT(span))) {
17607ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                    break;
17617ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                }
17627ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
17637ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            SkASSERT(span[less].fDone == span->fDone);
17647ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (span[less].fT == 0) {
17657ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                span->fT = newT = 0;
17667ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            } else {
17677ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                setSpanT(less, newT);
17687ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
17697ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#endif
17708f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            --less;
17718f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        }
17728f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com        int more = 1;
17737ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com        while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) {
17747ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#if 1
17757ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (span[more - 1].fDone) {
17767ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                break;
17777ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
1778c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            double tEndInterval = span[more].fT - newT;
1779c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            if (precisely_negative(tEndInterval)) {
1780c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                break;
1781c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            }
1782c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            if (fVerb == SkPath::kCubic_Verb) {
1783c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                double tMid = newT - tEndInterval / 2;
1784c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                _Point midEndPt;
1785c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                CubicXYAtT(fPts, tMid, &midEndPt);
1786c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                if (!midEndPt.approximatelyEqual(xyAtT(span))) {
1787c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                    break;
1788c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com                }
1789c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com            }
17908f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            span[more - 1].fTiny = true;
17918f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            span[more - 1].fDone = true;
17928f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            if (approximately_negative(span[more].fT - newT)) {
17938f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                if (approximately_greater_than_one(span[more].fT)) {
17948f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[more + 1].fUnsortableStart = true;
17958f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[more].fUnsortableEnd = true;
17960b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                }
17970b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                if (approximately_less_than_zero(newT)) {
17988f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[more].fUnsortableStart = true;
17998f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com                    span[more - 1].fUnsortableEnd = true;
18000b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com                }
18010b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com            }
1802f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com            ++fDoneSpans;
18037ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#else
18047ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            double tEndInterval = span[more].fT - newT;
18057ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (precisely_negative(tEndInterval)) {
18067ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                break;
18077ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
18087ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (fVerb == SkPath::kCubic_Verb) {
18097ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                double tMid = newT - tEndInterval / 2;
18107ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                _Point midEndPt;
18117ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                CubicXYAtT(fPts, tMid, &midEndPt);
18127ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                if (!midEndPt.approximatelyEqual(xyAtT(span))) {
18137ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                    break;
18147ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                }
18157ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
18167ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            SkASSERT(span[more - 1].fDone == span[more].fDone);
18177ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            if (newT == 0) {
18187ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                setSpanT(more, 0);
18197ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            } else {
18207ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com                span->fT = newT = span[more].fT;
18217ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com            }
18227ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com#endif
18238f9f468b0555e95b8fc3cf4e6ee1f1fbf5492a1bcaryclark@google.com            ++more;
1824f839c0359c308fd06895d9f73fc12c4f3869e399caryclark@google.com        }
182515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com        return insertedAt;
182615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com    }
182715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com
18288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // set spans from start to end to decrement by one
18298dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // note this walks other backwards
18308dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // FIMXE: there's probably an edge case that can be constructed where
18318dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // two span in one segment are separated by float epsilon on one span but
18328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // not the other, if one segment is very small. For this
18338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // case the counts asserted below may or may not be enough to separate the
18342ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    // spans. Even if the counts work out, what if the spans aren't correctly
18358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // sorted? It feels better in such a case to match the span's other span
18368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // pointer since both coincident segments must contain the same spans.
18378dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    void addTCancel(double startT, double endT, Segment& other,
18388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            double oStartT, double oEndT) {
18393350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(!approximately_negative(endT - startT));
18403350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(!approximately_negative(oEndT - oStartT));
1841235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com        bool binary = fOperand != other.fOperand;
18428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        int index = 0;
18433350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        while (!approximately_negative(startT - fTs[index].fT)) {
18448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            ++index;
18458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
1846b973801328ef25105f7f3255ab912a1b675da056caryclark@google.com        int oIndex = other.fTs.count();
18473350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
18488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            ;
184959823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com        double tRatio = (oEndT - oStartT) / (endT - startT);
18508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        Span* test = &fTs[index];
18518dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        Span* oTest = &other.fTs[oIndex];
185218063441c23b334ab2ee7075c39ceeb8378e6fcfcaryclark@google.com        SkTDArray<double> outsideTs;
185318063441c23b334ab2ee7075c39ceeb8378e6fcfcaryclark@google.com        SkTDArray<double> oOutsideTs;
18548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        do {
185531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com            bool decrement = test->fWindValue && oTest->fWindValue && !binary;
1856cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            bool track = test->fWindValue || oTest->fWindValue;
1857200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            double testT = test->fT;
1858200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            double oTestT = oTest->fT;
1859200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            Span* span = test;
18608dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            do {
18618dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                if (decrement) {
186231143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                    decrementSpan(span);
1863200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                } else if (track && span->fT < 1 && oTestT < 1) {
1864200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                    TrackOutside(outsideTs, span->fT, oTestT);
18658dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                }
1866200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                span = &fTs[++index];
18673350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com            } while (approximately_negative(span->fT - testT));
1868200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            Span* oSpan = oTest;
186959823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com            double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
187059823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com            double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
187159823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com            SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
18723350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com            while (approximately_negative(otherTMatchStart - oSpan->fT)
18733350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com                    && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
187403f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com        #ifdef SK_DEBUG
187559823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com                SkASSERT(originalWindValue == oSpan->fWindValue);
187603f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com        #endif
18778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                if (decrement) {
1878200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                    other.decrementSpan(oSpan);
1879200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                } else if (track && oSpan->fT < 1 && testT < 1) {
1880200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                    TrackOutside(oOutsideTs, oSpan->fT, testT);
18818dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                }
18828dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                if (!oIndex) {
18838dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                    break;
18848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com                }
1885200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com                oSpan = &other.fTs[--oIndex];
1886d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com            }
1887200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            test = span;
1888200c211d34b11a4a988fc2549df3c17ae6875899caryclark@google.com            oTest = oSpan;
18893350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(endT - test->fT));
18903350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
189118063441c23b334ab2ee7075c39ceeb8378e6fcfcaryclark@google.com        // FIXME: determine if canceled edges need outside ts added
1892cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        if (!done() && outsideTs.count()) {
18932ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            double tStart = outsideTs[0];
18942ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            double oStart = outsideTs[1];
18952ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            addCancelOutsides(tStart, oStart, other, oEndT);
18962ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            int count = outsideTs.count();
18972ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            if (count > 2) {
18982ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com                double tStart = outsideTs[count - 2];
18992ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com                double oStart = outsideTs[count - 1];
19002ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com                addCancelOutsides(tStart, oStart, other, oEndT);
19012ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            }
190218063441c23b334ab2ee7075c39ceeb8378e6fcfcaryclark@google.com        }
1903cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        if (!other.done() && oOutsideTs.count()) {
19042ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            double tStart = oOutsideTs[0];
19052ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            double oStart = oOutsideTs[1];
19062ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            other.addCancelOutsides(tStart, oStart, *this, endT);
190718063441c23b334ab2ee7075c39ceeb8378e6fcfcaryclark@google.com        }
19088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
1909631cdcb4a6b926b6447f328b81911a4499fb3698skia.committer@gmail.com
19104aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com    int addSelfT(Segment* other, const SkPoint& pt, double& newT) {
19114aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com        int result = addT(other, pt, newT);
19124aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com        Span* span = &fTs[result];
19134aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com        span->fLoop = true;
19144aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com        return result;
19154aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com    }
191615dd300ac6d7695b4d2aca81d8f3648eae704451skia.committer@gmail.com
19177ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com    int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) {
19187ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com        int result = addT(other, pt, newT);
191973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com        Span* span = &fTs[result];
192073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com        if (start) {
192173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            if (result > 0) {
192273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com                span[result - 1].fUnsortableEnd = true;
192373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            }
192473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            span[result].fUnsortableStart = true;
192573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com        } else {
192673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            span[result].fUnsortableEnd = true;
192773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            if (result + 1 < fTs.count()) {
192873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com                span[result + 1].fUnsortableStart = true;
192973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com            }
193073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com        }
193173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com        return result;
193273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    }
1933b3b6a60d35c8ee521252367200148561c628ee42skia.committer@gmail.com
19344eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    int bumpCoincidentThis(const Span* oTest, bool opp, int index,
19354eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            SkTDArray<double>& outsideTs) {
19364eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        int oWindValue = oTest->fWindValue;
19374eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        int oOppValue = oTest->fOppValue;
19384eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        if (opp) {
19394eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            SkTSwap<int>(oWindValue, oOppValue);
19404eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        }
194157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        Span* const test = &fTs[index];
194257cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        Span* end = test;
194357cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        const double oStartT = oTest->fT;
194457cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        do {
19454eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            if (bumpSpan(end, oWindValue, oOppValue)) {
19464eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                TrackOutside(outsideTs, end->fT, oStartT);
194757cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com            }
194857cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com            end = &fTs[++index];
194957cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        } while (approximately_negative(end->fT - test->fT));
195057cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        return index;
195157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    }
195257cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com
195357cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // because of the order in which coincidences are resolved, this and other
195457cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // may not have the same intermediate points. Compute the corresponding
195557cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // intermediate T values (using this as the master, other as the follower)
195657cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // and walk other conditionally -- hoping that it catches up in the end
19574eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,
19584eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            SkTDArray<double>& oOutsideTs) {
195957cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        Span* const oTest = &fTs[oIndex];
196057cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        Span* oEnd = oTest;
196157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        const double startT = test->fT;
196257cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        const double oStartT = oTest->fT;
196357cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        while (!approximately_negative(oEndT - oEnd->fT)
19644eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com                && approximately_negative(oEnd->fT - oStartT)) {
19654eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            zeroSpan(oEnd);
19664eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            TrackOutside(oOutsideTs, oEnd->fT, startT);
196757cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com            oEnd = &fTs[++oIndex];
196857cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        }
196957cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        return oIndex;
197057cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    }
197157cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com
197257cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // FIXME: need to test this case:
197357cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // contourA has two segments that are coincident
197457cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // contourB has two segments that are coincident in the same place
197557cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // each ends up with +2/0 pairs for winding count
197657cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // since logic below doesn't transfer count (only increments/decrements) can this be
197757cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com    // resolved to +4/0 ?
19788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
19798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // set spans from start to end to increment the greater by one and decrement
19808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    // the lesser
19814eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com    void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
19823350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(!approximately_negative(endT - startT));
19833350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(!approximately_negative(oEndT - oStartT));
198457cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com        bool opp = fOperand ^ other.fOperand;
19858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        int index = 0;
19863350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        while (!approximately_negative(startT - fTs[index].fT)) {
19878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            ++index;
19888dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
19898dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        int oIndex = 0;
19903350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
19918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            ++oIndex;
19928dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
19938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        Span* test = &fTs[index];
19948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        Span* oTest = &other.fTs[oIndex];
19958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkTDArray<double> outsideTs;
19968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        SkTDArray<double> oOutsideTs;
19978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        do {
19984eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            // if either span has an opposite value and the operands don't match, resolve first
1999e7bd5f4041701cbab87f6e779eb18fbb9fe74216caryclark@google.com     //       SkASSERT(!test->fDone || !oTest->fDone);
20000d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com            if (test->fDone || oTest->fDone) {
20010d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com                index = advanceCoincidentThis(oTest, opp, index);
20020d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com                oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
20030d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com            } else {
20040d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com                index = bumpCoincidentThis(oTest, opp, index, outsideTs);
20050d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com                oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
20060d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com            }
200757cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com            test = &fTs[index];
200857cff8dbdfb32b3fea426519a4fdc05f13be69d9caryclark@google.com            oTest = &other.fTs[oIndex];
20093350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        } while (!approximately_negative(endT - test->fT));
20103350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(approximately_negative(oTest->fT - oEndT));
20113350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com        SkASSERT(approximately_negative(oEndT - oTest->fT));
20124eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        if (!done() && outsideTs.count()) {
20134eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com            addCoinOutsides(outsideTs, other, oEndT);
20148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
20158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        if (!other.done() && oOutsideTs.count()) {
2016cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            other.addCoinOutsides(oOutsideTs, *this, endT);
20178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
20188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
2019d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
2020cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com    // FIXME: this doesn't prevent the same span from being added twice
2021aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com    // fix in caller, SkASSERT here?
202245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    void addTPair(double t, Segment& other, double otherT, bool borrowWind, const SkPoint& pt) {
202347580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com        int tCount = fTs.count();
2024cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        for (int tIndex = 0; tIndex < tCount; ++tIndex) {
2025cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com            const Span& span = fTs[tIndex];
20263350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.com            if (!approximately_negative(span.fT - t)) {
202747580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com                break;
20288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            }
20296aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com            if (approximately_negative(span.fT - t) && span.fOther == &other
20306aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com                    && approximately_equal(span.fOtherT, otherT)) {
2031cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com#if DEBUG_ADD_T_PAIR
2032cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
2033cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                        __FUNCTION__, fID, t, other.fID, otherT);
2034cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com#endif
2035cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com                return;
203647580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com            }
2037cc90505674cd845fcbebd7e0654c3ff04a2e4f25caryclark@google.com        }
203847580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#if DEBUG_ADD_T_PAIR
203947580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com        SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
204047580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com                __FUNCTION__, fID, t, other.fID, otherT);
204147580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com#endif
20427ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com        int insertedAt = addT(&other, pt, t);
20437ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com        int otherInsertedAt = other.addT(this, pt, otherT);
20448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        addOtherT(insertedAt, otherT, otherInsertedAt);
2045b973801328ef25105f7f3255ab912a1b675da056caryclark@google.com        other.addOtherT(otherInsertedAt, t, insertedAt);
20462ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        matchWindingValue(insertedAt, t, borrowWind);
20472ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
20488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
2049d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
20508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
2051b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        // add edge leading into junction
20524eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        int min = SkMin32(end, start);
20534eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
20548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com            addAngle(angles, end, start);
20558dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com        }
2056b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        // add edge leading away from junction
2057495f8e435b677f28913cd2adc8caa8d3d766dd17caryclark@google.com        int step = SkSign32(end - start);
2058a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        int tIndex = nextExactSpan(end, step);
20594eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        min = SkMin32(end, tIndex);
20604eeda37a7456876cb8d509a4ea43c7f4c684477acaryclark@google.com        if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
2061a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com            addAngle(angles, end, tIndex);
2062b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        }
2063b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    }
2064d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
20650d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com    int advanceCoincidentThis(const Span* oTest, bool opp, int index) {
20660d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        Span* const test = &fTs[index];
20670d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        Span* end = test;
20680d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        do {
20690d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com            end = &fTs[++index];
20700d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        } while (approximately_negative(end->fT - test->fT));
20710d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        return index;
20720d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com    }
20730d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com
20740d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com    int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {
20750d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        Span* const oTest = &fTs[oIndex];
20760d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        Span* oEnd = oTest;
20770d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        const double oStartT = oTest->fT;
20780d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        while (!approximately_negative(oEndT - oEnd->fT)
20790d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com                && approximately_negative(oEnd->fT - oStartT)) {
20800d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com            oEnd = &fTs[++oIndex];
20810d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        }
20820d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com        return oIndex;
20830d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com    }
2084b89a03c890668f98d9f8b269b6ad00824409435bskia.committer@gmail.com
2085db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    bool betweenTs(int lesser, double testT, int greater) {
2086db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        if (lesser > greater) {
2087db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com            SkTSwap<int>(lesser, greater);
2088db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        }
2089db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com        return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
2090db0b3e099f888213535c4ad4c785b84544309033caryclark@google.com    }
20910d3d09e5d2fd17aaed035ae23d59804b56b994ffcaryclark@google.com
2092fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    const Bounds& bounds() const {
2093fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        return fBounds;
2094fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
2095a833b5c40d0516237e0889fce8af44880423fc20caryclark@google.com
209631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com    void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {
2097a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        double referenceT = fTs[index].fT;
2098a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        int lesser = index;
209931143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
210031143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                && precisely_negative(referenceT - fTs[lesser].fT)) {
2101a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com            buildAnglesInner(lesser, angles);
2102a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        }
2103b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        do {
2104a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com            buildAnglesInner(index, angles);
210531143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
210631143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com                && precisely_negative(fTs[index].fT - referenceT));
2107b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com    }
2108a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com
2109a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com    void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
21101ab0aac67247bf3ec1f23b220456d316d9a80b45caryclark@google.com        const Span* span = &fTs[index];
2111a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        Segment* other = span->fOther;
2112a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com    // if there is only one live crossing, and no coincidence, continue
2113a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com    // in the same direction
2114a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com    // if there is coincidence, the only choice may be to reverse direction
2115a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        // find edge on either side of intersection
2116a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        int oIndex = span->fOtherIndex;
2117a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        // if done == -1, prior span has already been processed
2118a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        int step = 1;
2119a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com        int next = other->nextExactSpan(oIndex, step);
2120a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com       if (next < 0) {
2121a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com            step = -step;
2122a461ff0866526bc51dbd4c4f9f066a727ec21510caryclark@google.com            next = other->nextExactSpan(oIndex, step);
2123a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        }
2124a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        // add candidate into and away from junction
2125a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        other->addTwoAngles(next, oIndex, angles);
21268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com    }
21278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com
21287fce0de0b9674ca6cc65ebbb40b924b615d9fc9ecaryclark@google.com    int computeSum(int startIndex, int endIndex, bool binary) {
2129534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        SkTDArray<Angle> angles;
2130534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        addTwoAngles(startIndex, endIndex, angles);
213131143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        buildAngles(endIndex, angles, false);
2132d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        // OPTIMIZATION: check all angles to see if any have computed wind sum
2133d1688744d537d928699b6069f99c4470a0f6e772caryclark@google.com        // before sorting (early exit if none)
2134534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        SkTDArray<Angle*> sorted;
2135c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        bool sortable = SortAngles(angles, sorted);
213603f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com#if DEBUG_SORT
213731143cf37fa38dc98f71c71e518ecc21c83b5e27caryclark@google.com        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
213803f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com#endif
2139c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        if (!sortable) {
2140c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com            return SK_MinS32;
2141c91dfe417a51f73c28ecf2708df1e0bee942c6eacaryclark@google.com        }
2142534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        int angleCount = angles.count();
2143534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        const Angle* angle;
2144534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        const Segment* base;
2145534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        int winding;
21467ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com        int oWinding;
2147534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        int firstIndex = 0;
2148534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        do {
2149534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            angle = sorted[firstIndex];
2150534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            base = angle->segment();
2151534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            winding = base->windSum(angle);
2152534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            if (winding != SK_MinS32) {
21537ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com                oWinding = base->oppSum(angle);
2154534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com                break;
2155534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            }
2156534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            if (++firstIndex == angleCount) {
2157534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com                return SK_MinS32;
2158534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            }
2159534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        } while (true);
2160534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        // turn winding into contourWinding
21612ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        int spanWinding = base->spanSign(angle);
21622ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        bool inner = useInnerWinding(winding + spanWinding, winding);
21632ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    #if DEBUG_WINDING
216424bec79d6f3d71ff97b50db72461a3892bd4f6b5caryclark@google.com        SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
216559823f7f3ba43c7c6bc1fa8c600b093ecb4236aacaryclark@google.com            spanWinding, winding, angle->sign(), inner,
21662ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com            inner ? winding + spanWinding : winding);
21672ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com    #endif
21682ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        if (inner) {
2169534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            winding += spanWinding;
2170534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        }
2171534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com    #if DEBUG_SORT
21727ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com        base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
2173534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com    #endif
2174534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        int nextIndex = firstIndex + 1;
2175534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
21762ddff9388694263c7be9347de7eb768cd0847997caryclark@google.com        winding -= base->spanSign(angle);
21777ba591eb7a7ff71127172bbf140491e18298a97acaryclark@google.com        oWinding -= base->oppSign(angle);
2178534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com        do {
2179534aa5b9460639a09b9dc30d29e77782e44b8fffcaryclark@google.com            if