1 /*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "SkEdgeClipper.h"
18 #include "SkGeometry.h"
19
quick_reject(const SkRect & bounds,const SkRect & clip)20 static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
21 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
22 }
23
clamp_le(SkScalar & value,SkScalar max)24 static inline void clamp_le(SkScalar& value, SkScalar max) {
25 if (value > max) {
26 value = max;
27 }
28 }
29
clamp_ge(SkScalar & value,SkScalar min)30 static inline void clamp_ge(SkScalar& value, SkScalar min) {
31 if (value < min) {
32 value = min;
33 }
34 }
35
36 /* src[] must be monotonic in Y. This routine copies src into dst, and sorts
37 it to be increasing in Y. If it had to reverse the order of the points,
38 it returns true, otherwise it returns false
39 */
sort_increasing_Y(SkPoint dst[],const SkPoint src[],int count)40 static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) {
41 // we need the data to be monotonically increasing in Y
42 if (src[0].fY > src[count - 1].fY) {
43 for (int i = 0; i < count; i++) {
44 dst[i] = src[count - i - 1];
45 }
46 return true;
47 } else {
48 memcpy(dst, src, count * sizeof(SkPoint));
49 return false;
50 }
51 }
52
53 ///////////////////////////////////////////////////////////////////////////////
54
chopMonoQuadAt(SkScalar c0,SkScalar c1,SkScalar c2,SkScalar target,SkScalar * t)55 static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2,
56 SkScalar target, SkScalar* t) {
57 /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
58 * We solve for t, using quadratic equation, hence we have to rearrange
59 * our cooefficents to look like At^2 + Bt + C
60 */
61 SkScalar A = c0 - c1 - c1 + c2;
62 SkScalar B = 2*(c1 - c0);
63 SkScalar C = c0 - target;
64
65 SkScalar roots[2]; // we only expect one, but make room for 2 for safety
66 int count = SkFindUnitQuadRoots(A, B, C, roots);
67 if (count) {
68 *t = roots[0];
69 return true;
70 }
71 return false;
72 }
73
chopMonoQuadAtY(SkPoint pts[3],SkScalar y,SkScalar * t)74 static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) {
75 return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
76 }
77
chopMonoQuadAtX(SkPoint pts[3],SkScalar x,SkScalar * t)78 static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) {
79 return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t);
80 }
81
82 // 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)83 static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) {
84 SkScalar t;
85 SkPoint tmp[5]; // for SkChopQuadAt
86
87 // are we partially above
88 if (pts[0].fY < clip.fTop) {
89 if (chopMonoQuadAtY(pts, clip.fTop, &t)) {
90 // take the 2nd chopped quad
91 SkChopQuadAt(pts, tmp, t);
92 clamp_ge(tmp[2].fY, clip.fTop);
93 clamp_ge(tmp[3].fY, clip.fTop);
94 pts[0] = tmp[2];
95 pts[1] = tmp[3];
96 } else {
97 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
98 // so we just clamp against the top
99 for (int i = 0; i < 3; i++) {
100 if (pts[i].fY < clip.fTop) {
101 pts[i].fY = clip.fTop;
102 }
103 }
104 }
105 }
106
107 // are we partially below
108 if (pts[2].fY > clip.fBottom) {
109 if (chopMonoQuadAtY(pts, clip.fBottom, &t)) {
110 SkChopQuadAt(pts, tmp, t);
111 clamp_le(tmp[1].fY, clip.fBottom);
112 clamp_le(tmp[2].fY, clip.fBottom);
113 pts[1] = tmp[1];
114 pts[2] = tmp[2];
115 } else {
116 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
117 // so we just clamp against the bottom
118 for (int i = 0; i < 3; i++) {
119 if (pts[i].fY > clip.fBottom) {
120 pts[i].fY = clip.fBottom;
121 }
122 }
123 }
124 }
125 }
126
127 // srcPts[] must be monotonic in X and Y
clipMonoQuad(const SkPoint srcPts[3],const SkRect & clip)128 void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) {
129 SkPoint pts[3];
130 bool reverse = sort_increasing_Y(pts, srcPts, 3);
131
132 // are we completely above or below
133 if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
134 return;
135 }
136
137 // Now chop so that pts is contained within clip in Y
138 chop_quad_in_Y(pts, clip);
139
140 if (pts[0].fX > pts[2].fX) {
141 SkTSwap<SkPoint>(pts[0], pts[2]);
142 reverse = !reverse;
143 }
144 SkASSERT(pts[0].fX <= pts[1].fX);
145 SkASSERT(pts[1].fX <= pts[2].fX);
146
147 // Now chop in X has needed, and record the segments
148
149 if (pts[2].fX <= clip.fLeft) { // wholly to the left
150 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
151 return;
152 }
153 if (pts[0].fX >= clip.fRight) { // wholly to the right
154 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
155 return;
156 }
157
158 SkScalar t;
159 SkPoint tmp[5]; // for SkChopQuadAt
160
161 // are we partially to the left
162 if (pts[0].fX < clip.fLeft) {
163 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
164 SkChopQuadAt(pts, tmp, t);
165 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
166 clamp_ge(tmp[2].fX, clip.fLeft);
167 clamp_ge(tmp[3].fX, clip.fLeft);
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_le(tmp[1].fX, clip.fRight);
183 clamp_le(tmp[2].fX, clip.fRight);
184 this->appendQuad(tmp, reverse);
185 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
186 } else {
187 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
188 // so we just clamp against the right
189 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
190 }
191 } else { // wholly inside the clip
192 this->appendQuad(pts, reverse);
193 }
194 }
195
clipQuad(const SkPoint srcPts[3],const SkRect & clip)196 bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
197 fCurrPoint = fPoints;
198 fCurrVerb = fVerbs;
199
200 SkRect bounds;
201 bounds.set(srcPts, 3);
202
203 if (!quick_reject(bounds, clip)) {
204 SkPoint monoY[5];
205 int countY = SkChopQuadAtYExtrema(srcPts, monoY);
206 for (int y = 0; y <= countY; y++) {
207 SkPoint monoX[5];
208 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
209 for (int x = 0; x <= countX; x++) {
210 this->clipMonoQuad(&monoX[x * 2], clip);
211 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
212 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
213 }
214 }
215 }
216
217 *fCurrVerb = SkPath::kDone_Verb;
218 fCurrPoint = fPoints;
219 fCurrVerb = fVerbs;
220 return SkPath::kDone_Verb != fVerbs[0];
221 }
222
223 ///////////////////////////////////////////////////////////////////////////////
224
eval_cubic_coeff(SkScalar A,SkScalar B,SkScalar C,SkScalar D,SkScalar t)225 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
226 SkScalar D, SkScalar t) {
227 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
228 }
229
230 /* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
231 t value such that cubic(t) = target
232 */
chopMonoCubicAt(SkScalar c0,SkScalar c1,SkScalar c2,SkScalar c3,SkScalar target,SkScalar * t)233 static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
234 SkScalar target, SkScalar* t) {
235 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
236 SkASSERT(c0 < target && target < c3);
237
238 SkScalar D = c0 - target;
239 SkScalar A = c3 + 3*(c1 - c2) - c0;
240 SkScalar B = 3*(c2 - c1 - c1 + c0);
241 SkScalar C = 3*(c1 - c0);
242
243 const SkScalar TOLERANCE = SK_Scalar1 / 4096;
244 SkScalar minT = 0;
245 SkScalar maxT = SK_Scalar1;
246 SkScalar mid;
247 int i;
248 for (i = 0; i < 16; i++) {
249 mid = SkScalarAve(minT, maxT);
250 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
251 if (delta < 0) {
252 minT = mid;
253 delta = -delta;
254 } else {
255 maxT = mid;
256 }
257 if (delta < TOLERANCE) {
258 break;
259 }
260 }
261 *t = mid;
262 // SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t));
263 return true;
264 }
265
chopMonoCubicAtY(SkPoint pts[4],SkScalar y,SkScalar * t)266 static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) {
267 return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t);
268 }
269
chopMonoCubicAtX(SkPoint pts[4],SkScalar x,SkScalar * t)270 static bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) {
271 return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t);
272 }
273
274 // 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)275 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
276 SkScalar t;
277 SkPoint tmp[7]; // for SkChopCubicAt
278
279 // are we partially above
280 if (pts[0].fY < clip.fTop) {
281 if (chopMonoCubicAtY(pts, clip.fTop, &t)) {
282 SkChopCubicAt(pts, tmp, t);
283 // given the imprecision of computing t, we just slam our Y coord
284 // to the top of the clip. This also saves us in the bad case where
285 // the t was soooo bad that the entire segment could have been
286 // below fBottom
287 tmp[3].fY = clip.fTop;
288 clamp_ge(tmp[4].fY, clip.fTop);
289 clamp_ge(tmp[5].fY, clip.fTop);
290 pts[0] = tmp[3];
291 pts[1] = tmp[4];
292 pts[2] = tmp[5];
293 } else {
294 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
295 // so we just clamp against the top
296 for (int i = 0; i < 4; i++) {
297 clamp_ge(pts[i].fY, clip.fTop);
298 }
299 }
300 }
301
302 // are we partially below
303 if (pts[3].fY > clip.fBottom) {
304 if (chopMonoCubicAtY(pts, clip.fBottom, &t)) {
305 SkChopCubicAt(pts, tmp, t);
306 clamp_le(tmp[1].fY, clip.fBottom);
307 clamp_le(tmp[2].fY, clip.fBottom);
308 clamp_le(tmp[3].fY, clip.fBottom);
309 pts[1] = tmp[1];
310 pts[2] = tmp[2];
311 pts[3] = tmp[3];
312 } else {
313 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
314 // so we just clamp against the bottom
315 for (int i = 0; i < 4; i++) {
316 clamp_le(pts[i].fY, clip.fBottom);
317 }
318 }
319 }
320 }
321
322 // srcPts[] must be monotonic in X and Y
clipMonoCubic(const SkPoint src[4],const SkRect & clip)323 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
324 SkPoint pts[4];
325 bool reverse = sort_increasing_Y(pts, src, 4);
326
327 // are we completely above or below
328 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
329 return;
330 }
331
332 // Now chop so that pts is contained within clip in Y
333 chop_cubic_in_Y(pts, clip);
334
335 if (pts[0].fX > pts[3].fX) {
336 SkTSwap<SkPoint>(pts[0], pts[3]);
337 SkTSwap<SkPoint>(pts[1], pts[2]);
338 reverse = !reverse;
339 }
340
341 // Now chop in X has needed, and record the segments
342
343 if (pts[3].fX <= clip.fLeft) { // wholly to the left
344 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
345 return;
346 }
347 if (pts[0].fX >= clip.fRight) { // wholly to the right
348 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
349 return;
350 }
351
352 SkScalar t;
353 SkPoint tmp[7];
354
355 // are we partially to the left
356 if (pts[0].fX < clip.fLeft) {
357 if (chopMonoCubicAtX(pts, clip.fLeft, &t)) {
358 SkChopCubicAt(pts, tmp, t);
359 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
360 clamp_ge(tmp[3].fX, clip.fLeft);
361 clamp_ge(tmp[4].fX, clip.fLeft);
362 clamp_ge(tmp[5].fX, clip.fLeft);
363 pts[0] = tmp[3];
364 pts[1] = tmp[4];
365 pts[2] = tmp[5];
366 } else {
367 // if chopMonocubicAtY failed, then we may have hit inexact numerics
368 // so we just clamp against the left
369 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
370 return;
371 }
372 }
373
374 // are we partially to the right
375 if (pts[3].fX > clip.fRight) {
376 if (chopMonoCubicAtX(pts, clip.fRight, &t)) {
377 SkChopCubicAt(pts, tmp, t);
378 clamp_le(tmp[1].fX, clip.fRight);
379 clamp_le(tmp[2].fX, clip.fRight);
380 clamp_le(tmp[3].fX, clip.fRight);
381 this->appendCubic(tmp, reverse);
382 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
383 } else {
384 // if chopMonoCubicAtX failed, then we may have hit inexact numerics
385 // so we just clamp against the right
386 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
387 }
388 } else { // wholly inside the clip
389 this->appendCubic(pts, reverse);
390 }
391 }
392
clipCubic(const SkPoint srcPts[4],const SkRect & clip)393 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
394 fCurrPoint = fPoints;
395 fCurrVerb = fVerbs;
396
397 SkRect bounds;
398 bounds.set(srcPts, 4);
399
400 if (!quick_reject(bounds, clip)) {
401 SkPoint monoY[10];
402 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
403 for (int y = 0; y <= countY; y++) {
404 // sk_assert_monotonic_y(&monoY[y * 3], 4);
405 SkPoint monoX[10];
406 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
407 for (int x = 0; x <= countX; x++) {
408 // sk_assert_monotonic_y(&monoX[x * 3], 4);
409 // sk_assert_monotonic_x(&monoX[x * 3], 4);
410 this->clipMonoCubic(&monoX[x * 3], clip);
411 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
412 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
413 }
414 }
415 }
416
417 *fCurrVerb = SkPath::kDone_Verb;
418 fCurrPoint = fPoints;
419 fCurrVerb = fVerbs;
420 return SkPath::kDone_Verb != fVerbs[0];
421 }
422
423 ///////////////////////////////////////////////////////////////////////////////
424
appendVLine(SkScalar x,SkScalar y0,SkScalar y1,bool reverse)425 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
426 bool reverse) {
427 *fCurrVerb++ = SkPath::kLine_Verb;
428
429 if (reverse) {
430 SkTSwap<SkScalar>(y0, y1);
431 }
432 fCurrPoint[0].set(x, y0);
433 fCurrPoint[1].set(x, y1);
434 fCurrPoint += 2;
435 }
436
appendQuad(const SkPoint pts[3],bool reverse)437 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
438 *fCurrVerb++ = SkPath::kQuad_Verb;
439
440 if (reverse) {
441 fCurrPoint[0] = pts[2];
442 fCurrPoint[2] = pts[0];
443 } else {
444 fCurrPoint[0] = pts[0];
445 fCurrPoint[2] = pts[2];
446 }
447 fCurrPoint[1] = pts[1];
448 fCurrPoint += 3;
449 }
450
appendCubic(const SkPoint pts[4],bool reverse)451 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
452 *fCurrVerb++ = SkPath::kCubic_Verb;
453
454 if (reverse) {
455 for (int i = 0; i < 4; i++) {
456 fCurrPoint[i] = pts[3 - i];
457 }
458 } else {
459 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
460 }
461 fCurrPoint += 4;
462 }
463
next(SkPoint pts[])464 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
465 SkPath::Verb verb = *fCurrVerb;
466
467 switch (verb) {
468 case SkPath::kLine_Verb:
469 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
470 fCurrPoint += 2;
471 fCurrVerb += 1;
472 break;
473 case SkPath::kQuad_Verb:
474 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
475 fCurrPoint += 3;
476 fCurrVerb += 1;
477 break;
478 case SkPath::kCubic_Verb:
479 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
480 fCurrPoint += 4;
481 fCurrVerb += 1;
482 break;
483 case SkPath::kDone_Verb:
484 break;
485 default:
486 SkASSERT(!"unexpected verb in quadclippper2 iter");
487 break;
488 }
489 return verb;
490 }
491
492 ///////////////////////////////////////////////////////////////////////////////
493
494 #ifdef SK_DEBUG
assert_monotonic(const SkScalar coord[],int count)495 static void assert_monotonic(const SkScalar coord[], int count) {
496 if (coord[0] > coord[(count - 1) * 2]) {
497 for (int i = 1; i < count; i++) {
498 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
499 }
500 } else if (coord[0] < coord[(count - 1) * 2]) {
501 for (int i = 1; i < count; i++) {
502 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
503 }
504 } else {
505 for (int i = 1; i < count; i++) {
506 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
507 }
508 }
509 }
510
sk_assert_monotonic_y(const SkPoint pts[],int count)511 void sk_assert_monotonic_y(const SkPoint pts[], int count) {
512 if (count > 1) {
513 assert_monotonic(&pts[0].fY, count);
514 }
515 }
516
sk_assert_monotonic_x(const SkPoint pts[],int count)517 void sk_assert_monotonic_x(const SkPoint pts[], int count) {
518 if (count > 1) {
519 assert_monotonic(&pts[0].fX, count);
520 }
521 }
522 #endif
523