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
mono_cubic_closestT(const SkScalar src[],SkScalar x)228 static SkScalar mono_cubic_closestT(const SkScalar src[], SkScalar x) {
229 SkScalar t = 0.5f;
230 SkScalar lastT;
231 SkScalar bestT SK_INIT_TO_AVOID_WARNING;
232 SkScalar step = 0.25f;
233 SkScalar D = src[0];
234 SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
235 SkScalar B = 3*(src[4] - src[2] - src[2] + D);
236 SkScalar C = 3*(src[2] - D);
237 x -= D;
238 SkScalar closest = SK_ScalarMax;
239 do {
240 SkScalar loc = ((A * t + B) * t + C) * t;
241 SkScalar dist = SkScalarAbs(loc - x);
242 if (closest > dist) {
243 closest = dist;
244 bestT = t;
245 }
246 lastT = t;
247 t += loc < x ? step : -step;
248 step *= 0.5f;
249 } while (closest > 0.25f && lastT != t);
250 return bestT;
251 }
252
chop_mono_cubic_at_y(SkPoint src[4],SkScalar y,SkPoint dst[7])253 static void chop_mono_cubic_at_y(SkPoint src[4], SkScalar y, SkPoint dst[7]) {
254 if (SkChopMonoCubicAtY(src, y, dst)) {
255 return;
256 }
257 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y));
258 }
259
260 // 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)261 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
262
263 // are we partially above
264 if (pts[0].fY < clip.fTop) {
265 SkPoint tmp[7];
266 chop_mono_cubic_at_y(pts, clip.fTop, tmp);
267 // tmp[3, 4].fY should all be to the below clip.fTop.
268 // Since we can't trust the numerics of
269 // the chopper, we force those conditions now
270 tmp[3].fY = clip.fTop;
271 clamp_ge(tmp[4].fY, clip.fTop);
272
273 pts[0] = tmp[3];
274 pts[1] = tmp[4];
275 pts[2] = tmp[5];
276 }
277
278 // are we partially below
279 if (pts[3].fY > clip.fBottom) {
280 SkPoint tmp[7];
281 chop_mono_cubic_at_y(pts, clip.fBottom, tmp);
282 tmp[3].fY = clip.fBottom;
283 clamp_le(tmp[2].fY, clip.fBottom);
284
285 pts[1] = tmp[1];
286 pts[2] = tmp[2];
287 pts[3] = tmp[3];
288 }
289 }
290
chop_mono_cubic_at_x(SkPoint src[4],SkScalar x,SkPoint dst[7])291 static void chop_mono_cubic_at_x(SkPoint src[4], SkScalar x, SkPoint dst[7]) {
292 if (SkChopMonoCubicAtX(src, x, dst)) {
293 return;
294 }
295 SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x));
296 }
297
298 // srcPts[] must be monotonic in X and Y
clipMonoCubic(const SkPoint src[4],const SkRect & clip)299 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
300 SkPoint pts[4];
301 bool reverse = sort_increasing_Y(pts, src, 4);
302
303 // are we completely above or below
304 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
305 return;
306 }
307
308 // Now chop so that pts is contained within clip in Y
309 chop_cubic_in_Y(pts, clip);
310
311 if (pts[0].fX > pts[3].fX) {
312 SkTSwap<SkPoint>(pts[0], pts[3]);
313 SkTSwap<SkPoint>(pts[1], pts[2]);
314 reverse = !reverse;
315 }
316
317 // Now chop in X has needed, and record the segments
318
319 if (pts[3].fX <= clip.fLeft) { // wholly to the left
320 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
321 return;
322 }
323 if (pts[0].fX >= clip.fRight) { // wholly to the right
324 if (!this->canCullToTheRight()) {
325 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
326 }
327 return;
328 }
329
330 // are we partially to the left
331 if (pts[0].fX < clip.fLeft) {
332 SkPoint tmp[7];
333 chop_mono_cubic_at_x(pts, clip.fLeft, tmp);
334 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
335
336 // tmp[3, 4].fX should all be to the right of clip.fLeft.
337 // Since we can't trust the numerics of
338 // the chopper, we force those conditions now
339 tmp[3].fX = clip.fLeft;
340 clamp_ge(tmp[4].fX, clip.fLeft);
341
342 pts[0] = tmp[3];
343 pts[1] = tmp[4];
344 pts[2] = tmp[5];
345 }
346
347 // are we partially to the right
348 if (pts[3].fX > clip.fRight) {
349 SkPoint tmp[7];
350 chop_mono_cubic_at_x(pts, clip.fRight, tmp);
351 tmp[3].fX = clip.fRight;
352 clamp_le(tmp[2].fX, clip.fRight);
353
354 this->appendCubic(tmp, reverse);
355 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
356 } else { // wholly inside the clip
357 this->appendCubic(pts, reverse);
358 }
359 }
360
quick_reject_in_y(const SkPoint pts[4],const SkRect & clip)361 static bool quick_reject_in_y(const SkPoint pts[4], const SkRect& clip) {
362 Sk4s ys(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY);
363 Sk4s t(clip.top());
364 Sk4s b(clip.bottom());
365
366 return (ys < t).allTrue() || (ys > b).allTrue();
367 }
368
clipCubic(const SkPoint srcPts[4],const SkRect & clip)369 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
370 fCurrPoint = fPoints;
371 fCurrVerb = fVerbs;
372
373 if (!quick_reject_in_y(srcPts, clip)) {
374 SkPoint monoY[10];
375 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
376 for (int y = 0; y <= countY; y++) {
377 SkPoint monoX[10];
378 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
379 for (int x = 0; x <= countX; x++) {
380 this->clipMonoCubic(&monoX[x * 3], clip);
381 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
382 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
383 }
384 }
385 }
386
387 *fCurrVerb = SkPath::kDone_Verb;
388 fCurrPoint = fPoints;
389 fCurrVerb = fVerbs;
390 return SkPath::kDone_Verb != fVerbs[0];
391 }
392
393 ///////////////////////////////////////////////////////////////////////////////
394
appendVLine(SkScalar x,SkScalar y0,SkScalar y1,bool reverse)395 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
396 bool reverse) {
397 *fCurrVerb++ = SkPath::kLine_Verb;
398
399 if (reverse) {
400 SkTSwap<SkScalar>(y0, y1);
401 }
402 fCurrPoint[0].set(x, y0);
403 fCurrPoint[1].set(x, y1);
404 fCurrPoint += 2;
405 }
406
appendQuad(const SkPoint pts[3],bool reverse)407 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
408 *fCurrVerb++ = SkPath::kQuad_Verb;
409
410 if (reverse) {
411 fCurrPoint[0] = pts[2];
412 fCurrPoint[2] = pts[0];
413 } else {
414 fCurrPoint[0] = pts[0];
415 fCurrPoint[2] = pts[2];
416 }
417 fCurrPoint[1] = pts[1];
418 fCurrPoint += 3;
419 }
420
appendCubic(const SkPoint pts[4],bool reverse)421 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
422 *fCurrVerb++ = SkPath::kCubic_Verb;
423
424 if (reverse) {
425 for (int i = 0; i < 4; i++) {
426 fCurrPoint[i] = pts[3 - i];
427 }
428 } else {
429 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
430 }
431 fCurrPoint += 4;
432 }
433
next(SkPoint pts[])434 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
435 SkPath::Verb verb = *fCurrVerb;
436
437 switch (verb) {
438 case SkPath::kLine_Verb:
439 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
440 fCurrPoint += 2;
441 fCurrVerb += 1;
442 break;
443 case SkPath::kQuad_Verb:
444 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
445 fCurrPoint += 3;
446 fCurrVerb += 1;
447 break;
448 case SkPath::kCubic_Verb:
449 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
450 fCurrPoint += 4;
451 fCurrVerb += 1;
452 break;
453 case SkPath::kDone_Verb:
454 break;
455 default:
456 SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
457 break;
458 }
459 return verb;
460 }
461
462 ///////////////////////////////////////////////////////////////////////////////
463
464 #ifdef SK_DEBUG
assert_monotonic(const SkScalar coord[],int count)465 static void assert_monotonic(const SkScalar coord[], int count) {
466 if (coord[0] > coord[(count - 1) * 2]) {
467 for (int i = 1; i < count; i++) {
468 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
469 }
470 } else if (coord[0] < coord[(count - 1) * 2]) {
471 for (int i = 1; i < count; i++) {
472 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
473 }
474 } else {
475 for (int i = 1; i < count; i++) {
476 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
477 }
478 }
479 }
480
sk_assert_monotonic_y(const SkPoint pts[],int count)481 void sk_assert_monotonic_y(const SkPoint pts[], int count) {
482 if (count > 1) {
483 assert_monotonic(&pts[0].fY, count);
484 }
485 }
486
sk_assert_monotonic_x(const SkPoint pts[],int count)487 void sk_assert_monotonic_x(const SkPoint pts[], int count) {
488 if (count > 1) {
489 assert_monotonic(&pts[0].fX, count);
490 }
491 }
492 #endif
493