gfx/skia/trunk/src/core/SkEdgeClipper.cpp@b8a032363ba2
gfx/skia/trunk/src/core/SkEdgeClipper.cpp
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
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 */
10 #include "SkEdgeClipper.h"
11 #include "SkGeometry.h"
13 static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
14 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
15 }
17 static inline void clamp_le(SkScalar& value, SkScalar max) {
18 if (value > max) {
19 value = max;
20 }
21 }
23 static inline void clamp_ge(SkScalar& value, SkScalar min) {
24 if (value < min) {
25 value = min;
26 }
27 }
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 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 }
46 ///////////////////////////////////////////////////////////////////////////////
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;
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 }
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 }
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 }
75 // Modify pts[] in place so that it is clipped in Y to the clip rect
76 static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) {
77 SkScalar t;
78 SkPoint tmp[5]; // for SkChopQuadAt
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);
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 }
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;
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 }
124 // srcPts[] must be monotonic in X and Y
125 void SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) {
126 SkPoint pts[3];
127 bool reverse = sort_increasing_Y(pts, srcPts, 3);
129 // are we completely above or below
130 if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
131 return;
132 }
134 // Now chop so that pts is contained within clip in Y
135 chop_quad_in_Y(pts, clip);
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);
144 // Now chop in X has needed, and record the segments
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 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
152 return;
153 }
155 SkScalar t;
156 SkPoint tmp[5]; // for SkChopQuadAt
158 // are we partially to the left
159 if (pts[0].fX < clip.fLeft) {
160 if (chopMonoQuadAtX(pts, clip.fLeft, &t)) {
161 SkChopQuadAt(pts, tmp, t);
162 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse);
163 // clamp to clean up imprecise numerics in the chop
164 tmp[2].fX = clip.fLeft;
165 clamp_ge(tmp[3].fX, clip.fLeft);
167 pts[0] = tmp[2];
168 pts[1] = tmp[3];
169 } else {
170 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
171 // so we just clamp against the left
172 this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse);
173 return;
174 }
175 }
177 // are we partially to the right
178 if (pts[2].fX > clip.fRight) {
179 if (chopMonoQuadAtX(pts, clip.fRight, &t)) {
180 SkChopQuadAt(pts, tmp, t);
181 // clamp to clean up imprecise numerics in the chop
182 clamp_le(tmp[1].fX, clip.fRight);
183 tmp[2].fX = clip.fRight;
185 this->appendQuad(tmp, reverse);
186 this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse);
187 } else {
188 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
189 // so we just clamp against the right
190 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
191 }
192 } else { // wholly inside the clip
193 this->appendQuad(pts, reverse);
194 }
195 }
197 bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
198 fCurrPoint = fPoints;
199 fCurrVerb = fVerbs;
201 SkRect bounds;
202 bounds.set(srcPts, 3);
204 if (!quick_reject(bounds, clip)) {
205 SkPoint monoY[5];
206 int countY = SkChopQuadAtYExtrema(srcPts, monoY);
207 for (int y = 0; y <= countY; y++) {
208 SkPoint monoX[5];
209 int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX);
210 for (int x = 0; x <= countX; x++) {
211 this->clipMonoQuad(&monoX[x * 2], clip);
212 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
213 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
214 }
215 }
216 }
218 *fCurrVerb = SkPath::kDone_Verb;
219 fCurrPoint = fPoints;
220 fCurrVerb = fVerbs;
221 return SkPath::kDone_Verb != fVerbs[0];
222 }
224 ///////////////////////////////////////////////////////////////////////////////
226 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
227 SkScalar D, SkScalar t) {
228 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
229 }
231 /* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
232 t value such that cubic(t) = target
233 */
234 static bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
235 SkScalar target, SkScalar* t) {
236 // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
237 SkASSERT(c0 < target && target < c3);
239 SkScalar D = c0 - target;
240 SkScalar A = c3 + 3*(c1 - c2) - c0;
241 SkScalar B = 3*(c2 - c1 - c1 + c0);
242 SkScalar C = 3*(c1 - c0);
244 const SkScalar TOLERANCE = SK_Scalar1 / 4096;
245 SkScalar minT = 0;
246 SkScalar maxT = SK_Scalar1;
247 SkScalar mid;
249 // This is a lot of iterations. Is there a faster way?
250 for (int i = 0; i < 24; i++) {
251 mid = SkScalarAve(minT, maxT);
252 SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
253 if (delta < 0) {
254 minT = mid;
255 delta = -delta;
256 } else {
257 maxT = mid;
258 }
259 if (delta < TOLERANCE) {
260 break;
261 }
262 }
263 *t = mid;
264 // SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t));
265 return true;
266 }
268 static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) {
269 return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t);
270 }
272 static bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) {
273 return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t);
274 }
276 // Modify pts[] in place so that it is clipped in Y to the clip rect
277 static void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) {
279 // are we partially above
280 if (pts[0].fY < clip.fTop) {
281 SkScalar t;
282 if (chopMonoCubicAtY(pts, clip.fTop, &t)) {
283 SkPoint tmp[7];
284 SkChopCubicAt(pts, tmp, t);
286 // tmp[3, 4, 5].fY should all be to the below clip.fTop.
287 // Since we can't trust the numerics of
288 // the chopper, we force those conditions now
289 tmp[3].fY = clip.fTop;
290 clamp_ge(tmp[4].fY, clip.fTop);
291 clamp_ge(tmp[5].fY, clip.fTop);
293 pts[0] = tmp[3];
294 pts[1] = tmp[4];
295 pts[2] = tmp[5];
296 } else {
297 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
298 // so we just clamp against the top
299 for (int i = 0; i < 4; i++) {
300 clamp_ge(pts[i].fY, clip.fTop);
301 }
302 }
303 }
305 // are we partially below
306 if (pts[3].fY > clip.fBottom) {
307 SkScalar t;
308 if (chopMonoCubicAtY(pts, clip.fBottom, &t)) {
309 SkPoint tmp[7];
310 SkChopCubicAt(pts, tmp, t);
311 tmp[3].fY = clip.fBottom;
312 clamp_le(tmp[2].fY, clip.fBottom);
314 pts[1] = tmp[1];
315 pts[2] = tmp[2];
316 pts[3] = tmp[3];
317 } else {
318 // if chopMonoCubicAtY failed, then we may have hit inexact numerics
319 // so we just clamp against the bottom
320 for (int i = 0; i < 4; i++) {
321 clamp_le(pts[i].fY, clip.fBottom);
322 }
323 }
324 }
325 }
327 // srcPts[] must be monotonic in X and Y
328 void SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) {
329 SkPoint pts[4];
330 bool reverse = sort_increasing_Y(pts, src, 4);
332 // are we completely above or below
333 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
334 return;
335 }
337 // Now chop so that pts is contained within clip in Y
338 chop_cubic_in_Y(pts, clip);
340 if (pts[0].fX > pts[3].fX) {
341 SkTSwap<SkPoint>(pts[0], pts[3]);
342 SkTSwap<SkPoint>(pts[1], pts[2]);
343 reverse = !reverse;
344 }
346 // Now chop in X has needed, and record the segments
348 if (pts[3].fX <= clip.fLeft) { // wholly to the left
349 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
350 return;
351 }
352 if (pts[0].fX >= clip.fRight) { // wholly to the right
353 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
354 return;
355 }
357 // are we partially to the left
358 if (pts[0].fX < clip.fLeft) {
359 SkScalar t;
360 if (chopMonoCubicAtX(pts, clip.fLeft, &t)) {
361 SkPoint tmp[7];
362 SkChopCubicAt(pts, tmp, t);
363 this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse);
365 // tmp[3, 4, 5].fX should all be to the right of clip.fLeft.
366 // Since we can't trust the numerics of
367 // the chopper, we force those conditions now
368 tmp[3].fX = clip.fLeft;
369 clamp_ge(tmp[4].fX, clip.fLeft);
370 clamp_ge(tmp[5].fX, clip.fLeft);
372 pts[0] = tmp[3];
373 pts[1] = tmp[4];
374 pts[2] = tmp[5];
375 } else {
376 // if chopMonocubicAtY failed, then we may have hit inexact numerics
377 // so we just clamp against the left
378 this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse);
379 return;
380 }
381 }
383 // are we partially to the right
384 if (pts[3].fX > clip.fRight) {
385 SkScalar t;
386 if (chopMonoCubicAtX(pts, clip.fRight, &t)) {
387 SkPoint tmp[7];
388 SkChopCubicAt(pts, tmp, t);
389 tmp[3].fX = clip.fRight;
390 clamp_le(tmp[2].fX, clip.fRight);
391 clamp_le(tmp[1].fX, clip.fRight);
393 this->appendCubic(tmp, reverse);
394 this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse);
395 } else {
396 // if chopMonoCubicAtX failed, then we may have hit inexact numerics
397 // so we just clamp against the right
398 this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse);
399 }
400 } else { // wholly inside the clip
401 this->appendCubic(pts, reverse);
402 }
403 }
405 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
406 fCurrPoint = fPoints;
407 fCurrVerb = fVerbs;
409 SkRect bounds;
410 bounds.set(srcPts, 4);
412 if (!quick_reject(bounds, clip)) {
413 SkPoint monoY[10];
414 int countY = SkChopCubicAtYExtrema(srcPts, monoY);
415 for (int y = 0; y <= countY; y++) {
416 SkPoint monoX[10];
417 int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX);
418 for (int x = 0; x <= countX; x++) {
419 this->clipMonoCubic(&monoX[x * 3], clip);
420 SkASSERT(fCurrVerb - fVerbs < kMaxVerbs);
421 SkASSERT(fCurrPoint - fPoints <= kMaxPoints);
422 }
423 }
424 }
426 *fCurrVerb = SkPath::kDone_Verb;
427 fCurrPoint = fPoints;
428 fCurrVerb = fVerbs;
429 return SkPath::kDone_Verb != fVerbs[0];
430 }
432 ///////////////////////////////////////////////////////////////////////////////
434 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
435 bool reverse) {
436 *fCurrVerb++ = SkPath::kLine_Verb;
438 if (reverse) {
439 SkTSwap<SkScalar>(y0, y1);
440 }
441 fCurrPoint[0].set(x, y0);
442 fCurrPoint[1].set(x, y1);
443 fCurrPoint += 2;
444 }
446 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
447 *fCurrVerb++ = SkPath::kQuad_Verb;
449 if (reverse) {
450 fCurrPoint[0] = pts[2];
451 fCurrPoint[2] = pts[0];
452 } else {
453 fCurrPoint[0] = pts[0];
454 fCurrPoint[2] = pts[2];
455 }
456 fCurrPoint[1] = pts[1];
457 fCurrPoint += 3;
458 }
460 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
461 *fCurrVerb++ = SkPath::kCubic_Verb;
463 if (reverse) {
464 for (int i = 0; i < 4; i++) {
465 fCurrPoint[i] = pts[3 - i];
466 }
467 } else {
468 memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint));
469 }
470 fCurrPoint += 4;
471 }
473 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
474 SkPath::Verb verb = *fCurrVerb;
476 switch (verb) {
477 case SkPath::kLine_Verb:
478 memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint));
479 fCurrPoint += 2;
480 fCurrVerb += 1;
481 break;
482 case SkPath::kQuad_Verb:
483 memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint));
484 fCurrPoint += 3;
485 fCurrVerb += 1;
486 break;
487 case SkPath::kCubic_Verb:
488 memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint));
489 fCurrPoint += 4;
490 fCurrVerb += 1;
491 break;
492 case SkPath::kDone_Verb:
493 break;
494 default:
495 SkDEBUGFAIL("unexpected verb in quadclippper2 iter");
496 break;
497 }
498 return verb;
499 }
501 ///////////////////////////////////////////////////////////////////////////////
503 #ifdef SK_DEBUG
504 static void assert_monotonic(const SkScalar coord[], int count) {
505 if (coord[0] > coord[(count - 1) * 2]) {
506 for (int i = 1; i < count; i++) {
507 SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]);
508 }
509 } else if (coord[0] < coord[(count - 1) * 2]) {
510 for (int i = 1; i < count; i++) {
511 SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]);
512 }
513 } else {
514 for (int i = 1; i < count; i++) {
515 SkASSERT(coord[2 * (i - 1)] == coord[i * 2]);
516 }
517 }
518 }
520 void sk_assert_monotonic_y(const SkPoint pts[], int count) {
521 if (count > 1) {
522 assert_monotonic(&pts[0].fY, count);
523 }
524 }
526 void sk_assert_monotonic_x(const SkPoint pts[], int count) {
527 if (count > 1) {
528 assert_monotonic(&pts[0].fX, count);
529 }
530 }
531 #endif
