1c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/*
2c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * Copyright 2012 Google Inc.
3c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *
4c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be
5c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * found in the LICENSE file.
6c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */
7c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
88dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#include "Simplify.h"
9c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#undef SkASSERT
1178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
1378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com// FIXME: remove once debugging is complete
14fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#if 01 // set to 1 for no debugging whatsoever
1578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
1647580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com//const bool gRunTestsInOneThread = false;
1778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
1878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 0
192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 0
202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0
2178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0
2278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 0
23fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_ASSEMBLE 0
2478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_BOTTOM 0
25fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_BRIDGE 0
2678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_DUMP 0
272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 0
282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 0
292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0
30198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#define DEBUG_SPLIT 0
31fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_STITCH_EDGE 0
3278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_TRIM_LINE 0
3378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#else
352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
3647580694fbe974a065caf7c39c3d2075708c2018caryclark@google.com//const bool gRunTestsInOneThread = true;
3778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
3878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 0
392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 01
402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0
4178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0
4278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 1
43fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_ASSEMBLE 1
4478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_BOTTOM 0
45fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_BRIDGE 1
4678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_DUMP 1
472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 01
482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 01
492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0
50198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#define DEBUG_SPLIT 1
51fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#define DEBUG_STITCH_EDGE 1
5278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#define DEBUG_TRIM_LINE 1
53752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
56fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE || DEBUG_BRIDGE
57fb173424e915e696a73067d616ce4f39a407261acaryclark@google.comstatic const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
58fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
59fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_STITCH_EDGE
60fb173424e915e696a73067d616ce4f39a407261acaryclark@google.comstatic const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
61fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
62fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com
636680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2],
64a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        Intersections& intersections) {
65a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
66a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
6745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    return intersect(aLine, bLine, intersections);
68a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
69a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
70a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
71a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        Intersections& intersections) {
72a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
73a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
74198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    intersect(aQuad, bLine, intersections);
75198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return intersections.fUsed;
76a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
77a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
78a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
79a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        Intersections& intersections) {
80a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
81a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            {a[3].fX, a[3].fY}};
82a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
8373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com    return intersect(aCubic, bLine, intersections);
84a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
85a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
86a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
87a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        Intersections& intersections) {
88a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
89a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
9045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com    intersect2(aQuad, bQuad, intersections);
91198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return intersections.fUsed;
92a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
93a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
94a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
95a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        Intersections& intersections) {
96a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
97a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            {a[3].fX, a[3].fY}};
98a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
99a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            {b[3].fX, b[3].fY}};
100198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    intersect(aCubic, bCubic, intersections);
101198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return intersections.fUsed;
102c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
103c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
1052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkScalar y, double aRange[2]) {
106a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
1072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    return horizontalLineIntersect(aLine, left, right, y, aRange);
108c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
109c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
110198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comstatic int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
111198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkScalar y, double aRange[3]) {
112198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
113198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return horizontalIntersect(aQuad, left, right, y, aRange);
114198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com}
115198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
116198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comstatic int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
117198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkScalar y, double aRange[4]) {
118198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
119198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            {a[3].fX, a[3].fY}};
120198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return horizontalIntersect(aCubic, left, right, y, aRange);
121198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com}
122198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
123cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
124a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
125cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    double x, y;
126a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    xy_at_t(line, t, x, y);
127cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    out->fX = SkDoubleToScalar(x);
128cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    out->fY = SkDoubleToScalar(y);
129cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com}
130cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com
131a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
132a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
133a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    double x, y;
134a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    xy_at_t(quad, t, x, y);
135a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    out->fX = SkDoubleToScalar(x);
136a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    out->fY = SkDoubleToScalar(y);
1372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}
1382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
139a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
140a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
141a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            {a[3].fX, a[3].fY}};
142a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    double x, y;
143a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    xy_at_t(cubic, t, x, y);
144a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    out->fX = SkDoubleToScalar(x);
145a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    out->fY = SkDoubleToScalar(y);
1462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}
1472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
1486680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic SkScalar LineYAtT(const SkPoint a[2], double t) {
149a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
1506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    double y;
1516680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    xy_at_t(aLine, t, *(double*) 0, y);
1526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    return SkDoubleToScalar(y);
1536680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}
1546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
155a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic SkScalar QuadYAtT(const SkPoint a[3], double t) {
156a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
157a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    double y;
158a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    xy_at_t(quad, t, *(double*) 0, y);
159a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    return SkDoubleToScalar(y);
160a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
161a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
162a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic SkScalar CubicYAtT(const SkPoint a[4], double t) {
163a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
164a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            {a[3].fX, a[3].fY}};
165a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    double y;
166a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    xy_at_t(cubic, t, *(double*) 0, y);
167a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    return SkDoubleToScalar(y);
168a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
169a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
1706680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT,
1716680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        SkPoint sub[2]) {
172a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
1736680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    _Line dst;
1746680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    sub_divide(aLine, startT, endT, dst);
1756680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
1766680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
1776680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
1786680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
1796680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}
1806680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
181a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic void QuadSubDivide(const SkPoint a[3], double startT, double endT,
182a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        SkPoint sub[3]) {
18378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
18478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            {a[2].fX, a[2].fY}};
185a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    Quadratic dst;
186a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub_divide(aQuad, startT, endT, dst);
187a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
188a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
189a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
190a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
191a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[2].fX = SkDoubleToScalar(dst[2].x);
192a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[2].fY = SkDoubleToScalar(dst[2].y);
1932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}
1946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
195a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic void CubicSubDivide(const SkPoint a[4], double startT, double endT,
196a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        SkPoint sub[4]) {
19778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
19878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
199a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    Cubic dst;
200a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub_divide(aCubic, startT, endT, dst);
201a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[0].fX = SkDoubleToScalar(dst[0].x);
202a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[0].fY = SkDoubleToScalar(dst[0].y);
203a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[1].fX = SkDoubleToScalar(dst[1].x);
204a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[1].fY = SkDoubleToScalar(dst[1].y);
205a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[2].fX = SkDoubleToScalar(dst[2].x);
206a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[2].fY = SkDoubleToScalar(dst[2].y);
207a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[3].fX = SkDoubleToScalar(dst[3].x);
208a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    sub[3].fY = SkDoubleToScalar(dst[3].y);
209a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
210fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com
211fb173424e915e696a73067d616ce4f39a407261acaryclark@google.comstatic void QuadSubBounds(const SkPoint a[3], double startT, double endT,
212fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkRect& bounds) {
213fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    SkPoint dst[3];
214fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    QuadSubDivide(a, startT, endT, dst);
215fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    bounds.fLeft = bounds.fRight = dst[0].fX;
216fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    bounds.fTop = bounds.fBottom = dst[0].fY;
217fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    for (int index = 1; index < 3; ++index) {
218fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        bounds.growToInclude(dst[index].fX, dst[index].fY);
219fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
220fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com}
221fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com
222fb173424e915e696a73067d616ce4f39a407261acaryclark@google.comstatic void CubicSubBounds(const SkPoint a[4], double startT, double endT,
223fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkRect& bounds) {
224fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    SkPoint dst[4];
225fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    CubicSubDivide(a, startT, endT, dst);
226fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    bounds.fLeft = bounds.fRight = dst[0].fX;
227fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    bounds.fTop = bounds.fBottom = dst[0].fY;
228fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    for (int index = 1; index < 4; ++index) {
229fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        bounds.growToInclude(dst[index].fX, dst[index].fY);
230fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
231fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com}
232fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com
23378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.comstatic SkPath::Verb QuadReduceOrder(SkPoint a[4]) {
23478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const Quadratic aQuad =  {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
23578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            {a[2].fX, a[2].fY}};
23678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    Quadratic dst;
23747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com    int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);
23878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    for (int index = 0; index < order; ++index) {
23978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[index].fX = SkDoubleToScalar(dst[index].x);
24078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[index].fY = SkDoubleToScalar(dst[index].y);
24178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
24278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    if (order == 1) { // FIXME: allow returning points, caller should discard
24378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[1] = a[0];
24478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return (SkPath::Verb) order;
24578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
24678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    return (SkPath::Verb) (order - 1);
24778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com}
24878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
24978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.comstatic SkPath::Verb CubicReduceOrder(SkPoint a[4]) {
25078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
25178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
25278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    Cubic dst;
25347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com    int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill);
25478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    for (int index = 0; index < order; ++index) {
25578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[index].fX = SkDoubleToScalar(dst[index].x);
25678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[index].fY = SkDoubleToScalar(dst[index].y);
25778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
25878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    if (order == 1) { // FIXME: allow returning points, caller should discard
25978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        a[1] = a[0];
26078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return (SkPath::Verb) order;
26178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
26278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    return (SkPath::Verb) (order - 1);
26378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com}
26478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
26578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.comstatic bool IsCoincident(const SkPoint a[2], const SkPoint& above,
26678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        const SkPoint& below) {
26778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
26878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
26978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    return implicit_matches_ulps(aLine, bLine, 32);
27078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com}
27178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
272c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/*
273c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comlist of edges
274c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combounds for edge
275c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comsort
276c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comactive T
277c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
278d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.comif a contour's bounds is outside of the active area, no need to create edges
279c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com*/
280c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
281d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com/* given one or more paths,
282c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com find the bounds of each contour, select the active contours
283c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for each active contour, compute a set of edges
284c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com each edge corresponds to one or more lines and curves
285c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com leave edges unbroken as long as possible
286c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com when breaking edges, compute the t at the break but leave the control points alone
287c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
288c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */
289c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
290c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) {
291c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPath::Iter iter(path, false);
292c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPoint pts[4];
293c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPath::Verb verb;
294c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkRect bounds;
295c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    bounds.setEmpty();
296c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    int count = 0;
297c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
298c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        switch (verb) {
299c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kMove_Verb:
300c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                if (!bounds.isEmpty()) {
301c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                    *boundsArray.append() = bounds;
302c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                }
303c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
304c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                count = 0;
305c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
306d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com            case SkPath::kLine_Verb:
307c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                count = 1;
308c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
309c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kQuad_Verb:
310c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                count = 2;
311c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
312c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kCubic_Verb:
313c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                count = 3;
314c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
315c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kClose_Verb:
316c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                count = 0;
317c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
318c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            default:
319c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                SkDEBUGFAIL("bad verb");
320c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                return;
321c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
322c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        for (int i = 1; i <= count; ++i) {
323c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            bounds.growToInclude(pts[i].fX, pts[i].fY);
324c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
325c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
326c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
327c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
328f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic bool extendLine(const SkPoint line[2], const SkPoint& add) {
329f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    // FIXME: allow this to extend lines that have slopes that are nearly equal
330f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    SkScalar dx1 = line[1].fX - line[0].fX;
331f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    SkScalar dy1 = line[1].fY - line[0].fY;
332f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    SkScalar dx2 = add.fX - line[0].fX;
333f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    SkScalar dy2 = add.fY - line[0].fY;
334f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    return dx1 * dy2 == dx2 * dy1;
335f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}
3366680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
3372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZATION: this should point to a list of input data rather than duplicating
3382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// the line data here. This would reduce the need to assemble the results.
339f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstruct OutEdge {
340f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    bool operator<(const OutEdge& rh) const {
341cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& first = fPts[0];
342cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& rhFirst = rh.fPts[0];
343f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        return first.fY == rhFirst.fY
344f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                ? first.fX < rhFirst.fX
345f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                : first.fY < rhFirst.fY;
346f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
347752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
348cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    SkPoint fPts[4];
3492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    int fID; // id of edge generating data
350cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    uint8_t fVerb; // FIXME: not read from everywhere
3512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool fCloseCall; // edge is trimmable if not originally coincident
352f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com};
353f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
3546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass OutEdgeBuilder {
3556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.compublic:
356f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    OutEdgeBuilder(bool fill)
357f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        : fFill(fill) {
358f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        }
359f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
360a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    void addCurve(const SkPoint line[4], SkPath::Verb verb, int id,
361a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            bool closeCall) {
362c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com        OutEdge& newEdge = fEdges.push_back();
363a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint));
364a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        newEdge.fVerb = verb;
3652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        newEdge.fID = id;
3662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        newEdge.fCloseCall = closeCall;
3672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
368752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
3692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool trimLine(SkScalar y, int id) {
3702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        size_t count = fEdges.count();
3712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        while (count-- != 0) {
3722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            OutEdge& edge = fEdges[count];
3732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (edge.fID != id) {
3742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                continue;
3752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            }
3762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (edge.fCloseCall) {
3772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                return false;
3782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            }
3792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkASSERT(edge.fPts[0].fY <= y);
3802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (edge.fPts[1].fY <= y) {
3812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                continue;
3822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            }
3832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY)
3842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    * (edge.fPts[1].fX - edge.fPts[0].fX)
3852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    / (edge.fPts[1].fY - edge.fPts[0].fY);
3862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            edge.fPts[1].fY = y;
38778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#if DEBUG_TRIM_LINE
38878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id,
38978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                    edge.fPts[1].fX, y);
39078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com#endif
3912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            return true;
3922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
3932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        return false;
394f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
395f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
396f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    void assemble(SkPath& simple) {
3976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        size_t listCount = fEdges.count();
3986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        if (listCount == 0) {
3996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            return;
4006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        }
401f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        do {
4026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            size_t listIndex = 0;
4036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int advance = 1;
4046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            while (listIndex < listCount && fTops[listIndex] == 0) {
4056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                ++listIndex;
406f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            }
4076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            if (listIndex >= listCount) {
4086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                break;
409f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            }
4104917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            int closeEdgeIndex = -listIndex - 1;
411fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            // the curve is deferred and not added right away because the
412fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            // following edge may extend the first curve.
413a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            SkPoint firstPt, lastCurve[4];
414a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            uint8_t lastVerb;
415fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
416fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            int firstIndex, lastIndex;
417fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            const int tab = 8;
418fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
4196008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            bool doMove = true;
4206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int edgeIndex;
4216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            do {
422cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                SkPoint* ptArray = fEdges[listIndex].fPts;
423cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                uint8_t verb = fEdges[listIndex].fVerb;
424fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                SkPoint* curve[4];
4256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                if (advance < 0) {
426fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    curve[0] = &ptArray[verb];
427fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    if (verb == SkPath::kCubic_Verb) {
428fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        curve[1] = &ptArray[2];
429fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        curve[2] = &ptArray[1];
430fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    }
431fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    curve[verb] = &ptArray[0];
4326008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                } else {
433fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    curve[0] = &ptArray[0];
434fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    if (verb == SkPath::kCubic_Verb) {
435fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        curve[1] = &ptArray[1];
436fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        curve[2] = &ptArray[2];
437fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    }
438fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    curve[verb] = &ptArray[verb];
439fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                }
440fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                if (verb == SkPath::kQuad_Verb) {
441fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    curve[1] = &ptArray[1];
442f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                }
443a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                if (doMove) {
444fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    firstPt = *curve[0];
445fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    simple.moveTo(curve[0]->fX, curve[0]->fY);
446fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
447fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    SkDebugf("%s %d moveTo (%g,%g)\n", __FUNCTION__,
448fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            listIndex + 1, curve[0]->fX, curve[0]->fY);
449fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    firstIndex = listIndex;
450fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
451fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    for (int index = 0; index <= verb; ++index) {
452fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        lastCurve[index] = *curve[index];
453a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
454a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    doMove = false;
455a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                } else {
456fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    bool gap = lastCurve[lastVerb] != *curve[0];
457fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    if (gap || lastVerb != SkPath::kLine_Verb) { // output the accumulated curve before the gap
458a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        // FIXME: see comment in bridge -- this probably
459a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        // conceals errors
460fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY,
461fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                curve[0]->fY) <= 10);
462a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        switch (lastVerb) {
463a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kLine_Verb:
464a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
465a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
466a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kQuad_Verb:
467a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
468a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                        lastCurve[2].fX, lastCurve[2].fY);
469a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
470a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kCubic_Verb:
471a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
472a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                        lastCurve[2].fX, lastCurve[2].fY,
473a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                        lastCurve[3].fX, lastCurve[3].fY);
474a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
475cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                        }
476fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
477fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkDebugf("%*s %d %sTo (%g,%g)\n", tab, "", lastIndex + 1,
478fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                kLVerbStr[lastVerb], lastCurve[lastVerb].fX,
479fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                lastCurve[lastVerb].fY);
480fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
481a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
482fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    int firstCopy = 1;
48378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                    if (gap || (lastVerb == SkPath::kLine_Verb
48478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                             && (verb != SkPath::kLine_Verb
48578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                             || !extendLine(lastCurve, *curve[verb])))) {
486a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        // FIXME: see comment in bridge -- this probably
487a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        // conceals errors
488fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkASSERT(lastCurve[lastVerb] == *curve[0] ||
489fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                (fFill && UlpsDiff(lastCurve[lastVerb].fY,
490fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                curve[0]->fY) <= 10));
491fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        simple.lineTo(curve[0]->fX, curve[0]->fY);
492fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
493fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkDebugf("%*s %d gap lineTo (%g,%g)\n", tab, "",
494fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                lastIndex + 1, curve[0]->fX, curve[0]->fY);
495fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
496fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        firstCopy = 0;
497fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    } else if (lastVerb != SkPath::kLine_Verb) {
498fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        firstCopy = 0;
499a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
500fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    for (int index = firstCopy; index <= verb; ++index) {
501fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        lastCurve[index] = *curve[index];
502a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
5036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                }
504fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                lastVerb = verb;
505fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
506fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                lastIndex = listIndex;
507fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
5086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                if (advance < 0) {
5096008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    edgeIndex = fTops[listIndex];
5106008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fTops[listIndex] = 0;
511fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                } else {
5126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    edgeIndex = fBottoms[listIndex];
5136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fBottoms[listIndex] = 0;
5146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                }
5154917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                if (edgeIndex) {
5164917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    listIndex = abs(edgeIndex) - 1;
5174917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    if (edgeIndex < 0) {
5184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                        fTops[listIndex] = 0;
5194917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    } else {
5204917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                        fBottoms[listIndex] = 0;
5214917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    }
5224917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                }
5234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                if (edgeIndex == closeEdgeIndex || edgeIndex == 0) {
524fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    switch (lastVerb) {
525fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        case SkPath::kLine_Verb:
526fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
527fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            break;
528fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        case SkPath::kQuad_Verb:
529fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
530fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                    lastCurve[2].fX, lastCurve[2].fY);
531fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            break;
532fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        case SkPath::kCubic_Verb:
533fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
534fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                    lastCurve[2].fX, lastCurve[2].fY,
535fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                    lastCurve[3].fX, lastCurve[3].fY);
536fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            break;
537fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    }
538fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
539fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    SkDebugf("%*s %d %sTo last (%g, %g)\n", tab, "",
540fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            lastIndex + 1, kLVerbStr[lastVerb],
541fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            lastCurve[lastVerb].fX, lastCurve[lastVerb].fY);
542fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
543a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    if (lastCurve[lastVerb] != firstPt) {
544fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        simple.lineTo(firstPt.fX, firstPt.fY);
545fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
546fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkDebugf("%*s %d final line (%g, %g)\n", tab, "",
547fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                firstIndex + 1, firstPt.fX, firstPt.fY);
548fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
5494917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    }
550cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                    simple.close();
551fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
552fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    SkDebugf("%*s   close\n", tab, "");
553fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
554cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                    break;
555cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                }
556fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                // if this and next edge go different directions
557fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_ASSEMBLE
558fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                SkDebugf("%*s   advance=%d edgeIndex=%d flip=%s\n", tab, "",
559fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        advance, edgeIndex, advance > 0 ^ edgeIndex < 0 ?
560fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        "true" : "false");
561fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
5626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                if (advance > 0 ^ edgeIndex < 0) {
5636008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    advance = -advance;
5646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                }
5654917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            } while (edgeIndex);
5666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        } while (true);
567f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
568752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
569cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    // sort points by y, then x
570cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    // if x/y is identical, sort bottoms before tops
571cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    // if identical and both tops/bottoms, sort by angle
572cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    static bool lessThan(SkTArray<OutEdge>& edges, const int one,
573cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            const int two) {
574cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const OutEdge& oneEdge = edges[abs(one) - 1];
575cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        int oneIndex = one < 0 ? 0 : oneEdge.fVerb;
576cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& startPt1 = oneEdge.fPts[oneIndex];
577cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const OutEdge& twoEdge = edges[abs(two) - 1];
578cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        int twoIndex = two < 0 ? 0 : twoEdge.fVerb;
579cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& startPt2 = twoEdge.fPts[twoIndex];
580cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (startPt1.fY != startPt2.fY) {
5812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #if DEBUG_OUT_LESS_THAN
5822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__,
5832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    one, two, startPt1.fY, startPt2.fY,
5842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    startPt1.fY < startPt2.fY ? "true" : "false");
5852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #endif
586cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return startPt1.fY < startPt2.fY;
587cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
588cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (startPt1.fX != startPt2.fX) {
5892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #if DEBUG_OUT_LESS_THAN
5902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__,
5912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    one, two, startPt1.fX, startPt2.fX,
5922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    startPt1.fX < startPt2.fX ? "true" : "false");
5932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #endif
594cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return startPt1.fX < startPt2.fX;
595cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
596cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb];
597cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb];
598cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkScalar dy1 = startPt1.fY - endPt1.fY;
599cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkScalar dy2 = startPt2.fY - endPt2.fY;
600cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkScalar dy1y2 = dy1 * dy2;
601cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (dy1y2 < 0) { // different signs
6022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #if DEBUG_OUT_LESS_THAN
603cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two,
604cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                        dy1 > 0 ? "true" : "false");
6052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #endif
606cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return dy1 > 0; // one < two if one goes up and two goes down
607cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
608cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (dy1y2 == 0) {
6092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #if DEBUG_OUT_LESS_THAN
6102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__,
6112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    one, two, endPt1.fX < endPt2.fX ? "true" : "false");
6122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #endif
613cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return endPt1.fX < endPt2.fX;
614d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        }
615cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2;
616cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1;
6172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #if DEBUG_OUT_LESS_THAN
6182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__,
6192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false");
6202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    #endif
621cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        return dy2 > 0 ^ dx1y2 < dx2y1;
622f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
623f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
6246008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    // Sort the indices of paired points and then create more indices so
6256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    // assemble() can find the next edge and connect the top or bottom
626f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    void bridge() {
627f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        size_t index;
628f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        size_t count = fEdges.count();
629f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        if (!count) {
630f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            return;
631f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        }
632cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        SkASSERT(!fFill || count > 1);
633f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        fTops.setCount(count);
634f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        sk_bzero(fTops.begin(), sizeof(fTops[0]) * count);
635f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        fBottoms.setCount(count);
636f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count);
6376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        SkTDArray<int> order;
6386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        for (index = 1; index <= count; ++index) {
6396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            *order.append() = -index;
640f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        }
641cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        for (index = 1; index <= count; ++index) {
642cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            *order.append() = index;
643cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
644cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan);
6456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        int* lastPtr = order.end() - 1;
6466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        int* leftPtr = order.begin();
6476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        while (leftPtr < lastPtr) {
6486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int leftIndex = *leftPtr;
6496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int leftOutIndex = abs(leftIndex) - 1;
6506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            const OutEdge& left = fEdges[leftOutIndex];
651f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            int* rightPtr = leftPtr + 1;
6526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int rightIndex = *rightPtr;
6536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            int rightOutIndex = abs(rightIndex) - 1;
6546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            const OutEdge& right = fEdges[rightOutIndex];
655cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            bool pairUp = fFill;
656cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            if (!pairUp) {
657cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                const SkPoint& leftMatch =
658cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                        left.fPts[leftIndex < 0 ? 0 : left.fVerb];
659cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                const SkPoint& rightMatch =
660cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                        right.fPts[rightIndex < 0 ? 0 : right.fVerb];
661cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                pairUp = leftMatch == rightMatch;
662cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            } else {
6632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        #if DEBUG_OUT
664d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        // FIXME : not happy that error in low bit is allowed
665d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        // this probably conceals error elsewhere
666d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,
667d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                        right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) {
6682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    *fMismatches.append() = leftIndex;
6692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    if (rightPtr == lastPtr) {
6702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                        *fMismatches.append() = rightIndex;
6712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    }
6722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    pairUp = false;
6732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                }
6742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        #else
675d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,
676d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                        right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10);
6772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        #endif
678cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            }
679cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            if (pairUp) {
6806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                if (leftIndex < 0) {
6816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fTops[leftOutIndex] = rightIndex;
6826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                } else {
6836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fBottoms[leftOutIndex] = rightIndex;
6846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                }
6856008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                if (rightIndex < 0) {
6866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fTops[rightOutIndex] = leftIndex;
6876008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                } else {
6886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                    fBottoms[rightOutIndex] = leftIndex;
689f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                }
6906008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                ++rightPtr;
691f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            }
692f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            leftPtr = rightPtr;
6936680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        }
6942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT
6952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int* mismatch = fMismatches.begin();
6962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        while (mismatch != fMismatches.end()) {
6972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            int leftIndex = *mismatch++;
6982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            int leftOutIndex = abs(leftIndex) - 1;
6992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            const OutEdge& left = fEdges[leftOutIndex];
7002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb];
7012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n",
7022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot",
7032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    leftPt.fX, leftPt.fY);
7042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
7052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkASSERT(fMismatches.count() == 0);
7062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
707fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#if DEBUG_BRIDGE
708fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    for (index = 0; index < count; ++index) {
709fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        const OutEdge& edge = fEdges[index];
710fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        uint8_t verb = edge.fVerb;
711d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        SkDebugf("%s %d edge=%d %s (%1.9g,%1.9g) (%1.9g,%1.9g)\n",
712fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                index == 0 ? __FUNCTION__ : "      ",
713fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                index + 1, edge.fID, kLVerbStr[verb], edge.fPts[0].fX,
714fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                edge.fPts[0].fY, edge.fPts[verb].fX, edge.fPts[verb].fY);
715fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
716fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    for (index = 0; index < count; ++index) {
717fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkDebugf("       top    of % 2d connects to %s of % 2d\n", index + 1,
718fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                fTops[index] < 0 ? "top   " : "bottom", abs(fTops[index]));
719fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkDebugf("       bottom of % 2d connects to %s of % 2d\n", index + 1,
720fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                fBottoms[index] < 0 ? "top   " : "bottom", abs(fBottoms[index]));
721fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
722fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com#endif
7236680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    }
7246680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
7256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comprotected:
7266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    SkTArray<OutEdge> fEdges;
7276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    SkTDArray<int> fTops;
7286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    SkTDArray<int> fBottoms;
729f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    bool fFill;
7302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT
7312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkTDArray<int> fMismatches;
7322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
7336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com};
7346680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
735c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// Bounds, unlike Rect, does not consider a vertical line to be empty.
736c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct Bounds : public SkRect {
737c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    static bool Intersects(const Bounds& a, const Bounds& b) {
738c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
739c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                a.fTop <= b.fBottom && b.fTop <= a.fBottom;
740c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
741752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
7426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    bool isEmpty() {
7436008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        return fLeft > fRight || fTop > fBottom
7449f3e9a5a17a7546e1c5bfde1eb7e6e9c11870333caryclark@google.com                || (fLeft == fRight && fTop == fBottom)
7456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                || isnan(fLeft) || isnan(fRight)
7466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                || isnan(fTop) || isnan(fBottom);
7476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    }
748c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
749c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
7504917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.comclass Intercepts {
7514917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.compublic:
7524917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com    Intercepts()
7534917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com        : fTopIntercepts(0)
754198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        , fBottomIntercepts(0)
755198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        , fExplicit(false) {
756198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
757d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
758198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    Intercepts& operator=(const Intercepts& src) {
759198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fTs = src.fTs;
760198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fTopIntercepts = src.fTopIntercepts;
761198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fBottomIntercepts = src.fBottomIntercepts;
762b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        return *this;
763198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
764198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
765198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    // OPTIMIZATION: remove this function if it's never called
766198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    double t(int tIndex) const {
767198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (tIndex == 0) {
768198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            return 0;
769198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
770198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (tIndex > fTs.count()) {
771198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            return 1;
772198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
773198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        return fTs[tIndex - 1];
7744917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com    }
775752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
7762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP
777a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    void dump(const SkPoint* pts, SkPath::Verb verb) {
7782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const char className[] = "Intercepts";
7792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const int tab = 8;
7802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        for (int i = 0; i < fTs.count(); ++i) {
7812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkPoint out;
782a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            switch (verb) {
783a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                case SkPath::kLine_Verb:
784a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    LineXYAtT(pts, fTs[i], &out);
785a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    break;
786a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                case SkPath::kQuad_Verb:
787a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    QuadXYAtT(pts, fTs[i], &out);
788a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    break;
789a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                case SkPath::kCubic_Verb:
790a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    CubicXYAtT(pts, fTs[i], &out);
791a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    break;
792a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                default:
793a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    SkASSERT(0);
794a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            }
795752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className),
7962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    className, i, fTs[i], out.fX, out.fY);
7972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
798198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className),
7992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                className, fTopIntercepts);
800198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className),
8012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                className, fBottomIntercepts);
802fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className),
803fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                className, fExplicit);
8042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
8052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
8062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
807c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkTDArray<double> fTs;
808198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges
809198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    unsigned char fBottomIntercepts;
810198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    bool fExplicit; // if set, suppress 0 and 1
811d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
812c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
813c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
8142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstruct HorizontalEdge {
8152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool operator<(const HorizontalEdge& rh) const {
8162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight
8172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                : fLeft < rh.fLeft : fY < rh.fY;
8182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
8192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
8202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP
8212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void dump() {
8222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const char className[] = "HorizontalEdge";
8232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const int tab = 4;
824752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft);
825752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight);
826752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY);
8272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
8282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
8292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
8302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkScalar fLeft;
8312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkScalar fRight;
8322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkScalar fY;
8332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com};
8342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
8356680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct InEdge {
8366680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    bool operator<(const InEdge& rh) const {
837c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        return fBounds.fTop == rh.fBounds.fTop
838c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                ? fBounds.fLeft < rh.fBounds.fLeft
839c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                : fBounds.fTop < rh.fBounds.fTop;
840c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
841c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
8422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // Avoid collapsing t values that are close to the same since
8432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // we walk ts to describe consecutive intersections. Since a pair of ts can
8442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // be nearly equal, any problems caused by this should be taken care
845d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com    // of later.
8462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    int add(double* ts, size_t count, ptrdiff_t verbIndex) {
847c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        // FIXME: in the pathological case where there is a ton of intercepts, binary search?
8486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        bool foundIntercept = false;
8492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int insertedAt = -1;
8506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        Intercepts& intercepts = fIntercepts[verbIndex];
851c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        for (size_t index = 0; index < count; ++index) {
852c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            double t = ts[index];
8534917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            if (t <= 0) {
854198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                intercepts.fTopIntercepts <<= 1;
8554917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                fContainsIntercepts |= ++intercepts.fTopIntercepts > 1;
8564917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                continue;
8574917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            }
8584917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            if (t >= 1) {
859198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                intercepts.fBottomIntercepts <<= 1;
8604917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1;
8616008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                continue;
8626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            }
863198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            fIntersected = true;
8646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            foundIntercept = true;
865c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            size_t tCount = intercepts.fTs.count();
8662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            double delta;
867c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
868c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                if (t <= intercepts.fTs[idx2]) {
8692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    // FIXME: ?  if (t < intercepts.fTs[idx2]) // failed
8702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    delta = intercepts.fTs[idx2] - t;
871cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com                    if (delta > 0) {
8722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                        insertedAt = idx2;
873c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                        *intercepts.fTs.insert(idx2) = t;
874c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                    }
8752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    goto nextPt;
876c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                }
877c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            }
8782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) {
8792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                insertedAt = tCount;
880c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                *intercepts.fTs.append() = t;
881c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            }
8822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    nextPt:
8832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            ;
884c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
8854917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com        fContainsIntercepts |= foundIntercept;
8862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        return insertedAt;
887c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
888d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
889fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void addPartial(SkTArray<InEdge>& edges, int ptStart, int ptEnd,
890198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            int verbStart, int verbEnd) {
891198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        InEdge* edge = edges.push_back_n(1);
892198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        int verbCount = verbEnd - verbStart;
893198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fIntercepts.push_back_n(verbCount);
894a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com     //   uint8_t* verbs = &fVerbs[verbStart];
895198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) {
896198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx];
897198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
898198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]);
899198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fVerbs.append(verbCount, &fVerbs[verbStart]);
900198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->setBounds();
901198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fWinding = fWinding;
902198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
903198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
904198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
905fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb,
906fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            Intercepts& intercepts, int firstT, int lastT, bool flipped) {
907198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        InEdge* edge = edges.push_back_n(1);
908198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fIntercepts.push_back_n(1);
909fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        if (firstT == 0) {
910fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            *edge->fIntercepts[0].fTs.append() = 0;
911fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        } else {
912fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            *edge->fIntercepts[0].fTs.append() = intercepts.fTs[firstT - 1];
913fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        }
914fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        bool add1 = lastT == intercepts.fTs.count();
915fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        edge->fIntercepts[0].fTs.append(lastT - firstT, &intercepts.fTs[firstT]);
916fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        if (add1) {
917fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            *edge->fIntercepts[0].fTs.append() = 1;
918fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        }
919198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fIntercepts[0].fExplicit = true;
920fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        edge->fPts.append(verb + 1, pts);
921198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fVerbs.append(1, &verb);
922fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        // FIXME: bounds could be better for partial Ts
923fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        edge->setSubBounds();
924198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
925198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (flipped) {
926fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            edge->flipTs();
927fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            edge->fWinding = -fWinding;
928fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        } else {
929fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            edge->fWinding = fWinding;
930198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
931198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
932c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
9336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    bool cached(const InEdge* edge) {
934c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        // FIXME: in the pathological case where there is a ton of edges, binary search?
935c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        size_t count = fCached.count();
936c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        for (size_t index = 0; index < count; ++index) {
937c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            if (edge == fCached[index]) {
938c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                return true;
939c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            }
940c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            if (edge < fCached[index]) {
941c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                *fCached.insert(index) = edge;
942c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                return false;
943c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            }
944c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
945c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        *fCached.append() = edge;
946c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        return false;
947c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
948c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
949fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void complete(signed char winding) {
950198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        setBounds();
951198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fIntercepts.push_back_n(fVerbs.count());
952198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top
953198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            flip();
954198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
955198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fContainsIntercepts = fIntersected = false;
956198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
957d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
958fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void flip() {
959198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        size_t index;
960198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        size_t last = fPts.count() - 1;
961198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        for (index = 0; index < last; ++index, --last) {
962198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            SkTSwap<SkPoint>(fPts[index], fPts[last]);
963198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
964198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        last = fVerbs.count() - 1;
965198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        for (index = 0; index < last; ++index, --last) {
966198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);
967198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
968198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
969d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
970fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void flipTs() {
971fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkASSERT(fIntercepts.count() == 1);
972fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        Intercepts& intercepts = fIntercepts[0];
973fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkASSERT(intercepts.fExplicit);
974fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkTDArray<double>& ts = intercepts.fTs;
975fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        size_t index;
976fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        size_t last = ts.count() - 1;
977fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        for (index = 0; index < last; ++index, --last) {
978fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            SkTSwap<double>(ts[index], ts[last]);
979fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        }
980fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
981198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
982198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    void reset() {
983198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fCached.reset();
984198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fIntercepts.reset();
985198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fPts.reset();
986198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fVerbs.reset();
987198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
988198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fWinding = 0;
989198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fContainsIntercepts = false;
990198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fIntersected = false;
991198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
992198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
993198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    void setBounds() {
994c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        SkPoint* ptPtr = fPts.begin();
995c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        SkPoint* ptLast = fPts.end();
996c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        if (ptPtr == ptLast) {
997198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            SkDebugf("%s empty edge\n", __FUNCTION__);
998c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            SkASSERT(0);
999c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            // FIXME: delete empty edge?
1000c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            return;
1001c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
1002c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY);
1003c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        ++ptPtr;
1004c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        while (ptPtr != ptLast) {
1005c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            fBounds.growToInclude(ptPtr->fX, ptPtr->fY);
1006c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            ++ptPtr;
1007c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
1008198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    }
1009d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1010fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    // recompute bounds based on subrange of T values
1011fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void setSubBounds() {
1012fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkASSERT(fIntercepts.count() == 1);
1013fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        Intercepts& intercepts = fIntercepts[0];
1014fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkASSERT(intercepts.fExplicit);
1015fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkASSERT(fVerbs.count() == 1);
1016fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkTDArray<double>& ts = intercepts.fTs;
1017fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        if (fVerbs[0] == SkPath::kQuad_Verb) {
1018fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            SkASSERT(fPts.count() == 3);
1019fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            QuadSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);
1020fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        } else {
1021fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            SkASSERT(fVerbs[0] == SkPath::kCubic_Verb);
1022fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            SkASSERT(fPts.count() == 4);
1023fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            CubicSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);
1024fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        }
1025fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    }
1026198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
1027fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    void splitInflectionPts(SkTArray<InEdge>& edges) {
1028198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (!fIntersected) {
1029198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            return;
1030198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
1031198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        uint8_t* verbs = fVerbs.begin();
1032198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkPoint* pts = fPts.begin();
1033198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        int lastVerb = 0;
1034198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        int lastPt = 0;
1035198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        uint8_t verb;
1036198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        bool edgeSplit = false;
1037198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += verb) {
1038198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            Intercepts& intercepts = fIntercepts[ceptIdx];
1039198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            verb = *verbs++;
1040198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            if (verb <= SkPath::kLine_Verb) {
1041198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                continue;
1042198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            }
1043198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            size_t tCount = intercepts.fTs.count();
1044198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            if (!tCount) {
1045198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                continue;
1046198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            }
1047a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com            size_t tIndex = (size_t) -1;
1048198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            SkScalar y = pts[0].fY;
1049198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            int lastSplit = 0;
1050198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            int firstSplit = -1;
1051198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            bool curveSplit = false;
1052198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            while (++tIndex < tCount) {
1053198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                double nextT = intercepts.fTs[tIndex];
1054198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                SkScalar nextY = verb == SkPath::kQuad_Verb
1055198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT);
1056198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                if (nextY < y) {
1057198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    edgeSplit = curveSplit = true;
1058198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    if (firstSplit < 0) {
1059198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        firstSplit = tIndex;
1060198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        int nextPt = pts - fPts.begin();
1061198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        int nextVerb = verbs - 1 - fVerbs.begin();
1062198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        if (lastVerb < nextVerb) {
1063fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            addPartial(edges, lastPt, nextPt, lastVerb, nextVerb);
1064198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1065fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            SkDebugf("%s addPartial 1\n", __FUNCTION__);
1066198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
1067198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        }
1068198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        lastPt = nextPt;
1069198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        lastVerb = nextVerb;
1070198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    }
1071198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                } else {
1072198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    if (firstSplit >= 0) {
1073198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        if (lastSplit < firstSplit) {
1074fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            addSplit(edges, pts, verb, intercepts,
1075fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                    lastSplit, firstSplit, false);
1076198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1077fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            SkDebugf("%s addSplit 1 tIndex=%d,%d\n",
1078fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                    __FUNCTION__, lastSplit, firstSplit);
1079198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
1080198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        }
1081d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com                        addSplit(edges, pts, verb, intercepts,
1082fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                firstSplit, tIndex, true);
1083198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1084fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n",
1085fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                                __FUNCTION__, firstSplit, tIndex);
1086198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
1087198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        lastSplit = tIndex;
1088198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        firstSplit = -1;
1089198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    }
1090198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                }
1091198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                y = nextY;
1092198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            }
1093198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            if (curveSplit) {
1094198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                if (firstSplit < 0) {
1095198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    firstSplit = lastSplit;
1096198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                } else {
1097fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    addSplit(edges, pts, verb, intercepts, lastSplit,
1098fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            firstSplit, false);
1099198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1100fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                    SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__,
1101fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                            lastSplit, firstSplit);
1102198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
1103198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                }
1104fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                addSplit(edges, pts, verb, intercepts, firstSplit,
1105fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        tIndex, pts[verb].fY < y);
1106198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1107fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__,
1108fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                        firstSplit, tIndex, pts[verb].fY < y ? "flip" : "");
1109198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
11106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com            }
1111198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        }
1112198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        // collapse remainder -- if there's nothing left, clear it somehow?
1113198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (edgeSplit) {
1114198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            int nextVerb = verbs - 1 - fVerbs.begin();
1115198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            if (lastVerb < nextVerb) {
1116198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                int nextPt = pts - fPts.begin();
1117fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                addPartial(edges, lastPt, nextPt, lastVerb, nextVerb);
1118198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #if DEBUG_SPLIT
1119fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com                SkDebugf("%s addPartial 2\n", __FUNCTION__);
1120198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            #endif
11216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com            }
1122198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            // OPTIMIZATION: reuse the edge instead of marking it empty
1123198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            reset();
11246680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        }
11252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
11262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
11272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP
11282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void dump() {
11292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int i;
11302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const char className[] = "InEdge";
11312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        const int tab = 4;
11322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkDebugf("InEdge %p (edge=%d)\n", this, fID);
11332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        for (i = 0; i < fCached.count(); ++i) {
11342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className),
11352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    className, i, fCached[i]);
11362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
11372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        uint8_t* verbs = fVerbs.begin();
11382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkPoint* pts = fPts.begin();
11392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        for (i = 0; i < fIntercepts.count(); ++i) {
11402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className),
11412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    className, i);
1142a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            fIntercepts[i].dump(pts, (SkPath::Verb) *verbs);
11432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            pts += *verbs++;
11442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
11452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        for (i = 0; i < fPts.count(); ++i) {
1146752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className),
11472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    className, i, fPts[i].fX, fPts[i].fY);
11482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
11492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        for (i = 0; i < fVerbs.count(); ++i) {
11502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className),
11512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    className, i, fVerbs[i]);
11522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
1153fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        SkDebugf("%*s.fBounds=(%1.9g, %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className),
11542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                className, fBounds.fLeft, fBounds.fTop,
11552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                fBounds.fRight, fBounds.fBottom);
11562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className,
11572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                fWinding);
11582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
11592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                className, fContainsIntercepts);
1160198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className),
1161198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                className, fIntersected);
1162c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
11632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif
1164c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1165198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    // FIXME: temporary data : move this to a separate struct?
11666680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    SkTDArray<const InEdge*> fCached; // list of edges already intercepted
1167c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkTArray<Intercepts> fIntercepts; // one per verb
11684917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com
1169c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    // persistent data
1170c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkTDArray<SkPoint> fPts;
1171c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkTDArray<uint8_t> fVerbs;
1172c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    Bounds fBounds;
11732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    int fID;
1174c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    signed char fWinding;
11756680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    bool fContainsIntercepts;
1176198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    bool fIntersected;
1177c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
1178c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
11796680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass InEdgeBuilder {
1180c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.compublic:
1181c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
11822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comInEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges,
1183d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        SkTDArray<HorizontalEdge>& horizontalEdges)
1184c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    : fPath(path)
1185c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    , fCurrentEdge(NULL)
1186c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    , fEdges(edges)
11872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    , fHorizontalEdges(horizontalEdges)
1188c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    , fIgnoreHorizontal(ignoreHorizontal)
1189198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    , fContainsCurves(false)
1190c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{
1191c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    walk();
1192c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1193c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1194198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.combool containsCurves() const {
1195198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    return fContainsCurves;
1196198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com}
1197198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com
1198c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprotected:
1199c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1200c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid addEdge() {
1201f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    SkASSERT(fCurrentEdge);
1202c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);
1203c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    fPtOffset = 1;
1204c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    *fCurrentEdge->fVerbs.append() = fVerb;
1205c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1206c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
12076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.combool complete() {
12086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    if (fCurrentEdge && fCurrentEdge->fVerbs.count()) {
1209fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com        fCurrentEdge->complete(fWinding);
12106008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        fCurrentEdge = NULL;
12116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        return true;
12126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    }
12136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    return false;
12146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com}
12156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com
121678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.comint direction(SkPath::Verb verb) {
121778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    fPtCount = verb + 1;
12182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    if (fIgnoreHorizontal && isHorizontal()) {
1219c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        return 0;
1220c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
122178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    return fPts[0].fY == fPts[verb].fY
122278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ? fPts[0].fX == fPts[verb].fX ? 0 : fPts[0].fX < fPts[verb].fX
122378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ? 1 : -1 : fPts[0].fY < fPts[verb].fY ? 1 : -1;
1224c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1225c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1226c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool isHorizontal() {
1227c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkScalar y = fPts[0].fY;
1228c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    for (int i = 1; i < fPtCount; ++i) {
1229c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        if (fPts[i].fY != y) {
1230c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            return false;
1231c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
1232c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1233c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    return true;
1234c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1235c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1236c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid startEdge() {
12376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    if (!fCurrentEdge) {
12386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        fCurrentEdge = fEdges.push_back_n(1);
12396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    }
1240c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    fWinding = 0;
1241c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    fPtOffset = 0;
1242c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1243c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1244c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid walk() {
1245c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPath::Iter iter(fPath, true);
12462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    int winding = 0;
1247c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) {
1248c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        switch (fVerb) {
1249c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kMove_Verb:
1250c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                startEdge();
1251c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                continue;
1252c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kLine_Verb:
125378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                winding = direction(SkPath::kLine_Verb);
1254c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
1255c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kQuad_Verb:
125678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                fVerb = QuadReduceOrder(fPts);
125778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                winding = direction(fVerb);
125878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                fContainsCurves |= fVerb == SkPath::kQuad_Verb;
1259c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
1260c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kCubic_Verb:
126178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                fVerb = CubicReduceOrder(fPts);
126278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                winding = direction(fVerb);
126378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                fContainsCurves |= fVerb >= SkPath::kQuad_Verb;
1264c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                break;
1265c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            case SkPath::kClose_Verb:
1266f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                SkASSERT(fCurrentEdge);
12676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                complete();
1268c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                continue;
1269c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            default:
1270c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                SkDEBUGFAIL("bad verb");
1271c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com                return;
1272c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
12732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (winding == 0) {
12742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            HorizontalEdge* horizontalEdge = fHorizontalEdges.append();
12752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            // FIXME: for degenerate quads and cubics, compute x extremes
12762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            horizontalEdge->fLeft = fPts[0].fX;
12772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            horizontalEdge->fRight = fPts[fVerb].fX;
12782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            horizontalEdge->fY = fPts[0].fY;
12792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (horizontalEdge->fLeft > horizontalEdge->fRight) {
12802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight);
12812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            }
12826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            if (complete()) {
12836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com                startEdge();
12846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            }
1285c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            continue;
1286c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
1287c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        if (fWinding + winding == 0) {
1288c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            // FIXME: if prior verb or this verb is a horizontal line, reverse
1289c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com            // it instead of starting a new edge
1290f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            SkASSERT(fCurrentEdge);
1291cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            if (complete()) {
1292cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                startEdge();
1293cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            }
1294c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        }
1295c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        fWinding = winding;
1296c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        addEdge();
1297c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
12986b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com    if (!complete()) {
12996b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com        if (fCurrentEdge) {
13006b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com            fEdges.pop_back();
13016b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com        }
13026b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com    }
1303c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}
1304c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1305c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprivate:
1306c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    const SkPath& fPath;
13076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    InEdge* fCurrentEdge;
13086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    SkTArray<InEdge>& fEdges;
13092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkTDArray<HorizontalEdge>& fHorizontalEdges;
1310c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPoint fPts[4];
1311c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPath::Verb fVerb;
1312c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    int fPtCount;
1313c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    int fPtOffset;
1314c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    int8_t fWinding;
1315c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    bool fIgnoreHorizontal;
1316198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    bool fContainsCurves;
1317c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
1318c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
13196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct WorkEdge {
1320c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkScalar bottom() const {
13216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        return fPts[verb()].fY;
1322c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1323c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
13246680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    void init(const InEdge* edge) {
13256680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fEdge = edge;
13266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fPts = edge->fPts.begin();
13276680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fVerb = edge->fVerbs.begin();
1328c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1329c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1330cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    bool advance() {
13316680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        SkASSERT(fVerb < fEdge->fVerbs.end());
13326680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fPts += *fVerb++;
13336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        return fVerb != fEdge->fVerbs.end();
1334c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1335d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
133678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const SkPoint* lastPoints() const {
133778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb());
133878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return &fPts[-lastVerb()];
133978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
1340752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1341cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    SkPath::Verb lastVerb() const {
1342cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        SkASSERT(fVerb > fEdge->fVerbs.begin());
1343cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        return (SkPath::Verb) fVerb[-1];
1344cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    }
1345cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com
134678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const SkPoint* points() const {
134778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return fPts;
134878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
1349c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1350c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    SkPath::Verb verb() const {
1351c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com        return (SkPath::Verb) *fVerb;
1352c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1353c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
13546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    ptrdiff_t verbIndex() const {
13556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        return fVerb - fEdge->fVerbs.begin();
13566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    }
1357752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
13586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    int winding() const {
13596680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        return fEdge->fWinding;
1360c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1361c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
13626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    const InEdge* fEdge;
1363c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    const SkPoint* fPts;
1364c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    const uint8_t* fVerb;
1365c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
1366c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
13676680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// always constructed with SkTDArray because new edges are inserted
13686680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// this may be a inappropriate optimization, suggesting that a separate array of
13696680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// ActiveEdge* may be faster to insert and search
1370cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com
1371cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since
1372cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// as active edges are introduced, only local sorting should be required
13732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comclass ActiveEdge {
13742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic:
137578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    // this logic must be kept in sync with tooCloseToCall
1376fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    // callers expect this to only read fAbove, fTangent
13776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    bool operator<(const ActiveEdge& rh) const {
1378fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb == rh.fVerb) {
1379fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            // FIXME: don't know what to do if verb is quad, cubic
1380fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
1381fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1382fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // figure out which is quad, line
1383fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // if cached data says line did not intersect quad, use top/bottom
1384fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this)) {
1385fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
1386fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1387d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        // use whichever of top/tangent tangent/bottom overlaps more
1388fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // with line top/bot
1389fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // assumes quad/cubic can already be upconverted to cubic/cubic
1390fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        const SkPoint* line[2];
1391fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        const SkPoint* curve[4];
1392fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb != SkPath::kLine_Verb) {
1393fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            line[0] = &rh.fAbove;
1394fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            line[1] = &rh.fBelow;
1395fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[0] = &fAbove;
1396fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[1] = &fTangent;
1397fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[2] = &fBelow;
1398fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else {
1399fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            line[0] = &fAbove;
1400fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            line[1] = &fBelow;
1401fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[0] = &rh.fAbove;
1402fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[1] = &rh.fTangent;
1403fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            curve[2] = &rh.fBelow;
1404fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1405b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        // FIXME: code has been abandoned, incomplete....
1406b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com        return false;
1407fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1408d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1409fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1,
1410fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            const SkPoint& b2) const {
1411fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        double topD = a1.fX - b1.fX;
1412fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (b1.fY < a1.fY) {
1413fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX);
1414fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else if (b1.fY > a1.fY) {
1415fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX);
1416fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1417fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        double botD = a2.fX - b2.fX;
1418fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (b2.fY > a2.fY) {
1419fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX);
1420fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else if (b2.fY < a2.fY) {
1421fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX);
1422d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        }
1423d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        // return sign of greater absolute value
1424d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        return (fabs(topD) > fabs(botD) ? topD : botD) < 0;
1425d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com    }
1426d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com
14272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // If a pair of edges are nearly coincident for some span, add a T in the
14282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // edge so it can be shortened to match the other edge. Note that another
14292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // approach is to trim the edge after it is added to the OutBuilder list --
14302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // FIXME: since this has no effect if the edge is already done (i.e.,
14312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // fYBottom >= y) maybe this can only be done by calling trimLine later.
14322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void addTatYBelow(SkScalar y) {
14332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (fBelow.fY <= y || fYBottom >= y) {
14342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            return;
14352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
14362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        addTatYInner(y);
14372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        fFixBelow = true;
14382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
1439752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
14402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void addTatYAbove(SkScalar y) {
14412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (fBelow.fY <= y) {
14422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            return;
14432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
14442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        addTatYInner(y);
14452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
14462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
14472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void addTatYInner(SkScalar y) {
1448752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        if (fWorkEdge.fPts[0].fY > y) {
1449752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            backup(y);
1450752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        }
14512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkScalar left = fWorkEdge.fPts[0].fX;
14522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkScalar right = fWorkEdge.fPts[1].fX;
14532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (left > right) {
14542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            SkTSwap(left, right);
14552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
1456752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        double ts[2];
145778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb);
14582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts);
14592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkASSERT(pts == 1);
14602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        // An ActiveEdge or WorkEdge has no need to modify the T values computed
14612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        // in the InEdge, except in the following case. If a pair of edges are
14622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        // nearly coincident, this may not be detected when the edges are
14632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        // intersected. Later, when sorted, and this near-coincidence is found,
14642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        // an additional t value must be added, requiring the cast below.
14652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge);
14662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex());
1467752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    #if DEBUG_ADJUST_COINCIDENT
1468752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]);
1469752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    #endif
14702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (insertedAt >= 0) {
14712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            if (insertedAt + 1 < fTIndex) {
14722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                SkASSERT(insertedAt + 2 == fTIndex);
14732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                --fTIndex;
14742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            }
14752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
14762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
14776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com
1478cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    bool advanceT() {
1479198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
1480198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        return ++fTIndex <= fTs->count() - fExplicitTs;
1481cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    }
14822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
1483cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    bool advance() {
1484cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    // FIXME: flip sense of next
1485cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        bool result = fWorkEdge.advance();
1486cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        fDone = !result;
1487cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        initT();
1488cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        return result;
1489cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    }
1490752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1491752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    void backup(SkScalar y) {
1492752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        do {
1493752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb);
1494752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            fWorkEdge.fPts -= *--fWorkEdge.fVerb;
1495752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts);
1496752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        } while (fWorkEdge.fPts[0].fY >= y);
1497752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        initT();
1498198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkASSERT(!fExplicitTs);
1499752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        fTIndex = fTs->count() + 1;
1500752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    }
1501d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1502fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    void calcAboveBelow(double tAbove, double tBelow) {
1503fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fVerb = fWorkEdge.verb();
1504fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        switch (fVerb) {
1505fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            case SkPath::kLine_Verb:
1506fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
1507fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent);
1508fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fBelow = fTangent;
1509fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                break;
1510fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            case SkPath::kQuad_Verb:
1511fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                // FIXME: put array in struct to avoid copy?
1512fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                SkPoint quad[3];
1513fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad);
1514fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fAbove = quad[0];
1515fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fTangent = quad[0] != quad[1] ? quad[1] : quad[2];
1516fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fBelow = quad[2];
1517fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                break;
1518fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            case SkPath::kCubic_Verb:
1519fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                SkPoint cubic[3];
1520fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic);
1521fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fAbove = cubic[0];
1522fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                // FIXME: can't see how quad logic for how tangent is used
1523d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com                // extends to cubic
1524fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fTangent = cubic[0] != cubic[1] ? cubic[1]
1525fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                        : cubic[0] != cubic[2] ? cubic[2] : cubic[3];
1526fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                fBelow = cubic[3];
1527fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                break;
1528fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            default:
1529fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                SkASSERT(0);
1530fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1531fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
1532752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1533cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    void calcLeft(SkScalar y) {
1534cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        // OPTIMIZE: put a kDone_Verb at the end of the verb list?
15354917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com        if (fDone || fBelow.fY > y) {
1536cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return; // nothing to do; use last
15374917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com        }
1538cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        calcLeft();
1539752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        if (fAbove.fY == fBelow.fY) {
1540752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com            SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__,
1541752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com                    ID(), fAbove.fY);
1542752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        }
1543cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    }
1544752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1545cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    void calcLeft() {
1546198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        int add = (fTIndex <= fTs->count() - fExplicitTs) - 1;
1547a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        double tAbove = t(fTIndex + add);
1548a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        double tBelow = t(fTIndex - ~add);
1549fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // OPTIMIZATION: if fAbove, fBelow have already been computed
1550fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        //  for the fTIndex, don't do it again
1551fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        calcAboveBelow(tAbove, tBelow);
1552fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // For identical x, this lets us know which edge is first.
1553fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // If both edges have T values < 1, check x at next T (fBelow).
1554a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        SkASSERT(tAbove != tBelow);
1555a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        // FIXME: this can loop forever
1556a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        // need a break if we hit the end
1557198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        // FIXME: in unit test, figure out how explicit Ts work as well
1558a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        while (fAbove.fY == fBelow.fY) {
1559a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            if (add < 0 || fTIndex == fTs->count()) {
1560a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                add -= 1;
1561a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                SkASSERT(fTIndex + add >= 0);
1562a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                tAbove = t(fTIndex + add);
1563a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            } else {
1564a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                add += 1;
1565a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                SkASSERT(fTIndex - ~add <= fTs->count() + 1);
1566a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                tBelow = t(fTIndex - ~add);
1567a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            }
1568fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            calcAboveBelow(tAbove, tBelow);
1569a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        }
1570a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        fTAbove = tAbove;
1571a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        fTBelow = tBelow;
15726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    }
15736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com
1574752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    bool done(SkScalar bottom) const {
1575752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com        return fDone || fYBottom >= bottom;
1576cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    }
1577d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
15782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    void fixBelow() {
15792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (fFixBelow) {
1580fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            fTBelow = nextT();
1581fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            calcAboveBelow(fTAbove, fTBelow);
15822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            fFixBelow = false;
15832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
15842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
15852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
15866680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    void init(const InEdge* edge) {
15876680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fWorkEdge.init(edge);
1588fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        fDone = false;
15896680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        initT();
15904917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com        fBelow.fY = SK_ScalarMin;
1591cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        fYBottom = SK_ScalarMin;
15926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    }
1593752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
15946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    void initT() {
15956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front();
15966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count());
15976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex();
1598198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fTs = &interceptPtr->fTs;
1599198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        fExplicitTs = interceptPtr->fExplicit;
16006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com  //  the above is conceptually the same as
16016008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com  //    fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;
16026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com  //  but templated arrays don't allow returning a pointer to the end() element
16036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        fTIndex = 0;
1604fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (!fDone) {
1605fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            fVerb = fWorkEdge.verb();
1606fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        }
1607fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkASSERT(fVerb > SkPath::kMove_Verb);
16086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    }
1609752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1610cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    // OPTIMIZATION: record if two edges are coincident when the are intersected
1611cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    // It's unclear how to do this -- seems more complicated than recording the
1612cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    // t values, since the same t values could exist intersecting non-coincident
1613cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    // edges.
161478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    bool isCoincidentWith(const ActiveEdge* edge) const {
1615d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        if (fAbove != edge->fAbove || fBelow != edge->fBelow) {
1616d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com            return false;
1617d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        }
1618fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb != edge->fVerb) {
1619cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            return false;
1620cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        }
1621fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        switch (fVerb) {
162278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            case SkPath::kLine_Verb:
16234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                return true;
1624cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            default:
162578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                // FIXME: add support for quads, cubics
1626cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                SkASSERT(0);
162778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                return false;
1628cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
1629cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        return false;
1630cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    }
1631752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
163278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    bool isUnordered(const ActiveEdge* edge) const {
163378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return fAbove == edge->fAbove && fBelow == edge->fBelow;
163478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
163578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
1636fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com//    SkPath::Verb lastVerb() const {
1637fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com//        return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
1638fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com//    }
1639d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
164078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    const SkPoint* lastPoints() const {
164178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points();
164278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
1643d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1644fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    bool noIntersect(const ActiveEdge& ) const {
1645fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        // incomplete
1646fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        return false;
1647fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    }
164878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
16492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // The shortest close call edge should be moved into a position where
16502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // it contributes if the winding is transitioning to or from zero.
16512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const {
1652d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if DEBUG_ADJUST_COINCIDENT
1653d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n",
1654d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY,
1655d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                prev, wind, wind + next->fWorkEdge.winding());
1656d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif
16572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if ((prev & mask) == 0 || (wind & mask) == 0) {
16582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            return next->fBelow.fY < fBelow.fY;
16592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
16602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int nextWinding = wind + next->fWorkEdge.winding();
16612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if ((nextWinding & mask) == 0) {
16622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            return fBelow.fY < next->fBelow.fY;
16632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
16642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        return false;
16652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
1666752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
1667cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const {
1668cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        if (fBelow.fY >= bottom || fDone || edge->fDone) {
1669cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            return false;
1670cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        }
1671cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        ActiveEdge thisWork = *this;
1672cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        ActiveEdge edgeWork = *edge;
1673cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        while ((thisWork.advanceT() || thisWork.advance())
1674cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com                && (edgeWork.advanceT() || edgeWork.advance())) {
1675cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            thisWork.calcLeft();
1676cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            edgeWork.calcLeft();
1677cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            if (thisWork < edgeWork) {
1678cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com                return false;
1679cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            }
1680cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            if (edgeWork < thisWork) {
1681cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com                return true;
1682cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com            }
1683cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        }
1684cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com        return false;
1685cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    }
1686d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
1687a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com    bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const {
1688fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        SkASSERT(fVerb != SkPath::kLine_Verb
1689fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                || edge->fVerb != SkPath::kLine_Verb);
169078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        if (fDone || edge->fDone) {
169178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            return false;
169278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
169378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        ActiveEdge thisWork, edgeWork;
169478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        extractAboveBelow(thisWork);
169578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        edge->extractAboveBelow(edgeWork);
169678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return edgeWork < thisWork;
169778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
1698752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com
16992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool tooCloseToCall(const ActiveEdge* edge) const {
17002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        int ulps;
1701d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        double t1, t2, b1, b2;
170278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        // This logic must be kept in sync with operator <
1703d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        if (edge->fAbove.fY < fAbove.fY) {
1704fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
1705fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbove.fX);
1706d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        } else if (edge->fAbove.fY > fAbove.fY) {
1707fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
1708fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX);
1709d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        } else {
1710d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com            t1 = fAbove.fX;
1711d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com            t2 = edge->fAbove.fX;
1712d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        }
1713fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (edge->fTangent.fY > fTangent.fY) {
1714fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
1715fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge->fAbove.fX);
1716fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else if (edge->fTangent.fY < fTangent.fY) {
1717fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
1718fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX);
1719d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        } else {
1720fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b1 = fTangent.fX;
1721fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            b2 = edge->fTangent.fX;
1722d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        }
1723d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        if (fabs(t1 - t2) > fabs(b1 - b2)) {
1724b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com            ulps = UlpsDiff((float) t1, (float) t2);
1725d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        } else {
1726b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com            ulps = UlpsDiff((float) b1, (float) b2);
1727d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        }
1728d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if DEBUG_ADJUST_COINCIDENT
1729d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com        SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(),
1730d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com                ulps);
1731d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif
173278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        if (ulps < 0 || ulps > 32) {
173378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            return false;
173478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
1735fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) {
173678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            return true;
173778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
1738fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) {
173978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            return false;
174078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
174178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
174278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        double ts[2];
174378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        bool isLine = true;
174478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        bool curveQuad = true;
1745fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        if (fVerb == SkPath::kCubic_Verb) {
174678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[0] = (fTAbove * 2 + fTBelow) / 3;
174778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[1] = (fTAbove + fTBelow * 2) / 3;
174878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            curveQuad = isLine = false;
1749fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else if (edge->fVerb == SkPath::kCubic_Verb) {
175078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3;
175178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3;
175278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            curveQuad = false;
1753fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        } else if (fVerb == SkPath::kQuad_Verb) {
175478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                ts[0] = fTAbove;
175578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                ts[1] = (fTAbove + fTBelow) / 2;
175678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                isLine = false;
175778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        } else {
1758fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com            SkASSERT(edge->fVerb == SkPath::kQuad_Verb);
175978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[0] = edge->fTAbove;
176078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            ts[1] = (edge->fTAbove + edge->fTBelow) / 2;
176178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
176278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        const SkPoint* curvePts = isLine ? edge->lastPoints() : lastPoints();
176378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        const ActiveEdge* lineEdge = isLine ? this : edge;
176478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        SkPoint curveSample[2];
176578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        for (int index = 0; index < 2; ++index) {
176678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            if (curveQuad) {
176778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                QuadXYAtT(curvePts, ts[index], &curveSample[index]);
176878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            } else {
176978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                CubicXYAtT(curvePts, ts[index], &curveSample[index]);
177078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            }
177178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
177278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        return IsCoincident(curveSample, lineEdge->fAbove, lineEdge->fBelow);
17732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
1774d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com
17752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    double nextT() const {
1776198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
1777cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        return t(fTIndex + 1);
1778cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    }
1779c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1780cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    double t() const {
1781198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        return t(fTIndex);
1782c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com    }
1783c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
1784cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    double t(int tIndex) const {
1785198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com        if (fExplicitTs) {
1786198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            SkASSERT(tIndex < fTs->count());
1787198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            return (*fTs)[tIndex];
1788d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com        }
1789cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (tIndex == 0) {
1790cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return 0;
1791cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
1792cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        if (tIndex > fTs->count()) {
1793cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            return 1;
1794cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        }
1795cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        return (*fTs)[tIndex - 1];
1796cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    }
1797cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com
17982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    // FIXME: debugging only
1799752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    int ID() const {
18002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        return fWorkEdge.fEdge->fID;
18012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
18022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
180378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.comprivate:
180478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    // utility used only by swapUnordered
180578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    void extractAboveBelow(ActiveEdge& extracted) const {
180678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        SkPoint curve[4];
1807fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        switch (fVerb) {
1808d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com            case SkPath::kLine_Verb:
180978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                extracted.fAbove = fAbove;
1810fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com                extracted.fTangent = fTangent;
181178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                return;
181278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            case SkPath::kQuad_Verb:
181378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve);
181478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                break;
181578e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            case SkPath::kCubic_Verb:
181678e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                CubicSubDivide(lastPoints(), fTAbove, fTBelow, curve);
181778e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                break;
181878e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com            default:
181978e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com                SkASSERT(0);
182078e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        }
182178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com        extracted.fAbove = curve[0];
1822fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com        extracted.fTangent = curve[1];
182378e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    }
182478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com
18252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic:
18266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    WorkEdge fWorkEdge;
18276680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    const SkTDArray<double>* fTs;
1828cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    SkPoint fAbove;
1829fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    SkPoint fTangent;
1830cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com    SkPoint fBelow;
183178e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com    double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics
18322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    double fTBelow;
1833cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    SkScalar fYBottom;
18342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    int fCoincident;
18356680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    int fTIndex;
1836fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com    SkPath::Verb fVerb;
18372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool fSkip; // OPTIMIZATION: use bitfields?
18382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool fCloseCall;
1839cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    bool fDone;
18402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    bool fFixBelow;
1841198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    bool fExplicitTs;
1842c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com};
1843c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com
18446680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) {
18456680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    size_t count = activeEdges.count();
18466680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    for (size_t index = 0; index < count; ++index) {
18476680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        if (edge == activeEdges[index].fWorkEdge.fEdge) {
18486680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com            return;
18496680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com        }
18506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    }
18516680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    ActiveEdge* active = activeEdges.append();
18526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com    active->init(edge);
18536680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}
18546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com
18554917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// Find any intersections in the range of active edges. A pair of edges, on
18564917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// either side of another edge, may change the winding contribution for part of
1857d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com// the edge.
18582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// Keep horizontal edges just for
18594917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// the purpose of computing when edges change their winding contribution, since
1860d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com// this is essentially computing the horizontal intersection.
18612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void addBottomT(InEdge** currentPtr, InEdge** lastPtr,
18622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        HorizontalEdge** horizontal) {
18632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    InEdge** testPtr = currentPtr - 1;
18642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    HorizontalEdge* horzEdge = *horizontal;
18652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkScalar left = horzEdge->fLeft;
18662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    SkScalar bottom = horzEdge->fY;
18672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    while (++testPtr != lastPtr) {
18682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        InEdge* test = *testPtr;
18692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) {
18702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            continue;
18712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        }
18722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        WorkEdge wt;
18732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        wt.init(test);
18742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        do {
18752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            HorizontalEdge** sorted = horizontal;
18762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            horzEdge = *sorted;
1877f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            do {
1878198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                double wtTs[4];
1879198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                int pts;
1880198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                uint8_t verb = wt.verb();
1881198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                switch (verb) {
1882198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    case SkPath::kLine_Verb:
1883198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        pts = LineIntersect(wt.fPts, horzEdge->fLeft,
1884198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                                horzEdge->fRight, horzEdge->fY, wtTs);
1885198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        break;
1886198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    case SkPath::kQuad_Verb:
1887198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        pts = QuadIntersect(wt.fPts, horzEdge->fLeft,
1888198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                                horzEdge->fRight, horzEdge->fY, wtTs);
1889198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        break;
1890198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    case SkPath::kCubic_Verb:
1891198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        pts = CubicIntersect(wt.fPts, horzEdge->fLeft,
1892198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                                horzEdge->fRight, horzEdge->fY, wtTs);
1893198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        break;
1894198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                }
1895198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                if (pts) {
18962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADD_BOTTOM_TS
1897198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    for (int x = 0; x < pts; ++x) {
1898198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__,
1899198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                                horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0].fY);
1900198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        for (int y = 0; y < verb; ++y) {
1901198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                            SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1].fY));
19022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                        }
1903198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        SkDebugf(")\n");
1904f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                    }
1905198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    if (pts > verb) {
1906198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        SkASSERT(0); // FIXME ? should this work?
1907198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                        SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
1908198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    }
1909198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#endif
1910198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com                    test->add(wtTs, pts, wt.verbIndex());
1911f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                }
19122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                horzEdge = *++sorted;
19132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            } while (horzEdge->fY == bottom
19142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    && horzEdge->fLeft <= test->fBounds.fRight);
19152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        } while (wt.advance());
1916f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
1917f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}
1918f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
1919a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com#if DEBUG_ADD_INTERSECTING_TS
1920a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.comstatic void debugShowLineIntersection(int pts, const WorkEdge& wt,
1921a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) {
1922a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    if (!pts) {
1923a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        return;
1924a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    }
1925a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    SkPoint wtOutPt, wnOutPt;
1926a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    LineXYAtT(wt.fPts, wtTs[0], &wtOutPt);
1927a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    LineXYAtT(wn.fPts, wnTs[0], &wnOutPt);
1928fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
1929a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            __FUNCTION__,
1930a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,
1931fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY);
1932a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    if (pts == 2) {
1933a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
1934a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    }
1935fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com    SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
1936a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            __FUNCTION__,
1937a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com            wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY,
1938fb173424e915e696a73067d616ce4f39a407261acaryclark@google.com            wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY);
1939a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    if (pts == 2) {
1940a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com        SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
1941a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com    }
1942a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com}
1943a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com#else
1944a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.comstatic void debugShowLineIntersection(int , const WorkEdge& ,
1945a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        const WorkEdge& , const double [2], const double [2]) {
1946a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com}
1947a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com#endif
1948a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com
1949f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) {
1950cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    InEdge** testPtr = currentPtr - 1;
1951752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    // FIXME: lastPtr should be past the point of interest, so
1952752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    // test below should be  lastPtr - 2
1953752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com    // that breaks testSimplifyTriangle22, so further investigation is needed
1954cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com    while (++testPtr != lastPtr - 1) {
1955cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        InEdge* test = *testPtr;
1956cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        InEdge** nextPtr = testPtr;
1957cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        do {
1958cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            InEdge* next = *++nextPtr;
1959198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            // FIXME: this compares against the sentinel sometimes
1960198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            // OPTIMIZATION: this may never be needed since this gets called
1961198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com            // in two passes now. Verify that double hits are appropriate.
1962cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            if (test->cached(next)) {
1963cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                continue;
1964cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            }
1965cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            if (!Bounds::Intersects(test->fBounds, next->fBounds)) {
1966cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com                continue;
1967cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            }
1968f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            WorkEdge wt, wn;
1969f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            wt.init(test);
1970f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            wn.init(next);
1971f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            do {
1972a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                int pts;
1973a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                Intersections ts;
1974a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                bool swap = false;
1975a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                switch (wt.verb()) {
1976a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kLine_Verb:
1977a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        switch (wn.verb()) {
1978a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kLine_Verb: {
1979a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = LineIntersect(wt.fPts, wn.fPts, ts);
1980a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                debugShowLineIntersection(pts, wt, wn,
1981a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                        ts.fT[0], ts.fT[1]);
1982a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
1983a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
1984a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kQuad_Verb: {
1985a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                swap = true;
1986a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = QuadLineIntersect(wn.fPts, wt.fPts, ts);
1987a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
1988a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
1989a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kCubic_Verb: {
1990a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                swap = true;
1991a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = CubicLineIntersect(wn.fPts, wt.fPts, ts);
1992a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
1993a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
1994a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            default:
1995a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                SkASSERT(0);
19962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                        }
1997a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
1998a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kQuad_Verb:
1999a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        switch (wn.verb()) {
2000a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kLine_Verb: {
2001a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = QuadLineIntersect(wt.fPts, wn.fPts, ts);
2002a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2003a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2004a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kQuad_Verb: {
2005a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = QuadIntersect(wt.fPts, wn.fPts, ts);
2006a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2007a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2008a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kCubic_Verb: {
2009a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                // FIXME: promote quad to cubic
2010a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2011a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2012a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2013a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            default:
2014a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                SkASSERT(0);
20152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                        }
2016a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
2017a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kCubic_Verb:
2018a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        switch (wn.verb()) {
2019a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kLine_Verb: {
2020a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = CubicLineIntersect(wt.fPts, wn.fPts, ts);
2021a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2022a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2023a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kQuad_Verb: {
2024a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                 // FIXME: promote quad to cubic
2025a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2026a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2027a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2028a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            case SkPath::kCubic_Verb: {
2029a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2030a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                break;
2031a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            }
2032a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                            default:
2033a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                                SkASSERT(0);
2034a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        }
2035a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
2036a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    default:
2037a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        SkASSERT(0);
2038f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                }
2039a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                test->add(ts.fT[swap], pts, wt.verbIndex());
2040a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                next->add(ts.fT[!swap], pts, wn.verbIndex());
2041cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com            } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance());
2042cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        } while (nextPtr != lastPtr);
2043f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
2044f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}
2045f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
20462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges,
20476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        InEdge** currentPtr, InEdge** lastPtr,  SkScalar y) {
20486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    InEdge** testPtr = currentPtr - 1;
20496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    while (++testPtr != lastPtr) {
20506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        if ((*testPtr)->fBounds.fBottom > y) {
20516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            continue;
20526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        }
20532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        if (activeEdges) {
20542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            InEdge* test = *testPtr;
20552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            ActiveEdge* activePtr = activeEdges->begin() - 1;
20562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            ActiveEdge* lastActive = activeEdges->end();
20572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com            while (++activePtr != lastActive) {
20582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                if (activePtr->fWorkEdge.fEdge == test) {
20592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    activeEdges->remove(activePtr - activeEdges->begin());
20602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                    break;
20612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com                }
20626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            }
20636008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        }
20646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        if (testPtr == currentPtr) {
20656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com            ++currentPtr;
20666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com        }
20676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    }
20686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com    return currentPtr;
20696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com}
20706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com
20712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZE: inline?
20722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) {
20732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    while ((*edge)->fY < y) {
20742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        ++edge;
20752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    }
20762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    return edge;
20772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}
20782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com
2079f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// compute bottom taking into account any intersected edges
20802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges,
20812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        SkScalar y, SkScalar bottom) {
2082f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    ActiveEdge* activePtr = activeEdges.begin() - 1;
2083f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    ActiveEdge* lastActive = activeEdges.end();
2084f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    while (++activePtr != lastActive) {
2085f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        const InEdge* test = activePtr->fWorkEdge.fEdge;
2086f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        if (!test->fContainsIntercepts) {
2087f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            continue;
2088f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        }
2089f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        WorkEdge wt;
2090f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        wt.init(test);
2091f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com        do {
2092f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()];
20934917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            if (intercepts.fTopIntercepts > 1) {
20944917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                SkScalar yTop = wt.fPts[0].fY;
20954917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                if (yTop > y && bottom > yTop) {
20964917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    bottom = yTop;
20974917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                }
20984917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            }
20994917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            if (intercepts.fBottomIntercepts > 1) {
21004917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                SkScalar yBottom = wt.fPts[wt.verb()].fY;
21014917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                if (yBottom > y && bottom > yBottom) {
21024917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                    bottom = yBottom;
21034917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com                }
21044917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com            }
2105f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            const SkTDArray<double>& fTs = intercepts.fTs;
2106f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            size_t count = fTs.count();
2107f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            for (size_t index = 0; index < count; ++index) {
2108a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                SkScalar yIntercept;
2109a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                switch (wt.verb()) {
2110a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kLine_Verb: {
2111a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        yIntercept = LineYAtT(wt.fPts, fTs[index]);
2112a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
2113f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                    }
2114a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kQuad_Verb: {
2115a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        yIntercept = QuadYAtT(wt.fPts, fTs[index]);
2116a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
2117a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
2118a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    case SkPath::kCubic_Verb: {
2119a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        yIntercept = CubicYAtT(wt.fPts, fTs[index]);
2120a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        break;
2121a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    }
2122a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    default:
2123a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                        SkASSERT(0); // should never get here
2124a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                }
2125a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                if (yIntercept > y && bottom > yIntercept) {
2126a5764233aa6b207c4169fff7fccae567a160a0fdcaryclark@google.com                    bottom = yIntercept;
2127f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com                }
2128f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com            }
2129cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com        } while (wt.advance());
2130f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    }
2131198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#if DEBUG_BOTTOM
2132198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com    SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom);
2133198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#endif
21342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com    return bottom;
2135f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}
2136f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com
2137d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.comstatic SkScalar findBottom(InEdge** currentPtr,
21382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com        InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y,
2139a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com        bool /*asFill*/, InEdge**& testPtr) {
2140f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com    InEdge* current = *currentPtr;
2141f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com