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