The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkEdgeClipper.cpp

gfx/skia/trunk/src/core/SkEdgeClipper.cpp

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:7b8b7e640e7b
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
13 static bool quick_reject(const SkRect& bounds, const SkRect& clip) {
14 return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
15 }
16
17 static inline void clamp_le(SkScalar& value, SkScalar max) {
18 if (value > max) {
19 value = max;
20 }
21 }
22
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 */
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
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
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
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
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
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 this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse);
152 return;
153 }
154
155 SkScalar t;
156 SkPoint tmp[5]; // for SkChopQuadAt
157
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);
166
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 }
176
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;
184
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 }
196
197 bool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) {
198 fCurrPoint = fPoints;
199 fCurrVerb = fVerbs;
200
201 SkRect bounds;
202 bounds.set(srcPts, 3);
203
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 }
217
218 *fCurrVerb = SkPath::kDone_Verb;
219 fCurrPoint = fPoints;
220 fCurrVerb = fVerbs;
221 return SkPath::kDone_Verb != fVerbs[0];
222 }
223
224 ///////////////////////////////////////////////////////////////////////////////
225
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 }
230
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);
238
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);
243
244 const SkScalar TOLERANCE = SK_Scalar1 / 4096;
245 SkScalar minT = 0;
246 SkScalar maxT = SK_Scalar1;
247 SkScalar mid;
248
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 }
267
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 }
271
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 }
275
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) {
278
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);
285
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);
292
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 }
304
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);
313
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 }
326
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);
331
332 // are we completely above or below
333 if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) {
334 return;
335 }
336
337 // Now chop so that pts is contained within clip in Y
338 chop_cubic_in_Y(pts, clip);
339
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 }
345
346 // Now chop in X has needed, and record the segments
347
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 }
356
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);
364
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);
371
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 }
382
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);
392
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 }
404
405 bool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) {
406 fCurrPoint = fPoints;
407 fCurrVerb = fVerbs;
408
409 SkRect bounds;
410 bounds.set(srcPts, 4);
411
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 }
425
426 *fCurrVerb = SkPath::kDone_Verb;
427 fCurrPoint = fPoints;
428 fCurrVerb = fVerbs;
429 return SkPath::kDone_Verb != fVerbs[0];
430 }
431
432 ///////////////////////////////////////////////////////////////////////////////
433
434 void SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1,
435 bool reverse) {
436 *fCurrVerb++ = SkPath::kLine_Verb;
437
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 }
445
446 void SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) {
447 *fCurrVerb++ = SkPath::kQuad_Verb;
448
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 }
459
460 void SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) {
461 *fCurrVerb++ = SkPath::kCubic_Verb;
462
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 }
472
473 SkPath::Verb SkEdgeClipper::next(SkPoint pts[]) {
474 SkPath::Verb verb = *fCurrVerb;
475
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 }
500
501 ///////////////////////////////////////////////////////////////////////////////
502
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 }
519
520 void sk_assert_monotonic_y(const SkPoint pts[], int count) {
521 if (count > 1) {
522 assert_monotonic(&pts[0].fY, count);
523 }
524 }
525
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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial