blob: 2c1e5f5f4aafef7e04a21637c1e278d20a1225c4 [file] [log] [blame]
caryclark@google.comc6825902012-02-03 22:07:47 +00001
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
caryclark@google.com6680fb12012-02-07 22:10:51 +00009#include "CurveIntersection.h"
caryclark@google.comc6825902012-02-03 22:07:47 +000010#include "LineIntersection.h"
11#include "SkPath.h"
12#include "SkRect.h"
13#include "SkTArray.h"
14#include "SkTDArray.h"
15#include "TSearch.h"
16
caryclark@google.comcef7e3f2012-02-28 16:57:05 +000017static bool gShowDebugf = true; // FIXME: remove once debugging is complete
18static bool gShowPath = false;
caryclark@google.comcd4421d2012-03-01 19:16:31 +000019static bool gDebugLessThan = true;
caryclark@google.comc17972e2012-02-20 21:33:22 +000020
caryclark@google.com6680fb12012-02-07 22:10:51 +000021static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
caryclark@google.comc6825902012-02-03 22:07:47 +000022 double aRange[2], double bRange[2]) {
23 _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
24 _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
25 return intersect(aLine, bLine, aRange, bRange);
26}
27
caryclark@google.com6680fb12012-02-07 22:10:51 +000028static int LineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) {
caryclark@google.comc6825902012-02-03 22:07:47 +000029 _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
30 return horizontalIntersect(aLine, y, aRange);
31}
32
caryclark@google.comcd4421d2012-03-01 19:16:31 +000033static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +000034 _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
caryclark@google.comcd4421d2012-03-01 19:16:31 +000035 double x, y;
36 xy_at_t(aLine, t, x, y);
37 out->fX = SkDoubleToScalar(x);
38 out->fY = SkDoubleToScalar(y);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +000039}
40
caryclark@google.com6680fb12012-02-07 22:10:51 +000041static SkScalar LineYAtT(const SkPoint a[2], double t) {
42 _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
43 double y;
44 xy_at_t(aLine, t, *(double*) 0, y);
45 return SkDoubleToScalar(y);
46}
47
48static void LineSubDivide(const SkPoint a[2], double startT, double endT,
49 SkPoint sub[2]) {
50 _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
51 _Line dst;
52 sub_divide(aLine, startT, endT, dst);
53 sub[0].fX = SkDoubleToScalar(dst[0].x);
54 sub[0].fY = SkDoubleToScalar(dst[0].y);
55 sub[1].fX = SkDoubleToScalar(dst[1].x);
56 sub[1].fY = SkDoubleToScalar(dst[1].y);
57}
58
59
caryclark@google.comc6825902012-02-03 22:07:47 +000060// functions
61void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray);
62void simplify(const SkPath& path, bool asFill, SkPath& simple);
63/*
64list of edges
65bounds for edge
66sort
67active T
68
69if a contour's bounds is outside of the active area, no need to create edges
70*/
71
72/* given one or more paths,
73 find the bounds of each contour, select the active contours
74 for each active contour, compute a set of edges
75 each edge corresponds to one or more lines and curves
76 leave edges unbroken as long as possible
77 when breaking edges, compute the t at the break but leave the control points alone
78
79 */
80
81void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) {
82 SkPath::Iter iter(path, false);
83 SkPoint pts[4];
84 SkPath::Verb verb;
85 SkRect bounds;
86 bounds.setEmpty();
87 int count = 0;
88 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
89 switch (verb) {
90 case SkPath::kMove_Verb:
91 if (!bounds.isEmpty()) {
92 *boundsArray.append() = bounds;
93 }
94 bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
95 count = 0;
96 break;
97 case SkPath::kLine_Verb:
98 count = 1;
99 break;
100 case SkPath::kQuad_Verb:
101 count = 2;
102 break;
103 case SkPath::kCubic_Verb:
104 count = 3;
105 break;
106 case SkPath::kClose_Verb:
107 count = 0;
108 break;
109 default:
110 SkDEBUGFAIL("bad verb");
111 return;
112 }
113 for (int i = 1; i <= count; ++i) {
114 bounds.growToInclude(pts[i].fX, pts[i].fY);
115 }
116 }
117}
118
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000119static bool extendLine(const SkPoint line[2], const SkPoint& add) {
120 // FIXME: allow this to extend lines that have slopes that are nearly equal
121 SkScalar dx1 = line[1].fX - line[0].fX;
122 SkScalar dy1 = line[1].fY - line[0].fY;
123 SkScalar dx2 = add.fX - line[0].fX;
124 SkScalar dy2 = add.fY - line[0].fY;
125 return dx1 * dy2 == dx2 * dy1;
126}
caryclark@google.com6680fb12012-02-07 22:10:51 +0000127
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000128struct OutEdge {
129 bool operator<(const OutEdge& rh) const {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000130 const SkPoint& first = fPts[0];
131 const SkPoint& rhFirst = rh.fPts[0];
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000132 return first.fY == rhFirst.fY
133 ? first.fX < rhFirst.fX
134 : first.fY < rhFirst.fY;
135 }
136
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000137 SkPoint fPts[4];
138 uint8_t fVerb; // FIXME: not read from everywhere
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000139};
140
caryclark@google.com6680fb12012-02-07 22:10:51 +0000141class OutEdgeBuilder {
142public:
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000143 OutEdgeBuilder(bool fill)
144 : fFill(fill) {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000145 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000146
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000147 void addLine(const SkPoint line[2]) {
caryclark@google.comc17972e2012-02-20 21:33:22 +0000148 OutEdge& newEdge = fEdges.push_back();
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000149 newEdge.fPts[0] = line[0];
150 newEdge.fPts[1] = line[1];
151 newEdge.fVerb = SkPath::kLine_Verb;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000152 }
153
154 void assemble(SkPath& simple) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000155 size_t listCount = fEdges.count();
156 if (listCount == 0) {
157 return;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000158 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000159 do {
160 size_t listIndex = 0;
161 int advance = 1;
162 while (listIndex < listCount && fTops[listIndex] == 0) {
163 ++listIndex;
164 }
165 if (listIndex >= listCount) {
166 break;
167 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000168 SkPoint firstPt, lastLine[2];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000169 bool doMove = true;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000170 bool closed = false;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000171 int edgeIndex;
172 do {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000173 SkPoint* ptArray = fEdges[listIndex].fPts;
174 uint8_t verb = fEdges[listIndex].fVerb;
175 SkPoint* start, * end;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000176 if (advance < 0) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000177 start = &ptArray[verb];
178 end = &ptArray[0];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000179 } else {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000180 start = &ptArray[0];
181 end = &ptArray[verb];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000182 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000183 switch (verb) {
184 case SkPath::kLine_Verb:
185 bool gap;
186 if (doMove) {
187 firstPt = *start;
188 simple.moveTo(start->fX, start->fY);
189 if (gShowDebugf) {
190 SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__,
191 start->fX, start->fY);
192 }
193 lastLine[0] = *start;
194 lastLine[1] = *end;
195 doMove = false;
196 closed = false;
197 break;
198 }
199 gap = lastLine[1] != *start;
200 if (gap) {
201 SkASSERT(fFill && lastLine[1].fY == start->fY);
202 simple.lineTo(lastLine[1].fX, lastLine[1].fY);
203 if (gShowDebugf) {
204 SkDebugf("%s lineTo x (%g,%g)\n", __FUNCTION__,
205 lastLine[1].fX, lastLine[1].fY);
206 }
207 }
208 if (gap || !extendLine(lastLine, *end)) {
209 SkASSERT(lastLine[1] == *start ||
210 (fFill && lastLine[1].fY == start->fY));
211 simple.lineTo(start->fX, start->fY);
212 if (gShowDebugf) {
213 SkDebugf("%s lineTo (%g,%g)\n", __FUNCTION__,
214 start->fX, start->fY);
215 }
216 lastLine[0] = *start;
217 }
218 lastLine[1] = *end;
219 if (firstPt == *end) {
220 simple.lineTo(end->fX, end->fY);
221 simple.close();
222 if (gShowDebugf) {
223 SkDebugf("%s close 1 (%g, %g)\n", __FUNCTION__,
224 end->fX, end->fY);
225 }
226 closed = true;
caryclark@google.comc17972e2012-02-20 21:33:22 +0000227 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000228 break;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000229 default:
230 // FIXME: add other curve types
231 ;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000232 }
233 if (advance < 0) {
234 edgeIndex = fTops[listIndex];
235 fTops[listIndex] = 0;
236 } else {
237 edgeIndex = fBottoms[listIndex];
238 fBottoms[listIndex] = 0;
239 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000240 if (!edgeIndex) {
241 simple.lineTo(firstPt.fX, firstPt.fY);
242 simple.close();
243 if (gShowDebugf) {
244 SkDebugf("%s close 2 (%g,%g)\n", __FUNCTION__,
245 firstPt.fX, firstPt.fY);
246 }
247 break;
248 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000249 listIndex = abs(edgeIndex) - 1;
250 if (edgeIndex < 0) {
251 fTops[listIndex] = 0;
252 } else {
253 fBottoms[listIndex] = 0;
254 }
255 // if this and next edge go different directions
256 if (advance > 0 ^ edgeIndex < 0) {
257 advance = -advance;
258 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000259 } while (edgeIndex && !closed);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000260 } while (true);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000261 }
262
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000263 // sort points by y, then x
264 // if x/y is identical, sort bottoms before tops
265 // if identical and both tops/bottoms, sort by angle
266 static bool lessThan(SkTArray<OutEdge>& edges, const int one,
267 const int two) {
268 const OutEdge& oneEdge = edges[abs(one) - 1];
269 int oneIndex = one < 0 ? 0 : oneEdge.fVerb;
270 const SkPoint& startPt1 = oneEdge.fPts[oneIndex];
271 const OutEdge& twoEdge = edges[abs(two) - 1];
272 int twoIndex = two < 0 ? 0 : twoEdge.fVerb;
273 const SkPoint& startPt2 = twoEdge.fPts[twoIndex];
274 if (startPt1.fY != startPt2.fY) {
275 if (gDebugLessThan) {
276 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__,
277 one, two, startPt1.fY, startPt2.fY,
278 startPt1.fY < startPt2.fY ? "true" : "false");
279 }
280 return startPt1.fY < startPt2.fY;
281 }
282 if (startPt1.fX != startPt2.fX) {
283 if (gDebugLessThan) {
284 SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__,
285 one, two, startPt1.fX, startPt2.fX,
286 startPt1.fX < startPt2.fX ? "true" : "false");
287 }
288 return startPt1.fX < startPt2.fX;
289 }
290 const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb];
291 const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb];
292 SkScalar dy1 = startPt1.fY - endPt1.fY;
293 SkScalar dy2 = startPt2.fY - endPt2.fY;
294 SkScalar dy1y2 = dy1 * dy2;
295 if (dy1y2 < 0) { // different signs
296 if (gDebugLessThan) {
297 SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two,
298 dy1 > 0 ? "true" : "false");
299 }
300 return dy1 > 0; // one < two if one goes up and two goes down
301 }
302 if (dy1y2 == 0) {
303 if (gDebugLessThan) {
304 SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__,
305 one, two, endPt1.fX < endPt2.fX ? "true" : "false");
306 }
307 return endPt1.fX < endPt2.fX;
308 }
309 SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2;
310 SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1;
311 if (gDebugLessThan) {
312 SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__,
313 one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false");
314 }
315 return dy2 > 0 ^ dx1y2 < dx2y1;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000316 }
317
caryclark@google.com6008c6562012-02-15 22:01:16 +0000318 // Sort the indices of paired points and then create more indices so
319 // assemble() can find the next edge and connect the top or bottom
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000320 void bridge() {
321 size_t index;
322 size_t count = fEdges.count();
323 if (!count) {
324 return;
325 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000326 SkASSERT(!fFill || count > 1);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000327 fTops.setCount(count);
328 sk_bzero(fTops.begin(), sizeof(fTops[0]) * count);
329 fBottoms.setCount(count);
330 sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000331 SkTDArray<int> order;
332 for (index = 1; index <= count; ++index) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000333 *order.append() = -index;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000334 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000335 for (index = 1; index <= count; ++index) {
336 *order.append() = index;
337 }
338 QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000339 int* lastPtr = order.end() - 1;
340 int* leftPtr = order.begin();
341 while (leftPtr < lastPtr) {
342 int leftIndex = *leftPtr;
343 int leftOutIndex = abs(leftIndex) - 1;
344 const OutEdge& left = fEdges[leftOutIndex];
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000345 int* rightPtr = leftPtr + 1;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000346 int rightIndex = *rightPtr;
347 int rightOutIndex = abs(rightIndex) - 1;
348 const OutEdge& right = fEdges[rightOutIndex];
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000349 bool pairUp = fFill;
350 if (!pairUp) {
351 const SkPoint& leftMatch =
352 left.fPts[leftIndex < 0 ? 0 : left.fVerb];
353 const SkPoint& rightMatch =
354 right.fPts[rightIndex < 0 ? 0 : right.fVerb];
355 pairUp = leftMatch == rightMatch;
356 } else {
357 SkASSERT(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY
358 == right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY);
359 }
360 if (pairUp) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000361 if (leftIndex < 0) {
362 fTops[leftOutIndex] = rightIndex;
363 } else {
364 fBottoms[leftOutIndex] = rightIndex;
365 }
366 if (rightIndex < 0) {
367 fTops[rightOutIndex] = leftIndex;
368 } else {
369 fBottoms[rightOutIndex] = leftIndex;
370 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000371 ++rightPtr;
372 }
373 leftPtr = rightPtr;
374 }
375 }
376
caryclark@google.com6008c6562012-02-15 22:01:16 +0000377protected:
caryclark@google.com6680fb12012-02-07 22:10:51 +0000378 SkTArray<OutEdge> fEdges;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000379 SkTDArray<int> fTops;
380 SkTDArray<int> fBottoms;
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000381 bool fFill;
caryclark@google.com6680fb12012-02-07 22:10:51 +0000382};
383
caryclark@google.comc6825902012-02-03 22:07:47 +0000384// Bounds, unlike Rect, does not consider a vertical line to be empty.
385struct Bounds : public SkRect {
386 static bool Intersects(const Bounds& a, const Bounds& b) {
387 return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
388 a.fTop <= b.fBottom && b.fTop <= a.fBottom;
389 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000390
391 bool isEmpty() {
392 return fLeft > fRight || fTop > fBottom
393 || fLeft == fRight && fTop == fBottom
394 || isnan(fLeft) || isnan(fRight)
395 || isnan(fTop) || isnan(fBottom);
396 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000397};
398
caryclark@google.comc6825902012-02-03 22:07:47 +0000399struct Intercepts {
400 SkTDArray<double> fTs;
401};
402
caryclark@google.com6680fb12012-02-07 22:10:51 +0000403struct InEdge {
404 bool operator<(const InEdge& rh) const {
caryclark@google.comc6825902012-02-03 22:07:47 +0000405 return fBounds.fTop == rh.fBounds.fTop
406 ? fBounds.fLeft < rh.fBounds.fLeft
407 : fBounds.fTop < rh.fBounds.fTop;
408 }
409
caryclark@google.com6008c6562012-02-15 22:01:16 +0000410 bool add(double* ts, size_t count, ptrdiff_t verbIndex) {
caryclark@google.comc6825902012-02-03 22:07:47 +0000411 // FIXME: in the pathological case where there is a ton of intercepts, binary search?
caryclark@google.com6008c6562012-02-15 22:01:16 +0000412 bool foundIntercept = false;
413 Intercepts& intercepts = fIntercepts[verbIndex];
caryclark@google.comc6825902012-02-03 22:07:47 +0000414 for (size_t index = 0; index < count; ++index) {
415 double t = ts[index];
caryclark@google.com6008c6562012-02-15 22:01:16 +0000416 if (t <= 0 || t >= 1) {
417 continue;
418 }
419 foundIntercept = true;
caryclark@google.comc6825902012-02-03 22:07:47 +0000420 size_t tCount = intercepts.fTs.count();
421 for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
422 if (t <= intercepts.fTs[idx2]) {
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000423 double delta = intercepts.fTs[idx2] - t;
424 if (delta > 0) {
caryclark@google.comc6825902012-02-03 22:07:47 +0000425 *intercepts.fTs.insert(idx2) = t;
caryclark@google.comc6825902012-02-03 22:07:47 +0000426 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000427 return foundIntercept;
caryclark@google.comc6825902012-02-03 22:07:47 +0000428 }
429 }
430 if (tCount == 0 || t > intercepts.fTs[tCount - 1]) {
431 *intercepts.fTs.append() = t;
432 }
433 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000434 return foundIntercept;
caryclark@google.comc6825902012-02-03 22:07:47 +0000435 }
436
caryclark@google.com6680fb12012-02-07 22:10:51 +0000437 bool cached(const InEdge* edge) {
caryclark@google.comc6825902012-02-03 22:07:47 +0000438 // FIXME: in the pathological case where there is a ton of edges, binary search?
439 size_t count = fCached.count();
440 for (size_t index = 0; index < count; ++index) {
441 if (edge == fCached[index]) {
442 return true;
443 }
444 if (edge < fCached[index]) {
445 *fCached.insert(index) = edge;
446 return false;
447 }
448 }
449 *fCached.append() = edge;
450 return false;
451 }
452
453 void complete(signed char winding) {
454 SkPoint* ptPtr = fPts.begin();
455 SkPoint* ptLast = fPts.end();
456 if (ptPtr == ptLast) {
457 SkDebugf("empty edge\n");
458 SkASSERT(0);
459 // FIXME: delete empty edge?
460 return;
461 }
462 fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY);
463 ++ptPtr;
464 while (ptPtr != ptLast) {
465 fBounds.growToInclude(ptPtr->fX, ptPtr->fY);
466 ++ptPtr;
467 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000468 fIntercepts.push_back_n(fVerbs.count());
caryclark@google.com6680fb12012-02-07 22:10:51 +0000469 if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top
470 size_t index;
471 size_t last = fPts.count() - 1;
472 for (index = 0; index < last; ++index, --last) {
473 SkTSwap<SkPoint>(fPts[index], fPts[last]);
474 }
475 last = fVerbs.count() - 1;
476 for (index = 0; index < last; ++index, --last) {
477 SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);
478 }
479 }
480 fContainsIntercepts = false;
caryclark@google.comc6825902012-02-03 22:07:47 +0000481 }
482
483 // temporary data : move this to a separate struct?
caryclark@google.com6680fb12012-02-07 22:10:51 +0000484 SkTDArray<const InEdge*> fCached; // list of edges already intercepted
caryclark@google.comc6825902012-02-03 22:07:47 +0000485 SkTArray<Intercepts> fIntercepts; // one per verb
486
caryclark@google.comc6825902012-02-03 22:07:47 +0000487 // persistent data
488 SkTDArray<SkPoint> fPts;
489 SkTDArray<uint8_t> fVerbs;
490 Bounds fBounds;
491 signed char fWinding;
caryclark@google.com6680fb12012-02-07 22:10:51 +0000492 bool fContainsIntercepts;
caryclark@google.comc6825902012-02-03 22:07:47 +0000493};
494
caryclark@google.com6680fb12012-02-07 22:10:51 +0000495class InEdgeBuilder {
caryclark@google.comc6825902012-02-03 22:07:47 +0000496public:
497
caryclark@google.com6680fb12012-02-07 22:10:51 +0000498InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges)
caryclark@google.comc6825902012-02-03 22:07:47 +0000499 : fPath(path)
500 , fCurrentEdge(NULL)
501 , fEdges(edges)
502 , fIgnoreHorizontal(ignoreHorizontal)
503{
504 walk();
505}
506
507protected:
508
509void addEdge() {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000510 SkASSERT(fCurrentEdge);
caryclark@google.comc6825902012-02-03 22:07:47 +0000511 fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);
512 fPtOffset = 1;
513 *fCurrentEdge->fVerbs.append() = fVerb;
514}
515
caryclark@google.com6008c6562012-02-15 22:01:16 +0000516bool complete() {
517 if (fCurrentEdge && fCurrentEdge->fVerbs.count()) {
518 fCurrentEdge->complete(fWinding);
519 fCurrentEdge = NULL;
520 return true;
521 }
522 return false;
523}
524
caryclark@google.comc6825902012-02-03 22:07:47 +0000525int direction(int count) {
526 fPtCount = count;
527 fIgnorableHorizontal = fIgnoreHorizontal && isHorizontal();
528 if (fIgnorableHorizontal) {
529 return 0;
530 }
531 int last = count - 1;
532 return fPts[0].fY == fPts[last].fY
caryclark@google.com6680fb12012-02-07 22:10:51 +0000533 ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX < fPts[last].fX
534 ? 1 : -1 : fPts[0].fY < fPts[last].fY ? 1 : -1;
caryclark@google.comc6825902012-02-03 22:07:47 +0000535}
536
537bool isHorizontal() {
538 SkScalar y = fPts[0].fY;
539 for (int i = 1; i < fPtCount; ++i) {
540 if (fPts[i].fY != y) {
541 return false;
542 }
543 }
544 return true;
545}
546
547void startEdge() {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000548 if (!fCurrentEdge) {
549 fCurrentEdge = fEdges.push_back_n(1);
550 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000551 fWinding = 0;
552 fPtOffset = 0;
553}
554
555void walk() {
556 SkPath::Iter iter(fPath, true);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000557 int winding;
caryclark@google.comc6825902012-02-03 22:07:47 +0000558 while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) {
559 switch (fVerb) {
560 case SkPath::kMove_Verb:
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000561 if (gShowPath) {
562 SkDebugf("path.moveTo(%g, %g);\n", fPts[0].fX, fPts[0].fY);
563 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000564 startEdge();
565 continue;
566 case SkPath::kLine_Verb:
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000567 if (gShowPath) {
568 SkDebugf("path.lineTo(%g, %g);\n", fPts[1].fX, fPts[1].fY);
569 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000570 winding = direction(2);
571 break;
572 case SkPath::kQuad_Verb:
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000573 if (gShowPath) {
574 SkDebugf("path.quadTo(%g, %g, %g, %g);\n",
575 fPts[1].fX, fPts[1].fY, fPts[2].fX, fPts[2].fY);
576 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000577 winding = direction(3);
578 break;
579 case SkPath::kCubic_Verb:
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000580 if (gShowPath) {
581 SkDebugf("path.cubicTo(%g, %g, %g, %g);\n",
582 fPts[1].fX, fPts[1].fY, fPts[2].fX, fPts[2].fY,
583 fPts[3].fX, fPts[3].fY);
584 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000585 winding = direction(4);
586 break;
587 case SkPath::kClose_Verb:
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000588 if (gShowPath) {
589 SkDebugf("path.close();\n");
590 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000591 SkASSERT(fCurrentEdge);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000592 complete();
caryclark@google.comc6825902012-02-03 22:07:47 +0000593 continue;
594 default:
595 SkDEBUGFAIL("bad verb");
596 return;
597 }
598 if (fIgnorableHorizontal) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000599 if (complete()) {
600 startEdge();
601 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000602 continue;
603 }
604 if (fWinding + winding == 0) {
605 // FIXME: if prior verb or this verb is a horizontal line, reverse
606 // it instead of starting a new edge
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000607 SkASSERT(fCurrentEdge);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000608 if (complete()) {
609 startEdge();
610 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000611 }
612 fWinding = winding;
613 addEdge();
614 }
caryclark@google.com6b9cfb32012-02-16 21:24:41 +0000615 if (!complete()) {
616 if (fCurrentEdge) {
617 fEdges.pop_back();
618 }
619 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000620 if (gShowPath) {
621 SkDebugf("\n");
622 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000623}
624
625private:
626 const SkPath& fPath;
caryclark@google.com6680fb12012-02-07 22:10:51 +0000627 InEdge* fCurrentEdge;
628 SkTArray<InEdge>& fEdges;
caryclark@google.comc6825902012-02-03 22:07:47 +0000629 SkPoint fPts[4];
630 SkPath::Verb fVerb;
631 int fPtCount;
632 int fPtOffset;
633 int8_t fWinding;
634 bool fIgnorableHorizontal;
635 bool fIgnoreHorizontal;
636};
637
caryclark@google.com6680fb12012-02-07 22:10:51 +0000638struct WorkEdge {
639 SkScalar bottom() const {
640 return fPts[verb()].fY;
caryclark@google.comc6825902012-02-03 22:07:47 +0000641 }
642
caryclark@google.com6680fb12012-02-07 22:10:51 +0000643 void init(const InEdge* edge) {
644 fEdge = edge;
645 fPts = edge->fPts.begin();
646 fVerb = edge->fVerbs.begin();
caryclark@google.comc6825902012-02-03 22:07:47 +0000647 }
648
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000649 bool advance() {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000650 SkASSERT(fVerb < fEdge->fVerbs.end());
651 fPts += *fVerb++;
652 return fVerb != fEdge->fVerbs.end();
caryclark@google.comc6825902012-02-03 22:07:47 +0000653 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000654
655 SkPath::Verb lastVerb() const {
656 SkASSERT(fVerb > fEdge->fVerbs.begin());
657 return (SkPath::Verb) fVerb[-1];
658 }
659
caryclark@google.comc6825902012-02-03 22:07:47 +0000660
661 SkPath::Verb verb() const {
662 return (SkPath::Verb) *fVerb;
663 }
664
caryclark@google.com6008c6562012-02-15 22:01:16 +0000665 ptrdiff_t verbIndex() const {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000666 return fVerb - fEdge->fVerbs.begin();
667 }
668
669 int winding() const {
670 return fEdge->fWinding;
caryclark@google.comc6825902012-02-03 22:07:47 +0000671 }
672
caryclark@google.com6680fb12012-02-07 22:10:51 +0000673 const InEdge* fEdge;
caryclark@google.comc6825902012-02-03 22:07:47 +0000674 const SkPoint* fPts;
675 const uint8_t* fVerb;
caryclark@google.comc6825902012-02-03 22:07:47 +0000676};
677
caryclark@google.com6680fb12012-02-07 22:10:51 +0000678// always constructed with SkTDArray because new edges are inserted
679// this may be a inappropriate optimization, suggesting that a separate array of
680// ActiveEdge* may be faster to insert and search
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000681
682// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since
683// as active edges are introduced, only local sorting should be required
caryclark@google.comc6825902012-02-03 22:07:47 +0000684struct ActiveEdge {
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000685 // OPTIMIZATION: fold return statements into one
caryclark@google.com6008c6562012-02-15 22:01:16 +0000686 bool operator<(const ActiveEdge& rh) const {
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000687 if (rh.fAbove.fY - fAbove.fY > fBelow.fY - rh.fAbove.fY
688 && fBelow.fY < rh.fBelow.fY
689 || fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - fAbove.fY
690 && rh.fBelow.fY < fBelow.fY) {
691 // FIXME: need to compute distance, not check for points equal
692 const SkPoint& check = rh.fBelow.fY <= fBelow.fY
693 && fBelow != rh.fBelow ? rh.fBelow :
694 rh.fAbove;
695 if (gDebugLessThan) {
696 SkDebugf("%s < %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}"
697 " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\n", __FUNCTION__,
698 rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A',
699 (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX)
700 < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)
701 ? ' ' : '!',
702 fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY,
703 rh.fIndex, rh.fAbove.fX, rh.fAbove.fY,
704 rh.fBelow.fX, rh.fBelow.fY);
705 }
706 return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX)
707 < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX);
708 }
709 // FIXME: need to compute distance, not check for points equal
710 const SkPoint& check = fBelow.fY <= rh.fBelow.fY
711 && fBelow != rh.fBelow ? fBelow : fAbove;
712 if (gDebugLessThan) {
713 SkDebugf("%s > %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}"
714 " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\n", __FUNCTION__,
715 fBelow.fY <= rh.fBelow.fY & fBelow != rh.fBelow ? 'B' : 'A',
716 (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX)
717 < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)
718 ? ' ' : '!',
719 fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY,
720 rh.fIndex, rh.fAbove.fX, rh.fAbove.fY,
721 rh.fBelow.fX, rh.fBelow.fY);
722 }
723 return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX)
724 < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000725 }
726
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000727 bool advanceT() {
728 SkASSERT(fTIndex <= fTs->count());
729 return ++fTIndex <= fTs->count();
730 }
731
732 bool advance() {
733 // FIXME: flip sense of next
734 bool result = fWorkEdge.advance();
735 fDone = !result;
736 initT();
737 return result;
738 }
739
740 void calcLeft(SkScalar y) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000741 // OPTIMIZE: put a kDone_Verb at the end of the verb list?
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000742 if (done(y))
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000743 return; // nothing to do; use last
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000744 calcLeft();
745 }
746
747 void calcLeft() {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000748 switch (fWorkEdge.verb()) {
749 case SkPath::kLine_Verb: {
750 // OPTIMIZATION: if fXAbove, fXBelow have already been computed
751 // for the fTIndex, don't do it again
752 // For identical x, this lets us know which edge is first.
753 // If both edges have T values < 1, check x at next T (fXBelow).
754 int add = (fTIndex <= fTs->count()) - 1;
755 double tAbove = t(fTIndex + add);
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000756 // OPTIMIZATION: may not need Y
757 LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000758 double tBelow = t(fTIndex - ~add);
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000759 LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000760 break;
761 }
762 default:
763 // FIXME: add support for all curve types
764 SkASSERT(0);
765 }
caryclark@google.com6008c6562012-02-15 22:01:16 +0000766 }
767
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000768 bool done(SkScalar y) {
769 return fDone || fYBottom > y;
770 }
771
caryclark@google.com6680fb12012-02-07 22:10:51 +0000772 void init(const InEdge* edge) {
773 fWorkEdge.init(edge);
774 initT();
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000775 fDone = false;
776 fYBottom = SK_ScalarMin;
caryclark@google.com6680fb12012-02-07 22:10:51 +0000777 }
778
779 void initT() {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000780 const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front();
781 SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count());
782 const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex();
783 fTs = &interceptPtr->fTs;
784 // the above is conceptually the same as
785 // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;
786 // but templated arrays don't allow returning a pointer to the end() element
caryclark@google.com6680fb12012-02-07 22:10:51 +0000787 fTIndex = 0;
caryclark@google.comc6825902012-02-03 22:07:47 +0000788 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000789
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000790 // OPTIMIZATION: record if two edges are coincident when the are intersected
791 // It's unclear how to do this -- seems more complicated than recording the
792 // t values, since the same t values could exist intersecting non-coincident
793 // edges.
794 bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const {
795 if (fAbove.fX != edge->fAbove.fX || fBelow.fX != edge->fBelow.fX) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000796 return false;
797 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000798 uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
799 uint8_t edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb()
800 : edge->fWorkEdge.verb();
801 if (verb != edgeVerb) {
802 return false;
803 }
804 switch (verb) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000805 case SkPath::kLine_Verb: {
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000806 int offset = fDone ? -1 : 1;
807 int edgeOffset = edge->fDone ? -1 : 1;
808 const SkPoint* pts = fWorkEdge.fPts;
809 const SkPoint* edgePts = edge->fWorkEdge.fPts;
810 return (pts->fX - pts[offset].fX)
811 * (edgePts->fY - edgePts[edgeOffset].fY)
812 == (pts->fY - pts[offset].fY)
813 * (edgePts->fX - edgePts[edgeOffset].fX);
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000814 }
815 default:
816 // FIXME: add support for all curve types
817 SkASSERT(0);
818 }
819 return false;
820 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000821
822 bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const {
823 if (fBelow.fY >= bottom || fDone || edge->fDone) {
824 return false;
825 }
826 ActiveEdge thisWork = *this;
827 ActiveEdge edgeWork = *edge;
828 while ((thisWork.advanceT() || thisWork.advance())
829 && (edgeWork.advanceT() || edgeWork.advance())) {
830 thisWork.calcLeft();
831 edgeWork.calcLeft();
832 if (thisWork < edgeWork) {
833 return false;
834 }
835 if (edgeWork < thisWork) {
836 return true;
837 }
838 }
839 return false;
840 }
caryclark@google.comc6825902012-02-03 22:07:47 +0000841
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000842 double nextT() {
843 SkASSERT(fTIndex <= fTs->count());
844 return t(fTIndex + 1);
845 }
caryclark@google.com6680fb12012-02-07 22:10:51 +0000846
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000847 double t() const {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000848 if (fTIndex == 0) {
849 return 0;
850 }
851 if (fTIndex > fTs->count()) {
852 return 1;
853 }
854 return (*fTs)[fTIndex - 1];
855 }
856
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000857 double t(int tIndex) const {
858 if (tIndex == 0) {
859 return 0;
860 }
861 if (tIndex > fTs->count()) {
862 return 1;
863 }
864 return (*fTs)[tIndex - 1];
865 }
866
caryclark@google.com6680fb12012-02-07 22:10:51 +0000867 WorkEdge fWorkEdge;
868 const SkTDArray<double>* fTs;
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000869 SkPoint fAbove;
870 SkPoint fBelow;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000871 SkScalar fYBottom;
caryclark@google.com6680fb12012-02-07 22:10:51 +0000872 int fTIndex;
caryclark@google.com6008c6562012-02-15 22:01:16 +0000873 bool fSkip;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000874 bool fDone;
caryclark@google.comcd4421d2012-03-01 19:16:31 +0000875 int fIndex; // REMOVE: debugging only
caryclark@google.comc6825902012-02-03 22:07:47 +0000876};
877
caryclark@google.com6680fb12012-02-07 22:10:51 +0000878static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000879 size_t count = activeEdges.count();
880 for (size_t index = 0; index < count; ++index) {
caryclark@google.com6680fb12012-02-07 22:10:51 +0000881 if (edge == activeEdges[index].fWorkEdge.fEdge) {
882 return;
883 }
884 }
885 ActiveEdge* active = activeEdges.append();
886 active->init(edge);
887}
888
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000889 // find any intersections in the range of active edges
890static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, SkScalar bottom) {
891 InEdge** testPtr = currentPtr;
892 InEdge* test = *testPtr;
893 while (testPtr != lastPtr) {
894 if (test->fBounds.fBottom > bottom) {
895 WorkEdge wt;
896 wt.init(test);
897 do {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000898 // OPTIMIZATION: if bottom intersection does not change
899 // the winding on either side of the split, don't intersect
900 if (wt.verb() == SkPath::kLine_Verb) {
901 double wtTs[2];
902 int pts = LineIntersect(wt.fPts, bottom, wtTs);
903 if (pts) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000904 test->fContainsIntercepts |= test->add(wtTs, pts,
905 wt.verbIndex());
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000906 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000907 } else {
908 // FIXME: add all curve types
909 SkASSERT(0);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000910 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000911 } while (wt.advance());
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000912 }
913 test = *++testPtr;
914 }
915}
916
917static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000918 InEdge** testPtr = currentPtr - 1;
919 while (++testPtr != lastPtr - 1) {
920 InEdge* test = *testPtr;
921 InEdge** nextPtr = testPtr;
922 do {
923 InEdge* next = *++nextPtr;
924 if (test->cached(next)) {
925 continue;
926 }
927 if (!Bounds::Intersects(test->fBounds, next->fBounds)) {
928 continue;
929 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000930 WorkEdge wt, wn;
931 wt.init(test);
932 wn.init(next);
933 do {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000934 if (wt.verb() == SkPath::kLine_Verb
935 && wn.verb() == SkPath::kLine_Verb) {
936 double wtTs[2], wnTs[2];
937 int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs);
938 if (pts) {
caryclark@google.com6008c6562012-02-15 22:01:16 +0000939 test->fContainsIntercepts |= test->add(wtTs, pts,
940 wt.verbIndex());
941 next->fContainsIntercepts |= next->add(wnTs, pts,
942 wn.verbIndex());
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000943 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000944 } else {
945 // FIXME: add all combinations of curve types
946 SkASSERT(0);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000947 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000948 } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance());
949 } while (nextPtr != lastPtr);
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000950 }
951}
952
caryclark@google.com6008c6562012-02-15 22:01:16 +0000953static InEdge** advanceEdges(SkTDArray<ActiveEdge>& activeEdges,
954 InEdge** currentPtr, InEdge** lastPtr, SkScalar y) {
955 InEdge** testPtr = currentPtr - 1;
956 while (++testPtr != lastPtr) {
957 if ((*testPtr)->fBounds.fBottom > y) {
958 continue;
959 }
960 InEdge* test = *testPtr;
961 ActiveEdge* activePtr = activeEdges.begin() - 1;
962 ActiveEdge* lastActive = activeEdges.end();
963 while (++activePtr != lastActive) {
964 if (activePtr->fWorkEdge.fEdge == test) {
965 activeEdges.remove(activePtr - activeEdges.begin());
966 break;
967 }
968 }
969 if (testPtr == currentPtr) {
970 ++currentPtr;
971 }
972 }
973 return currentPtr;
974}
975
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000976// compute bottom taking into account any intersected edges
977static void computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges,
caryclark@google.com6008c6562012-02-15 22:01:16 +0000978 SkScalar y, SkScalar& bottom) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000979 ActiveEdge* activePtr = activeEdges.begin() - 1;
980 ActiveEdge* lastActive = activeEdges.end();
981 while (++activePtr != lastActive) {
982 const InEdge* test = activePtr->fWorkEdge.fEdge;
983 if (!test->fContainsIntercepts) {
984 continue;
985 }
986 WorkEdge wt;
987 wt.init(test);
988 do {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000989 const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()];
990 const SkTDArray<double>& fTs = intercepts.fTs;
991 size_t count = fTs.count();
992 for (size_t index = 0; index < count; ++index) {
993 if (wt.verb() == SkPath::kLine_Verb) {
994 SkScalar yIntercept = LineYAtT(wt.fPts, fTs[index]);
caryclark@google.com6008c6562012-02-15 22:01:16 +0000995 if (yIntercept > y && bottom > yIntercept) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +0000996 bottom = yIntercept;
997 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +0000998 } else {
999 // FIXME: add all curve types
1000 SkASSERT(0);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001001 }
1002 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001003 } while (wt.advance());
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001004 }
1005}
1006
1007static SkScalar findBottom(InEdge** currentPtr,
1008 InEdge** edgeListEnd, SkTDArray<ActiveEdge>& activeEdges, SkScalar y,
caryclark@google.com6008c6562012-02-15 22:01:16 +00001009 bool asFill, InEdge**& testPtr) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001010 InEdge* current = *currentPtr;
1011 SkScalar bottom = current->fBounds.fBottom;
1012
1013 // find the list of edges that cross y
caryclark@google.com6008c6562012-02-15 22:01:16 +00001014 InEdge* test = *testPtr;
1015 while (testPtr != edgeListEnd) {
1016 SkScalar testTop = test->fBounds.fTop;
1017 if (bottom <= testTop) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001018 break;
1019 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001020 SkScalar testBottom = test->fBounds.fBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001021 // OPTIMIZATION: Shortening the bottom is only interesting when filling
1022 // and when the edge is to the left of a longer edge. If it's a framing
1023 // edge, or part of the right, it won't effect the longer edges.
caryclark@google.com6008c6562012-02-15 22:01:16 +00001024 if (testTop > y) {
1025 bottom = testTop;
1026 break;
1027 }
1028 if (y < testBottom) {
1029 if (bottom > testBottom) {
1030 bottom = testBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001031 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001032 addToActive(activeEdges, test);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001033 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001034 test = *++testPtr;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001035 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001036 return bottom;
1037}
1038
1039static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel,
1040 SkTDArray<InEdge*>& edgeList) {
1041 size_t edgeCount = edges.count();
1042 if (edgeCount == 0) {
1043 return;
1044 }
1045 for (size_t index = 0; index < edgeCount; ++index) {
1046 *edgeList.append() = &edges[index];
1047 }
1048 edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1049 *edgeList.append() = &edgeSentinel;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001050 QSort<InEdge>(edgeList.begin(), edgeList.end() - 1);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001051}
1052
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001053
1054static void skipCoincidence(int lastWinding, int winding, int windingMask,
1055 ActiveEdge* activePtr, ActiveEdge* firstCoincident) {
1056 if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) {
1057 return;
1058 }
1059 if (lastWinding) {
1060 activePtr->fSkip = false;
1061 } else {
1062 firstCoincident->fSkip = false;
1063 }
1064}
1065
caryclark@google.com6008c6562012-02-15 22:01:16 +00001066static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges,
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001067 SkTDArray<ActiveEdge*>& edgeList, int windingMask, SkScalar y,
1068 SkScalar bottom) {
caryclark@google.com6008c6562012-02-15 22:01:16 +00001069 size_t edgeCount = activeEdges.count();
1070 if (edgeCount == 0) {
1071 return;
1072 }
1073 size_t index;
1074 for (index = 0; index < edgeCount; ++index) {
1075 ActiveEdge& activeEdge = activeEdges[index];
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001076 activeEdge.calcLeft(y);
caryclark@google.com6008c6562012-02-15 22:01:16 +00001077 activeEdge.fSkip = false;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001078 activeEdge.fIndex = index; // REMOVE: debugging only
caryclark@google.com6008c6562012-02-15 22:01:16 +00001079 *edgeList.append() = &activeEdge;
1080 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001081 QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1);
caryclark@google.com6008c6562012-02-15 22:01:16 +00001082 // remove coincident edges
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001083 // OPTIMIZE: remove edges? This is tricky because the current logic expects
1084 // the winding count to be maintained while skipping coincident edges. In
1085 // addition to removing the coincident edges, the remaining edges would need
1086 // to have a different winding value, possibly different per intercept span.
1087 int lastWinding = 0;
1088 bool lastSkipped = false;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001089 ActiveEdge* activePtr = edgeList[0];
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001090 ActiveEdge* firstCoincident = NULL;
1091 int winding = 0;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001092 for (index = 1; index < edgeCount; ++index) {
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001093 winding += activePtr->fWorkEdge.winding();
caryclark@google.com6008c6562012-02-15 22:01:16 +00001094 ActiveEdge* nextPtr = edgeList[index];
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001095 if (activePtr->isCoincidentWith(nextPtr, y)) {
1096 // the coincident edges may not have been sorted above -- advance
1097 // the edges and resort if needed
1098 // OPTIMIZE: if sorting is done incrementally as new edges are added
1099 // and not all at once as is done here, fold this test into the
1100 // current less than test.
1101 if (activePtr->swapCoincident(nextPtr, bottom)) {
1102 SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]);
1103 SkTSwap<ActiveEdge*>(activePtr, nextPtr);
1104 }
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001105 if (!firstCoincident) {
1106 firstCoincident = activePtr;
1107 }
1108 activePtr->fSkip = nextPtr->fSkip = lastSkipped = true;
1109 } else if (lastSkipped) {
1110 skipCoincidence(lastWinding, winding, windingMask, activePtr,
1111 firstCoincident);
1112 lastSkipped = false;
1113 firstCoincident = NULL;
1114 }
1115 if (!lastSkipped) {
1116 lastWinding = winding;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001117 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001118 activePtr = nextPtr;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001119 }
caryclark@google.com6b9cfb32012-02-16 21:24:41 +00001120 if (lastSkipped) {
1121 winding += activePtr->fWorkEdge.winding();
1122 skipCoincidence(lastWinding, winding, windingMask, activePtr,
1123 firstCoincident);
1124 }
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001125}
1126
1127// stitch edge and t range that satisfies operation
caryclark@google.com6008c6562012-02-15 22:01:16 +00001128static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y,
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001129 SkScalar bottom, int windingMask, OutEdgeBuilder& outBuilder) {
1130 int winding = 0;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001131 ActiveEdge** activeHandle = edgeList.begin() - 1;
1132 ActiveEdge** lastActive = edgeList.end();
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001133 if (gShowDebugf) {
caryclark@google.comc17972e2012-02-20 21:33:22 +00001134 SkDebugf("%s y=%g bottom=%g\n", __FUNCTION__, y, bottom);
1135 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001136 while (++activeHandle != lastActive) {
1137 ActiveEdge* activePtr = *activeHandle;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001138 const WorkEdge& wt = activePtr->fWorkEdge;
1139 int lastWinding = winding;
1140 winding += wt.winding();
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001141 if (activePtr->done(y)) {
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001142 // FIXME: if this is successful, rewrite done to take bottom as well
1143 if (activePtr->fDone) {
1144 continue;
1145 }
1146 if (activePtr->fYBottom >= bottom) {
1147 continue;
1148 }
1149 if (0) {
1150 SkDebugf("%s bot %g,%g\n", __FUNCTION__, activePtr->fYBottom, bottom);
1151 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001152 }
caryclark@google.comc17972e2012-02-20 21:33:22 +00001153 int opener = (lastWinding & windingMask) == 0;
1154 bool closer = (winding & windingMask) == 0;
1155 SkASSERT(!opener | !closer);
1156 bool inWinding = opener | closer;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001157 const SkPoint* clipped;
1158 uint8_t verb = wt.verb();
1159 bool moreToDo, aboveBottom;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001160 do {
1161 double currentT = activePtr->t();
caryclark@google.com6008c6562012-02-15 22:01:16 +00001162 SkASSERT(currentT < 1);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001163 const SkPoint* points = wt.fPts;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001164 double nextT;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001165 do {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001166 nextT = activePtr->nextT();
1167 if (verb == SkPath::kLine_Verb) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001168 SkPoint clippedPts[2];
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001169 // FIXME: obtuse: want efficient way to say
1170 // !currentT && currentT != 1 || !nextT && nextT != 1
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001171 if (currentT * nextT != 0 || currentT + nextT != 1) {
caryclark@google.com6008c6562012-02-15 22:01:16 +00001172 // OPTIMIZATION: if !inWinding, we only need
1173 // clipped[1].fY
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001174 LineSubDivide(points, currentT, nextT, clippedPts);
1175 clipped = clippedPts;
1176 } else {
1177 clipped = points;
1178 }
caryclark@google.com6008c6562012-02-15 22:01:16 +00001179 if (inWinding && !activePtr->fSkip) {
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001180 if (gShowDebugf) {
caryclark@google.comc17972e2012-02-20 21:33:22 +00001181 SkDebugf("%s line %g,%g %g,%g\n", __FUNCTION__,
1182 clipped[0].fX, clipped[0].fY,
1183 clipped[1].fX, clipped[1].fY);
1184 }
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001185 outBuilder.addLine(clipped);
caryclark@google.com6008c6562012-02-15 22:01:16 +00001186 }
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001187 activePtr->fSkip = false;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001188 } else {
1189 // FIXME: add all curve types
1190 SkASSERT(0);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001191 }
1192 currentT = nextT;
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001193 moreToDo = activePtr->advanceT();
1194 activePtr->fYBottom = clipped[verb].fY;
1195 aboveBottom = activePtr->fYBottom < bottom;
1196 } while (moreToDo & aboveBottom);
1197 } while ((moreToDo || activePtr->advance()) & aboveBottom);
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001198 }
1199}
1200
caryclark@google.comc6825902012-02-03 22:07:47 +00001201void simplify(const SkPath& path, bool asFill, SkPath& simple) {
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001202 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
1203 int windingMask = (path.getFillType() & 1) ? 1 : -1;
1204 simple.reset();
1205 simple.setFillType(SkPath::kEvenOdd_FillType);
caryclark@google.comc6825902012-02-03 22:07:47 +00001206 // turn path into list of edges increasing in y
caryclark@google.comcef7e3f2012-02-28 16:57:05 +00001207 // if an edge is a quad or a cubic with a y extrema, note it, but leave it
1208 // unbroken. Once we have a list, sort it, then walk the list (walk edges
1209 // twice that have y extrema's on top) and detect crossings -- look for raw
1210 // bounds that cross over, then tight bounds that cross
caryclark@google.com6680fb12012-02-07 22:10:51 +00001211 SkTArray<InEdge> edges;
1212 InEdgeBuilder builder(path, asFill, edges);
caryclark@google.com6680fb12012-02-07 22:10:51 +00001213 SkTDArray<InEdge*> edgeList;
caryclark@google.com6680fb12012-02-07 22:10:51 +00001214 InEdge edgeSentinel;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001215 makeEdgeList(edges, edgeSentinel, edgeList);
caryclark@google.com6680fb12012-02-07 22:10:51 +00001216 InEdge** currentPtr = edgeList.begin();
caryclark@google.comc6825902012-02-03 22:07:47 +00001217 // walk the sorted edges from top to bottom, computing accumulated winding
caryclark@google.com6680fb12012-02-07 22:10:51 +00001218 SkTDArray<ActiveEdge> activeEdges;
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001219 OutEdgeBuilder outBuilder(asFill);
1220 SkScalar y = (*currentPtr)->fBounds.fTop;
caryclark@google.comc6825902012-02-03 22:07:47 +00001221 do {
caryclark@google.com6680fb12012-02-07 22:10:51 +00001222 InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001223 SkScalar bottom = findBottom(currentPtr, edgeList.end(),
1224 activeEdges, y, asFill, lastPtr);
caryclark@google.comc17972e2012-02-20 21:33:22 +00001225 if (lastPtr > currentPtr) {
1226 addBottomT(currentPtr, lastPtr, bottom);
1227 addIntersectingTs(currentPtr, lastPtr);
1228 computeInterceptBottom(activeEdges, y, bottom);
1229 SkTDArray<ActiveEdge*> activeEdgeList;
caryclark@google.comcd4421d2012-03-01 19:16:31 +00001230 sortHorizontal(activeEdges, activeEdgeList, windingMask, y, bottom);
caryclark@google.comc17972e2012-02-20 21:33:22 +00001231 stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder);
1232 }
caryclark@google.comc6825902012-02-03 22:07:47 +00001233 y = bottom;
caryclark@google.com6008c6562012-02-15 22:01:16 +00001234 currentPtr = advanceEdges(activeEdges, currentPtr, lastPtr, y);
caryclark@google.comc6825902012-02-03 22:07:47 +00001235 } while (*currentPtr != &edgeSentinel);
caryclark@google.comc6825902012-02-03 22:07:47 +00001236 // assemble output path from string of pts, verbs
caryclark@google.comf8b000d2012-02-09 22:04:27 +00001237 outBuilder.bridge();
1238 outBuilder.assemble(simple);
caryclark@google.comc6825902012-02-03 22:07:47 +00001239}