1
2 /*
3 * Copyright 2009 The Android Open Source Project
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
9
10 #include "SkEdgeClipper.h"
11 #include "SkGeometry.h"
12
quick_reject(const SkRect & bounds,const SkRect & clip)13 static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
14 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
15 }
16
clamp_le(SkScalar & value,SkScalar max)17 static inline void clamp_le(SkScalar& value, SkScalar max) {
18 if (value > max) {
19 value = max;
20 }
21 }
22
clamp_ge(SkScalar & value,SkScalar min)23 static inline void clamp_ge(SkScalar& value, SkScalar min) {
24 if (value < min) {
25 value = min;
26 }
27 }
28
29 /* src[] must be monotonic in Y. This routine copies src into dst, and sorts
30 it to be increasing in Y. If it had to reverse the order of the points,
31 it returns true, otherwise it returns false
32 */
sort_increasing_Y(SkPoint dst[],const SkPoint src[],int count)33 static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) {
34 // we need the data to be monotonically increasing in Y
35 if (src[0].fY > src[count - 1].fY) {
36 for (int i = 0; i < count; i++) {
37 dst[i] = src[count - i - 1];
38 }
39 return true;
40 } else {
41 memcpy(dst, src, count * sizeof(SkPoint));
42 return false;
43 }
44 }
45
46 ///////////////////////////////////////////////////////////////////////////////
47
chopMonoQuadAt(SkScalar c0,SkScalar c1,SkScalar c2,SkScalar target,SkScalar * t)48 static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2,
49 SkScalar target, SkScalar* t) {
50 /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
51 * We solve for t, using quadratic equation, hence we have to rearrange
52 * our cooefficents to look like At^2 + Bt + C
53 */
54 SkScalar A = c0 - c1 - c1 + c2;
55 SkScalar B = 2*(c1 - c0);
56 SkScalar C = c0 - target;
57
58 SkScalar roots[2]; // we only expect one, but make room for 2 for safety
59 int count = SkFindUnitQuadRoots(A, B, C, roots);
60 if (count) {
61 *t = roots[0];
62 return true;
63 }
64 return false;
65 }
66
chopMonoQuadAtY(SkPoint pts[3],SkScalar y,SkScalar * t)67 static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) {
68 return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
69 }
70
chopMonoQuadAtX(SkPoint pts[3],SkScalar x,SkScalar * t)71 static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) {
72 return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t);
73 }
74
75 // Modify pts[] in place so that it is clipped in Y to the clip rect
chop_quad_in_Y(SkPoint pts[3],const SkRect & clip)76 static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) {
77 SkScalar t;
78 SkPoint tmp[5]; // for SkChopQuadAt
79
80 // are we partially above
81 if (pts[0].fY < clip.fTop) {
82 if (chopMonoQuadAtY(pts, clip.fTop, &t)) {
83 // take the 2nd chopped quad
84 SkChopQuadAt(pts, tmp, t);
85 // clamp to clean up imprecise numerics in the chop
86 tmp[2].fY = clip.fTop;
87 clamp_ge(tmp[3].fY, clip.fTop);
88
89 pts[0] = tmp[2];
90 pts[1] = tmp[3];
91 } else {
92 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
93 // so we just clamp against the top
94 for (int i = 0; i < 3; i++) {
95 if (pts[i].fY < clip.fTop) {
96 pts[i].fY = clip.fTop;
97 }
98 }
99 }
100 }
101
102 // are we partially below
103 if (pts[2].fY > clip.fBottom) {
104 if (chopMonoQuadAtY(pts, clip.fBottom, &t)) {
105 SkChopQuadAt(pts, tmp, t);
106 // clamp to clean up imprecise numerics in the chop
107 clamp_le(tmp[1].fY, clip.fBottom);
108 tmp[2].fY = clip.fBottom;
109
110 pts[1] = tmp[1];
111 pts[2] = tmp[2];
112 } else {
113 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
114 // so we just clamp against the bottom
115 for (int i = 0; i < 3; i++) {
116 if (pts[i].fY > clip.fBottom) {
117 pts[i].fY = clip.fBottom;
118 }
119 }
120 }
121 }
122 }
123
124 // srcPts[] must be monotonic in X and Y
clipMonoQuad(const SkPoint srcPts[3],const SkRect & clip)125 void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) {
126 SkPoint pts[3];
127 bool reverse = sort_increasing_Y(pts, srcPts, 3);
128
129 // are we completely above or below
130 if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
131 return;
132 }
133
134 // Now chop so that pts is contained within clip in Y
135 chop_quad_in_Y(pts, clip);
136
137 if (pts[0].fX > pts[2].fX) {
138 SkTSwap<SkPoint>(pts[0], pts[2]);
139 reverse = !reverse;
140 }
141 SkASSERT(pts[0].fX <= pts[1].fX);
142 SkASSERT(pts[1].fX <= pts[2].fX);
143
144 // Now chop in X has needed, and record the segments
145
146 if (pts[2].fX <= clip.fLeft) { // wholly to the left
147 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
148 return;
149 }
150 if (pts[0].fX >= clip.fRight) { // wholly to the right
151 if (!this->canCullToTheRight()) {
152 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
153 }
154 return;
155 }
156
157 SkScalar t;
158 SkPoint tmp[5]; // for SkChopQuadAt
159
160 // are we partially to the left
161 if (pts[0].fX < clip.fLeft) {
162 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
163 SkChopQuadAt(pts, tmp, t);
164 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
165 // clamp to clean up imprecise numerics in the chop
166 tmp[2].fX = clip.fLeft;
167 clamp_ge(tmp[3].fX, clip.fLeft);
168
169 pts[0] = tmp[2];
170 pts[1] = tmp[3];
171 } else {
172 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
173 // so we just clamp against the left
174 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
175 return;
176 }
177 }
178
179 // are we partially to the right
180 if (pts[2].fX > clip.fRight) {
181 if (chopMonoQuadAtX(pts, clip.fRight, &t)) {
182 SkChopQuadAt(pts, tmp, t);
183 // clamp to clean up imprecise numerics in the chop
184 clamp_le(tmp[1].fX, clip.fRight);
185 tmp[2].fX = clip.fRight;
186
187 this->appendQuad(tmp, reverse);
188 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
189 } else {
190 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
191 // so we just clamp against the right
192 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
193 }
194 } else { // wholly inside the clip
195 this->appendQuad(pts, reverse);
196 }
197 }
198
clipQuad(const SkPoint srcPts[3],const SkRect & clip)199 bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
200 fCurrPoint = fPoints;
201 fCurrVerb = fVerbs;
202
203 SkRect bounds;
204 bounds.set(srcPts, 3);
205
206 if (!quick_reject(bounds, clip)) {
207 SkPoint monoY[5];
208 int countY = SkChopQuadAtYExtrema(srcPts, monoY);
209 for (int y = 0; y <= countY; y++) {
210 SkPoint monoX[5];
211 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
212 for (int x = 0; x <= countX; x++) {
213 this->clipMonoQuad(&monoX[x * 2], clip);
214 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
215 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
216 }
217 }
218 }
219
220 *fCurrVerb = SkPath::kDone_Verb;
221 fCurrPoint = fPoints;
222 fCurrVerb = fVerbs;
223 return SkPath::kDone_Verb != fVerbs[0];
224 }
225
226 ///////////////////////////////////////////////////////////////////////////////
227
228 // Modify pts[] in place so that it is clipped in Y to the clip rect
chop_cubic_in_Y(SkPoint pts[4],const SkRect & clip)229 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
230
231 // are we partially above
232 if (pts[0].fY < clip.fTop) {
233 SkPoint tmp[7];
234 if (SkChopMonoCubicAtY(pts, clip.fTop, tmp)) {
235 // tmp[3, 4].fY should all be to the below clip.fTop.
236 // Since we can't trust the numerics of
237 // the chopper, we force those conditions now
238 tmp[3].fY = clip.fTop;
239 clamp_ge(tmp[4].fY, clip.fTop);
240
241 pts[0] = tmp[3];
242 pts[1] = tmp[4];
243 pts[2] = tmp[5];
244 } else {
245 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
246 // so we just clamp against the top
247 for (int i = 0; i < 4; i++) {
248 clamp_ge(pts[i].fY, clip.fTop);
249 }
250 }
251 }
252
253 // are we partially below
254 if (pts[3].fY > clip.fBottom) {
255 SkPoint tmp[7];
256 if (SkChopMonoCubicAtY(pts, clip.fBottom, tmp)) {
257 tmp[3].fY = clip.fBottom;
258 clamp_le(tmp[2].fY, clip.fBottom);
259
260 pts[1] = tmp[1];
261 pts[2] = tmp[2];
262 pts[3] = tmp[3];
263 } else {
264 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
265 // so we just clamp against the bottom
266 for (int i = 0; i < 4; i++) {
267 clamp_le(pts[i].fY, clip.fBottom);
268 }
269 }
270 }
271 }
272
273 // srcPts[] must be monotonic in X and Y
clipMonoCubic(const SkPoint src[4],const SkRect & clip)274 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
275 SkPoint pts[4];
276 bool reverse = sort_increasing_Y(pts, src, 4);
277
278 // are we completely above or below
279 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
280 return;
281 }
282
283 // Now chop so that pts is contained within clip in Y
284 chop_cubic_in_Y(pts, clip);
285
286 if (pts[0].fX > pts[3].fX) {
287 SkTSwap<SkPoint>(pts[0], pts[3]);
288 SkTSwap<SkPoint>(pts[1], pts[2]);
289 reverse = !reverse;
290 }
291
292 // Now chop in X has needed, and record the segments
293
294 if (pts[3].fX <= clip.fLeft) { // wholly to the left
295 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
296 return;
297 }
298 if (pts[0].fX >= clip.fRight) { // wholly to the right
299 if (!this->canCullToTheRight()) {
300 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
301 }
302 return;
303 }
304
305 // are we partially to the left
306 if (pts[0].fX < clip.fLeft) {
307 SkPoint tmp[7];
308 if (SkChopMonoCubicAtX(pts, clip.fLeft, tmp)) {
309 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
310
311 // tmp[3, 4].fX should all be to the right of clip.fLeft.
312 // Since we can't trust the numerics of
313 // the chopper, we force those conditions now
314 tmp[3].fX = clip.fLeft;
315 clamp_ge(tmp[4].fX, clip.fLeft);
316
317 pts[0] = tmp[3];
318 pts[1] = tmp[4];
319 pts[2] = tmp[5];
320 } else {
321 // if chopMonocubicAtY failed, then we may have hit inexact numerics
322 // so we just clamp against the left
323 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
324 return;
325 }
326 }
327
328 // are we partially to the right
329 if (pts[3].fX > clip.fRight) {
330 SkPoint tmp[7];
331 if (SkChopMonoCubicAtX(pts, clip.fRight, tmp)) {
332 tmp[3].fX = clip.fRight;
333 clamp_le(tmp[2].fX, clip.fRight);
334
335 this->appendCubic(tmp, reverse);
336 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
337 } else {
338 // if chopMonoCubicAtX failed, then we may have hit inexact numerics
339 // so we just clamp against the right
340 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
341 }
342 } else { // wholly inside the clip
343 this->appendCubic(pts, reverse);
344 }
345 }
346
clipCubic(const SkPoint srcPts[4],const SkRect & clip)347 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
348 fCurrPoint = fPoints;
349 fCurrVerb = fVerbs;
350
351 SkRect bounds;
352 bounds.set(srcPts, 4);
353
354 if (!quick_reject(bounds, clip)) {
355 SkPoint monoY[10];
356 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
357 for (int y = 0; y <= countY; y++) {
358 SkPoint monoX[10];
359 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
360 for (int x = 0; x <= countX; x++) {
361 this->clipMonoCubic(&monoX[x * 3], clip);
362 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
363 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
364 }
365 }
366 }
367
368 *fCurrVerb = SkPath::kDone_Verb;
369 fCurrPoint = fPoints;
370 fCurrVerb = fVerbs;
371 return SkPath::kDone_Verb != fVerbs[0];
372 }
373
374 ///////////////////////////////////////////////////////////////////////////////
375
appendVLine(SkScalar x,SkScalar y0,SkScalar y1,bool reverse)376 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
377 bool reverse) {
378 *fCurrVerb++ = SkPath::kLine_Verb;
379
380 if (reverse) {
381 SkTSwap<SkScalar>(y0, y1);
382 }
383 fCurrPoint[0].set(x, y0);
384 fCurrPoint[1].set(x, y1);
385 fCurrPoint += 2;
386 }
387
appendQuad(const SkPoint pts[3],bool reverse)388 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
389 *fCurrVerb++ = SkPath::kQuad_Verb;
390
391 if (reverse) {
392 fCurrPoint[0] = pts[2];
393 fCurrPoint[2] = pts[0];
394 } else {
395 fCurrPoint[0] = pts[0];
396 fCurrPoint[2] = pts[2];
397 }
398 fCurrPoint[1] = pts[1];
399 fCurrPoint += 3;
400 }
401
appendCubic(const SkPoint pts[4],bool reverse)402 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
403 *fCurrVerb++ = SkPath::kCubic_Verb;
404
405 if (reverse) {
406 for (int i = 0; i < 4; i++) {
407 fCurrPoint[i] = pts[3 - i];
408 }
409 } else {
410 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
411 }
412 fCurrPoint += 4;
413 }
414
next(SkPoint pts[])415 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
416 SkPath::Verb verb = *fCurrVerb;
417
418 switch (verb) {
419 case SkPath::kLine_Verb:
420 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
421 fCurrPoint += 2;
422 fCurrVerb += 1;
423 break;
424 case SkPath::kQuad_Verb:
425 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
426 fCurrPoint += 3;
427 fCurrVerb += 1;
428 break;
429 case SkPath::kCubic_Verb:
430 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
431 fCurrPoint += 4;
432 fCurrVerb += 1;
433 break;
434 case SkPath::kDone_Verb:
435 break;
436 default:
437 SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
438 break;
439 }
440 return verb;
441 }
442
443 ///////////////////////////////////////////////////////////////////////////////
444
445 #ifdef SK_DEBUG
assert_monotonic(const SkScalar coord[],int count)446 static void assert_monotonic(const SkScalar coord[], int count) {
447 if (coord[0] > coord[(count - 1) * 2]) {
448 for (int i = 1; i < count; i++) {
449 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
450 }
451 } else if (coord[0] < coord[(count - 1) * 2]) {
452 for (int i = 1; i < count; i++) {
453 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
454 }
455 } else {
456 for (int i = 1; i < count; i++) {
457 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
458 }
459 }
460 }
461
sk_assert_monotonic_y(const SkPoint pts[],int count)462 void sk_assert_monotonic_y(const SkPoint pts[], int count) {
463 if (count > 1) {
464 assert_monotonic(&pts[0].fY, count);
465 }
466 }
467
sk_assert_monotonic_x(const SkPoint pts[],int count)468 void sk_assert_monotonic_x(const SkPoint pts[], int count) {
469 if (count > 1) {
470 assert_monotonic(&pts[0].fX, count);
471 }
472 }
473 #endif
474