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