OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright 2012 Google Inc. | |
3 * | |
4 * Use of this source code is governed by a BSD-style license that can be | |
5 * found in the LICENSE file. | |
6 */ | |
7 | |
8 #include "Simplify.h" | |
9 | |
10 #undef SkASSERT | |
11 #define SkASSERT(cond) while (!(cond)) { sk_throw(); } | |
12 | |
13 // FIXME: remove once debugging is complete | |
14 #if 01 // set to 1 for no debugging whatsoever | |
15 | |
16 //const bool gRunTestsInOneThread = false; | |
17 | |
18 #define DEBUG_ACTIVE_LESS_THAN 0 | |
19 #define DEBUG_ADD 0 | |
20 #define DEBUG_ADD_BOTTOM_TS 0 | |
21 #define DEBUG_ADD_INTERSECTING_TS 0 | |
22 #define DEBUG_ADJUST_COINCIDENT 0 | |
23 #define DEBUG_ASSEMBLE 0 | |
24 #define DEBUG_BOTTOM 0 | |
25 #define DEBUG_BRIDGE 0 | |
26 #define DEBUG_DUMP 0 | |
27 #define DEBUG_SORT_HORIZONTAL 0 | |
28 #define DEBUG_OUT 0 | |
29 #define DEBUG_OUT_LESS_THAN 0 | |
30 #define DEBUG_SPLIT 0 | |
31 #define DEBUG_STITCH_EDGE 0 | |
32 #define DEBUG_TRIM_LINE 0 | |
33 | |
34 #else | |
35 | |
36 //const bool gRunTestsInOneThread = true; | |
37 | |
38 #define DEBUG_ACTIVE_LESS_THAN 0 | |
39 #define DEBUG_ADD 01 | |
40 #define DEBUG_ADD_BOTTOM_TS 0 | |
41 #define DEBUG_ADD_INTERSECTING_TS 0 | |
42 #define DEBUG_ADJUST_COINCIDENT 1 | |
43 #define DEBUG_ASSEMBLE 1 | |
44 #define DEBUG_BOTTOM 0 | |
45 #define DEBUG_BRIDGE 1 | |
46 #define DEBUG_DUMP 1 | |
47 #define DEBUG_SORT_HORIZONTAL 01 | |
48 #define DEBUG_OUT 01 | |
49 #define DEBUG_OUT_LESS_THAN 0 | |
50 #define DEBUG_SPLIT 1 | |
51 #define DEBUG_STITCH_EDGE 1 | |
52 #define DEBUG_TRIM_LINE 1 | |
53 | |
54 #endif | |
55 | |
56 #if DEBUG_ASSEMBLE || DEBUG_BRIDGE | |
57 static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; | |
58 #endif | |
59 #if DEBUG_STITCH_EDGE | |
60 static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; | |
61 #endif | |
62 | |
63 static int LineIntersect(const SkPoint a[2], const SkPoint b[2], | |
64 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); | |
68 } | |
69 | |
70 static 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}}; | |
74 intersect(aQuad, bLine, intersections); | |
75 return intersections.fUsed; | |
76 } | |
77 | |
78 static 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}}; | |
83 return intersect(aCubic, bLine, intersections); | |
84 } | |
85 | |
86 static 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}}; | |
90 intersect2(aQuad, bQuad, intersections); | |
91 return intersections.fUsed; | |
92 } | |
93 | |
94 static 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}}; | |
100 intersect(aCubic, bCubic, intersections); | |
101 return intersections.fUsed; | |
102 } | |
103 | |
104 static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, | |
105 SkScalar y, double aRange[2]) { | |
106 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; | |
107 return horizontalLineIntersect(aLine, left, right, y, aRange); | |
108 } | |
109 | |
110 static 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 | |
116 static 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 | |
123 static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { | |
124 const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; | |
125 double x, y; | |
126 xy_at_t(line, t, x, y); | |
127 out->fX = SkDoubleToScalar(x); | |
128 out->fY = SkDoubleToScalar(y); | |
129 } | |
130 | |
131 static 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); | |
137 } | |
138 | |
139 static 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); | |
146 } | |
147 | |
148 static SkScalar LineYAtT(const SkPoint a[2], double t) { | |
149 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; | |
150 double y; | |
151 xy_at_t(aLine, t, *(double*) 0, y); | |
152 return SkDoubleToScalar(y); | |
153 } | |
154 | |
155 static 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 | |
162 static 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 | |
170 static void LineSubDivide(const SkPoint a[2], double startT, double endT, | |
171 SkPoint sub[2]) { | |
172 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; | |
173 _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 | |
181 static void QuadSubDivide(const SkPoint a[3], double startT, double endT, | |
182 SkPoint sub[3]) { | |
183 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, | |
184 {a[2].fX, a[2].fY}}; | |
185 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); | |
193 } | |
194 | |
195 static void CubicSubDivide(const SkPoint a[4], double startT, double endT, | |
196 SkPoint sub[4]) { | |
197 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}}; | |
199 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 } | |
210 | |
211 static 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 | |
222 static 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 | |
233 static 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, kReduceOrder_TreatAsFill); | |
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 | |
249 static 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, kReduce
Order_TreatAsFill); | |
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 | |
265 static 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 | |
272 /* | |
273 list of edges | |
274 bounds for edge | |
275 sort | |
276 active T | |
277 | |
278 if 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 al
one | |
287 | |
288 */ | |
289 | |
290 void 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 | |
328 static 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 } | |
336 | |
337 // OPTIMIZATION: this should point to a list of input data rather than duplicati
ng | |
338 // the line data here. This would reduce the need to assemble the results. | |
339 struct OutEdge { | |
340 bool operator<(const OutEdge& rh) const { | |
341 const SkPoint& first = fPts[0]; | |
342 const SkPoint& rhFirst = rh.fPts[0]; | |
343 return first.fY == rhFirst.fY | |
344 ? first.fX < rhFirst.fX | |
345 : first.fY < rhFirst.fY; | |
346 } | |
347 | |
348 SkPoint fPts[4]; | |
349 int fID; // id of edge generating data | |
350 uint8_t fVerb; // FIXME: not read from everywhere | |
351 bool fCloseCall; // edge is trimmable if not originally coincident | |
352 }; | |
353 | |
354 class OutEdgeBuilder { | |
355 public: | |
356 OutEdgeBuilder(bool fill) | |
357 : fFill(fill) { | |
358 } | |
359 | |
360 void addCurve(const SkPoint line[4], SkPath::Verb verb, int id, | |
361 bool closeCall) { | |
362 OutEdge& newEdge = fEdges.push_back(); | |
363 memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint)); | |
364 newEdge.fVerb = verb; | |
365 newEdge.fID = id; | |
366 newEdge.fCloseCall = closeCall; | |
367 } | |
368 | |
369 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; | |
387 #if DEBUG_TRIM_LINE | |
388 SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, | |
389 edge.fPts[1].fX, y); | |
390 #endif | |
391 return true; | |
392 } | |
393 return false; | |
394 } | |
395 | |
396 void assemble(SkPath& simple) { | |
397 size_t listCount = fEdges.count(); | |
398 if (listCount == 0) { | |
399 return; | |
400 } | |
401 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 } | |
410 int closeEdgeIndex = -listIndex - 1; | |
411 // the curve is deferred and not added right away because the | |
412 // following edge may extend the first curve. | |
413 SkPoint firstPt, lastCurve[4]; | |
414 uint8_t lastVerb; | |
415 #if DEBUG_ASSEMBLE | |
416 int firstIndex, lastIndex; | |
417 const int tab = 8; | |
418 #endif | |
419 bool doMove = true; | |
420 int edgeIndex; | |
421 do { | |
422 SkPoint* ptArray = fEdges[listIndex].fPts; | |
423 uint8_t verb = fEdges[listIndex].fVerb; | |
424 SkPoint* curve[4]; | |
425 if (advance < 0) { | |
426 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]; | |
432 } else { | |
433 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]; | |
442 } | |
443 if (doMove) { | |
444 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]; | |
453 } | |
454 doMove = false; | |
455 } else { | |
456 bool gap = lastCurve[lastVerb] != *curve[0]; | |
457 if (gap || lastVerb != SkPath::kLine_Verb) { // output the a
ccumulated curve before the gap | |
458 // FIXME: see comment in bridge -- this probably | |
459 // conceals errors | |
460 SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY, | |
461 curve[0]->fY) <= 10); | |
462 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; | |
475 } | |
476 #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 | |
481 } | |
482 int firstCopy = 1; | |
483 if (gap || (lastVerb == SkPath::kLine_Verb | |
484 && (verb != SkPath::kLine_Verb | |
485 || !extendLine(lastCurve, *curve[verb])))) { | |
486 // FIXME: see comment in bridge -- this probably | |
487 // conceals errors | |
488 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; | |
499 } | |
500 for (int index = firstCopy; index <= verb; ++index) { | |
501 lastCurve[index] = *curve[index]; | |
502 } | |
503 } | |
504 lastVerb = verb; | |
505 #if DEBUG_ASSEMBLE | |
506 lastIndex = listIndex; | |
507 #endif | |
508 if (advance < 0) { | |
509 edgeIndex = fTops[listIndex]; | |
510 fTops[listIndex] = 0; | |
511 } else { | |
512 edgeIndex = fBottoms[listIndex]; | |
513 fBottoms[listIndex] = 0; | |
514 } | |
515 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) { | |
524 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 | |
543 if (lastCurve[lastVerb] != firstPt) { | |
544 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 | |
549 } | |
550 simple.close(); | |
551 #if DEBUG_ASSEMBLE | |
552 SkDebugf("%*s close\n", tab, ""); | |
553 #endif | |
554 break; | |
555 } | |
556 // 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 | |
562 if (advance > 0 ^ edgeIndex < 0) { | |
563 advance = -advance; | |
564 } | |
565 } while (edgeIndex); | |
566 } while (true); | |
567 } | |
568 | |
569 // 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) { | |
581 #if DEBUG_OUT_LESS_THAN | |
582 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTI
ON__, | |
583 one, two, startPt1.fY, startPt2.fY, | |
584 startPt1.fY < startPt2.fY ? "true" : "false"); | |
585 #endif | |
586 return startPt1.fY < startPt2.fY; | |
587 } | |
588 if (startPt1.fX != startPt2.fX) { | |
589 #if DEBUG_OUT_LESS_THAN | |
590 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTI
ON__, | |
591 one, two, startPt1.fX, startPt2.fX, | |
592 startPt1.fX < startPt2.fX ? "true" : "false"); | |
593 #endif | |
594 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 | |
602 #if DEBUG_OUT_LESS_THAN | |
603 SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two, | |
604 dy1 > 0 ? "true" : "false"); | |
605 #endif | |
606 return dy1 > 0; // one < two if one goes up and two goes down | |
607 } | |
608 if (dy1y2 == 0) { | |
609 #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 | |
613 return endPt1.fX < endPt2.fX; | |
614 } | |
615 SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2; | |
616 SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1; | |
617 #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 | |
621 return dy2 > 0 ^ dx1y2 < dx2y1; | |
622 } | |
623 | |
624 // 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 | |
626 void bridge() { | |
627 size_t index; | |
628 size_t count = fEdges.count(); | |
629 if (!count) { | |
630 return; | |
631 } | |
632 SkASSERT(!fFill || count > 1); | |
633 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); | |
637 SkTDArray<int> order; | |
638 for (index = 1; index <= count; ++index) { | |
639 *order.append() = -index; | |
640 } | |
641 for (index = 1; index <= count; ++index) { | |
642 *order.append() = index; | |
643 } | |
644 QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, le
ssThan); | |
645 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]; | |
651 int* rightPtr = leftPtr + 1; | |
652 int rightIndex = *rightPtr; | |
653 int rightOutIndex = abs(rightIndex) - 1; | |
654 const OutEdge& right = fEdges[rightOutIndex]; | |
655 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 { | |
663 #if DEBUG_OUT | |
664 // 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) { | |
668 *fMismatches.append() = leftIndex; | |
669 if (rightPtr == lastPtr) { | |
670 *fMismatches.append() = rightIndex; | |
671 } | |
672 pairUp = false; | |
673 } | |
674 #else | |
675 SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, | |
676 right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10); | |
677 #endif | |
678 } | |
679 if (pairUp) { | |
680 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 } | |
690 ++rightPtr; | |
691 } | |
692 leftPtr = rightPtr; | |
693 } | |
694 #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 | |
707 #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 | |
723 } | |
724 | |
725 protected: | |
726 SkTArray<OutEdge> fEdges; | |
727 SkTDArray<int> fTops; | |
728 SkTDArray<int> fBottoms; | |
729 bool fFill; | |
730 #if DEBUG_OUT | |
731 SkTDArray<int> fMismatches; | |
732 #endif | |
733 }; | |
734 | |
735 // Bounds, unlike Rect, does not consider a vertical line to be empty. | |
736 struct 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 } | |
741 | |
742 bool isEmpty() { | |
743 return fLeft > fRight || fTop > fBottom | |
744 || (fLeft == fRight && fTop == fBottom) | |
745 || isnan(fLeft) || isnan(fRight) | |
746 || isnan(fTop) || isnan(fBottom); | |
747 } | |
748 }; | |
749 | |
750 class Intercepts { | |
751 public: | |
752 Intercepts() | |
753 : fTopIntercepts(0) | |
754 , 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; | |
762 return *this; | |
763 } | |
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]; | |
774 } | |
775 | |
776 #if DEBUG_DUMP | |
777 void dump(const SkPoint* pts, SkPath::Verb verb) { | |
778 const char className[] = "Intercepts"; | |
779 const int tab = 8; | |
780 for (int i = 0; i < fTs.count(); ++i) { | |
781 SkPoint out; | |
782 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 } | |
795 SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className
), | |
796 className, i, fTs[i], out.fX, out.fY); | |
797 } | |
798 SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className), | |
799 className, fTopIntercepts); | |
800 SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className), | |
801 className, fBottomIntercepts); | |
802 SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className), | |
803 className, fExplicit); | |
804 } | |
805 #endif | |
806 | |
807 SkTDArray<double> fTs; | |
808 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 | |
812 }; | |
813 | |
814 struct 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; | |
824 SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft)
; | |
825 SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRigh
t); | |
826 SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY); | |
827 } | |
828 #endif | |
829 | |
830 SkScalar fLeft; | |
831 SkScalar fRight; | |
832 SkScalar fY; | |
833 }; | |
834 | |
835 struct InEdge { | |
836 bool operator<(const InEdge& rh) const { | |
837 return fBounds.fTop == rh.fBounds.fTop | |
838 ? fBounds.fLeft < rh.fBounds.fLeft | |
839 : fBounds.fTop < rh.fBounds.fTop; | |
840 } | |
841 | |
842 // 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) { | |
847 // FIXME: in the pathological case where there is a ton of intercepts, b
inary search? | |
848 bool foundIntercept = false; | |
849 int insertedAt = -1; | |
850 Intercepts& intercepts = fIntercepts[verbIndex]; | |
851 for (size_t index = 0; index < count; ++index) { | |
852 double t = ts[index]; | |
853 if (t <= 0) { | |
854 intercepts.fTopIntercepts <<= 1; | |
855 fContainsIntercepts |= ++intercepts.fTopIntercepts > 1; | |
856 continue; | |
857 } | |
858 if (t >= 1) { | |
859 intercepts.fBottomIntercepts <<= 1; | |
860 fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1; | |
861 continue; | |
862 } | |
863 fIntersected = true; | |
864 foundIntercept = true; | |
865 size_t tCount = intercepts.fTs.count(); | |
866 double delta; | |
867 for (size_t idx2 = 0; idx2 < tCount; ++idx2) { | |
868 if (t <= intercepts.fTs[idx2]) { | |
869 // FIXME: ? if (t < intercepts.fTs[idx2]) // failed | |
870 delta = intercepts.fTs[idx2] - t; | |
871 if (delta > 0) { | |
872 insertedAt = idx2; | |
873 *intercepts.fTs.insert(idx2) = t; | |
874 } | |
875 goto nextPt; | |
876 } | |
877 } | |
878 if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { | |
879 insertedAt = tCount; | |
880 *intercepts.fTs.append() = t; | |
881 } | |
882 nextPt: | |
883 ; | |
884 } | |
885 fContainsIntercepts |= foundIntercept; | |
886 return insertedAt; | |
887 } | |
888 | |
889 void addPartial(SkTArray<InEdge>& edges, int ptStart, int ptEnd, | |
890 int verbStart, int verbEnd) { | |
891 InEdge* edge = edges.push_back_n(1); | |
892 int verbCount = verbEnd - verbStart; | |
893 edge->fIntercepts.push_back_n(verbCount); | |
894 // uint8_t* verbs = &fVerbs[verbStart]; | |
895 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(); | |
901 edge->fWinding = fWinding; | |
902 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be co
rrect -- but do we need to know? | |
903 } | |
904 | |
905 void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb, | |
906 Intercepts& intercepts, int firstT, int lastT, bool flipped) { | |
907 InEdge* edge = edges.push_back_n(1); | |
908 edge->fIntercepts.push_back_n(1); | |
909 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 } | |
919 edge->fIntercepts[0].fExplicit = true; | |
920 edge->fPts.append(verb + 1, pts); | |
921 edge->fVerbs.append(1, &verb); | |
922 // FIXME: bounds could be better for partial Ts | |
923 edge->setSubBounds(); | |
924 edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be co
rrect -- but do we need to know? | |
925 if (flipped) { | |
926 edge->flipTs(); | |
927 edge->fWinding = -fWinding; | |
928 } else { | |
929 edge->fWinding = fWinding; | |
930 } | |
931 } | |
932 | |
933 bool cached(const InEdge* edge) { | |
934 // 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 | |
949 void complete(signed char winding) { | |
950 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; | |
956 } | |
957 | |
958 void flip() { | |
959 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 } | |
969 | |
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 } | |
981 | |
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); | |
988 fWinding = 0; | |
989 fContainsIntercepts = false; | |
990 fIntersected = false; | |
991 } | |
992 | |
993 void setBounds() { | |
994 SkPoint* ptPtr = fPts.begin(); | |
995 SkPoint* ptLast = fPts.end(); | |
996 if (ptPtr == ptLast) { | |
997 SkDebugf("%s empty edge\n", __FUNCTION__); | |
998 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 } | |
1008 } | |
1009 | |
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 } | |
1026 | |
1027 void splitInflectionPts(SkTArray<InEdge>& edges) { | |
1028 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 += v
erb) { | |
1038 Intercepts& intercepts = fIntercepts[ceptIdx]; | |
1039 verb = *verbs++; | |
1040 if (verb <= SkPath::kLine_Verb) { | |
1041 continue; | |
1042 } | |
1043 size_t tCount = intercepts.fTs.count(); | |
1044 if (!tCount) { | |
1045 continue; | |
1046 } | |
1047 size_t tIndex = (size_t) -1; | |
1048 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) { | |
1063 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb
); | |
1064 #if DEBUG_SPLIT | |
1065 SkDebugf("%s addPartial 1\n", __FUNCTION__); | |
1066 #endif | |
1067 } | |
1068 lastPt = nextPt; | |
1069 lastVerb = nextVerb; | |
1070 } | |
1071 } else { | |
1072 if (firstSplit >= 0) { | |
1073 if (lastSplit < firstSplit) { | |
1074 addSplit(edges, pts, verb, intercepts, | |
1075 lastSplit, firstSplit, false); | |
1076 #if DEBUG_SPLIT | |
1077 SkDebugf("%s addSplit 1 tIndex=%d,%d\n", | |
1078 __FUNCTION__, lastSplit, firstSplit); | |
1079 #endif | |
1080 } | |
1081 addSplit(edges, pts, verb, intercepts, | |
1082 firstSplit, tIndex, true); | |
1083 #if DEBUG_SPLIT | |
1084 SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n", | |
1085 __FUNCTION__, firstSplit, tIndex); | |
1086 #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 { | |
1097 addSplit(edges, pts, verb, intercepts, lastSplit, | |
1098 firstSplit, false); | |
1099 #if DEBUG_SPLIT | |
1100 SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__, | |
1101 lastSplit, firstSplit); | |
1102 #endif | |
1103 } | |
1104 addSplit(edges, pts, verb, intercepts, firstSplit, | |
1105 tIndex, pts[verb].fY < y); | |
1106 #if DEBUG_SPLIT | |
1107 SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__, | |
1108 firstSplit, tIndex, pts[verb].fY < y ? "flip" : ""); | |
1109 #endif | |
1110 } | |
1111 } | |
1112 // 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(); | |
1117 addPartial(edges, lastPt, nextPt, lastVerb, nextVerb); | |
1118 #if DEBUG_SPLIT | |
1119 SkDebugf("%s addPartial 2\n", __FUNCTION__); | |
1120 #endif | |
1121 } | |
1122 // OPTIMIZATION: reuse the edge instead of marking it empty | |
1123 reset(); | |
1124 } | |
1125 } | |
1126 | |
1127 #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); | |
1142 fIntercepts[i].dump(pts, (SkPath::Verb) *verbs); | |
1143 pts += *verbs++; | |
1144 } | |
1145 for (i = 0; i < fPts.count(); ++i) { | |
1146 SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className), | |
1147 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 } | |
1153 SkDebugf("%*s.fBounds=(%1.9g, %1.9g, %1.9g, %1.9g)\n", tab + sizeof(clas
sName), | |
1154 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); | |
1160 SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className), | |
1161 className, fIntersected); | |
1162 } | |
1163 #endif | |
1164 | |
1165 // FIXME: temporary data : move this to a separate struct? | |
1166 SkTDArray<const InEdge*> fCached; // list of edges already intercepted | |
1167 SkTArray<Intercepts> fIntercepts; // one per verb | |
1168 | |
1169 // persistent data | |
1170 SkTDArray<SkPoint> fPts; | |
1171 SkTDArray<uint8_t> fVerbs; | |
1172 Bounds fBounds; | |
1173 int fID; | |
1174 signed char fWinding; | |
1175 bool fContainsIntercepts; | |
1176 bool fIntersected; | |
1177 }; | |
1178 | |
1179 class InEdgeBuilder { | |
1180 public: | |
1181 | |
1182 InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges
, | |
1183 SkTDArray<HorizontalEdge>& horizontalEdges) | |
1184 : fPath(path) | |
1185 , fCurrentEdge(NULL) | |
1186 , fEdges(edges) | |
1187 , fHorizontalEdges(horizontalEdges) | |
1188 , fIgnoreHorizontal(ignoreHorizontal) | |
1189 , fContainsCurves(false) | |
1190 { | |
1191 walk(); | |
1192 } | |
1193 | |
1194 bool containsCurves() const { | |
1195 return fContainsCurves; | |
1196 } | |
1197 | |
1198 protected: | |
1199 | |
1200 void addEdge() { | |
1201 SkASSERT(fCurrentEdge); | |
1202 fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); | |
1203 fPtOffset = 1; | |
1204 *fCurrentEdge->fVerbs.append() = fVerb; | |
1205 } | |
1206 | |
1207 bool complete() { | |
1208 if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { | |
1209 fCurrentEdge->complete(fWinding); | |
1210 fCurrentEdge = NULL; | |
1211 return true; | |
1212 } | |
1213 return false; | |
1214 } | |
1215 | |
1216 int direction(SkPath::Verb verb) { | |
1217 fPtCount = verb + 1; | |
1218 if (fIgnoreHorizontal && isHorizontal()) { | |
1219 return 0; | |
1220 } | |
1221 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; | |
1224 } | |
1225 | |
1226 bool 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 | |
1236 void startEdge() { | |
1237 if (!fCurrentEdge) { | |
1238 fCurrentEdge = fEdges.push_back_n(1); | |
1239 } | |
1240 fWinding = 0; | |
1241 fPtOffset = 0; | |
1242 } | |
1243 | |
1244 void walk() { | |
1245 SkPath::Iter iter(fPath, true); | |
1246 int winding = 0; | |
1247 while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { | |
1248 switch (fVerb) { | |
1249 case SkPath::kMove_Verb: | |
1250 startEdge(); | |
1251 continue; | |
1252 case SkPath::kLine_Verb: | |
1253 winding = direction(SkPath::kLine_Verb); | |
1254 break; | |
1255 case SkPath::kQuad_Verb: | |
1256 fVerb = QuadReduceOrder(fPts); | |
1257 winding = direction(fVerb); | |
1258 fContainsCurves |= fVerb == SkPath::kQuad_Verb; | |
1259 break; | |
1260 case SkPath::kCubic_Verb: | |
1261 fVerb = CubicReduceOrder(fPts); | |
1262 winding = direction(fVerb); | |
1263 fContainsCurves |= fVerb >= SkPath::kQuad_Verb; | |
1264 break; | |
1265 case SkPath::kClose_Verb: | |
1266 SkASSERT(fCurrentEdge); | |
1267 complete(); | |
1268 continue; | |
1269 default: | |
1270 SkDEBUGFAIL("bad verb"); | |
1271 return; | |
1272 } | |
1273 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 } | |
1282 if (complete()) { | |
1283 startEdge(); | |
1284 } | |
1285 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 | |
1290 SkASSERT(fCurrentEdge); | |
1291 if (complete()) { | |
1292 startEdge(); | |
1293 } | |
1294 } | |
1295 fWinding = winding; | |
1296 addEdge(); | |
1297 } | |
1298 if (!complete()) { | |
1299 if (fCurrentEdge) { | |
1300 fEdges.pop_back(); | |
1301 } | |
1302 } | |
1303 } | |
1304 | |
1305 private: | |
1306 const SkPath& fPath; | |
1307 InEdge* fCurrentEdge; | |
1308 SkTArray<InEdge>& fEdges; | |
1309 SkTDArray<HorizontalEdge>& fHorizontalEdges; | |
1310 SkPoint fPts[4]; | |
1311 SkPath::Verb fVerb; | |
1312 int fPtCount; | |
1313 int fPtOffset; | |
1314 int8_t fWinding; | |
1315 bool fIgnoreHorizontal; | |
1316 bool fContainsCurves; | |
1317 }; | |
1318 | |
1319 struct WorkEdge { | |
1320 SkScalar bottom() const { | |
1321 return fPts[verb()].fY; | |
1322 } | |
1323 | |
1324 void init(const InEdge* edge) { | |
1325 fEdge = edge; | |
1326 fPts = edge->fPts.begin(); | |
1327 fVerb = edge->fVerbs.begin(); | |
1328 } | |
1329 | |
1330 bool advance() { | |
1331 SkASSERT(fVerb < fEdge->fVerbs.end()); | |
1332 fPts += *fVerb++; | |
1333 return fVerb != fEdge->fVerbs.end(); | |
1334 } | |
1335 | |
1336 const SkPoint* lastPoints() const { | |
1337 SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb()); | |
1338 return &fPts[-lastVerb()]; | |
1339 } | |
1340 | |
1341 SkPath::Verb lastVerb() const { | |
1342 SkASSERT(fVerb > fEdge->fVerbs.begin()); | |
1343 return (SkPath::Verb) fVerb[-1]; | |
1344 } | |
1345 | |
1346 const SkPoint* points() const { | |
1347 return fPts; | |
1348 } | |
1349 | |
1350 SkPath::Verb verb() const { | |
1351 return (SkPath::Verb) *fVerb; | |
1352 } | |
1353 | |
1354 ptrdiff_t verbIndex() const { | |
1355 return fVerb - fEdge->fVerbs.begin(); | |
1356 } | |
1357 | |
1358 int winding() const { | |
1359 return fEdge->fWinding; | |
1360 } | |
1361 | |
1362 const InEdge* fEdge; | |
1363 const SkPoint* fPts; | |
1364 const uint8_t* fVerb; | |
1365 }; | |
1366 | |
1367 // 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 | |
1370 | |
1371 // OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since | |
1372 // as active edges are introduced, only local sorting should be required | |
1373 class ActiveEdge { | |
1374 public: | |
1375 // this logic must be kept in sync with tooCloseToCall | |
1376 // callers expect this to only read fAbove, fTangent | |
1377 bool operator<(const ActiveEdge& rh) const { | |
1378 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); | |
1381 } | |
1382 // 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 } | |
1405 // FIXME: code has been abandoned, incomplete.... | |
1406 return false; | |
1407 } | |
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); | |
1422 } | |
1423 // return sign of greater absolute value | |
1424 return (fabs(topD) > fabs(botD) ? topD : botD) < 0; | |
1425 } | |
1426 | |
1427 // 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 } | |
1439 | |
1440 void addTatYAbove(SkScalar y) { | |
1441 if (fBelow.fY <= y) { | |
1442 return; | |
1443 } | |
1444 addTatYInner(y); | |
1445 } | |
1446 | |
1447 void addTatYInner(SkScalar y) { | |
1448 if (fWorkEdge.fPts[0].fY > y) { | |
1449 backup(y); | |
1450 } | |
1451 SkScalar left = fWorkEdge.fPts[0].fX; | |
1452 SkScalar right = fWorkEdge.fPts[1].fX; | |
1453 if (left > right) { | |
1454 SkTSwap(left, right); | |
1455 } | |
1456 double ts[2]; | |
1457 SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb); | |
1458 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()); | |
1467 #if DEBUG_ADJUST_COINCIDENT | |
1468 SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); | |
1469 #endif | |
1470 if (insertedAt >= 0) { | |
1471 if (insertedAt + 1 < fTIndex) { | |
1472 SkASSERT(insertedAt + 2 == fTIndex); | |
1473 --fTIndex; | |
1474 } | |
1475 } | |
1476 } | |
1477 | |
1478 bool advanceT() { | |
1479 SkASSERT(fTIndex <= fTs->count() - fExplicitTs); | |
1480 return ++fTIndex <= fTs->count() - fExplicitTs; | |
1481 } | |
1482 | |
1483 bool advance() { | |
1484 // FIXME: flip sense of next | |
1485 bool result = fWorkEdge.advance(); | |
1486 fDone = !result; | |
1487 initT(); | |
1488 return result; | |
1489 } | |
1490 | |
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(); | |
1498 SkASSERT(!fExplicitTs); | |
1499 fTIndex = fTs->count() + 1; | |
1500 } | |
1501 | |
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 } | |
1532 | |
1533 void calcLeft(SkScalar y) { | |
1534 // OPTIMIZE: put a kDone_Verb at the end of the verb list? | |
1535 if (fDone || fBelow.fY > y) { | |
1536 return; // nothing to do; use last | |
1537 } | |
1538 calcLeft(); | |
1539 if (fAbove.fY == fBelow.fY) { | |
1540 SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, | |
1541 ID(), fAbove.fY); | |
1542 } | |
1543 } | |
1544 | |
1545 void calcLeft() { | |
1546 int add = (fTIndex <= fTs->count() - fExplicitTs) - 1; | |
1547 double tAbove = t(fTIndex + add); | |
1548 double tBelow = t(fTIndex - ~add); | |
1549 // 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). | |
1554 SkASSERT(tAbove != tBelow); | |
1555 // FIXME: this can loop forever | |
1556 // need a break if we hit the end | |
1557 // FIXME: in unit test, figure out how explicit Ts work as well | |
1558 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); | |
1563 } else { | |
1564 add += 1; | |
1565 SkASSERT(fTIndex - ~add <= fTs->count() + 1); | |
1566 tBelow = t(fTIndex - ~add); | |
1567 } | |
1568 calcAboveBelow(tAbove, tBelow); | |
1569 } | |
1570 fTAbove = tAbove; | |
1571 fTBelow = tBelow; | |
1572 } | |
1573 | |
1574 bool done(SkScalar bottom) const { | |
1575 return fDone || fYBottom >= bottom; | |
1576 } | |
1577 | |
1578 void fixBelow() { | |
1579 if (fFixBelow) { | |
1580 fTBelow = nextT(); | |
1581 calcAboveBelow(fTAbove, fTBelow); | |
1582 fFixBelow = false; | |
1583 } | |
1584 } | |
1585 | |
1586 void init(const InEdge* edge) { | |
1587 fWorkEdge.init(edge); | |
1588 fDone = false; | |
1589 initT(); | |
1590 fBelow.fY = SK_ScalarMin; | |
1591 fYBottom = SK_ScalarMin; | |
1592 } | |
1593 | |
1594 void initT() { | |
1595 const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); | |
1596 SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); | |
1597 const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); | |
1598 fTs = &interceptPtr->fTs; | |
1599 fExplicitTs = interceptPtr->fExplicit; | |
1600 // 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 | |
1603 fTIndex = 0; | |
1604 if (!fDone) { | |
1605 fVerb = fWorkEdge.verb(); | |
1606 } | |
1607 SkASSERT(fVerb > SkPath::kMove_Verb); | |
1608 } | |
1609 | |
1610 // 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. | |
1614 bool isCoincidentWith(const ActiveEdge* edge) const { | |
1615 if (fAbove != edge->fAbove || fBelow != edge->fBelow) { | |
1616 return false; | |
1617 } | |
1618 if (fVerb != edge->fVerb) { | |
1619 return false; | |
1620 } | |
1621 switch (fVerb) { | |
1622 case SkPath::kLine_Verb: | |
1623 return true; | |
1624 default: | |
1625 // FIXME: add support for quads, cubics | |
1626 SkASSERT(0); | |
1627 return false; | |
1628 } | |
1629 return false; | |
1630 } | |
1631 | |
1632 bool isUnordered(const ActiveEdge* edge) const { | |
1633 return fAbove == edge->fAbove && fBelow == edge->fBelow; | |
1634 } | |
1635 | |
1636 // SkPath::Verb lastVerb() const { | |
1637 // return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); | |
1638 // } | |
1639 | |
1640 const SkPoint* lastPoints() const { | |
1641 return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points(); | |
1642 } | |
1643 | |
1644 bool noIntersect(const ActiveEdge& ) const { | |
1645 // incomplete | |
1646 return false; | |
1647 } | |
1648 | |
1649 // 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 { | |
1652 #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 | |
1657 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 } | |
1666 | |
1667 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 } | |
1686 | |
1687 bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const { | |
1688 SkASSERT(fVerb != SkPath::kLine_Verb | |
1689 || edge->fVerb != SkPath::kLine_Verb); | |
1690 if (fDone || edge->fDone) { | |
1691 return false; | |
1692 } | |
1693 ActiveEdge thisWork, edgeWork; | |
1694 extractAboveBelow(thisWork); | |
1695 edge->extractAboveBelow(edgeWork); | |
1696 return edgeWork < thisWork; | |
1697 } | |
1698 | |
1699 bool tooCloseToCall(const ActiveEdge* edge) const { | |
1700 int ulps; | |
1701 double t1, t2, b1, b2; | |
1702 // This logic must be kept in sync with operator < | |
1703 if (edge->fAbove.fY < fAbove.fY) { | |
1704 t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbo
ve.fX); | |
1705 t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbo
ve.fX); | |
1706 } else if (edge->fAbove.fY > fAbove.fY) { | |
1707 t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX); | |
1708 t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX); | |
1709 } else { | |
1710 t1 = fAbove.fX; | |
1711 t2 = edge->fAbove.fX; | |
1712 } | |
1713 if (edge->fTangent.fY > fTangent.fY) { | |
1714 b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fT
angent.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); | |
1719 } else { | |
1720 b1 = fTangent.fX; | |
1721 b2 = edge->fTangent.fX; | |
1722 } | |
1723 if (fabs(t1 - t2) > fabs(b1 - b2)) { | |
1724 ulps = UlpsDiff((float) t1, (float) t2); | |
1725 } else { | |
1726 ulps = UlpsDiff((float) b1, (float) b2); | |
1727 } | |
1728 #if DEBUG_ADJUST_COINCIDENT | |
1729 SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(), | |
1730 ulps); | |
1731 #endif | |
1732 if (ulps < 0 || ulps > 32) { | |
1733 return false; | |
1734 } | |
1735 if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) { | |
1736 return true; | |
1737 } | |
1738 if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) { | |
1739 return false; | |
1740 } | |
1741 | |
1742 double ts[2]; | |
1743 bool isLine = true; | |
1744 bool curveQuad = true; | |
1745 if (fVerb == SkPath::kCubic_Verb) { | |
1746 ts[0] = (fTAbove * 2 + fTBelow) / 3; | |
1747 ts[1] = (fTAbove + fTBelow * 2) / 3; | |
1748 curveQuad = isLine = false; | |
1749 } else if (edge->fVerb == SkPath::kCubic_Verb) { | |
1750 ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3; | |
1751 ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3; | |
1752 curveQuad = false; | |
1753 } else if (fVerb == SkPath::kQuad_Verb) { | |
1754 ts[0] = fTAbove; | |
1755 ts[1] = (fTAbove + fTBelow) / 2; | |
1756 isLine = false; | |
1757 } else { | |
1758 SkASSERT(edge->fVerb == SkPath::kQuad_Verb); | |
1759 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); | |
1773 } | |
1774 | |
1775 double nextT() const { | |
1776 SkASSERT(fTIndex <= fTs->count() - fExplicitTs); | |
1777 return t(fTIndex + 1); | |
1778 } | |
1779 | |
1780 double t() const { | |
1781 return t(fTIndex); | |
1782 } | |
1783 | |
1784 double t(int tIndex) const { | |
1785 if (fExplicitTs) { | |
1786 SkASSERT(tIndex < fTs->count()); | |
1787 return (*fTs)[tIndex]; | |
1788 } | |
1789 if (tIndex == 0) { | |
1790 return 0; | |
1791 } | |
1792 if (tIndex > fTs->count()) { | |
1793 return 1; | |
1794 } | |
1795 return (*fTs)[tIndex - 1]; | |
1796 } | |
1797 | |
1798 // FIXME: debugging only | |
1799 int ID() const { | |
1800 return fWorkEdge.fEdge->fID; | |
1801 } | |
1802 | |
1803 private: | |
1804 // utility used only by swapUnordered | |
1805 void extractAboveBelow(ActiveEdge& extracted) const { | |
1806 SkPoint curve[4]; | |
1807 switch (fVerb) { | |
1808 case SkPath::kLine_Verb: | |
1809 extracted.fAbove = fAbove; | |
1810 extracted.fTangent = fTangent; | |
1811 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]; | |
1822 extracted.fTangent = curve[1]; | |
1823 } | |
1824 | |
1825 public: | |
1826 WorkEdge fWorkEdge; | |
1827 const SkTDArray<double>* fTs; | |
1828 SkPoint fAbove; | |
1829 SkPoint fTangent; | |
1830 SkPoint fBelow; | |
1831 double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics | |
1832 double fTBelow; | |
1833 SkScalar fYBottom; | |
1834 int fCoincident; | |
1835 int fTIndex; | |
1836 SkPath::Verb fVerb; | |
1837 bool fSkip; // OPTIMIZATION: use bitfields? | |
1838 bool fCloseCall; | |
1839 bool fDone; | |
1840 bool fFixBelow; | |
1841 bool fExplicitTs; | |
1842 }; | |
1843 | |
1844 static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge)
{ | |
1845 size_t count = activeEdges.count(); | |
1846 for (size_t index = 0; index < count; ++index) { | |
1847 if (edge == activeEdges[index].fWorkEdge.fEdge) { | |
1848 return; | |
1849 } | |
1850 } | |
1851 ActiveEdge* active = activeEdges.append(); | |
1852 active->init(edge); | |
1853 } | |
1854 | |
1855 // 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. | |
1858 // Keep horizontal edges just for | |
1859 // the purpose of computing when edges change their winding contribution, since | |
1860 // this is essentially computing the horizontal intersection. | |
1861 static 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; | |
1877 do { | |
1878 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) { | |
1896 #if DEBUG_ADD_BOTTOM_TS | |
1897 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)); | |
1902 } | |
1903 SkDebugf(")\n"); | |
1904 } | |
1905 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()); | |
1911 } | |
1912 horzEdge = *++sorted; | |
1913 } while (horzEdge->fY == bottom | |
1914 && horzEdge->fLeft <= test->fBounds.fRight); | |
1915 } while (wt.advance()); | |
1916 } | |
1917 } | |
1918 | |
1919 #if DEBUG_ADD_INTERSECTING_TS | |
1920 static void debugShowLineIntersection(int pts, const WorkEdge& wt, | |
1921 const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) { | |
1922 if (!pts) { | |
1923 return; | |
1924 } | |
1925 SkPoint wtOutPt, wnOutPt; | |
1926 LineXYAtT(wt.fPts, wtTs[0], &wtOutPt); | |
1927 LineXYAtT(wn.fPts, wnTs[0], &wnOutPt); | |
1928 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", | |
1929 __FUNCTION__, | |
1930 wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, | |
1931 wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY); | |
1932 if (pts == 2) { | |
1933 SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); | |
1934 } | |
1935 SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", | |
1936 __FUNCTION__, | |
1937 wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, | |
1938 wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY); | |
1939 if (pts == 2) { | |
1940 SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); | |
1941 } | |
1942 } | |
1943 #else | |
1944 static void debugShowLineIntersection(int , const WorkEdge& , | |
1945 const WorkEdge& , const double [2], const double [2]) { | |
1946 } | |
1947 #endif | |
1948 | |
1949 static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { | |
1950 InEdge** testPtr = currentPtr - 1; | |
1951 // 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 | |
1954 while (++testPtr != lastPtr - 1) { | |
1955 InEdge* test = *testPtr; | |
1956 InEdge** nextPtr = testPtr; | |
1957 do { | |
1958 InEdge* next = *++nextPtr; | |
1959 // 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. | |
1962 if (test->cached(next)) { | |
1963 continue; | |
1964 } | |
1965 if (!Bounds::Intersects(test->fBounds, next->fBounds)) { | |
1966 continue; | |
1967 } | |
1968 WorkEdge wt, wn; | |
1969 wt.init(test); | |
1970 wn.init(next); | |
1971 do { | |
1972 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); | |
1996 } | |
1997 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); | |
2015 } | |
2016 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); | |
2038 } | |
2039 test->add(ts.fT[swap], pts, wt.verbIndex()); | |
2040 next->add(ts.fT[!swap], pts, wn.verbIndex()); | |
2041 } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance()); | |
2042 } while (nextPtr != lastPtr); | |
2043 } | |
2044 } | |
2045 | |
2046 static InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges, | |
2047 InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { | |
2048 InEdge** testPtr = currentPtr - 1; | |
2049 while (++testPtr != lastPtr) { | |
2050 if ((*testPtr)->fBounds.fBottom > y) { | |
2051 continue; | |
2052 } | |
2053 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 } | |
2062 } | |
2063 } | |
2064 if (testPtr == currentPtr) { | |
2065 ++currentPtr; | |
2066 } | |
2067 } | |
2068 return currentPtr; | |
2069 } | |
2070 | |
2071 // OPTIMIZE: inline? | |
2072 static HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) { | |
2073 while ((*edge)->fY < y) { | |
2074 ++edge; | |
2075 } | |
2076 return edge; | |
2077 } | |
2078 | |
2079 // compute bottom taking into account any intersected edges | |
2080 static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, | |
2081 SkScalar y, SkScalar bottom) { | |
2082 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 { | |
2092 const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; | |
2093 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 } | |
2105 const SkTDArray<double>& fTs = intercepts.fTs; | |
2106 size_t count = fTs.count(); | |
2107 for (size_t index = 0; index < count; ++index) { | |
2108 SkScalar yIntercept; | |
2109 switch (wt.verb()) { | |
2110 case SkPath::kLine_Verb: { | |
2111 yIntercept = LineYAtT(wt.fPts, fTs[index]); | |
2112 break; | |
2113 } | |
2114 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; | |
2127 } | |
2128 } | |
2129 } while (wt.advance()); | |
2130 } | |
2131 #if DEBUG_BOTTOM | |
2132 SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom); | |
2133 #endif | |
2134 return bottom; | |
2135 } | |
2136 | |
2137 static SkScalar findBottom(InEdge** currentPtr, | |
2138 InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, | |
2139 bool /*asFill*/, InEdge**& testPtr) { | |
2140 InEdge* current = *currentPtr; | |
2141 SkScalar bottom = current->fBounds.fBottom; | |
2142 | |
2143 // find the list of edges that cross y | |
2144 InEdge* test = *testPtr; | |
2145 while (testPtr != edgeListEnd) { | |
2146 SkScalar testTop = test->fBounds.fTop; | |
2147 if (bottom <= testTop) { | |
2148 break; | |
2149 } | |
2150 SkScalar testBottom = test->fBounds.fBottom; | |
2151 // 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. | |
2154 if (testTop > y) { | |
2155 bottom = testTop; | |
2156 break; | |
2157 } | |
2158 if (y < testBottom) { | |
2159 if (bottom > testBottom) { | |
2160 bottom = testBottom; | |
2161 } | |
2162 if (activeEdges) { | |
2163 addToActive(*activeEdges, test); | |
2164 } | |
2165 } | |
2166 test = *++testPtr; | |
2167 } | |
2168 #if DEBUG_BOTTOM | |
2169 SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom); | |
2170 #endif | |
2171 return bottom; | |
2172 } | |
2173 | |
2174 static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, | |
2175 SkTDArray<InEdge*>& edgeList) { | |
2176 size_t edgeCount = edges.count(); | |
2177 if (edgeCount == 0) { | |
2178 return; | |
2179 } | |
2180 int id = 0; | |
2181 for (size_t index = 0; index < edgeCount; ++index) { | |
2182 InEdge& edge = edges[index]; | |
2183 if (!edge.fWinding) { | |
2184 continue; | |
2185 } | |
2186 edge.fID = ++id; | |
2187 *edgeList.append() = &edge; | |
2188 } | |
2189 *edgeList.append() = &edgeSentinel; | |
2190 QSort<InEdge>(edgeList.begin(), edgeList.end() - 1); | |
2191 } | |
2192 | |
2193 static 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 } | |
2206 | |
2207 static void skipCoincidence(int lastWinding, int winding, int windingMask, | |
2208 ActiveEdge* activePtr, ActiveEdge* firstCoincident) { | |
2209 if (((lastWinding & windingMask) == 0) ^ ((winding & windingMask) != 0)) { | |
2210 return; | |
2211 } | |
2212 // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? | |
2213 if (lastWinding) { | |
2214 #if DEBUG_ADJUST_COINCIDENT | |
2215 SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID())
; | |
2216 #endif | |
2217 activePtr->fSkip = false; | |
2218 } else { | |
2219 #if DEBUG_ADJUST_COINCIDENT | |
2220 SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident-
>ID()); | |
2221 #endif | |
2222 firstCoincident->fSkip = false; | |
2223 } | |
2224 } | |
2225 | |
2226 static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, | |
2227 SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { | |
2228 size_t edgeCount = activeEdges.count(); | |
2229 if (edgeCount == 0) { | |
2230 return; | |
2231 } | |
2232 #if DEBUG_SORT_HORIZONTAL | |
2233 const int tab = 3; // FIXME: debugging only | |
2234 SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); | |
2235 #endif | |
2236 size_t index; | |
2237 for (index = 0; index < edgeCount; ++index) { | |
2238 ActiveEdge& activeEdge = activeEdges[index]; | |
2239 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; | |
2262 *edgeList.append() = &activeEdge; | |
2263 nextEdge: | |
2264 ; | |
2265 } | |
2266 QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1); | |
2267 } | |
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. | |
2274 static 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 } | |
2284 ActiveEdge* activePtr, * nextPtr = edgeList[0]; | |
2285 size_t index; | |
2286 bool foundCoincident = false; | |
2287 size_t firstIndex = 0; | |
2288 for (index = 1; index < edgeCount; ++index) { | |
2289 activePtr = nextPtr; | |
2290 nextPtr = edgeList[index]; | |
2291 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; | |
2301 } | |
2302 bool closeCall = false; | |
2303 activePtr->fCoincident = firstIndex; | |
2304 if (activePtr->isCoincidentWith(nextPtr) | |
2305 || (closeCall = activePtr->tooCloseToCall(nextPtr))) { | |
2306 activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; | |
2307 activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; | |
2308 } else if (activePtr->isUnordered(nextPtr)) { | |
2309 foundCoincident = true; | |
2310 } else { | |
2311 firstIndex = index; | |
2312 } | |
2313 } | |
2314 nextPtr->fCoincident = firstIndex; | |
2315 if (!foundCoincident) { | |
2316 return bottom; | |
2317 } | |
2318 int winding = 0; | |
2319 nextPtr = edgeList[0]; | |
2320 for (index = 1; index < edgeCount; ++index) { | |
2321 int priorWinding = winding; | |
2322 winding += activePtr->fWorkEdge.winding(); | |
2323 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) { | |
2355 if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, | |
2356 priorWinding, winding, windingMask) | |
2357 : activePtr->swapCoincident(nextPtr, bottom)) { | |
2358 winding -= activePtr->fWorkEdge.winding(); | |
2359 SkASSERT(activePtr == edgeList[index - 1]); | |
2360 SkASSERT(nextPtr == edgeList[index]); | |
2361 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); | |
2362 SkTSwap<ActiveEdge*>(activePtr, nextPtr); | |
2363 winding += activePtr->fWorkEdge.winding(); | |
2364 SkASSERT(activePtr == edgeList[index - 1]); | |
2365 SkASSERT(nextPtr == edgeList[index]); | |
2366 } | |
2367 } | |
2368 } | |
2369 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; | |
2375 winding += activePtr->fWorkEdge.winding(); | |
2376 nextPtr = edgeList[index]; | |
2377 if (activePtr->fSkip && nextPtr->fSkip | |
2378 && activePtr->fCoincident == nextPtr->fCoincident) { | |
2379 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); | |
2388 #if DEBUG_ADJUST_COINCIDENT | |
2389 SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", | |
2390 __FUNCTION__, activePtr->ID(), y, activePtr->fYBotto
m); | |
2391 #endif | |
2392 activePtr->fYBottom = y; | |
2393 } | |
2394 if (outBuilder.trimLine(y, nextPtr->ID())) { | |
2395 nextPtr->addTatYAbove(y); | |
2396 #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 | |
2400 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) { | |
2406 #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 | |
2410 bottom = testY; | |
2411 } | |
2412 testY = nextPtr->fBelow.fY; | |
2413 activePtr->addTatYBelow(testY); | |
2414 if (bottom > testY && testY > y) { | |
2415 #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 | |
2419 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, | |
2432 firstCoincident); | |
2433 } | |
2434 // 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; | |
2441 } | |
2442 | |
2443 // stitch edge and t range that satisfies operation | |
2444 static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar | |
2445 #if DEBUG_STITCH_EDGE | |
2446 y | |
2447 #endif | |
2448 , | |
2449 SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder)
{ | |
2450 int winding = 0; | |
2451 ActiveEdge** activeHandle = edgeList.begin() - 1; | |
2452 ActiveEdge** lastActive = edgeList.end(); | |
2453 #if DEBUG_STITCH_EDGE | |
2454 const int tab = 7; // FIXME: debugging only | |
2455 SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); | |
2456 #endif | |
2457 while (++activeHandle != lastActive) { | |
2458 ActiveEdge* activePtr = *activeHandle; | |
2459 const WorkEdge& wt = activePtr->fWorkEdge; | |
2460 int lastWinding = winding; | |
2461 winding += wt.winding(); | |
2462 #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); | |
2468 #endif | |
2469 if (activePtr->done(bottom)) { | |
2470 #if DEBUG_STITCH_EDGE | |
2471 SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", | |
2472 activePtr->fDone, activePtr->fYBottom); | |
2473 #endif | |
2474 continue; | |
2475 } | |
2476 int opener = (lastWinding & windingMask) == 0; | |
2477 bool closer = (winding & windingMask) == 0; | |
2478 SkASSERT(!opener | !closer); | |
2479 bool inWinding = opener | closer; | |
2480 SkPoint clippedPts[4]; | |
2481 const SkPoint* clipped = NULL; | |
2482 bool moreToDo, aboveBottom; | |
2483 do { | |
2484 double currentT = activePtr->t(); | |
2485 const SkPoint* points = wt.fPts; | |
2486 double nextT; | |
2487 SkPath::Verb verb = activePtr->fVerb; | |
2488 do { | |
2489 nextT = activePtr->nextT(); | |
2490 // 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; | |
2508 } | |
2509 clipped = clippedPts; | |
2510 } else { | |
2511 clipped = points; | |
2512 } | |
2513 if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY | |
2514 != clipped[verb].fY : clipped[0] != clipped[verb])) { | |
2515 #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 | |
2525 outBuilder.addCurve(clipped, (SkPath::Verb) verb, | |
2526 activePtr->fWorkEdge.fEdge->fID, | |
2527 activePtr->fCloseCall); | |
2528 } else { | |
2529 #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 | |
2539 } | |
2540 // by advancing fAbove/fBelow, the next call to sortHorizontal | |
2541 // will use these values if they're still valid instead of | |
2542 // recomputing | |
2543 if (clipped[verb].fY > activePtr->fBelow.fY | |
2544 && bottom >= activePtr->fBelow.fY | |
2545 && verb == SkPath::kLine_Verb) { | |
2546 activePtr->fAbove = activePtr->fBelow; | |
2547 activePtr->fBelow = activePtr->fTangent = clipped[verb]; | |
2548 activePtr->fTAbove = activePtr->fTBelow < 1 | |
2549 ? activePtr->fTBelow : 0; | |
2550 activePtr->fTBelow = nextT; | |
2551 } | |
2552 currentT = nextT; | |
2553 moreToDo = activePtr->advanceT(); | |
2554 activePtr->fYBottom = clipped[verb].fY; // was activePtr->fClose
Call ? bottom : | |
2555 | |
2556 // clearing the fSkip/fCloseCall bit here means that trailing ed
ges | |
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 interse
ction 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 no
t 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 i
s computed | |
2568 | |
2569 // FIXME: initialized in sortHorizontal, cleared here as well so | |
2570 // that next edge is not skipped -- but should skipped edges eve
r | |
2571 // continue? (probably not) | |
2572 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; | |
2577 } | |
2578 #if DEBUG_STITCH_EDGE | |
2579 else { | |
2580 if (activePtr->fSkip || activePtr->fCloseCall) { | |
2581 SkDebugf("%s skip or close == %1.9g\n", __FUNCTION__, | |
2582 clippedPts[0].fY); | |
2583 } | |
2584 } | |
2585 #endif | |
2586 } while (moreToDo & aboveBottom); | |
2587 } while ((moreToDo || activePtr->advance()) & aboveBottom); | |
2588 } | |
2589 } | |
2590 | |
2591 #if DEBUG_DUMP | |
2592 static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList, | |
2593 const InEdge& edgeSentinel) { | |
2594 InEdge** debugPtr = edgeList.begin(); | |
2595 do { | |
2596 (*debugPtr++)->dump(); | |
2597 } while (*debugPtr != &edgeSentinel); | |
2598 } | |
2599 #else | |
2600 static void dumpEdgeList(const SkTDArray<InEdge*>& , | |
2601 const InEdge& ) { | |
2602 } | |
2603 #endif | |
2604 | |
2605 void simplify(const SkPath& path, bool asFill, SkPath& simple) { | |
2606 // 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); | |
2610 // turn path into list of edges increasing in y | |
2611 // 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 | |
2615 SkTArray<InEdge> edges; | |
2616 SkTDArray<HorizontalEdge> horizontalEdges; | |
2617 InEdgeBuilder builder(path, asFill, edges, horizontalEdges); | |
2618 SkTDArray<InEdge*> edgeList; | |
2619 InEdge edgeSentinel; | |
2620 edgeSentinel.reset(); | |
2621 makeEdgeList(edges, edgeSentinel, edgeList); | |
2622 SkTDArray<HorizontalEdge*> horizontalList; | |
2623 HorizontalEdge horizontalSentinel; | |
2624 makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList); | |
2625 InEdge** currentPtr = edgeList.begin(); | |
2626 if (!currentPtr) { | |
2627 return; | |
2628 } | |
2629 // 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. | |
2634 SkScalar y = (*currentPtr)->fBounds.fTop; | |
2635 HorizontalEdge** currentHorizontal = horizontalList.begin(); | |
2636 do { | |
2637 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the
first set | |
2638 SkScalar bottom = findBottom(currentPtr, edgeList.end(), | |
2639 NULL, y, asFill, lastPtr); | |
2640 if (lastPtr > currentPtr) { | |
2641 if (currentHorizontal) { | |
2642 if ((*currentHorizontal)->fY < SK_ScalarMax) { | |
2643 addBottomT(currentPtr, lastPtr, currentHorizontal); | |
2644 } | |
2645 currentHorizontal = advanceHorizontal(currentHorizontal, bottom)
; | |
2646 } | |
2647 addIntersectingTs(currentPtr, lastPtr); | |
2648 } | |
2649 y = bottom; | |
2650 currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); | |
2651 } while (*currentPtr != &edgeSentinel); | |
2652 // 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, spli
t | |
2654 // the curve at the new T. | |
2655 | |
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 neve
r | |
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. | |
2666 if (builder.containsCurves()) { | |
2667 currentPtr = edgeList.begin(); | |
2668 SkTArray<InEdge> splits; | |
2669 do { | |
2670 (*currentPtr)->splitInflectionPts(splits); | |
2671 } while (*++currentPtr != &edgeSentinel); | |
2672 if (splits.count()) { | |
2673 for (int index = 0; index < splits.count(); ++index) { | |
2674 edges.push_back(splits[index]); | |
2675 } | |
2676 edgeList.reset(); | |
2677 makeEdgeList(edges, edgeSentinel, edgeList); | |
2678 } | |
2679 } | |
2680 dumpEdgeList(edgeList, edgeSentinel); | |
2681 // 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); | |
2692 SkTDArray<ActiveEdge*> activeEdgeList; | |
2693 sortHorizontal(activeEdges, activeEdgeList, y); | |
2694 bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, | |
2695 outBuilder); | |
2696 stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilde
r); | |
2697 } | |
2698 y = bottom; | |
2699 // OPTIMIZATION: as edges expire, InEdge allocations could be released | |
2700 currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y); | |
2701 } while (*currentPtr != &edgeSentinel); | |
2702 // assemble output path from string of pts, verbs | |
2703 outBuilder.bridge(); | |
2704 outBuilder.assemble(simple); | |
2705 } | |
OLD | NEW |