blob: 4442e9226a0104212c51643120fe4f4f6631150f [file] [log] [blame]
caryclark@google.comc6825902012-02-03 22:07:47 +00001/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
caryclark@google.com8dcf1142012-07-02 20:27:02 +00008#include "Simplify.h"
caryclark@google.comc6825902012-02-03 22:07:47 +00009
caryclark@google.com78e17132012-04-17 11:40:34 +000010#undef SkASSERT
11#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000012
caryclark@google.com78e17132012-04-17 11:40:34 +000013// FIXME: remove once debugging is complete
caryclark@google.comfa0588f2012-04-26 21:01:06 +000014#if 01 // set to 1 for no debugging whatsoever
caryclark@google.com78e17132012-04-17 11:40:34 +000015
caryclark@google.com47580692012-07-23 12:14:49 +000016//const bool gRunTestsInOneThread = false;
caryclark@google.com78e17132012-04-17 11:40:34 +000017
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000018#define DEBUG_ACTIVE_LESS_THAN 0
caryclark@google.com78e17132012-04-17 11:40:34 +000019#define DEBUG_ADD 0
20#define DEBUG_ADD_BOTTOM_TS 0
21#define DEBUG_ADD_INTERSECTING_TS 0
22#define DEBUG_ADJUST_COINCIDENT 0
caryclark@google.comfb173422012-04-10 18:28:55 +000023#define DEBUG_ASSEMBLE 0
caryclark@google.com78e17132012-04-17 11:40:34 +000024#define DEBUG_BOTTOM 0
caryclark@google.comfb173422012-04-10 18:28:55 +000025#define DEBUG_BRIDGE 0
caryclark@google.com78e17132012-04-17 11:40:34 +000026#define DEBUG_DUMP 0
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000027#define DEBUG_SORT_HORIZONTAL 0
28#define DEBUG_OUT 0
29#define DEBUG_OUT_LESS_THAN 0
caryclark@google.com198e0542012-03-30 18:47:02 +000030#define DEBUG_SPLIT 0
caryclark@google.comfb173422012-04-10 18:28:55 +000031#define DEBUG_STITCH_EDGE 0
caryclark@google.com78e17132012-04-17 11:40:34 +000032#define DEBUG_TRIM_LINE 0
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000033
caryclark@google.com78e17132012-04-17 11:40:34 +000034#else
35
caryclark@google.com47580692012-07-23 12:14:49 +000036//const bool gRunTestsInOneThread = true;
caryclark@google.com78e17132012-04-17 11:40:34 +000037
caryclark@google.coma5764232012-03-28 16:20:21 +000038#define DEBUG_ACTIVE_LESS_THAN 0
caryclark@google.com78e17132012-04-17 11:40:34 +000039#define DEBUG_ADD 01
40#define DEBUG_ADD_BOTTOM_TS 0
41#define DEBUG_ADD_INTERSECTING_TS 0
42#define DEBUG_ADJUST_COINCIDENT 1
caryclark@google.comfb173422012-04-10 18:28:55 +000043#define DEBUG_ASSEMBLE 1
caryclark@google.com78e17132012-04-17 11:40:34 +000044#define DEBUG_BOTTOM 0
caryclark@google.comfb173422012-04-10 18:28:55 +000045#define DEBUG_BRIDGE 1
caryclark@google.com78e17132012-04-17 11:40:34 +000046#define DEBUG_DUMP 1
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000047#define DEBUG_SORT_HORIZONTAL 01
48#define DEBUG_OUT 01
49#define DEBUG_OUT_LESS_THAN 0
caryclark@google.com198e0542012-03-30 18:47:02 +000050#define DEBUG_SPLIT 1
caryclark@google.comfb173422012-04-10 18:28:55 +000051#define DEBUG_STITCH_EDGE 1
caryclark@google.com78e17132012-04-17 11:40:34 +000052#define DEBUG_TRIM_LINE 1
caryclark@google.com752b60e2012-03-22 21:11:17 +000053
caryclark@google.com2e7f4c82012-03-20 21:11:59 +000054#endif
55
caryclark@google.comfb173422012-04-10 18:28:55 +000056#if DEBUG_ASSEMBLE || DEBUG_BRIDGE
57static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
58#endif
59#if DEBUG_STITCH_EDGE
60static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
61#endif
62
caryclark@google.com6680fb12012-02-07 22:10:51 +000063static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
caryclark@google.coma5764232012-03-28 16:20:21 +000064 Intersections& intersections) {
65 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
66 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
67 return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
68}
69
70static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
71 Intersections& intersections) {
72 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
73 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
caryclark@google.com198e0542012-03-30 18:47:02 +000074 intersect(aQuad, bLine, intersections);
75 return intersections.fUsed;
caryclark@google.coma5764232012-03-28 16:20:21 +000076}
77
78static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
79 Intersections& intersections) {
80 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
81 {a[3].fX, a[3].fY}};
82 const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
caryclark@google.com198e0542012-03-30 18:47:02 +000083 return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
caryclark@google.coma5764232012-03-28 16:20:21 +000084}
85
86static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
87 Intersections& intersections) {
88 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
89 const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
caryclark@google.com198e0542012-03-30 18:47:02 +000090 intersect(aQuad, bQuad, intersections);
91 return intersections.fUsed;
caryclark@google.coma5764232012-03-28 16:20:21 +000092}
93
94static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
95 Intersections& intersections) {
96 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
97 {a[3].fX, a[3].fY}};
98 const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
99 {b[3].fX, b[3].fY}};
caryclark@google.com198e0542012-03-30 18:47:02 +0000100 intersect(aCubic, bCubic, intersections);
101 return intersections.fUsed;
caryclark@google.comc6825902012-02-03 22:07:47 +0000102}
103
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000104static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
105 SkScalar y, double aRange[2]) {
caryclark@google.coma5764232012-03-28 16:20:21 +0000106 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000107 return horizontalLineIntersect(aLine, left, right, y, aRange);
caryclark@google.comc6825902012-02-03 22:07:47 +0000108}
109
caryclark@google.com198e0542012-03-30 18:47:02 +0000110static int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
111 SkScalar y, double aRange[3]) {
112 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
113 return horizontalIntersect(aQuad, left, right, y, aRange);
114}
115
116static int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
117 SkScalar y, double aRange[4]) {
118 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
119 {a[3].fX, a[3].fY}};
120 return horizontalIntersect(aCubic, left, right, y, aRange);
121}
122
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000123static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
caryclark@google.coma5764232012-03-28 16:20:21 +0000124 const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000125 double x, y;
caryclark@google.coma5764232012-03-28 16:20:21 +0000126 xy_at_t(line, t, x, y);
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000127 out->fX = SkDoubleToScalar(x);
128 out->fY = SkDoubleToScalar(y);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000129}
130
caryclark@google.coma5764232012-03-28 16:20:21 +0000131static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
132 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
133 double x, y;
134 xy_at_t(quad, t, x, y);
135 out->fX = SkDoubleToScalar(x);
136 out->fY = SkDoubleToScalar(y);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000137}
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000138
caryclark@google.coma5764232012-03-28 16:20:21 +0000139static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
140 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
141 {a[3].fX, a[3].fY}};
142 double x, y;
143 xy_at_t(cubic, t, x, y);
144 out->fX = SkDoubleToScalar(x);
145 out->fY = SkDoubleToScalar(y);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000146}
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000147
caryclark@google.com6680fb12012-02-07 22:10:51 +0000148static SkScalar LineYAtT(const SkPoint a[2], double t) {
caryclark@google.coma5764232012-03-28 16:20:21 +0000149 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
caryclark@google.com6680fb12012-02-07 22:10:51 +0000150 double y;
151 xy_at_t(aLine, t, *(double*) 0, y);
152 return SkDoubleToScalar(y);
153}
154
caryclark@google.coma5764232012-03-28 16:20:21 +0000155static SkScalar QuadYAtT(const SkPoint a[3], double t) {
156 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
157 double y;
158 xy_at_t(quad, t, *(double*) 0, y);
159 return SkDoubleToScalar(y);
160}
161
162static SkScalar CubicYAtT(const SkPoint a[4], double t) {
163 const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
164 {a[3].fX, a[3].fY}};
165 double y;
166 xy_at_t(cubic, t, *(double*) 0, y);
167 return SkDoubleToScalar(y);
168}
169
caryclark@google.com6680fb12012-02-07 22:10:51 +0000170static void LineSubDivide(const SkPoint a[2], double startT, double endT,
171 SkPoint sub[2]) {
caryclark@google.coma5764232012-03-28 16:20:21 +0000172 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
caryclark@google.com6680fb12012-02-07 22:10:51 +0000173 _Line dst;
174 sub_divide(aLine, startT, endT, dst);
175 sub[0].fX = SkDoubleToScalar(dst[0].x);
176 sub[0].fY = SkDoubleToScalar(dst[0].y);
177 sub[1].fX = SkDoubleToScalar(dst[1].x);
178 sub[1].fY = SkDoubleToScalar(dst[1].y);
179}
180
caryclark@google.coma5764232012-03-28 16:20:21 +0000181static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
182 SkPoint sub[3]) {
caryclark@google.com78e17132012-04-17 11:40:34 +0000183 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
184 {a[2].fX, a[2].fY}};
caryclark@google.coma5764232012-03-28 16:20:21 +0000185 Quadratic dst;
186 sub_divide(aQuad, startT, endT, dst);
187 sub[0].fX = SkDoubleToScalar(dst[0].x);
188 sub[0].fY = SkDoubleToScalar(dst[0].y);
189 sub[1].fX = SkDoubleToScalar(dst[1].x);
190 sub[1].fY = SkDoubleToScalar(dst[1].y);
191 sub[2].fX = SkDoubleToScalar(dst[2].x);
192 sub[2].fY = SkDoubleToScalar(dst[2].y);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000193}
caryclark@google.com6680fb12012-02-07 22:10:51 +0000194
caryclark@google.coma5764232012-03-28 16:20:21 +0000195static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
196 SkPoint sub[4]) {
caryclark@google.com78e17132012-04-17 11:40:34 +0000197 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
198 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
caryclark@google.coma5764232012-03-28 16:20:21 +0000199 Cubic dst;
200 sub_divide(aCubic, startT, endT, dst);
201 sub[0].fX = SkDoubleToScalar(dst[0].x);
202 sub[0].fY = SkDoubleToScalar(dst[0].y);
203 sub[1].fX = SkDoubleToScalar(dst[1].x);
204 sub[1].fY = SkDoubleToScalar(dst[1].y);
205 sub[2].fX = SkDoubleToScalar(dst[2].x);
206 sub[2].fY = SkDoubleToScalar(dst[2].y);
207 sub[3].fX = SkDoubleToScalar(dst[3].x);
208 sub[3].fY = SkDoubleToScalar(dst[3].y);
209}
caryclark@google.comfb173422012-04-10 18:28:55 +0000210
211static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
212 SkRect& bounds) {
213 SkPoint dst[3];
214 QuadSubDivide(a, startT, endT, dst);
215 bounds.fLeft = bounds.fRight = dst[0].fX;
216 bounds.fTop = bounds.fBottom = dst[0].fY;
217 for (int index = 1; index < 3; ++index) {
218 bounds.growToInclude(dst[index].fX, dst[index].fY);
219 }
220}
221
222static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
223 SkRect& bounds) {
224 SkPoint dst[4];
225 CubicSubDivide(a, startT, endT, dst);
226 bounds.fLeft = bounds.fRight = dst[0].fX;
227 bounds.fTop = bounds.fBottom = dst[0].fY;
228 for (int index = 1; index < 4; ++index) {
229 bounds.growToInclude(dst[index].fX, dst[index].fY);
230 }
231}
232
caryclark@google.com78e17132012-04-17 11:40:34 +0000233static SkPath::Verb QuadReduceOrder(SkPoint a[4]) {
234 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
235 {a[2].fX, a[2].fY}};
236 Quadratic dst;
237 int order = reduceOrder(aQuad, dst);
238 for (int index = 0; index < order; ++index) {
239 a[index].fX = SkDoubleToScalar(dst[index].x);
240 a[index].fY = SkDoubleToScalar(dst[index].y);
241 }
242 if (order == 1) { // FIXME: allow returning points, caller should discard
243 a[1] = a[0];
244 return (SkPath::Verb) order;
245 }
246 return (SkPath::Verb) (order - 1);
247}
248
249static SkPath::Verb CubicReduceOrder(SkPoint a[4]) {
250 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
251 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
252 Cubic dst;
253 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
254 for (int index = 0; index < order; ++index) {
255 a[index].fX = SkDoubleToScalar(dst[index].x);
256 a[index].fY = SkDoubleToScalar(dst[index].y);
257 }
258 if (order == 1) { // FIXME: allow returning points, caller should discard
259 a[1] = a[0];
260 return (SkPath::Verb) order;
261 }
262 return (SkPath::Verb) (order - 1);
263}
264
265static bool IsCoincident(const SkPoint a[2], const SkPoint& above,
266 const SkPoint& below) {
267 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
268 const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}};
269 return implicit_matches_ulps(aLine, bLine, 32);
270}
271
caryclark@google.comc6825902012-02-03 22:07:47 +0000272/*
273list of edges
274bounds for edge
275sort
276active T
277
278if a contour's bounds is outside of the active area, no need to create edges
279*/
280
281/* given one or more paths,
282 find the bounds of each contour, select the active contours
283 for each active contour, compute a set of edges
284 each edge corresponds to one or more lines and curves
285 leave edges unbroken as long as possible
286 when breaking edges, compute the t at the break but leave the control points alone
287
288 */
289
290void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) {
291 SkPath::Iter iter(path, false);
292 SkPoint pts[4];
293 SkPath::Verb verb;
294 SkRect bounds;
295 bounds.setEmpty();
296 int count = 0;
297 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
298 switch (verb) {
299 case SkPath::kMove_Verb:
300 if (!bounds.isEmpty()) {
301 *boundsArray.append() = bounds;
302 }
303 bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
304 count = 0;
305 break;
306 case SkPath::kLine_Verb:
307 count = 1;
308 break;
309 case SkPath::kQuad_Verb:
310 count = 2;
311 break;
312 case SkPath::kCubic_Verb:
313 count = 3;
314 break;
315 case SkPath::kClose_Verb:
316 count = 0;
317 break;
318 default:
319 SkDEBUGFAIL("bad verb");
320 return;
321 }
322 for (int i = 1; i <= count; ++i) {
323 bounds.growToInclude(pts[i].fX, pts[i].fY);
324 }
325 }
326}
327
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000328static bool extendLine(const SkPoint line[2], const SkPoint& add) {
329 // FIXME: allow this to extend lines that have slopes that are nearly equal
330 SkScalar dx1 = line[1].fX - line[0].fX;
331 SkScalar dy1 = line[1].fY - line[0].fY;
332 SkScalar dx2 = add.fX - line[0].fX;
333 SkScalar dy2 = add.fY - line[0].fY;
334 return dx1 * dy2 == dx2 * dy1;
335}
caryclark@google.com6680fb12012-02-07 22:10:51 +0000336
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000337// OPTIMIZATION: this should point to a list of input data rather than duplicating
338// the line data here. This would reduce the need to assemble the results.
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000339struct OutEdge {
340 bool operator<(const OutEdge& rh) const {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000341 const SkPoint& first = fPts[0];
342 const SkPoint& rhFirst = rh.fPts[0];
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000343 return first.fY == rhFirst.fY
344 ? first.fX < rhFirst.fX
345 : first.fY < rhFirst.fY;
346 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000347
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000348 SkPoint fPts[4];
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000349 int fID; // id of edge generating data
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000350 uint8_t fVerb; // FIXME: not read from everywhere
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000351 bool fCloseCall; // edge is trimmable if not originally coincident
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000352};
353
caryclark@google.com6680fb12012-02-07 22:10:51 +0000354class OutEdgeBuilder {
355public:
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000356 OutEdgeBuilder(bool fill)
357 : fFill(fill) {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000358 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000359
caryclark@google.coma5764232012-03-28 16:20:21 +0000360 void addCurve(const SkPoint line[4], SkPath::Verb verb, int id,
361 bool closeCall) {
caryclark@google.comc17972e2012-02-20 21:33:22 +0000362 OutEdge& newEdge = fEdges.push_back();
caryclark@google.coma5764232012-03-28 16:20:21 +0000363 memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint));
364 newEdge.fVerb = verb;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000365 newEdge.fID = id;
366 newEdge.fCloseCall = closeCall;
367 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000368
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000369 bool trimLine(SkScalar y, int id) {
370 size_t count = fEdges.count();
371 while (count-- != 0) {
372 OutEdge& edge = fEdges[count];
373 if (edge.fID != id) {
374 continue;
375 }
376 if (edge.fCloseCall) {
377 return false;
378 }
379 SkASSERT(edge.fPts[0].fY <= y);
380 if (edge.fPts[1].fY <= y) {
381 continue;
382 }
383 edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY)
384 * (edge.fPts[1].fX - edge.fPts[0].fX)
385 / (edge.fPts[1].fY - edge.fPts[0].fY);
386 edge.fPts[1].fY = y;
caryclark@google.com78e17132012-04-17 11:40:34 +0000387#if DEBUG_TRIM_LINE
388 SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id,
389 edge.fPts[1].fX, y);
390#endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000391 return true;
392 }
393 return false;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000394 }
395
396 void assemble(SkPath& simple) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000397 size_t listCount = fEdges.count();
398 if (listCount == 0) {
399 return;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000400 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000401 do {
402 size_t listIndex = 0;
403 int advance = 1;
404 while (listIndex < listCount && fTops[listIndex] == 0) {
405 ++listIndex;
406 }
407 if (listIndex >= listCount) {
408 break;
409 }
caryclark@google.com4917f172012-03-05 22:01:21 +0000410 int closeEdgeIndex = -listIndex - 1;
caryclark@google.comfb173422012-04-10 18:28:55 +0000411 // the curve is deferred and not added right away because the
412 // following edge may extend the first curve.
caryclark@google.coma5764232012-03-28 16:20:21 +0000413 SkPoint firstPt, lastCurve[4];
414 uint8_t lastVerb;
caryclark@google.comfb173422012-04-10 18:28:55 +0000415#if DEBUG_ASSEMBLE
416 int firstIndex, lastIndex;
417 const int tab = 8;
418#endif
caryclark@google.com6008c6562012-02-15 22:01:16 +0000419 bool doMove = true;
420 int edgeIndex;
421 do {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000422 SkPoint* ptArray = fEdges[listIndex].fPts;
423 uint8_t verb = fEdges[listIndex].fVerb;
caryclark@google.comfb173422012-04-10 18:28:55 +0000424 SkPoint* curve[4];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000425 if (advance < 0) {
caryclark@google.comfb173422012-04-10 18:28:55 +0000426 curve[0] = &ptArray[verb];
427 if (verb == SkPath::kCubic_Verb) {
428 curve[1] = &ptArray[2];
429 curve[2] = &ptArray[1];
430 }
431 curve[verb] = &ptArray[0];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000432 } else {
caryclark@google.comfb173422012-04-10 18:28:55 +0000433 curve[0] = &ptArray[0];
434 if (verb == SkPath::kCubic_Verb) {
435 curve[1] = &ptArray[1];
436 curve[2] = &ptArray[2];
437 }
438 curve[verb] = &ptArray[verb];
439 }
440 if (verb == SkPath::kQuad_Verb) {
441 curve[1] = &ptArray[1];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000442 }
caryclark@google.coma5764232012-03-28 16:20:21 +0000443 if (doMove) {
caryclark@google.comfb173422012-04-10 18:28:55 +0000444 firstPt = *curve[0];
445 simple.moveTo(curve[0]->fX, curve[0]->fY);
446#if DEBUG_ASSEMBLE
447 SkDebugf("%s %d moveTo (%g,%g)\n", __FUNCTION__,
448 listIndex + 1, curve[0]->fX, curve[0]->fY);
449 firstIndex = listIndex;
450#endif
451 for (int index = 0; index <= verb; ++index) {
452 lastCurve[index] = *curve[index];
caryclark@google.coma5764232012-03-28 16:20:21 +0000453 }
caryclark@google.coma5764232012-03-28 16:20:21 +0000454 doMove = false;
455 } else {
caryclark@google.comfb173422012-04-10 18:28:55 +0000456 bool gap = lastCurve[lastVerb] != *curve[0];
457 if (gap || lastVerb != SkPath::kLine_Verb) { // output the accumulated curve before the gap
caryclark@google.coma5764232012-03-28 16:20:21 +0000458 // FIXME: see comment in bridge -- this probably
459 // conceals errors
caryclark@google.comfb173422012-04-10 18:28:55 +0000460 SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY,
461 curve[0]->fY) <= 10);
caryclark@google.coma5764232012-03-28 16:20:21 +0000462 switch (lastVerb) {
463 case SkPath::kLine_Verb:
464 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
465 break;
466 case SkPath::kQuad_Verb:
467 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
468 lastCurve[2].fX, lastCurve[2].fY);
469 break;
470 case SkPath::kCubic_Verb:
471 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
472 lastCurve[2].fX, lastCurve[2].fY,
473 lastCurve[3].fX, lastCurve[3].fY);
474 break;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000475 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000476#if DEBUG_ASSEMBLE
477 SkDebugf("%*s %d %sTo (%g,%g)\n", tab, "", lastIndex + 1,
478 kLVerbStr[lastVerb], lastCurve[lastVerb].fX,
479 lastCurve[lastVerb].fY);
480#endif
caryclark@google.coma5764232012-03-28 16:20:21 +0000481 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000482 int firstCopy = 1;
caryclark@google.com78e17132012-04-17 11:40:34 +0000483 if (gap || (lastVerb == SkPath::kLine_Verb
484 && (verb != SkPath::kLine_Verb
485 || !extendLine(lastCurve, *curve[verb])))) {
caryclark@google.coma5764232012-03-28 16:20:21 +0000486 // FIXME: see comment in bridge -- this probably
487 // conceals errors
caryclark@google.comfb173422012-04-10 18:28:55 +0000488 SkASSERT(lastCurve[lastVerb] == *curve[0] ||
489 (fFill && UlpsDiff(lastCurve[lastVerb].fY,
490 curve[0]->fY) <= 10));
491 simple.lineTo(curve[0]->fX, curve[0]->fY);
492#if DEBUG_ASSEMBLE
493 SkDebugf("%*s %d gap lineTo (%g,%g)\n", tab, "",
494 lastIndex + 1, curve[0]->fX, curve[0]->fY);
495#endif
496 firstCopy = 0;
497 } else if (lastVerb != SkPath::kLine_Verb) {
498 firstCopy = 0;
caryclark@google.coma5764232012-03-28 16:20:21 +0000499 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000500 for (int index = firstCopy; index <= verb; ++index) {
501 lastCurve[index] = *curve[index];
caryclark@google.coma5764232012-03-28 16:20:21 +0000502 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000503 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000504 lastVerb = verb;
505#if DEBUG_ASSEMBLE
506 lastIndex = listIndex;
507#endif
caryclark@google.com6008c6562012-02-15 22:01:16 +0000508 if (advance < 0) {
509 edgeIndex = fTops[listIndex];
510 fTops[listIndex] = 0;
caryclark@google.comfb173422012-04-10 18:28:55 +0000511 } else {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000512 edgeIndex = fBottoms[listIndex];
513 fBottoms[listIndex] = 0;
514 }
caryclark@google.com4917f172012-03-05 22:01:21 +0000515 if (edgeIndex) {
516 listIndex = abs(edgeIndex) - 1;
517 if (edgeIndex < 0) {
518 fTops[listIndex] = 0;
519 } else {
520 fBottoms[listIndex] = 0;
521 }
522 }
523 if (edgeIndex == closeEdgeIndex || edgeIndex == 0) {
caryclark@google.comfb173422012-04-10 18:28:55 +0000524 switch (lastVerb) {
525 case SkPath::kLine_Verb:
526 simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
527 break;
528 case SkPath::kQuad_Verb:
529 simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
530 lastCurve[2].fX, lastCurve[2].fY);
531 break;
532 case SkPath::kCubic_Verb:
533 simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
534 lastCurve[2].fX, lastCurve[2].fY,
535 lastCurve[3].fX, lastCurve[3].fY);
536 break;
537 }
538#if DEBUG_ASSEMBLE
539 SkDebugf("%*s %d %sTo last (%g, %g)\n", tab, "",
540 lastIndex + 1, kLVerbStr[lastVerb],
541 lastCurve[lastVerb].fX, lastCurve[lastVerb].fY);
542#endif
caryclark@google.coma5764232012-03-28 16:20:21 +0000543 if (lastCurve[lastVerb] != firstPt) {
caryclark@google.comfb173422012-04-10 18:28:55 +0000544 simple.lineTo(firstPt.fX, firstPt.fY);
545#if DEBUG_ASSEMBLE
546 SkDebugf("%*s %d final line (%g, %g)\n", tab, "",
547 firstIndex + 1, firstPt.fX, firstPt.fY);
548#endif
caryclark@google.com4917f172012-03-05 22:01:21 +0000549 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000550 simple.close();
caryclark@google.comfb173422012-04-10 18:28:55 +0000551#if DEBUG_ASSEMBLE
552 SkDebugf("%*s close\n", tab, "");
553#endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000554 break;
555 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000556 // if this and next edge go different directions
557#if DEBUG_ASSEMBLE
558 SkDebugf("%*s advance=%d edgeIndex=%d flip=%s\n", tab, "",
559 advance, edgeIndex, advance > 0 ^ edgeIndex < 0 ?
560 "true" : "false");
561#endif
caryclark@google.com6008c6562012-02-15 22:01:16 +0000562 if (advance > 0 ^ edgeIndex < 0) {
563 advance = -advance;
564 }
caryclark@google.com4917f172012-03-05 22:01:21 +0000565 } while (edgeIndex);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000566 } while (true);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000567 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000568
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000569 // sort points by y, then x
570 // if x/y is identical, sort bottoms before tops
571 // if identical and both tops/bottoms, sort by angle
572 static bool lessThan(SkTArray<OutEdge>& edges, const int one,
573 const int two) {
574 const OutEdge& oneEdge = edges[abs(one) - 1];
575 int oneIndex = one < 0 ? 0 : oneEdge.fVerb;
576 const SkPoint& startPt1 = oneEdge.fPts[oneIndex];
577 const OutEdge& twoEdge = edges[abs(two) - 1];
578 int twoIndex = two < 0 ? 0 : twoEdge.fVerb;
579 const SkPoint& startPt2 = twoEdge.fPts[twoIndex];
580 if (startPt1.fY != startPt2.fY) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000581 #if DEBUG_OUT_LESS_THAN
582 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__,
583 one, two, startPt1.fY, startPt2.fY,
584 startPt1.fY < startPt2.fY ? "true" : "false");
585 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000586 return startPt1.fY < startPt2.fY;
587 }
588 if (startPt1.fX != startPt2.fX) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000589 #if DEBUG_OUT_LESS_THAN
590 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__,
591 one, two, startPt1.fX, startPt2.fX,
592 startPt1.fX < startPt2.fX ? "true" : "false");
593 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000594 return startPt1.fX < startPt2.fX;
595 }
596 const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb];
597 const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb];
598 SkScalar dy1 = startPt1.fY - endPt1.fY;
599 SkScalar dy2 = startPt2.fY - endPt2.fY;
600 SkScalar dy1y2 = dy1 * dy2;
601 if (dy1y2 < 0) { // different signs
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000602 #if DEBUG_OUT_LESS_THAN
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000603 SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two,
604 dy1 > 0 ? "true" : "false");
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000605 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000606 return dy1 > 0; // one < two if one goes up and two goes down
607 }
608 if (dy1y2 == 0) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000609 #if DEBUG_OUT_LESS_THAN
610 SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__,
611 one, two, endPt1.fX < endPt2.fX ? "true" : "false");
612 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000613 return endPt1.fX < endPt2.fX;
614 }
615 SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2;
616 SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000617 #if DEBUG_OUT_LESS_THAN
618 SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__,
619 one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false");
620 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000621 return dy2 > 0 ^ dx1y2 < dx2y1;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000622 }
623
caryclark@google.com6008c6562012-02-15 22:01:16 +0000624 // Sort the indices of paired points and then create more indices so
625 // assemble() can find the next edge and connect the top or bottom
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000626 void bridge() {
627 size_t index;
628 size_t count = fEdges.count();
629 if (!count) {
630 return;
631 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000632 SkASSERT(!fFill || count > 1);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000633 fTops.setCount(count);
634 sk_bzero(fTops.begin(), sizeof(fTops[0]) * count);
635 fBottoms.setCount(count);
636 sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000637 SkTDArray<int> order;
638 for (index = 1; index <= count; ++index) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000639 *order.append() = -index;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000640 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000641 for (index = 1; index <= count; ++index) {
642 *order.append() = index;
643 }
644 QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000645 int* lastPtr = order.end() - 1;
646 int* leftPtr = order.begin();
647 while (leftPtr < lastPtr) {
648 int leftIndex = *leftPtr;
649 int leftOutIndex = abs(leftIndex) - 1;
650 const OutEdge& left = fEdges[leftOutIndex];
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000651 int* rightPtr = leftPtr + 1;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000652 int rightIndex = *rightPtr;
653 int rightOutIndex = abs(rightIndex) - 1;
654 const OutEdge& right = fEdges[rightOutIndex];
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000655 bool pairUp = fFill;
656 if (!pairUp) {
657 const SkPoint& leftMatch =
658 left.fPts[leftIndex < 0 ? 0 : left.fVerb];
659 const SkPoint& rightMatch =
660 right.fPts[rightIndex < 0 ? 0 : right.fVerb];
661 pairUp = leftMatch == rightMatch;
662 } else {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000663 #if DEBUG_OUT
caryclark@google.comd88e0892012-03-27 13:23:51 +0000664 // FIXME : not happy that error in low bit is allowed
665 // this probably conceals error elsewhere
666 if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,
667 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000668 *fMismatches.append() = leftIndex;
669 if (rightPtr == lastPtr) {
670 *fMismatches.append() = rightIndex;
671 }
672 pairUp = false;
673 }
674 #else
caryclark@google.comd88e0892012-03-27 13:23:51 +0000675 SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY,
676 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000677 #endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000678 }
679 if (pairUp) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000680 if (leftIndex < 0) {
681 fTops[leftOutIndex] = rightIndex;
682 } else {
683 fBottoms[leftOutIndex] = rightIndex;
684 }
685 if (rightIndex < 0) {
686 fTops[rightOutIndex] = leftIndex;
687 } else {
688 fBottoms[rightOutIndex] = leftIndex;
689 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000690 ++rightPtr;
691 }
692 leftPtr = rightPtr;
693 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000694#if DEBUG_OUT
695 int* mismatch = fMismatches.begin();
696 while (mismatch != fMismatches.end()) {
697 int leftIndex = *mismatch++;
698 int leftOutIndex = abs(leftIndex) - 1;
699 const OutEdge& left = fEdges[leftOutIndex];
700 const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb];
701 SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n",
702 __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot",
703 leftPt.fX, leftPt.fY);
704 }
705 SkASSERT(fMismatches.count() == 0);
706#endif
caryclark@google.comfb173422012-04-10 18:28:55 +0000707#if DEBUG_BRIDGE
708 for (index = 0; index < count; ++index) {
709 const OutEdge& edge = fEdges[index];
710 uint8_t verb = edge.fVerb;
711 SkDebugf("%s %d edge=%d %s (%1.9g,%1.9g) (%1.9g,%1.9g)\n",
712 index == 0 ? __FUNCTION__ : " ",
713 index + 1, edge.fID, kLVerbStr[verb], edge.fPts[0].fX,
714 edge.fPts[0].fY, edge.fPts[verb].fX, edge.fPts[verb].fY);
715 }
716 for (index = 0; index < count; ++index) {
717 SkDebugf(" top of % 2d connects to %s of % 2d\n", index + 1,
718 fTops[index] < 0 ? "top " : "bottom", abs(fTops[index]));
719 SkDebugf(" bottom of % 2d connects to %s of % 2d\n", index + 1,
720 fBottoms[index] < 0 ? "top " : "bottom", abs(fBottoms[index]));
721 }
722#endif
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000723 }
724
caryclark@google.com6008c6562012-02-15 22:01:16 +0000725protected:
caryclark@google.com6680fb12012-02-07 22:10:51 +0000726 SkTArray<OutEdge> fEdges;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000727 SkTDArray<int> fTops;
728 SkTDArray<int> fBottoms;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000729 bool fFill;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000730#if DEBUG_OUT
731 SkTDArray<int> fMismatches;
732#endif
caryclark@google.com6680fb12012-02-07 22:10:51 +0000733};
734
caryclark@google.comc6825902012-02-03 22:07:47 +0000735// Bounds, unlike Rect, does not consider a vertical line to be empty.
736struct Bounds : public SkRect {
737 static bool Intersects(const Bounds& a, const Bounds& b) {
738 return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
739 a.fTop <= b.fBottom && b.fTop <= a.fBottom;
740 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000741
caryclark@google.com6008c6562012-02-15 22:01:16 +0000742 bool isEmpty() {
743 return fLeft > fRight || fTop > fBottom
744 || fLeft == fRight && fTop == fBottom
745 || isnan(fLeft) || isnan(fRight)
746 || isnan(fTop) || isnan(fBottom);
747 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000748};
749
caryclark@google.com4917f172012-03-05 22:01:21 +0000750class Intercepts {
751public:
752 Intercepts()
753 : fTopIntercepts(0)
caryclark@google.com198e0542012-03-30 18:47:02 +0000754 , fBottomIntercepts(0)
755 , fExplicit(false) {
756 }
757
758 Intercepts& operator=(const Intercepts& src) {
759 fTs = src.fTs;
760 fTopIntercepts = src.fTopIntercepts;
761 fBottomIntercepts = src.fBottomIntercepts;
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000762 return *this;
caryclark@google.com198e0542012-03-30 18:47:02 +0000763 }
764
765 // OPTIMIZATION: remove this function if it's never called
766 double t(int tIndex) const {
767 if (tIndex == 0) {
768 return 0;
769 }
770 if (tIndex > fTs.count()) {
771 return 1;
772 }
773 return fTs[tIndex - 1];
caryclark@google.com4917f172012-03-05 22:01:21 +0000774 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000775
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000776#if DEBUG_DUMP
caryclark@google.coma5764232012-03-28 16:20:21 +0000777 void dump(const SkPoint* pts, SkPath::Verb verb) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000778 const char className[] = "Intercepts";
779 const int tab = 8;
780 for (int i = 0; i < fTs.count(); ++i) {
781 SkPoint out;
caryclark@google.coma5764232012-03-28 16:20:21 +0000782 switch (verb) {
783 case SkPath::kLine_Verb:
784 LineXYAtT(pts, fTs[i], &out);
785 break;
786 case SkPath::kQuad_Verb:
787 QuadXYAtT(pts, fTs[i], &out);
788 break;
789 case SkPath::kCubic_Verb:
790 CubicXYAtT(pts, fTs[i], &out);
791 break;
792 default:
793 SkASSERT(0);
794 }
caryclark@google.com752b60e2012-03-22 21:11:17 +0000795 SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000796 className, i, fTs[i], out.fX, out.fY);
797 }
caryclark@google.com198e0542012-03-30 18:47:02 +0000798 SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000799 className, fTopIntercepts);
caryclark@google.com198e0542012-03-30 18:47:02 +0000800 SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000801 className, fBottomIntercepts);
caryclark@google.comfb173422012-04-10 18:28:55 +0000802 SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className),
803 className, fExplicit);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000804 }
805#endif
806
caryclark@google.comc6825902012-02-03 22:07:47 +0000807 SkTDArray<double> fTs;
caryclark@google.com198e0542012-03-30 18:47:02 +0000808 unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges
809 unsigned char fBottomIntercepts;
810 bool fExplicit; // if set, suppress 0 and 1
811
caryclark@google.comc6825902012-02-03 22:07:47 +0000812};
813
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000814struct HorizontalEdge {
815 bool operator<(const HorizontalEdge& rh) const {
816 return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight
817 : fLeft < rh.fLeft : fY < rh.fY;
818 }
819
820#if DEBUG_DUMP
821 void dump() {
822 const char className[] = "HorizontalEdge";
823 const int tab = 4;
caryclark@google.com752b60e2012-03-22 21:11:17 +0000824 SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft);
825 SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight);
826 SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000827 }
828#endif
829
830 SkScalar fLeft;
831 SkScalar fRight;
832 SkScalar fY;
833};
834
caryclark@google.com6680fb12012-02-07 22:10:51 +0000835struct InEdge {
836 bool operator<(const InEdge& rh) const {
caryclark@google.comc6825902012-02-03 22:07:47 +0000837 return fBounds.fTop == rh.fBounds.fTop
838 ? fBounds.fLeft < rh.fBounds.fLeft
839 : fBounds.fTop < rh.fBounds.fTop;
840 }
841
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000842 // Avoid collapsing t values that are close to the same since
843 // we walk ts to describe consecutive intersections. Since a pair of ts can
844 // be nearly equal, any problems caused by this should be taken care
845 // of later.
846 int add(double* ts, size_t count, ptrdiff_t verbIndex) {
caryclark@google.comc6825902012-02-03 22:07:47 +0000847 // FIXME: in the pathological case where there is a ton of intercepts, binary search?
caryclark@google.com6008c6562012-02-15 22:01:16 +0000848 bool foundIntercept = false;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000849 int insertedAt = -1;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000850 Intercepts& intercepts = fIntercepts[verbIndex];
caryclark@google.comc6825902012-02-03 22:07:47 +0000851 for (size_t index = 0; index < count; ++index) {
852 double t = ts[index];
caryclark@google.com4917f172012-03-05 22:01:21 +0000853 if (t <= 0) {
caryclark@google.com198e0542012-03-30 18:47:02 +0000854 intercepts.fTopIntercepts <<= 1;
caryclark@google.com4917f172012-03-05 22:01:21 +0000855 fContainsIntercepts |= ++intercepts.fTopIntercepts > 1;
856 continue;
857 }
858 if (t >= 1) {
caryclark@google.com198e0542012-03-30 18:47:02 +0000859 intercepts.fBottomIntercepts <<= 1;
caryclark@google.com4917f172012-03-05 22:01:21 +0000860 fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000861 continue;
862 }
caryclark@google.com198e0542012-03-30 18:47:02 +0000863 fIntersected = true;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000864 foundIntercept = true;
caryclark@google.comc6825902012-02-03 22:07:47 +0000865 size_t tCount = intercepts.fTs.count();
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000866 double delta;
caryclark@google.comc6825902012-02-03 22:07:47 +0000867 for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
868 if (t <= intercepts.fTs[idx2]) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000869 // FIXME: ? if (t < intercepts.fTs[idx2]) // failed
870 delta = intercepts.fTs[idx2] - t;
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000871 if (delta > 0) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000872 insertedAt = idx2;
caryclark@google.comc6825902012-02-03 22:07:47 +0000873 *intercepts.fTs.insert(idx2) = t;
caryclark@google.comc6825902012-02-03 22:07:47 +0000874 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000875 goto nextPt;
caryclark@google.comc6825902012-02-03 22:07:47 +0000876 }
877 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000878 if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) {
879 insertedAt = tCount;
caryclark@google.comc6825902012-02-03 22:07:47 +0000880 *intercepts.fTs.append() = t;
881 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000882 nextPt:
883 ;
caryclark@google.comc6825902012-02-03 22:07:47 +0000884 }
caryclark@google.com4917f172012-03-05 22:01:21 +0000885 fContainsIntercepts |= foundIntercept;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +0000886 return insertedAt;
caryclark@google.comc6825902012-02-03 22:07:47 +0000887 }
caryclark@google.com198e0542012-03-30 18:47:02 +0000888
caryclark@google.comfb173422012-04-10 18:28:55 +0000889 void addPartial(SkTArray<InEdge>& edges, int ptStart, int ptEnd,
caryclark@google.com198e0542012-03-30 18:47:02 +0000890 int verbStart, int verbEnd) {
891 InEdge* edge = edges.push_back_n(1);
892 int verbCount = verbEnd - verbStart;
893 edge->fIntercepts.push_back_n(verbCount);
caryclark@google.coma3f05fa2012-06-01 17:44:28 +0000894 // uint8_t* verbs = &fVerbs[verbStart];
caryclark@google.com198e0542012-03-30 18:47:02 +0000895 for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) {
896 edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx];
897 }
898 edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]);
899 edge->fVerbs.append(verbCount, &fVerbs[verbStart]);
900 edge->setBounds();
caryclark@google.com198e0542012-03-30 18:47:02 +0000901 edge->fWinding = fWinding;
902 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
903 }
904
caryclark@google.comfb173422012-04-10 18:28:55 +0000905 void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb,
906 Intercepts& intercepts, int firstT, int lastT, bool flipped) {
caryclark@google.com198e0542012-03-30 18:47:02 +0000907 InEdge* edge = edges.push_back_n(1);
908 edge->fIntercepts.push_back_n(1);
caryclark@google.comfb173422012-04-10 18:28:55 +0000909 if (firstT == 0) {
910 *edge->fIntercepts[0].fTs.append() = 0;
911 } else {
912 *edge->fIntercepts[0].fTs.append() = intercepts.fTs[firstT - 1];
913 }
914 bool add1 = lastT == intercepts.fTs.count();
915 edge->fIntercepts[0].fTs.append(lastT - firstT, &intercepts.fTs[firstT]);
916 if (add1) {
917 *edge->fIntercepts[0].fTs.append() = 1;
918 }
caryclark@google.com198e0542012-03-30 18:47:02 +0000919 edge->fIntercepts[0].fExplicit = true;
caryclark@google.comfb173422012-04-10 18:28:55 +0000920 edge->fPts.append(verb + 1, pts);
caryclark@google.com198e0542012-03-30 18:47:02 +0000921 edge->fVerbs.append(1, &verb);
caryclark@google.comfb173422012-04-10 18:28:55 +0000922 // FIXME: bounds could be better for partial Ts
923 edge->setSubBounds();
caryclark@google.com198e0542012-03-30 18:47:02 +0000924 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
925 if (flipped) {
caryclark@google.comfb173422012-04-10 18:28:55 +0000926 edge->flipTs();
927 edge->fWinding = -fWinding;
928 } else {
929 edge->fWinding = fWinding;
caryclark@google.com198e0542012-03-30 18:47:02 +0000930 }
931 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000932
caryclark@google.com6680fb12012-02-07 22:10:51 +0000933 bool cached(const InEdge* edge) {
caryclark@google.comc6825902012-02-03 22:07:47 +0000934 // FIXME: in the pathological case where there is a ton of edges, binary search?
935 size_t count = fCached.count();
936 for (size_t index = 0; index < count; ++index) {
937 if (edge == fCached[index]) {
938 return true;
939 }
940 if (edge < fCached[index]) {
941 *fCached.insert(index) = edge;
942 return false;
943 }
944 }
945 *fCached.append() = edge;
946 return false;
947 }
948
caryclark@google.comfb173422012-04-10 18:28:55 +0000949 void complete(signed char winding) {
caryclark@google.com198e0542012-03-30 18:47:02 +0000950 setBounds();
951 fIntercepts.push_back_n(fVerbs.count());
952 if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top
953 flip();
954 }
955 fContainsIntercepts = fIntersected = false;
caryclark@google.com198e0542012-03-30 18:47:02 +0000956 }
957
caryclark@google.comfb173422012-04-10 18:28:55 +0000958 void flip() {
caryclark@google.com198e0542012-03-30 18:47:02 +0000959 size_t index;
960 size_t last = fPts.count() - 1;
961 for (index = 0; index < last; ++index, --last) {
962 SkTSwap<SkPoint>(fPts[index], fPts[last]);
963 }
964 last = fVerbs.count() - 1;
965 for (index = 0; index < last; ++index, --last) {
966 SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);
967 }
968 }
caryclark@google.comfb173422012-04-10 18:28:55 +0000969
970 void flipTs() {
971 SkASSERT(fIntercepts.count() == 1);
972 Intercepts& intercepts = fIntercepts[0];
973 SkASSERT(intercepts.fExplicit);
974 SkTDArray<double>& ts = intercepts.fTs;
975 size_t index;
976 size_t last = ts.count() - 1;
977 for (index = 0; index < last; ++index, --last) {
978 SkTSwap<double>(ts[index], ts[last]);
979 }
980 }
caryclark@google.com198e0542012-03-30 18:47:02 +0000981
982 void reset() {
983 fCached.reset();
984 fIntercepts.reset();
985 fPts.reset();
986 fVerbs.reset();
987 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
caryclark@google.com198e0542012-03-30 18:47:02 +0000988 fWinding = 0;
989 fContainsIntercepts = false;
990 fIntersected = false;
991 }
992
993 void setBounds() {
caryclark@google.comc6825902012-02-03 22:07:47 +0000994 SkPoint* ptPtr = fPts.begin();
995 SkPoint* ptLast = fPts.end();
996 if (ptPtr == ptLast) {
caryclark@google.com198e0542012-03-30 18:47:02 +0000997 SkDebugf("%s empty edge\n", __FUNCTION__);
caryclark@google.comc6825902012-02-03 22:07:47 +0000998 SkASSERT(0);
999 // FIXME: delete empty edge?
1000 return;
1001 }
1002 fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY);
1003 ++ptPtr;
1004 while (ptPtr != ptLast) {
1005 fBounds.growToInclude(ptPtr->fX, ptPtr->fY);
1006 ++ptPtr;
1007 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001008 }
caryclark@google.comfb173422012-04-10 18:28:55 +00001009
1010 // recompute bounds based on subrange of T values
1011 void setSubBounds() {
1012 SkASSERT(fIntercepts.count() == 1);
1013 Intercepts& intercepts = fIntercepts[0];
1014 SkASSERT(intercepts.fExplicit);
1015 SkASSERT(fVerbs.count() == 1);
1016 SkTDArray<double>& ts = intercepts.fTs;
1017 if (fVerbs[0] == SkPath::kQuad_Verb) {
1018 SkASSERT(fPts.count() == 3);
1019 QuadSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);
1020 } else {
1021 SkASSERT(fVerbs[0] == SkPath::kCubic_Verb);
1022 SkASSERT(fPts.count() == 4);
1023 CubicSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds);
1024 }
1025 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001026
caryclark@google.comfb173422012-04-10 18:28:55 +00001027 void splitInflectionPts(SkTArray<InEdge>& edges) {
caryclark@google.com198e0542012-03-30 18:47:02 +00001028 if (!fIntersected) {
1029 return;
1030 }
1031 uint8_t* verbs = fVerbs.begin();
1032 SkPoint* pts = fPts.begin();
1033 int lastVerb = 0;
1034 int lastPt = 0;
1035 uint8_t verb;
1036 bool edgeSplit = false;
1037 for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += verb) {
1038 Intercepts& intercepts = fIntercepts[ceptIdx];
1039 verb = *verbs++;
1040 if (verb <= SkPath::kLine_Verb) {
1041 continue;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001042 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001043 size_t tCount = intercepts.fTs.count();
1044 if (!tCount) {
1045 continue;
1046 }
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00001047 size_t tIndex = (size_t) -1;
caryclark@google.com198e0542012-03-30 18:47:02 +00001048 SkScalar y = pts[0].fY;
1049 int lastSplit = 0;
1050 int firstSplit = -1;
1051 bool curveSplit = false;
1052 while (++tIndex < tCount) {
1053 double nextT = intercepts.fTs[tIndex];
1054 SkScalar nextY = verb == SkPath::kQuad_Verb
1055 ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT);
1056 if (nextY < y) {
1057 edgeSplit = curveSplit = true;
1058 if (firstSplit < 0) {
1059 firstSplit = tIndex;
1060 int nextPt = pts - fPts.begin();
1061 int nextVerb = verbs - 1 - fVerbs.begin();
1062 if (lastVerb < nextVerb) {
caryclark@google.comfb173422012-04-10 18:28:55 +00001063 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb);
caryclark@google.com198e0542012-03-30 18:47:02 +00001064 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001065 SkDebugf("%s addPartial 1\n", __FUNCTION__);
caryclark@google.com198e0542012-03-30 18:47:02 +00001066 #endif
1067 }
1068 lastPt = nextPt;
1069 lastVerb = nextVerb;
1070 }
1071 } else {
1072 if (firstSplit >= 0) {
1073 if (lastSplit < firstSplit) {
caryclark@google.comfb173422012-04-10 18:28:55 +00001074 addSplit(edges, pts, verb, intercepts,
1075 lastSplit, firstSplit, false);
caryclark@google.com198e0542012-03-30 18:47:02 +00001076 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001077 SkDebugf("%s addSplit 1 tIndex=%d,%d\n",
1078 __FUNCTION__, lastSplit, firstSplit);
caryclark@google.com198e0542012-03-30 18:47:02 +00001079 #endif
1080 }
caryclark@google.comfb173422012-04-10 18:28:55 +00001081 addSplit(edges, pts, verb, intercepts,
1082 firstSplit, tIndex, true);
caryclark@google.com198e0542012-03-30 18:47:02 +00001083 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001084 SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n",
1085 __FUNCTION__, firstSplit, tIndex);
caryclark@google.com198e0542012-03-30 18:47:02 +00001086 #endif
1087 lastSplit = tIndex;
1088 firstSplit = -1;
1089 }
1090 }
1091 y = nextY;
1092 }
1093 if (curveSplit) {
1094 if (firstSplit < 0) {
1095 firstSplit = lastSplit;
1096 } else {
caryclark@google.comfb173422012-04-10 18:28:55 +00001097 addSplit(edges, pts, verb, intercepts, lastSplit,
1098 firstSplit, false);
caryclark@google.com198e0542012-03-30 18:47:02 +00001099 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001100 SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__,
1101 lastSplit, firstSplit);
caryclark@google.com198e0542012-03-30 18:47:02 +00001102 #endif
1103 }
caryclark@google.comfb173422012-04-10 18:28:55 +00001104 addSplit(edges, pts, verb, intercepts, firstSplit,
1105 tIndex, pts[verb].fY < y);
caryclark@google.com198e0542012-03-30 18:47:02 +00001106 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001107 SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__,
1108 firstSplit, tIndex, pts[verb].fY < y ? "flip" : "");
caryclark@google.com198e0542012-03-30 18:47:02 +00001109 #endif
caryclark@google.com6680fb12012-02-07 22:10:51 +00001110 }
1111 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001112 // collapse remainder -- if there's nothing left, clear it somehow?
1113 if (edgeSplit) {
1114 int nextVerb = verbs - 1 - fVerbs.begin();
1115 if (lastVerb < nextVerb) {
1116 int nextPt = pts - fPts.begin();
caryclark@google.comfb173422012-04-10 18:28:55 +00001117 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb);
caryclark@google.com198e0542012-03-30 18:47:02 +00001118 #if DEBUG_SPLIT
caryclark@google.comfb173422012-04-10 18:28:55 +00001119 SkDebugf("%s addPartial 2\n", __FUNCTION__);
caryclark@google.com198e0542012-03-30 18:47:02 +00001120 #endif
1121 }
1122 // OPTIMIZATION: reuse the edge instead of marking it empty
1123 reset();
1124 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001125 }
1126
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001127#if DEBUG_DUMP
1128 void dump() {
1129 int i;
1130 const char className[] = "InEdge";
1131 const int tab = 4;
1132 SkDebugf("InEdge %p (edge=%d)\n", this, fID);
1133 for (i = 0; i < fCached.count(); ++i) {
1134 SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className),
1135 className, i, fCached[i]);
1136 }
1137 uint8_t* verbs = fVerbs.begin();
1138 SkPoint* pts = fPts.begin();
1139 for (i = 0; i < fIntercepts.count(); ++i) {
1140 SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className),
1141 className, i);
caryclark@google.coma5764232012-03-28 16:20:21 +00001142 fIntercepts[i].dump(pts, (SkPath::Verb) *verbs);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001143 pts += *verbs++;
1144 }
1145 for (i = 0; i < fPts.count(); ++i) {
caryclark@google.com752b60e2012-03-22 21:11:17 +00001146 SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001147 className, i, fPts[i].fX, fPts[i].fY);
1148 }
1149 for (i = 0; i < fVerbs.count(); ++i) {
1150 SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className),
1151 className, i, fVerbs[i]);
1152 }
caryclark@google.comfb173422012-04-10 18:28:55 +00001153 SkDebugf("%*s.fBounds=(%1.9g, %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001154 className, fBounds.fLeft, fBounds.fTop,
1155 fBounds.fRight, fBounds.fBottom);
1156 SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className,
1157 fWinding);
1158 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
1159 className, fContainsIntercepts);
caryclark@google.com198e0542012-03-30 18:47:02 +00001160 SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className),
1161 className, fIntersected);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001162 }
1163#endif
1164
caryclark@google.com198e0542012-03-30 18:47:02 +00001165 // FIXME: temporary data : move this to a separate struct?
caryclark@google.com6680fb12012-02-07 22:10:51 +00001166 SkTDArray<const InEdge*> fCached; // list of edges already intercepted
caryclark@google.comc6825902012-02-03 22:07:47 +00001167 SkTArray<Intercepts> fIntercepts; // one per verb
caryclark@google.com4917f172012-03-05 22:01:21 +00001168
caryclark@google.comc6825902012-02-03 22:07:47 +00001169 // persistent data
1170 SkTDArray<SkPoint> fPts;
1171 SkTDArray<uint8_t> fVerbs;
1172 Bounds fBounds;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001173 int fID;
caryclark@google.comc6825902012-02-03 22:07:47 +00001174 signed char fWinding;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001175 bool fContainsIntercepts;
caryclark@google.com198e0542012-03-30 18:47:02 +00001176 bool fIntersected;
caryclark@google.comc6825902012-02-03 22:07:47 +00001177};
1178
caryclark@google.com6680fb12012-02-07 22:10:51 +00001179class InEdgeBuilder {
caryclark@google.comc6825902012-02-03 22:07:47 +00001180public:
1181
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001182InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges,
1183 SkTDArray<HorizontalEdge>& horizontalEdges)
caryclark@google.comc6825902012-02-03 22:07:47 +00001184 : fPath(path)
1185 , fCurrentEdge(NULL)
1186 , fEdges(edges)
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001187 , fHorizontalEdges(horizontalEdges)
caryclark@google.comc6825902012-02-03 22:07:47 +00001188 , fIgnoreHorizontal(ignoreHorizontal)
caryclark@google.com198e0542012-03-30 18:47:02 +00001189 , fContainsCurves(false)
caryclark@google.comc6825902012-02-03 22:07:47 +00001190{
1191 walk();
1192}
1193
caryclark@google.com198e0542012-03-30 18:47:02 +00001194bool containsCurves() const {
1195 return fContainsCurves;
1196}
1197
caryclark@google.comc6825902012-02-03 22:07:47 +00001198protected:
1199
1200void addEdge() {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001201 SkASSERT(fCurrentEdge);
caryclark@google.comc6825902012-02-03 22:07:47 +00001202 fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);
1203 fPtOffset = 1;
1204 *fCurrentEdge->fVerbs.append() = fVerb;
1205}
1206
caryclark@google.com6008c6562012-02-15 22:01:16 +00001207bool complete() {
1208 if (fCurrentEdge && fCurrentEdge->fVerbs.count()) {
caryclark@google.comfb173422012-04-10 18:28:55 +00001209 fCurrentEdge->complete(fWinding);
caryclark@google.com6008c6562012-02-15 22:01:16 +00001210 fCurrentEdge = NULL;
1211 return true;
1212 }
1213 return false;
1214}
1215
caryclark@google.com78e17132012-04-17 11:40:34 +00001216int direction(SkPath::Verb verb) {
1217 fPtCount = verb + 1;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001218 if (fIgnoreHorizontal && isHorizontal()) {
caryclark@google.comc6825902012-02-03 22:07:47 +00001219 return 0;
1220 }
caryclark@google.com78e17132012-04-17 11:40:34 +00001221 return fPts[0].fY == fPts[verb].fY
1222 ? fPts[0].fX == fPts[verb].fX ? 0 : fPts[0].fX < fPts[verb].fX
1223 ? 1 : -1 : fPts[0].fY < fPts[verb].fY ? 1 : -1;
caryclark@google.comc6825902012-02-03 22:07:47 +00001224}
1225
1226bool isHorizontal() {
1227 SkScalar y = fPts[0].fY;
1228 for (int i = 1; i < fPtCount; ++i) {
1229 if (fPts[i].fY != y) {
1230 return false;
1231 }
1232 }
1233 return true;
1234}
1235
1236void startEdge() {
caryclark@google.com6008c6562012-02-15 22:01:16 +00001237 if (!fCurrentEdge) {
1238 fCurrentEdge = fEdges.push_back_n(1);
1239 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001240 fWinding = 0;
1241 fPtOffset = 0;
1242}
1243
1244void walk() {
1245 SkPath::Iter iter(fPath, true);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001246 int winding = 0;
caryclark@google.comc6825902012-02-03 22:07:47 +00001247 while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) {
1248 switch (fVerb) {
1249 case SkPath::kMove_Verb:
caryclark@google.comc6825902012-02-03 22:07:47 +00001250 startEdge();
1251 continue;
1252 case SkPath::kLine_Verb:
caryclark@google.com78e17132012-04-17 11:40:34 +00001253 winding = direction(SkPath::kLine_Verb);
caryclark@google.comc6825902012-02-03 22:07:47 +00001254 break;
1255 case SkPath::kQuad_Verb:
caryclark@google.com78e17132012-04-17 11:40:34 +00001256 fVerb = QuadReduceOrder(fPts);
1257 winding = direction(fVerb);
1258 fContainsCurves |= fVerb == SkPath::kQuad_Verb;
caryclark@google.comc6825902012-02-03 22:07:47 +00001259 break;
1260 case SkPath::kCubic_Verb:
caryclark@google.com78e17132012-04-17 11:40:34 +00001261 fVerb = CubicReduceOrder(fPts);
1262 winding = direction(fVerb);
1263 fContainsCurves |= fVerb >= SkPath::kQuad_Verb;
caryclark@google.comc6825902012-02-03 22:07:47 +00001264 break;
1265 case SkPath::kClose_Verb:
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001266 SkASSERT(fCurrentEdge);
caryclark@google.com6008c6562012-02-15 22:01:16 +00001267 complete();
caryclark@google.comc6825902012-02-03 22:07:47 +00001268 continue;
1269 default:
1270 SkDEBUGFAIL("bad verb");
1271 return;
1272 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001273 if (winding == 0) {
1274 HorizontalEdge* horizontalEdge = fHorizontalEdges.append();
1275 // FIXME: for degenerate quads and cubics, compute x extremes
1276 horizontalEdge->fLeft = fPts[0].fX;
1277 horizontalEdge->fRight = fPts[fVerb].fX;
1278 horizontalEdge->fY = fPts[0].fY;
1279 if (horizontalEdge->fLeft > horizontalEdge->fRight) {
1280 SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight);
1281 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001282 if (complete()) {
1283 startEdge();
1284 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001285 continue;
1286 }
1287 if (fWinding + winding == 0) {
1288 // FIXME: if prior verb or this verb is a horizontal line, reverse
1289 // it instead of starting a new edge
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001290 SkASSERT(fCurrentEdge);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001291 if (complete()) {
1292 startEdge();
1293 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001294 }
1295 fWinding = winding;
1296 addEdge();
1297 }
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001298 if (!complete()) {
1299 if (fCurrentEdge) {
1300 fEdges.pop_back();
1301 }
1302 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001303}
1304
1305private:
1306 const SkPath& fPath;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001307 InEdge* fCurrentEdge;
1308 SkTArray<InEdge>& fEdges;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001309 SkTDArray<HorizontalEdge>& fHorizontalEdges;
caryclark@google.comc6825902012-02-03 22:07:47 +00001310 SkPoint fPts[4];
1311 SkPath::Verb fVerb;
1312 int fPtCount;
1313 int fPtOffset;
1314 int8_t fWinding;
caryclark@google.comc6825902012-02-03 22:07:47 +00001315 bool fIgnoreHorizontal;
caryclark@google.com198e0542012-03-30 18:47:02 +00001316 bool fContainsCurves;
caryclark@google.comc6825902012-02-03 22:07:47 +00001317};
1318
caryclark@google.com6680fb12012-02-07 22:10:51 +00001319struct WorkEdge {
1320 SkScalar bottom() const {
1321 return fPts[verb()].fY;
caryclark@google.comc6825902012-02-03 22:07:47 +00001322 }
1323
caryclark@google.com6680fb12012-02-07 22:10:51 +00001324 void init(const InEdge* edge) {
1325 fEdge = edge;
1326 fPts = edge->fPts.begin();
1327 fVerb = edge->fVerbs.begin();
caryclark@google.comc6825902012-02-03 22:07:47 +00001328 }
1329
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001330 bool advance() {
caryclark@google.com6680fb12012-02-07 22:10:51 +00001331 SkASSERT(fVerb < fEdge->fVerbs.end());
1332 fPts += *fVerb++;
1333 return fVerb != fEdge->fVerbs.end();
caryclark@google.comc6825902012-02-03 22:07:47 +00001334 }
caryclark@google.com78e17132012-04-17 11:40:34 +00001335
1336 const SkPoint* lastPoints() const {
1337 SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb());
1338 return &fPts[-lastVerb()];
1339 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001340
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001341 SkPath::Verb lastVerb() const {
1342 SkASSERT(fVerb > fEdge->fVerbs.begin());
1343 return (SkPath::Verb) fVerb[-1];
1344 }
1345
caryclark@google.com78e17132012-04-17 11:40:34 +00001346 const SkPoint* points() const {
1347 return fPts;
1348 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001349
1350 SkPath::Verb verb() const {
1351 return (SkPath::Verb) *fVerb;
1352 }
1353
caryclark@google.com6008c6562012-02-15 22:01:16 +00001354 ptrdiff_t verbIndex() const {
caryclark@google.com6680fb12012-02-07 22:10:51 +00001355 return fVerb - fEdge->fVerbs.begin();
1356 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001357
caryclark@google.com6680fb12012-02-07 22:10:51 +00001358 int winding() const {
1359 return fEdge->fWinding;
caryclark@google.comc6825902012-02-03 22:07:47 +00001360 }
1361
caryclark@google.com6680fb12012-02-07 22:10:51 +00001362 const InEdge* fEdge;
caryclark@google.comc6825902012-02-03 22:07:47 +00001363 const SkPoint* fPts;
1364 const uint8_t* fVerb;
caryclark@google.comc6825902012-02-03 22:07:47 +00001365};
1366
caryclark@google.com6680fb12012-02-07 22:10:51 +00001367// always constructed with SkTDArray because new edges are inserted
1368// this may be a inappropriate optimization, suggesting that a separate array of
1369// ActiveEdge* may be faster to insert and search
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001370
1371// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since
1372// as active edges are introduced, only local sorting should be required
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001373class ActiveEdge {
1374public:
caryclark@google.com78e17132012-04-17 11:40:34 +00001375 // this logic must be kept in sync with tooCloseToCall
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001376 // callers expect this to only read fAbove, fTangent
caryclark@google.com6008c6562012-02-15 22:01:16 +00001377 bool operator<(const ActiveEdge& rh) const {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001378 if (fVerb == rh.fVerb) {
1379 // FIXME: don't know what to do if verb is quad, cubic
1380 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001381 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001382 // figure out which is quad, line
1383 // if cached data says line did not intersect quad, use top/bottom
1384 if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this)) {
1385 return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow);
1386 }
1387 // use whichever of top/tangent tangent/bottom overlaps more
1388 // with line top/bot
1389 // assumes quad/cubic can already be upconverted to cubic/cubic
1390 const SkPoint* line[2];
1391 const SkPoint* curve[4];
1392 if (fVerb != SkPath::kLine_Verb) {
1393 line[0] = &rh.fAbove;
1394 line[1] = &rh.fBelow;
1395 curve[0] = &fAbove;
1396 curve[1] = &fTangent;
1397 curve[2] = &fBelow;
1398 } else {
1399 line[0] = &fAbove;
1400 line[1] = &fBelow;
1401 curve[0] = &rh.fAbove;
1402 curve[1] = &rh.fTangent;
1403 curve[2] = &rh.fBelow;
1404 }
caryclark@google.comb45a1b42012-05-18 20:50:33 +00001405 // FIXME: code has been abandoned, incomplete....
1406 return false;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001407 }
1408
1409 bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1,
1410 const SkPoint& b2) const {
1411 double topD = a1.fX - b1.fX;
1412 if (b1.fY < a1.fY) {
1413 topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX);
1414 } else if (b1.fY > a1.fY) {
1415 topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX);
1416 }
1417 double botD = a2.fX - b2.fX;
1418 if (b2.fY > a2.fY) {
1419 botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX);
1420 } else if (b2.fY < a2.fY) {
1421 botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001422 }
1423 // return sign of greater absolute value
1424 return (fabs(topD) > fabs(botD) ? topD : botD) < 0;
1425 }
1426
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001427 // If a pair of edges are nearly coincident for some span, add a T in the
1428 // edge so it can be shortened to match the other edge. Note that another
1429 // approach is to trim the edge after it is added to the OutBuilder list --
1430 // FIXME: since this has no effect if the edge is already done (i.e.,
1431 // fYBottom >= y) maybe this can only be done by calling trimLine later.
1432 void addTatYBelow(SkScalar y) {
1433 if (fBelow.fY <= y || fYBottom >= y) {
1434 return;
1435 }
1436 addTatYInner(y);
1437 fFixBelow = true;
1438 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001439
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001440 void addTatYAbove(SkScalar y) {
1441 if (fBelow.fY <= y) {
1442 return;
1443 }
1444 addTatYInner(y);
1445 }
1446
1447 void addTatYInner(SkScalar y) {
caryclark@google.com752b60e2012-03-22 21:11:17 +00001448 if (fWorkEdge.fPts[0].fY > y) {
1449 backup(y);
1450 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001451 SkScalar left = fWorkEdge.fPts[0].fX;
1452 SkScalar right = fWorkEdge.fPts[1].fX;
1453 if (left > right) {
1454 SkTSwap(left, right);
1455 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001456 double ts[2];
caryclark@google.com78e17132012-04-17 11:40:34 +00001457 SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001458 int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts);
1459 SkASSERT(pts == 1);
1460 // An ActiveEdge or WorkEdge has no need to modify the T values computed
1461 // in the InEdge, except in the following case. If a pair of edges are
1462 // nearly coincident, this may not be detected when the edges are
1463 // intersected. Later, when sorted, and this near-coincidence is found,
1464 // an additional t value must be added, requiring the cast below.
1465 InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge);
1466 int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex());
caryclark@google.com752b60e2012-03-22 21:11:17 +00001467 #if DEBUG_ADJUST_COINCIDENT
1468 SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]);
1469 #endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001470 if (insertedAt >= 0) {
1471 if (insertedAt + 1 < fTIndex) {
1472 SkASSERT(insertedAt + 2 == fTIndex);
1473 --fTIndex;
1474 }
1475 }
1476 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001477
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001478 bool advanceT() {
caryclark@google.com198e0542012-03-30 18:47:02 +00001479 SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
1480 return ++fTIndex <= fTs->count() - fExplicitTs;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001481 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001482
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001483 bool advance() {
1484 // FIXME: flip sense of next
1485 bool result = fWorkEdge.advance();
1486 fDone = !result;
1487 initT();
1488 return result;
1489 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001490
1491 void backup(SkScalar y) {
1492 do {
1493 SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb);
1494 fWorkEdge.fPts -= *--fWorkEdge.fVerb;
1495 SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts);
1496 } while (fWorkEdge.fPts[0].fY >= y);
1497 initT();
caryclark@google.com198e0542012-03-30 18:47:02 +00001498 SkASSERT(!fExplicitTs);
caryclark@google.com752b60e2012-03-22 21:11:17 +00001499 fTIndex = fTs->count() + 1;
1500 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001501
1502 void calcAboveBelow(double tAbove, double tBelow) {
1503 fVerb = fWorkEdge.verb();
1504 switch (fVerb) {
1505 case SkPath::kLine_Verb:
1506 LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
1507 LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent);
1508 fBelow = fTangent;
1509 break;
1510 case SkPath::kQuad_Verb:
1511 // FIXME: put array in struct to avoid copy?
1512 SkPoint quad[3];
1513 QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad);
1514 fAbove = quad[0];
1515 fTangent = quad[0] != quad[1] ? quad[1] : quad[2];
1516 fBelow = quad[2];
1517 break;
1518 case SkPath::kCubic_Verb:
1519 SkPoint cubic[3];
1520 CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic);
1521 fAbove = cubic[0];
1522 // FIXME: can't see how quad logic for how tangent is used
1523 // extends to cubic
1524 fTangent = cubic[0] != cubic[1] ? cubic[1]
1525 : cubic[0] != cubic[2] ? cubic[2] : cubic[3];
1526 fBelow = cubic[3];
1527 break;
1528 default:
1529 SkASSERT(0);
1530 }
1531 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001532
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001533 void calcLeft(SkScalar y) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001534 // OPTIMIZE: put a kDone_Verb at the end of the verb list?
caryclark@google.com4917f172012-03-05 22:01:21 +00001535 if (fDone || fBelow.fY > y) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001536 return; // nothing to do; use last
caryclark@google.com4917f172012-03-05 22:01:21 +00001537 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001538 calcLeft();
caryclark@google.com752b60e2012-03-22 21:11:17 +00001539 if (fAbove.fY == fBelow.fY) {
1540 SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__,
1541 ID(), fAbove.fY);
1542 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001543 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001544
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001545 void calcLeft() {
caryclark@google.com198e0542012-03-30 18:47:02 +00001546 int add = (fTIndex <= fTs->count() - fExplicitTs) - 1;
caryclark@google.coma5764232012-03-28 16:20:21 +00001547 double tAbove = t(fTIndex + add);
caryclark@google.coma5764232012-03-28 16:20:21 +00001548 double tBelow = t(fTIndex - ~add);
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001549 // OPTIMIZATION: if fAbove, fBelow have already been computed
1550 // for the fTIndex, don't do it again
1551 calcAboveBelow(tAbove, tBelow);
1552 // For identical x, this lets us know which edge is first.
1553 // If both edges have T values < 1, check x at next T (fBelow).
caryclark@google.coma5764232012-03-28 16:20:21 +00001554 SkASSERT(tAbove != tBelow);
1555 // FIXME: this can loop forever
1556 // need a break if we hit the end
caryclark@google.com198e0542012-03-30 18:47:02 +00001557 // FIXME: in unit test, figure out how explicit Ts work as well
caryclark@google.coma5764232012-03-28 16:20:21 +00001558 while (fAbove.fY == fBelow.fY) {
1559 if (add < 0 || fTIndex == fTs->count()) {
1560 add -= 1;
1561 SkASSERT(fTIndex + add >= 0);
1562 tAbove = t(fTIndex + add);
caryclark@google.coma5764232012-03-28 16:20:21 +00001563 } else {
1564 add += 1;
1565 SkASSERT(fTIndex - ~add <= fTs->count() + 1);
1566 tBelow = t(fTIndex - ~add);
caryclark@google.coma5764232012-03-28 16:20:21 +00001567 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001568 calcAboveBelow(tAbove, tBelow);
caryclark@google.coma5764232012-03-28 16:20:21 +00001569 }
caryclark@google.coma5764232012-03-28 16:20:21 +00001570 fTAbove = tAbove;
1571 fTBelow = tBelow;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001572 }
1573
caryclark@google.com752b60e2012-03-22 21:11:17 +00001574 bool done(SkScalar bottom) const {
1575 return fDone || fYBottom >= bottom;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001576 }
caryclark@google.com78e17132012-04-17 11:40:34 +00001577
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001578 void fixBelow() {
1579 if (fFixBelow) {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001580 fTBelow = nextT();
1581 calcAboveBelow(fTAbove, fTBelow);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001582 fFixBelow = false;
1583 }
1584 }
1585
caryclark@google.com6680fb12012-02-07 22:10:51 +00001586 void init(const InEdge* edge) {
1587 fWorkEdge.init(edge);
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001588 fDone = false;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001589 initT();
caryclark@google.com4917f172012-03-05 22:01:21 +00001590 fBelow.fY = SK_ScalarMin;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001591 fYBottom = SK_ScalarMin;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001592 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001593
caryclark@google.com6680fb12012-02-07 22:10:51 +00001594 void initT() {
caryclark@google.com6008c6562012-02-15 22:01:16 +00001595 const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front();
1596 SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count());
1597 const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex();
caryclark@google.com198e0542012-03-30 18:47:02 +00001598 fTs = &interceptPtr->fTs;
1599 fExplicitTs = interceptPtr->fExplicit;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001600 // the above is conceptually the same as
1601 // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;
1602 // but templated arrays don't allow returning a pointer to the end() element
caryclark@google.com6680fb12012-02-07 22:10:51 +00001603 fTIndex = 0;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001604 if (!fDone) {
1605 fVerb = fWorkEdge.verb();
1606 }
1607 SkASSERT(fVerb > SkPath::kMove_Verb);
caryclark@google.comc6825902012-02-03 22:07:47 +00001608 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001609
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001610 // OPTIMIZATION: record if two edges are coincident when the are intersected
1611 // It's unclear how to do this -- seems more complicated than recording the
1612 // t values, since the same t values could exist intersecting non-coincident
1613 // edges.
caryclark@google.com78e17132012-04-17 11:40:34 +00001614 bool isCoincidentWith(const ActiveEdge* edge) const {
caryclark@google.comd88e0892012-03-27 13:23:51 +00001615 if (fAbove != edge->fAbove || fBelow != edge->fBelow) {
1616 return false;
1617 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001618 if (fVerb != edge->fVerb) {
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001619 return false;
1620 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001621 switch (fVerb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001622 case SkPath::kLine_Verb:
caryclark@google.com4917f172012-03-05 22:01:21 +00001623 return true;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001624 default:
caryclark@google.com78e17132012-04-17 11:40:34 +00001625 // FIXME: add support for quads, cubics
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001626 SkASSERT(0);
caryclark@google.com78e17132012-04-17 11:40:34 +00001627 return false;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001628 }
1629 return false;
1630 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001631
caryclark@google.com78e17132012-04-17 11:40:34 +00001632 bool isUnordered(const ActiveEdge* edge) const {
1633 return fAbove == edge->fAbove && fBelow == edge->fBelow;
1634 }
1635
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001636// SkPath::Verb lastVerb() const {
1637// return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
1638// }
caryclark@google.com78e17132012-04-17 11:40:34 +00001639
1640 const SkPoint* lastPoints() const {
1641 return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points();
1642 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001643
1644 bool noIntersect(const ActiveEdge& ) const {
1645 // incomplete
1646 return false;
1647 }
caryclark@google.com78e17132012-04-17 11:40:34 +00001648
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001649 // The shortest close call edge should be moved into a position where
1650 // it contributes if the winding is transitioning to or from zero.
1651 bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const {
caryclark@google.comd88e0892012-03-27 13:23:51 +00001652#if DEBUG_ADJUST_COINCIDENT
1653 SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n",
1654 __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY,
1655 prev, wind, wind + next->fWorkEdge.winding());
1656#endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001657 if ((prev & mask) == 0 || (wind & mask) == 0) {
1658 return next->fBelow.fY < fBelow.fY;
1659 }
1660 int nextWinding = wind + next->fWorkEdge.winding();
1661 if ((nextWinding & mask) == 0) {
1662 return fBelow.fY < next->fBelow.fY;
1663 }
1664 return false;
1665 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001666
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001667 bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const {
1668 if (fBelow.fY >= bottom || fDone || edge->fDone) {
1669 return false;
1670 }
1671 ActiveEdge thisWork = *this;
1672 ActiveEdge edgeWork = *edge;
1673 while ((thisWork.advanceT() || thisWork.advance())
1674 && (edgeWork.advanceT() || edgeWork.advance())) {
1675 thisWork.calcLeft();
1676 edgeWork.calcLeft();
1677 if (thisWork < edgeWork) {
1678 return false;
1679 }
1680 if (edgeWork < thisWork) {
1681 return true;
1682 }
1683 }
1684 return false;
1685 }
caryclark@google.com78e17132012-04-17 11:40:34 +00001686
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00001687 bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001688 SkASSERT(fVerb != SkPath::kLine_Verb
1689 || edge->fVerb != SkPath::kLine_Verb);
caryclark@google.com78e17132012-04-17 11:40:34 +00001690 if (fDone || edge->fDone) {
1691 return false;
1692 }
1693 ActiveEdge thisWork, edgeWork;
1694 extractAboveBelow(thisWork);
1695 edge->extractAboveBelow(edgeWork);
1696 return edgeWork < thisWork;
1697 }
caryclark@google.com752b60e2012-03-22 21:11:17 +00001698
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001699 bool tooCloseToCall(const ActiveEdge* edge) const {
1700 int ulps;
caryclark@google.comd88e0892012-03-27 13:23:51 +00001701 double t1, t2, b1, b2;
caryclark@google.com78e17132012-04-17 11:40:34 +00001702 // This logic must be kept in sync with operator <
caryclark@google.comd88e0892012-03-27 13:23:51 +00001703 if (edge->fAbove.fY < fAbove.fY) {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001704 t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
1705 t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbove.fX);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001706 } else if (edge->fAbove.fY > fAbove.fY) {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001707 t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX);
1708 t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001709 } else {
1710 t1 = fAbove.fX;
1711 t2 = edge->fAbove.fX;
1712 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001713 if (edge->fTangent.fY > fTangent.fY) {
1714 b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
1715 b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge->fAbove.fX);
1716 } else if (edge->fTangent.fY < fTangent.fY) {
1717 b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX);
1718 b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001719 } else {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001720 b1 = fTangent.fX;
1721 b2 = edge->fTangent.fX;
caryclark@google.comd88e0892012-03-27 13:23:51 +00001722 }
1723 if (fabs(t1 - t2) > fabs(b1 - b2)) {
caryclark@google.comb45a1b42012-05-18 20:50:33 +00001724 ulps = UlpsDiff((float) t1, (float) t2);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001725 } else {
caryclark@google.comb45a1b42012-05-18 20:50:33 +00001726 ulps = UlpsDiff((float) b1, (float) b2);
caryclark@google.comd88e0892012-03-27 13:23:51 +00001727 }
1728#if DEBUG_ADJUST_COINCIDENT
1729 SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(),
1730 ulps);
1731#endif
caryclark@google.com78e17132012-04-17 11:40:34 +00001732 if (ulps < 0 || ulps > 32) {
1733 return false;
1734 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001735 if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001736 return true;
1737 }
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001738 if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001739 return false;
1740 }
1741
1742 double ts[2];
1743 bool isLine = true;
1744 bool curveQuad = true;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001745 if (fVerb == SkPath::kCubic_Verb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001746 ts[0] = (fTAbove * 2 + fTBelow) / 3;
1747 ts[1] = (fTAbove + fTBelow * 2) / 3;
1748 curveQuad = isLine = false;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001749 } else if (edge->fVerb == SkPath::kCubic_Verb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001750 ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3;
1751 ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3;
1752 curveQuad = false;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001753 } else if (fVerb == SkPath::kQuad_Verb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001754 ts[0] = fTAbove;
1755 ts[1] = (fTAbove + fTBelow) / 2;
1756 isLine = false;
1757 } else {
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001758 SkASSERT(edge->fVerb == SkPath::kQuad_Verb);
caryclark@google.com78e17132012-04-17 11:40:34 +00001759 ts[0] = edge->fTAbove;
1760 ts[1] = (edge->fTAbove + edge->fTBelow) / 2;
1761 }
1762 const SkPoint* curvePts = isLine ? edge->lastPoints() : lastPoints();
1763 const ActiveEdge* lineEdge = isLine ? this : edge;
1764 SkPoint curveSample[2];
1765 for (int index = 0; index < 2; ++index) {
1766 if (curveQuad) {
1767 QuadXYAtT(curvePts, ts[index], &curveSample[index]);
1768 } else {
1769 CubicXYAtT(curvePts, ts[index], &curveSample[index]);
1770 }
1771 }
1772 return IsCoincident(curveSample, lineEdge->fAbove, lineEdge->fBelow);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001773 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001774
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001775 double nextT() const {
caryclark@google.com198e0542012-03-30 18:47:02 +00001776 SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001777 return t(fTIndex + 1);
1778 }
caryclark@google.com6680fb12012-02-07 22:10:51 +00001779
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001780 double t() const {
caryclark@google.com198e0542012-03-30 18:47:02 +00001781 return t(fTIndex);
caryclark@google.com6680fb12012-02-07 22:10:51 +00001782 }
1783
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001784 double t(int tIndex) const {
caryclark@google.com198e0542012-03-30 18:47:02 +00001785 if (fExplicitTs) {
1786 SkASSERT(tIndex < fTs->count());
1787 return (*fTs)[tIndex];
1788 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001789 if (tIndex == 0) {
1790 return 0;
1791 }
1792 if (tIndex > fTs->count()) {
1793 return 1;
1794 }
1795 return (*fTs)[tIndex - 1];
1796 }
1797
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001798 // FIXME: debugging only
caryclark@google.com752b60e2012-03-22 21:11:17 +00001799 int ID() const {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001800 return fWorkEdge.fEdge->fID;
1801 }
1802
caryclark@google.com78e17132012-04-17 11:40:34 +00001803private:
1804 // utility used only by swapUnordered
1805 void extractAboveBelow(ActiveEdge& extracted) const {
1806 SkPoint curve[4];
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001807 switch (fVerb) {
caryclark@google.com78e17132012-04-17 11:40:34 +00001808 case SkPath::kLine_Verb:
1809 extracted.fAbove = fAbove;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001810 extracted.fTangent = fTangent;
caryclark@google.com78e17132012-04-17 11:40:34 +00001811 return;
1812 case SkPath::kQuad_Verb:
1813 QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve);
1814 break;
1815 case SkPath::kCubic_Verb:
1816 CubicSubDivide(lastPoints(), fTAbove, fTBelow, curve);
1817 break;
1818 default:
1819 SkASSERT(0);
1820 }
1821 extracted.fAbove = curve[0];
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001822 extracted.fTangent = curve[1];
caryclark@google.com78e17132012-04-17 11:40:34 +00001823 }
1824
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001825public:
caryclark@google.com6680fb12012-02-07 22:10:51 +00001826 WorkEdge fWorkEdge;
1827 const SkTDArray<double>* fTs;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001828 SkPoint fAbove;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001829 SkPoint fTangent;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001830 SkPoint fBelow;
caryclark@google.com78e17132012-04-17 11:40:34 +00001831 double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001832 double fTBelow;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001833 SkScalar fYBottom;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001834 int fCoincident;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001835 int fTIndex;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00001836 SkPath::Verb fVerb;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001837 bool fSkip; // OPTIMIZATION: use bitfields?
1838 bool fCloseCall;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001839 bool fDone;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001840 bool fFixBelow;
caryclark@google.com198e0542012-03-30 18:47:02 +00001841 bool fExplicitTs;
caryclark@google.comc6825902012-02-03 22:07:47 +00001842};
1843
caryclark@google.com6680fb12012-02-07 22:10:51 +00001844static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) {
caryclark@google.com6680fb12012-02-07 22:10:51 +00001845 size_t count = activeEdges.count();
1846 for (size_t index = 0; index < count; ++index) {
caryclark@google.com6680fb12012-02-07 22:10:51 +00001847 if (edge == activeEdges[index].fWorkEdge.fEdge) {
1848 return;
1849 }
1850 }
1851 ActiveEdge* active = activeEdges.append();
1852 active->init(edge);
1853}
1854
caryclark@google.com4917f172012-03-05 22:01:21 +00001855// Find any intersections in the range of active edges. A pair of edges, on
1856// either side of another edge, may change the winding contribution for part of
1857// the edge.
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001858// Keep horizontal edges just for
caryclark@google.com4917f172012-03-05 22:01:21 +00001859// the purpose of computing when edges change their winding contribution, since
1860// this is essentially computing the horizontal intersection.
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001861static void addBottomT(InEdge** currentPtr, InEdge** lastPtr,
1862 HorizontalEdge** horizontal) {
1863 InEdge** testPtr = currentPtr - 1;
1864 HorizontalEdge* horzEdge = *horizontal;
1865 SkScalar left = horzEdge->fLeft;
1866 SkScalar bottom = horzEdge->fY;
1867 while (++testPtr != lastPtr) {
1868 InEdge* test = *testPtr;
1869 if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) {
1870 continue;
1871 }
1872 WorkEdge wt;
1873 wt.init(test);
1874 do {
1875 HorizontalEdge** sorted = horizontal;
1876 horzEdge = *sorted;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001877 do {
caryclark@google.com198e0542012-03-30 18:47:02 +00001878 double wtTs[4];
1879 int pts;
1880 uint8_t verb = wt.verb();
1881 switch (verb) {
1882 case SkPath::kLine_Verb:
1883 pts = LineIntersect(wt.fPts, horzEdge->fLeft,
1884 horzEdge->fRight, horzEdge->fY, wtTs);
1885 break;
1886 case SkPath::kQuad_Verb:
1887 pts = QuadIntersect(wt.fPts, horzEdge->fLeft,
1888 horzEdge->fRight, horzEdge->fY, wtTs);
1889 break;
1890 case SkPath::kCubic_Verb:
1891 pts = CubicIntersect(wt.fPts, horzEdge->fLeft,
1892 horzEdge->fRight, horzEdge->fY, wtTs);
1893 break;
1894 }
1895 if (pts) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001896#if DEBUG_ADD_BOTTOM_TS
caryclark@google.com198e0542012-03-30 18:47:02 +00001897 for (int x = 0; x < pts; ++x) {
1898 SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__,
1899 horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0].fY);
1900 for (int y = 0; y < verb; ++y) {
1901 SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1].fY));
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001902 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001903 SkDebugf(")\n");
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001904 }
caryclark@google.com198e0542012-03-30 18:47:02 +00001905 if (pts > verb) {
1906 SkASSERT(0); // FIXME ? should this work?
1907 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
1908 }
1909#endif
1910 test->add(wtTs, pts, wt.verbIndex());
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001911 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001912 horzEdge = *++sorted;
1913 } while (horzEdge->fY == bottom
1914 && horzEdge->fLeft <= test->fBounds.fRight);
1915 } while (wt.advance());
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001916 }
1917}
1918
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00001919#if DEBUG_ADD_INTERSECTING_TS
caryclark@google.coma5764232012-03-28 16:20:21 +00001920static void debugShowLineIntersection(int pts, const WorkEdge& wt,
1921 const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) {
caryclark@google.coma5764232012-03-28 16:20:21 +00001922 if (!pts) {
1923 return;
1924 }
1925 SkPoint wtOutPt, wnOutPt;
1926 LineXYAtT(wt.fPts, wtTs[0], &wtOutPt);
1927 LineXYAtT(wn.fPts, wnTs[0], &wnOutPt);
caryclark@google.comfb173422012-04-10 18:28:55 +00001928 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
caryclark@google.coma5764232012-03-28 16:20:21 +00001929 __FUNCTION__,
1930 wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,
caryclark@google.comfb173422012-04-10 18:28:55 +00001931 wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY);
caryclark@google.coma5764232012-03-28 16:20:21 +00001932 if (pts == 2) {
1933 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
1934 }
caryclark@google.comfb173422012-04-10 18:28:55 +00001935 SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n",
caryclark@google.coma5764232012-03-28 16:20:21 +00001936 __FUNCTION__,
1937 wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY,
caryclark@google.comfb173422012-04-10 18:28:55 +00001938 wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY);
caryclark@google.coma5764232012-03-28 16:20:21 +00001939 if (pts == 2) {
1940 SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
1941 }
caryclark@google.coma5764232012-03-28 16:20:21 +00001942}
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00001943#else
1944static void debugShowLineIntersection(int , const WorkEdge& ,
1945 const WorkEdge& , const double [2], const double [2]) {
1946}
1947#endif
caryclark@google.coma5764232012-03-28 16:20:21 +00001948
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001949static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001950 InEdge** testPtr = currentPtr - 1;
caryclark@google.com752b60e2012-03-22 21:11:17 +00001951 // FIXME: lastPtr should be past the point of interest, so
1952 // test below should be lastPtr - 2
1953 // that breaks testSimplifyTriangle22, so further investigation is needed
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001954 while (++testPtr != lastPtr - 1) {
1955 InEdge* test = *testPtr;
1956 InEdge** nextPtr = testPtr;
1957 do {
1958 InEdge* next = *++nextPtr;
caryclark@google.com198e0542012-03-30 18:47:02 +00001959 // FIXME: this compares against the sentinel sometimes
1960 // OPTIMIZATION: this may never be needed since this gets called
1961 // in two passes now. Verify that double hits are appropriate.
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001962 if (test->cached(next)) {
1963 continue;
1964 }
1965 if (!Bounds::Intersects(test->fBounds, next->fBounds)) {
1966 continue;
1967 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001968 WorkEdge wt, wn;
1969 wt.init(test);
1970 wn.init(next);
1971 do {
caryclark@google.coma5764232012-03-28 16:20:21 +00001972 int pts;
1973 Intersections ts;
1974 bool swap = false;
1975 switch (wt.verb()) {
1976 case SkPath::kLine_Verb:
1977 switch (wn.verb()) {
1978 case SkPath::kLine_Verb: {
1979 pts = LineIntersect(wt.fPts, wn.fPts, ts);
1980 debugShowLineIntersection(pts, wt, wn,
1981 ts.fT[0], ts.fT[1]);
1982 break;
1983 }
1984 case SkPath::kQuad_Verb: {
1985 swap = true;
1986 pts = QuadLineIntersect(wn.fPts, wt.fPts, ts);
1987 break;
1988 }
1989 case SkPath::kCubic_Verb: {
1990 swap = true;
1991 pts = CubicLineIntersect(wn.fPts, wt.fPts, ts);
1992 break;
1993 }
1994 default:
1995 SkASSERT(0);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00001996 }
caryclark@google.coma5764232012-03-28 16:20:21 +00001997 break;
1998 case SkPath::kQuad_Verb:
1999 switch (wn.verb()) {
2000 case SkPath::kLine_Verb: {
2001 pts = QuadLineIntersect(wt.fPts, wn.fPts, ts);
2002 break;
2003 }
2004 case SkPath::kQuad_Verb: {
2005 pts = QuadIntersect(wt.fPts, wn.fPts, ts);
2006 break;
2007 }
2008 case SkPath::kCubic_Verb: {
2009 // FIXME: promote quad to cubic
2010 pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2011 break;
2012 }
2013 default:
2014 SkASSERT(0);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002015 }
caryclark@google.coma5764232012-03-28 16:20:21 +00002016 break;
2017 case SkPath::kCubic_Verb:
2018 switch (wn.verb()) {
2019 case SkPath::kLine_Verb: {
2020 pts = CubicLineIntersect(wt.fPts, wn.fPts, ts);
2021 break;
2022 }
2023 case SkPath::kQuad_Verb: {
2024 // FIXME: promote quad to cubic
2025 pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2026 break;
2027 }
2028 case SkPath::kCubic_Verb: {
2029 pts = CubicIntersect(wt.fPts, wn.fPts, ts);
2030 break;
2031 }
2032 default:
2033 SkASSERT(0);
2034 }
2035 break;
2036 default:
2037 SkASSERT(0);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002038 }
caryclark@google.coma5764232012-03-28 16:20:21 +00002039 test->add(ts.fT[swap], pts, wt.verbIndex());
2040 next->add(ts.fT[!swap], pts, wn.verbIndex());
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002041 } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance());
2042 } while (nextPtr != lastPtr);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002043 }
2044}
2045
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002046static InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges,
caryclark@google.com6008c6562012-02-15 22:01:16 +00002047 InEdge** currentPtr, InEdge** lastPtr, SkScalar y) {
2048 InEdge** testPtr = currentPtr - 1;
2049 while (++testPtr != lastPtr) {
2050 if ((*testPtr)->fBounds.fBottom > y) {
2051 continue;
2052 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002053 if (activeEdges) {
2054 InEdge* test = *testPtr;
2055 ActiveEdge* activePtr = activeEdges->begin() - 1;
2056 ActiveEdge* lastActive = activeEdges->end();
2057 while (++activePtr != lastActive) {
2058 if (activePtr->fWorkEdge.fEdge == test) {
2059 activeEdges->remove(activePtr - activeEdges->begin());
2060 break;
2061 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00002062 }
2063 }
2064 if (testPtr == currentPtr) {
2065 ++currentPtr;
2066 }
2067 }
2068 return currentPtr;
2069}
2070
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002071// OPTIMIZE: inline?
2072static HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) {
2073 while ((*edge)->fY < y) {
2074 ++edge;
2075 }
2076 return edge;
2077}
2078
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002079// compute bottom taking into account any intersected edges
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002080static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges,
2081 SkScalar y, SkScalar bottom) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002082 ActiveEdge* activePtr = activeEdges.begin() - 1;
2083 ActiveEdge* lastActive = activeEdges.end();
2084 while (++activePtr != lastActive) {
2085 const InEdge* test = activePtr->fWorkEdge.fEdge;
2086 if (!test->fContainsIntercepts) {
2087 continue;
2088 }
2089 WorkEdge wt;
2090 wt.init(test);
2091 do {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002092 const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()];
caryclark@google.com4917f172012-03-05 22:01:21 +00002093 if (intercepts.fTopIntercepts > 1) {
2094 SkScalar yTop = wt.fPts[0].fY;
2095 if (yTop > y && bottom > yTop) {
2096 bottom = yTop;
2097 }
2098 }
2099 if (intercepts.fBottomIntercepts > 1) {
2100 SkScalar yBottom = wt.fPts[wt.verb()].fY;
2101 if (yBottom > y && bottom > yBottom) {
2102 bottom = yBottom;
2103 }
2104 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002105 const SkTDArray<double>& fTs = intercepts.fTs;
2106 size_t count = fTs.count();
2107 for (size_t index = 0; index < count; ++index) {
caryclark@google.coma5764232012-03-28 16:20:21 +00002108 SkScalar yIntercept;
2109 switch (wt.verb()) {
2110 case SkPath::kLine_Verb: {
2111 yIntercept = LineYAtT(wt.fPts, fTs[index]);
2112 break;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002113 }
caryclark@google.coma5764232012-03-28 16:20:21 +00002114 case SkPath::kQuad_Verb: {
2115 yIntercept = QuadYAtT(wt.fPts, fTs[index]);
2116 break;
2117 }
2118 case SkPath::kCubic_Verb: {
2119 yIntercept = CubicYAtT(wt.fPts, fTs[index]);
2120 break;
2121 }
2122 default:
2123 SkASSERT(0); // should never get here
2124 }
2125 if (yIntercept > y && bottom > yIntercept) {
2126 bottom = yIntercept;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002127 }
2128 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002129 } while (wt.advance());
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002130 }
caryclark@google.com198e0542012-03-30 18:47:02 +00002131#if DEBUG_BOTTOM
2132 SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom);
2133#endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002134 return bottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002135}
2136
2137static SkScalar findBottom(InEdge** currentPtr,
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002138 InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y,
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00002139 bool /*asFill*/, InEdge**& testPtr) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002140 InEdge* current = *currentPtr;
2141 SkScalar bottom = current->fBounds.fBottom;
caryclark@google.com752b60e2012-03-22 21:11:17 +00002142
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002143 // find the list of edges that cross y
caryclark@google.com6008c6562012-02-15 22:01:16 +00002144 InEdge* test = *testPtr;
2145 while (testPtr != edgeListEnd) {
2146 SkScalar testTop = test->fBounds.fTop;
2147 if (bottom <= testTop) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002148 break;
2149 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00002150 SkScalar testBottom = test->fBounds.fBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002151 // OPTIMIZATION: Shortening the bottom is only interesting when filling
2152 // and when the edge is to the left of a longer edge. If it's a framing
2153 // edge, or part of the right, it won't effect the longer edges.
caryclark@google.com6008c6562012-02-15 22:01:16 +00002154 if (testTop > y) {
2155 bottom = testTop;
2156 break;
2157 }
2158 if (y < testBottom) {
2159 if (bottom > testBottom) {
2160 bottom = testBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002161 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002162 if (activeEdges) {
2163 addToActive(*activeEdges, test);
2164 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002165 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00002166 test = *++testPtr;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002167 }
caryclark@google.com198e0542012-03-30 18:47:02 +00002168#if DEBUG_BOTTOM
2169 SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom);
2170#endif
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002171 return bottom;
2172}
2173
2174static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel,
2175 SkTDArray<InEdge*>& edgeList) {
2176 size_t edgeCount = edges.count();
2177 if (edgeCount == 0) {
2178 return;
2179 }
caryclark@google.comfb173422012-04-10 18:28:55 +00002180 int id = 0;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002181 for (size_t index = 0; index < edgeCount; ++index) {
caryclark@google.comfb173422012-04-10 18:28:55 +00002182 InEdge& edge = edges[index];
2183 if (!edge.fWinding) {
2184 continue;
2185 }
2186 edge.fID = ++id;
2187 *edgeList.append() = &edge;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002188 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002189 *edgeList.append() = &edgeSentinel;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00002190 QSort<InEdge>(edgeList.begin(), edgeList.end() - 1);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002191}
2192
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002193static void makeHorizontalList(SkTDArray<HorizontalEdge>& edges,
2194 HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) {
2195 size_t edgeCount = edges.count();
2196 if (edgeCount == 0) {
2197 return;
2198 }
2199 for (size_t index = 0; index < edgeCount; ++index) {
2200 *edgeList.append() = &edges[index];
2201 }
2202 edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax;
2203 *edgeList.append() = &edgeSentinel;
2204 QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1);
2205}
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002206
2207static void skipCoincidence(int lastWinding, int winding, int windingMask,
2208 ActiveEdge* activePtr, ActiveEdge* firstCoincident) {
2209 if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) {
2210 return;
2211 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002212 // FIXME: ? shouldn't this be if (lastWinding & windingMask) ?
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002213 if (lastWinding) {
caryclark@google.com752b60e2012-03-22 21:11:17 +00002214#if DEBUG_ADJUST_COINCIDENT
2215 SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID());
2216#endif
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002217 activePtr->fSkip = false;
2218 } else {
caryclark@google.com752b60e2012-03-22 21:11:17 +00002219#if DEBUG_ADJUST_COINCIDENT
2220 SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID());
2221#endif
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002222 firstCoincident->fSkip = false;
2223 }
2224}
2225
caryclark@google.com6008c6562012-02-15 22:01:16 +00002226static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges,
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002227 SkTDArray<ActiveEdge*>& edgeList, SkScalar y) {
caryclark@google.com6008c6562012-02-15 22:01:16 +00002228 size_t edgeCount = activeEdges.count();
2229 if (edgeCount == 0) {
2230 return;
2231 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002232#if DEBUG_SORT_HORIZONTAL
caryclark@google.comd88e0892012-03-27 13:23:51 +00002233 const int tab = 3; // FIXME: debugging only
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002234 SkDebugf("%s y=%1.9g\n", __FUNCTION__, y);
2235#endif
caryclark@google.com6008c6562012-02-15 22:01:16 +00002236 size_t index;
2237 for (index = 0; index < edgeCount; ++index) {
2238 ActiveEdge& activeEdge = activeEdges[index];
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002239 do {
2240 activeEdge.calcLeft(y);
2241 // skip segments that don't span y
2242 if (activeEdge.fAbove != activeEdge.fBelow) {
2243 break;
2244 }
2245 if (activeEdge.fDone) {
2246#if DEBUG_SORT_HORIZONTAL
2247 SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID());
2248#endif
2249 goto nextEdge;
2250 }
2251#if DEBUG_SORT_HORIZONTAL
2252 SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID());
2253#endif
2254 } while (activeEdge.advanceT() || activeEdge.advance());
2255#if DEBUG_SORT_HORIZONTAL
2256 SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)"
2257 " (%1.9g)\n", tab, "", activeEdge.ID(),
2258 activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove,
2259 activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow);
2260#endif
2261 activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false;
caryclark@google.com6008c6562012-02-15 22:01:16 +00002262 *edgeList.append() = &activeEdge;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002263nextEdge:
2264 ;
caryclark@google.com6008c6562012-02-15 22:01:16 +00002265 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +00002266 QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002267}
2268
2269// remove coincident edges
2270// OPTIMIZE: remove edges? This is tricky because the current logic expects
2271// the winding count to be maintained while skipping coincident edges. In
2272// addition to removing the coincident edges, the remaining edges would need
2273// to have a different winding value, possibly different per intercept span.
2274static SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList,
2275 int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder)
2276{
2277#if DEBUG_ADJUST_COINCIDENT
2278 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom);
2279#endif
2280 size_t edgeCount = edgeList.count();
2281 if (edgeCount == 0) {
2282 return bottom;
2283 }
caryclark@google.com78e17132012-04-17 11:40:34 +00002284 ActiveEdge* activePtr, * nextPtr = edgeList[0];
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002285 size_t index;
2286 bool foundCoincident = false;
caryclark@google.comf25edfe2012-06-01 18:20:10 +00002287 size_t firstIndex = 0;
caryclark@google.com6008c6562012-02-15 22:01:16 +00002288 for (index = 1; index < edgeCount; ++index) {
caryclark@google.com78e17132012-04-17 11:40:34 +00002289 activePtr = nextPtr;
2290 nextPtr = edgeList[index];
caryclark@google.comfa0588f2012-04-26 21:01:06 +00002291 if (firstIndex != index - 1 && activePtr->fVerb > SkPath::kLine_Verb
2292 && nextPtr->fVerb == SkPath::kLine_Verb
2293 && activePtr->isUnordered(nextPtr)) {
2294 // swap the line with the curve
2295 // back up to the previous edge and retest
2296 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
2297 SkASSERT(index > 1);
2298 index -= 2;
2299 nextPtr = edgeList[index];
2300 continue;
caryclark@google.com78e17132012-04-17 11:40:34 +00002301 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002302 bool closeCall = false;
2303 activePtr->fCoincident = firstIndex;
caryclark@google.com78e17132012-04-17 11:40:34 +00002304 if (activePtr->isCoincidentWith(nextPtr)
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002305 || (closeCall = activePtr->tooCloseToCall(nextPtr))) {
2306 activePtr->fSkip = nextPtr->fSkip = foundCoincident = true;
2307 activePtr->fCloseCall = nextPtr->fCloseCall = closeCall;
caryclark@google.com78e17132012-04-17 11:40:34 +00002308 } else if (activePtr->isUnordered(nextPtr)) {
2309 foundCoincident = true;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002310 } else {
2311 firstIndex = index;
2312 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002313 }
caryclark@google.com78e17132012-04-17 11:40:34 +00002314 nextPtr->fCoincident = firstIndex;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002315 if (!foundCoincident) {
2316 return bottom;
2317 }
2318 int winding = 0;
caryclark@google.com78e17132012-04-17 11:40:34 +00002319 nextPtr = edgeList[0];
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002320 for (index = 1; index < edgeCount; ++index) {
2321 int priorWinding = winding;
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002322 winding += activePtr->fWorkEdge.winding();
caryclark@google.com78e17132012-04-17 11:40:34 +00002323 activePtr = nextPtr;
2324 nextPtr = edgeList[index];
2325 SkASSERT(activePtr == edgeList[index - 1]);
2326 SkASSERT(nextPtr == edgeList[index]);
2327 if (activePtr->fCoincident != nextPtr->fCoincident) {
2328 continue;
2329 }
2330 // the coincident edges may not have been sorted above -- advance
2331 // the edges and resort if needed
2332 // OPTIMIZE: if sorting is done incrementally as new edges are added
2333 // and not all at once as is done here, fold this test into the
2334 // current less than test.
2335 while ((!activePtr->fSkip || !nextPtr->fSkip)
2336 && activePtr->fCoincident == nextPtr->fCoincident) {
2337 if (activePtr->swapUnordered(nextPtr, bottom)) {
2338 winding -= activePtr->fWorkEdge.winding();
2339 SkASSERT(activePtr == edgeList[index - 1]);
2340 SkASSERT(nextPtr == edgeList[index]);
2341 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
2342 if (--index == 0) {
2343 winding += activePtr->fWorkEdge.winding();
2344 break;
2345 }
2346 // back up one
2347 activePtr = edgeList[index - 1];
2348 continue;
2349 }
2350 SkASSERT(activePtr == edgeList[index - 1]);
2351 SkASSERT(nextPtr == edgeList[index]);
2352 break;
2353 }
2354 if (activePtr->fSkip && nextPtr->fSkip) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002355 if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr,
2356 priorWinding, winding, windingMask)
2357 : activePtr->swapCoincident(nextPtr, bottom)) {
caryclark@google.com4917f172012-03-05 22:01:21 +00002358 winding -= activePtr->fWorkEdge.winding();
caryclark@google.com78e17132012-04-17 11:40:34 +00002359 SkASSERT(activePtr == edgeList[index - 1]);
2360 SkASSERT(nextPtr == edgeList[index]);
caryclark@google.comcd4421d2012-03-01 19:16:31 +00002361 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
2362 SkTSwap<ActiveEdge*>(activePtr, nextPtr);
caryclark@google.com4917f172012-03-05 22:01:21 +00002363 winding += activePtr->fWorkEdge.winding();
caryclark@google.com78e17132012-04-17 11:40:34 +00002364 SkASSERT(activePtr == edgeList[index - 1]);
2365 SkASSERT(nextPtr == edgeList[index]);
caryclark@google.comcd4421d2012-03-01 19:16:31 +00002366 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002367 }
2368 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002369 int firstCoincidentWinding = 0;
2370 ActiveEdge* firstCoincident = NULL;
2371 winding = 0;
2372 activePtr = edgeList[0];
2373 for (index = 1; index < edgeCount; ++index) {
2374 int priorWinding = winding;
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002375 winding += activePtr->fWorkEdge.winding();
caryclark@google.com78e17132012-04-17 11:40:34 +00002376 nextPtr = edgeList[index];
2377 if (activePtr->fSkip && nextPtr->fSkip
2378 && activePtr->fCoincident == nextPtr->fCoincident) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002379 if (!firstCoincident) {
2380 firstCoincident = activePtr;
2381 firstCoincidentWinding = priorWinding;
2382 }
2383 if (activePtr->fCloseCall) {
2384 // If one of the edges has already been added to out as a non
2385 // coincident edge, trim it back to the top of this span
2386 if (outBuilder.trimLine(y, activePtr->ID())) {
2387 activePtr->addTatYAbove(y);
caryclark@google.com752b60e2012-03-22 21:11:17 +00002388 #if DEBUG_ADJUST_COINCIDENT
2389 SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n",
2390 __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom);
2391 #endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002392 activePtr->fYBottom = y;
2393 }
2394 if (outBuilder.trimLine(y, nextPtr->ID())) {
2395 nextPtr->addTatYAbove(y);
caryclark@google.com752b60e2012-03-22 21:11:17 +00002396 #if DEBUG_ADJUST_COINCIDENT
2397 SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n",
2398 __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom);
2399 #endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002400 nextPtr->fYBottom = y;
2401 }
2402 // add missing t values so edges can be the same length
2403 SkScalar testY = activePtr->fBelow.fY;
2404 nextPtr->addTatYBelow(testY);
2405 if (bottom > testY && testY > y) {
caryclark@google.com752b60e2012-03-22 21:11:17 +00002406 #if DEBUG_ADJUST_COINCIDENT
2407 SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n",
2408 __FUNCTION__, activePtr->ID(), testY, bottom);
2409 #endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002410 bottom = testY;
2411 }
2412 testY = nextPtr->fBelow.fY;
2413 activePtr->addTatYBelow(testY);
2414 if (bottom > testY && testY > y) {
caryclark@google.com752b60e2012-03-22 21:11:17 +00002415 #if DEBUG_ADJUST_COINCIDENT
2416 SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n",
2417 __FUNCTION__, nextPtr->ID(), testY, bottom);
2418 #endif
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002419 bottom = testY;
2420 }
2421 }
2422 } else if (firstCoincident) {
2423 skipCoincidence(firstCoincidentWinding, winding, windingMask,
2424 activePtr, firstCoincident);
2425 firstCoincident = NULL;
2426 }
2427 activePtr = nextPtr;
2428 }
2429 if (firstCoincident) {
2430 winding += activePtr->fWorkEdge.winding();
2431 skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr,
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00002432 firstCoincident);
2433 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002434 // fix up the bottom for close call edges. OPTIMIZATION: maybe this could
2435 // be in the loop above, but moved here since loop above reads fBelow and
2436 // it felt unsafe to write it in that loop
2437 for (index = 0; index < edgeCount; ++index) {
2438 (edgeList[index])->fixBelow();
2439 }
2440 return bottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002441}
2442
2443// stitch edge and t range that satisfies operation
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00002444static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar
2445#if DEBUG_STITCH_EDGE
2446y
2447#endif
2448,
caryclark@google.com752b60e2012-03-22 21:11:17 +00002449 SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002450 int winding = 0;
caryclark@google.com6008c6562012-02-15 22:01:16 +00002451 ActiveEdge** activeHandle = edgeList.begin() - 1;
2452 ActiveEdge** lastActive = edgeList.end();
caryclark@google.com78e17132012-04-17 11:40:34 +00002453#if DEBUG_STITCH_EDGE
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00002454 const int tab = 7; // FIXME: debugging only
caryclark@google.com78e17132012-04-17 11:40:34 +00002455 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom);
2456#endif
caryclark@google.com6008c6562012-02-15 22:01:16 +00002457 while (++activeHandle != lastActive) {
2458 ActiveEdge* activePtr = *activeHandle;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002459 const WorkEdge& wt = activePtr->fWorkEdge;
2460 int lastWinding = winding;
2461 winding += wt.winding();
caryclark@google.com78e17132012-04-17 11:40:34 +00002462#if DEBUG_STITCH_EDGE
2463 SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d"
2464 " above=%1.9g below=%1.9g\n",
2465 tab-4, "", activePtr->ID(), lastWinding,
2466 winding, activePtr->fSkip, activePtr->fCloseCall,
2467 activePtr->fTAbove, activePtr->fTBelow);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002468#endif
caryclark@google.com752b60e2012-03-22 21:11:17 +00002469 if (activePtr->done(bottom)) {
caryclark@google.com78e17132012-04-17 11:40:34 +00002470#if DEBUG_STITCH_EDGE
2471 SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "",
2472 activePtr->fDone, activePtr->fYBottom);
2473#endif
caryclark@google.com752b60e2012-03-22 21:11:17 +00002474 continue;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002475 }
caryclark@google.comc17972e2012-02-20 21:33:22 +00002476 int opener = (lastWinding & windingMask) == 0;
2477 bool closer = (winding & windingMask) == 0;
2478 SkASSERT(!opener | !closer);
2479 bool inWinding = opener | closer;
caryclark@google.coma5764232012-03-28 16:20:21 +00002480 SkPoint clippedPts[4];
caryclark@google.com4917f172012-03-05 22:01:21 +00002481 const SkPoint* clipped = NULL;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002482 bool moreToDo, aboveBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002483 do {
2484 double currentT = activePtr->t();
2485 const SkPoint* points = wt.fPts;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002486 double nextT;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00002487 SkPath::Verb verb = activePtr->fVerb;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002488 do {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002489 nextT = activePtr->nextT();
caryclark@google.coma5764232012-03-28 16:20:21 +00002490 // FIXME: obtuse: want efficient way to say
2491 // !currentT && currentT != 1 || !nextT && nextT != 1
2492 if (currentT * nextT != 0 || currentT + nextT != 1) {
2493 // OPTIMIZATION: if !inWinding, we only need
2494 // clipped[1].fY
2495 switch (verb) {
2496 case SkPath::kLine_Verb:
2497 LineSubDivide(points, currentT, nextT, clippedPts);
2498 break;
2499 case SkPath::kQuad_Verb:
2500 QuadSubDivide(points, currentT, nextT, clippedPts);
2501 break;
2502 case SkPath::kCubic_Verb:
2503 CubicSubDivide(points, currentT, nextT, clippedPts);
2504 break;
2505 default:
2506 SkASSERT(0);
2507 break;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002508 }
caryclark@google.coma5764232012-03-28 16:20:21 +00002509 clipped = clippedPts;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002510 } else {
caryclark@google.coma5764232012-03-28 16:20:21 +00002511 clipped = points;
2512 }
2513 if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY
2514 != clipped[verb].fY : clipped[0] != clipped[verb])) {
caryclark@google.comfb173422012-04-10 18:28:55 +00002515#if DEBUG_STITCH_EDGE
2516 SkDebugf("%*s add%s %1.9g,%1.9g %1.9g,%1.9g edge=%d"
2517 " v=%d t=(%1.9g,%1.9g)\n", tab, "",
2518 kUVerbStr[verb], clipped[0].fX, clipped[0].fY,
2519 clipped[verb].fX, clipped[verb].fY,
2520 activePtr->ID(),
2521 activePtr->fWorkEdge.fVerb
2522 - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
2523 currentT, nextT);
2524#endif
caryclark@google.coma5764232012-03-28 16:20:21 +00002525 outBuilder.addCurve(clipped, (SkPath::Verb) verb,
2526 activePtr->fWorkEdge.fEdge->fID,
2527 activePtr->fCloseCall);
2528 } else {
caryclark@google.comfb173422012-04-10 18:28:55 +00002529#if DEBUG_STITCH_EDGE
2530 SkDebugf("%*s skip%s %1.9g,%1.9g %1.9g,%1.9g"
2531 " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "",
2532 kUVerbStr[verb], clipped[0].fX, clipped[0].fY,
2533 clipped[verb].fX, clipped[verb].fY,
2534 activePtr->ID(),
2535 activePtr->fWorkEdge.fVerb
2536 - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
2537 currentT, nextT);
2538#endif
caryclark@google.coma5764232012-03-28 16:20:21 +00002539 }
2540 // by advancing fAbove/fBelow, the next call to sortHorizontal
2541 // will use these values if they're still valid instead of
2542 // recomputing
caryclark@google.com78e17132012-04-17 11:40:34 +00002543 if (clipped[verb].fY > activePtr->fBelow.fY
caryclark@google.comfa0588f2012-04-26 21:01:06 +00002544 && bottom >= activePtr->fBelow.fY
2545 && verb == SkPath::kLine_Verb) {
caryclark@google.coma5764232012-03-28 16:20:21 +00002546 activePtr->fAbove = activePtr->fBelow;
caryclark@google.comfa0588f2012-04-26 21:01:06 +00002547 activePtr->fBelow = activePtr->fTangent = clipped[verb];
caryclark@google.com78e17132012-04-17 11:40:34 +00002548 activePtr->fTAbove = activePtr->fTBelow < 1
2549 ? activePtr->fTBelow : 0;
caryclark@google.coma5764232012-03-28 16:20:21 +00002550 activePtr->fTBelow = nextT;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002551 }
2552 currentT = nextT;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002553 moreToDo = activePtr->advanceT();
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002554 activePtr->fYBottom = clipped[verb].fY; // was activePtr->fCloseCall ? bottom :
2555
2556 // clearing the fSkip/fCloseCall bit here means that trailing edges
2557 // fall out of sync, if one edge is long and another is a series of short pieces
2558 // if fSkip/fCloseCall is set, need to recompute coincidence/too-close-to-call
2559 // after advancing
2560 // another approach would be to restrict bottom to smaller part of close call
2561 // maybe this is already happening with coincidence when intersection is computed,
2562 // and needs to be added to the close call computation as well
2563 // this is hard to do because that the bottom is important is not known when
2564 // the lines are intersected; only when the computation for edge sorting is done
2565 // does the need for new bottoms become apparent.
2566 // maybe this is good incentive to scrap the current sort and do an insertion
2567 // sort that can take this into consideration when the x value is computed
2568
2569 // FIXME: initialized in sortHorizontal, cleared here as well so
2570 // that next edge is not skipped -- but should skipped edges ever
2571 // continue? (probably not)
caryclark@google.com752b60e2012-03-22 21:11:17 +00002572 aboveBottom = clipped[verb].fY < bottom;
2573 if (clipped[0].fY != clipped[verb].fY) {
2574 activePtr->fSkip = false;
2575 activePtr->fCloseCall = false;
2576 aboveBottom &= !activePtr->fCloseCall;
caryclark@google.com78e17132012-04-17 11:40:34 +00002577 }
2578#if DEBUG_STITCH_EDGE
2579 else {
caryclark@google.com752b60e2012-03-22 21:11:17 +00002580 if (activePtr->fSkip || activePtr->fCloseCall) {
caryclark@google.com78e17132012-04-17 11:40:34 +00002581 SkDebugf("%s skip or close == %1.9g\n", __FUNCTION__,
2582 clippedPts[0].fY);
caryclark@google.com752b60e2012-03-22 21:11:17 +00002583 }
2584 }
caryclark@google.com78e17132012-04-17 11:40:34 +00002585#endif
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002586 } while (moreToDo & aboveBottom);
2587 } while ((moreToDo || activePtr->advance()) & aboveBottom);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002588 }
2589}
2590
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00002591#if DEBUG_DUMP
caryclark@google.com198e0542012-03-30 18:47:02 +00002592static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList,
2593 const InEdge& edgeSentinel) {
caryclark@google.com198e0542012-03-30 18:47:02 +00002594 InEdge** debugPtr = edgeList.begin();
2595 do {
2596 (*debugPtr++)->dump();
2597 } while (*debugPtr != &edgeSentinel);
caryclark@google.com198e0542012-03-30 18:47:02 +00002598}
caryclark@google.coma3f05fa2012-06-01 17:44:28 +00002599#else
2600static void dumpEdgeList(const SkTDArray<InEdge*>& ,
2601 const InEdge& ) {
2602}
2603#endif
caryclark@google.com198e0542012-03-30 18:47:02 +00002604
caryclark@google.comc6825902012-02-03 22:07:47 +00002605void simplify(const SkPath& path, bool asFill, SkPath& simple) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002606 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
2607 int windingMask = (path.getFillType() & 1) ? 1 : -1;
2608 simple.reset();
2609 simple.setFillType(SkPath::kEvenOdd_FillType);
caryclark@google.comc6825902012-02-03 22:07:47 +00002610 // turn path into list of edges increasing in y
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00002611 // if an edge is a quad or a cubic with a y extrema, note it, but leave it
2612 // unbroken. Once we have a list, sort it, then walk the list (walk edges
2613 // twice that have y extrema's on top) and detect crossings -- look for raw
2614 // bounds that cross over, then tight bounds that cross
caryclark@google.com6680fb12012-02-07 22:10:51 +00002615 SkTArray<InEdge> edges;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002616 SkTDArray<HorizontalEdge> horizontalEdges;
2617 InEdgeBuilder builder(path, asFill, edges, horizontalEdges);
caryclark@google.com6680fb12012-02-07 22:10:51 +00002618 SkTDArray<InEdge*> edgeList;
caryclark@google.com6680fb12012-02-07 22:10:51 +00002619 InEdge edgeSentinel;
caryclark@google.comfb173422012-04-10 18:28:55 +00002620 edgeSentinel.reset();
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002621 makeEdgeList(edges, edgeSentinel, edgeList);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002622 SkTDArray<HorizontalEdge*> horizontalList;
2623 HorizontalEdge horizontalSentinel;
2624 makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList);
caryclark@google.com6680fb12012-02-07 22:10:51 +00002625 InEdge** currentPtr = edgeList.begin();
caryclark@google.com4917f172012-03-05 22:01:21 +00002626 if (!currentPtr) {
2627 return;
2628 }
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002629 // find all intersections between edges
2630// beyond looking for horizontal intercepts, we need to know if any active edges
2631// intersect edges below 'bottom', but above the active edge segment.
2632// maybe it makes more sense to compute all intercepts before doing anything
2633// else, since the intercept list is long-lived, at least in the current design.
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002634 SkScalar y = (*currentPtr)->fBounds.fTop;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002635 HorizontalEdge** currentHorizontal = horizontalList.begin();
caryclark@google.comc6825902012-02-03 22:07:47 +00002636 do {
caryclark@google.com6680fb12012-02-07 22:10:51 +00002637 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002638 SkScalar bottom = findBottom(currentPtr, edgeList.end(),
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002639 NULL, y, asFill, lastPtr);
caryclark@google.comc17972e2012-02-20 21:33:22 +00002640 if (lastPtr > currentPtr) {
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002641 if (currentHorizontal) {
2642 if ((*currentHorizontal)->fY < SK_ScalarMax) {
2643 addBottomT(currentPtr, lastPtr, currentHorizontal);
2644 }
2645 currentHorizontal = advanceHorizontal(currentHorizontal, bottom);
2646 }
caryclark@google.comc17972e2012-02-20 21:33:22 +00002647 addIntersectingTs(currentPtr, lastPtr);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002648 }
2649 y = bottom;
2650 currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y);
2651 } while (*currentPtr != &edgeSentinel);
caryclark@google.com198e0542012-03-30 18:47:02 +00002652 // if a quadratic or cubic now has an intermediate T value, see if the Ts
2653 // on either side cause the Y values to monotonically increase. If not, split
2654 // the curve at the new T.
caryclark@google.comfa0588f2012-04-26 21:01:06 +00002655
2656 // try an alternate approach which does not split curves or stitch edges
2657 // (may still need adjustCoincident, though)
2658 // the idea is to output non-intersecting contours, then figure out their
2659 // respective winding contribution
2660 // each contour will need to know whether it is CW or CCW, and then whether
2661 // a ray from that contour hits any a contour that contains it. The ray can
2662 // move to the left and then arbitrarily move up or down (as long as it never
2663 // moves to the right) to find a reference sibling contour or containing
2664 // contour. If the contour is part of an intersection, the companion contour
2665 // that is part of the intersection can determine the containership.
caryclark@google.com198e0542012-03-30 18:47:02 +00002666 if (builder.containsCurves()) {
2667 currentPtr = edgeList.begin();
2668 SkTArray<InEdge> splits;
2669 do {
caryclark@google.comfb173422012-04-10 18:28:55 +00002670 (*currentPtr)->splitInflectionPts(splits);
caryclark@google.com198e0542012-03-30 18:47:02 +00002671 } while (*++currentPtr != &edgeSentinel);
2672 if (splits.count()) {
caryclark@google.com198e0542012-03-30 18:47:02 +00002673 for (int index = 0; index < splits.count(); ++index) {
2674 edges.push_back(splits[index]);
2675 }
caryclark@google.comfb173422012-04-10 18:28:55 +00002676 edgeList.reset();
caryclark@google.com198e0542012-03-30 18:47:02 +00002677 makeEdgeList(edges, edgeSentinel, edgeList);
2678 }
2679 }
2680 dumpEdgeList(edgeList, edgeSentinel);
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002681 // walk the sorted edges from top to bottom, computing accumulated winding
2682 SkTDArray<ActiveEdge> activeEdges;
2683 OutEdgeBuilder outBuilder(asFill);
2684 currentPtr = edgeList.begin();
2685 y = (*currentPtr)->fBounds.fTop;
2686 do {
2687 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set
2688 SkScalar bottom = findBottom(currentPtr, edgeList.end(),
2689 &activeEdges, y, asFill, lastPtr);
2690 if (lastPtr > currentPtr) {
2691 bottom = computeInterceptBottom(activeEdges, y, bottom);
caryclark@google.comc17972e2012-02-20 21:33:22 +00002692 SkTDArray<ActiveEdge*> activeEdgeList;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002693 sortHorizontal(activeEdges, activeEdgeList, y);
2694 bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom,
2695 outBuilder);
caryclark@google.com752b60e2012-03-22 21:11:17 +00002696 stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder);
caryclark@google.comc17972e2012-02-20 21:33:22 +00002697 }
caryclark@google.comc6825902012-02-03 22:07:47 +00002698 y = bottom;
caryclark@google.com2e7f4c82012-03-20 21:11:59 +00002699 // OPTIMIZATION: as edges expire, InEdge allocations could be released
2700 currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y);
caryclark@google.comc6825902012-02-03 22:07:47 +00002701 } while (*currentPtr != &edgeSentinel);
caryclark@google.comc6825902012-02-03 22:07:47 +00002702 // assemble output path from string of pts, verbs
caryclark@google.comf8b000d2012-02-09 22:04:27 +00002703 outBuilder.bridge();
2704 outBuilder.assemble(simple);
caryclark@google.comc6825902012-02-03 22:07:47 +00002705}