Line data Source code
1 : /*
2 : * Copyright 2006 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 "SkEdge.h"
10 : #include "SkFDot6.h"
11 : #include "SkMathPriv.h"
12 :
13 : /*
14 : In setLine, setQuadratic, setCubic, the first thing we do is to convert
15 : the points into FDot6. This is modulated by the shift parameter, which
16 : will either be 0, or something like 2 for antialiasing.
17 :
18 : In the float case, we want to turn the float into .6 by saying pt * 64,
19 : or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
20 :
21 : In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
22 : or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
23 : */
24 :
25 32 : static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
26 : // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
27 : // away data in value, so just perform a modify up-shift
28 32 : return SkLeftShift(value, 16 - 6 - 1);
29 : }
30 :
31 : /////////////////////////////////////////////////////////////////////////
32 :
33 0 : int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
34 : int shift) {
35 : SkFDot6 x0, y0, x1, y1;
36 :
37 : {
38 : #ifdef SK_RASTERIZE_EVEN_ROUNDING
39 0 : x0 = SkScalarRoundToFDot6(p0.fX, shift);
40 0 : y0 = SkScalarRoundToFDot6(p0.fY, shift);
41 0 : x1 = SkScalarRoundToFDot6(p1.fX, shift);
42 0 : y1 = SkScalarRoundToFDot6(p1.fY, shift);
43 : #else
44 : float scale = float(1 << (shift + 6));
45 : x0 = int(p0.fX * scale);
46 : y0 = int(p0.fY * scale);
47 : x1 = int(p1.fX * scale);
48 : y1 = int(p1.fY * scale);
49 : #endif
50 : }
51 :
52 0 : int winding = 1;
53 :
54 0 : if (y0 > y1) {
55 0 : SkTSwap(x0, x1);
56 0 : SkTSwap(y0, y1);
57 0 : winding = -1;
58 : }
59 :
60 0 : int top = SkFDot6Round(y0);
61 0 : int bot = SkFDot6Round(y1);
62 :
63 : // are we a zero-height line?
64 0 : if (top == bot) {
65 0 : return 0;
66 : }
67 : // are we completely above or below the clip?
68 0 : if (clip && (top >= clip->fBottom || bot <= clip->fTop)) {
69 0 : return 0;
70 : }
71 :
72 0 : SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
73 0 : const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
74 :
75 0 : fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
76 0 : fDX = slope;
77 0 : fFirstY = top;
78 0 : fLastY = bot - 1;
79 0 : fCurveCount = 0;
80 0 : fWinding = SkToS8(winding);
81 0 : fCurveShift = 0;
82 :
83 0 : if (clip) {
84 0 : this->chopLineWithClip(*clip);
85 : }
86 0 : return 1;
87 : }
88 :
89 : // called from a curve subclass
90 1264 : int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
91 : {
92 1264 : SkASSERT(fWinding == 1 || fWinding == -1);
93 1264 : SkASSERT(fCurveCount != 0);
94 : // SkASSERT(fCurveShift != 0);
95 :
96 1264 : y0 >>= 10;
97 1264 : y1 >>= 10;
98 :
99 1264 : SkASSERT(y0 <= y1);
100 :
101 1264 : int top = SkFDot6Round(y0);
102 1264 : int bot = SkFDot6Round(y1);
103 :
104 : // SkASSERT(top >= fFirstY);
105 :
106 : // are we a zero-height line?
107 1264 : if (top == bot)
108 33 : return 0;
109 :
110 1231 : x0 >>= 10;
111 1231 : x1 >>= 10;
112 :
113 1231 : SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
114 1231 : const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
115 :
116 1231 : fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
117 1231 : fDX = slope;
118 1231 : fFirstY = top;
119 1231 : fLastY = bot - 1;
120 :
121 1231 : return 1;
122 : }
123 :
124 0 : void SkEdge::chopLineWithClip(const SkIRect& clip)
125 : {
126 0 : int top = fFirstY;
127 :
128 0 : SkASSERT(top < clip.fBottom);
129 :
130 : // clip the line to the top
131 0 : if (top < clip.fTop)
132 : {
133 0 : SkASSERT(fLastY >= clip.fTop);
134 0 : fX += fDX * (clip.fTop - top);
135 0 : fFirstY = clip.fTop;
136 : }
137 0 : }
138 :
139 : ///////////////////////////////////////////////////////////////////////////////
140 :
141 : /* We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
142 : Note that this limits the number of lines we use to approximate a curve.
143 : If we need to increase this, we need to store fCurveCount in something
144 : larger than int8_t.
145 : */
146 : #define MAX_COEFF_SHIFT 6
147 :
148 413 : static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy)
149 : {
150 413 : dx = SkAbs32(dx);
151 413 : dy = SkAbs32(dy);
152 : // return max + min/2
153 413 : if (dx > dy)
154 129 : dx += dy >> 1;
155 : else
156 284 : dx = dy + (dx >> 1);
157 413 : return dx;
158 : }
159 :
160 413 : static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy, int shiftAA = 2)
161 : {
162 : // cheap calc of distance from center of p0-p2 to the center of the curve
163 413 : SkFDot6 dist = cheap_distance(dx, dy);
164 :
165 : // shift down dist (it is currently in dot6)
166 : // down by 3 should give us 1/8 pixel accuracy (assuming our dist is accurate...)
167 : // this is chosen by heuristic: make it as big as possible (to minimize segments)
168 : // ... but small enough so that our curves still look smooth
169 : // When shift > 0, we're using AA and everything is scaled up so we can
170 : // lower the accuracy.
171 : #ifdef SK_SUPPORT_LEGACY_QUAD_SHIFT
172 : dist = (dist + (1 << 4)) >> 5;
173 : #else
174 413 : dist = (dist + (1 << 4)) >> (3 + shiftAA);
175 : #endif
176 :
177 : // each subdivision (shift value) cuts this dist (error) by 1/4
178 413 : return (32 - SkCLZ(dist)) >> 1;
179 : }
180 :
181 16 : bool SkQuadraticEdge::setQuadraticWithoutUpdate(const SkPoint pts[3], int shift) {
182 : SkFDot6 x0, y0, x1, y1, x2, y2;
183 :
184 : {
185 : #ifdef SK_RASTERIZE_EVEN_ROUNDING
186 16 : x0 = SkScalarRoundToFDot6(pts[0].fX, shift);
187 16 : y0 = SkScalarRoundToFDot6(pts[0].fY, shift);
188 16 : x1 = SkScalarRoundToFDot6(pts[1].fX, shift);
189 16 : y1 = SkScalarRoundToFDot6(pts[1].fY, shift);
190 16 : x2 = SkScalarRoundToFDot6(pts[2].fX, shift);
191 16 : y2 = SkScalarRoundToFDot6(pts[2].fY, shift);
192 : #else
193 : float scale = float(1 << (shift + 6));
194 : x0 = int(pts[0].fX * scale);
195 : y0 = int(pts[0].fY * scale);
196 : x1 = int(pts[1].fX * scale);
197 : y1 = int(pts[1].fY * scale);
198 : x2 = int(pts[2].fX * scale);
199 : y2 = int(pts[2].fY * scale);
200 : #endif
201 : }
202 :
203 16 : int winding = 1;
204 16 : if (y0 > y2)
205 : {
206 8 : SkTSwap(x0, x2);
207 8 : SkTSwap(y0, y2);
208 8 : winding = -1;
209 : }
210 16 : SkASSERT(y0 <= y1 && y1 <= y2);
211 :
212 16 : int top = SkFDot6Round(y0);
213 16 : int bot = SkFDot6Round(y2);
214 :
215 : // are we a zero-height quad (line)?
216 16 : if (top == bot)
217 0 : return 0;
218 :
219 : // compute number of steps needed (1 << shift)
220 : {
221 16 : SkFDot6 dx = (SkLeftShift(x1, 1) - x0 - x2) >> 2;
222 16 : SkFDot6 dy = (SkLeftShift(y1, 1) - y0 - y2) >> 2;
223 : // This is a little confusing:
224 : // before this line, shift is the scale up factor for AA;
225 : // after this line, shift is the fCurveShift.
226 16 : shift = diff_to_shift(dx, dy, shift);
227 16 : SkASSERT(shift >= 0);
228 : }
229 : // need at least 1 subdivision for our bias trick
230 16 : if (shift == 0) {
231 0 : shift = 1;
232 16 : } else if (shift > MAX_COEFF_SHIFT) {
233 0 : shift = MAX_COEFF_SHIFT;
234 : }
235 :
236 16 : fWinding = SkToS8(winding);
237 : //fCubicDShift only set for cubics
238 16 : fCurveCount = SkToS8(1 << shift);
239 :
240 : /*
241 : * We want to reformulate into polynomial form, to make it clear how we
242 : * should forward-difference.
243 : *
244 : * p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
245 : *
246 : * A = p0 - 2p1 + p2
247 : * B = 2(p1 - p0)
248 : * C = p0
249 : *
250 : * Our caller must have constrained our inputs (p0..p2) to all fit into
251 : * 16.16. However, as seen above, we sometimes compute values that can be
252 : * larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
253 : * A and B at 1/2 of their actual value, and just apply a 2x scale during
254 : * application in updateQuadratic(). Hence we store (shift - 1) in
255 : * fCurveShift.
256 : */
257 :
258 16 : fCurveShift = SkToU8(shift - 1);
259 :
260 16 : SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2); // 1/2 the real value
261 16 : SkFixed B = SkFDot6ToFixed(x1 - x0); // 1/2 the real value
262 :
263 16 : fQx = SkFDot6ToFixed(x0);
264 16 : fQDx = B + (A >> shift); // biased by shift
265 16 : fQDDx = A >> (shift - 1); // biased by shift
266 :
267 16 : A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2); // 1/2 the real value
268 16 : B = SkFDot6ToFixed(y1 - y0); // 1/2 the real value
269 :
270 16 : fQy = SkFDot6ToFixed(y0);
271 16 : fQDy = B + (A >> shift); // biased by shift
272 16 : fQDDy = A >> (shift - 1); // biased by shift
273 :
274 16 : fQLastX = SkFDot6ToFixed(x2);
275 16 : fQLastY = SkFDot6ToFixed(y2);
276 :
277 16 : return true;
278 : }
279 :
280 16 : int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift) {
281 16 : if (!setQuadraticWithoutUpdate(pts, shift)) {
282 0 : return 0;
283 : }
284 16 : return this->updateQuadratic();
285 : }
286 :
287 48 : int SkQuadraticEdge::updateQuadratic()
288 : {
289 : int success;
290 48 : int count = fCurveCount;
291 48 : SkFixed oldx = fQx;
292 48 : SkFixed oldy = fQy;
293 48 : SkFixed dx = fQDx;
294 48 : SkFixed dy = fQDy;
295 : SkFixed newx, newy;
296 48 : int shift = fCurveShift;
297 :
298 48 : SkASSERT(count > 0);
299 :
300 0 : do {
301 48 : if (--count > 0)
302 : {
303 32 : newx = oldx + (dx >> shift);
304 32 : dx += fQDDx;
305 32 : newy = oldy + (dy >> shift);
306 32 : dy += fQDDy;
307 : }
308 : else // last segment
309 : {
310 16 : newx = fQLastX;
311 16 : newy = fQLastY;
312 : }
313 48 : success = this->updateLine(oldx, oldy, newx, newy);
314 48 : oldx = newx;
315 48 : oldy = newy;
316 48 : } while (count > 0 && !success);
317 :
318 48 : fQx = newx;
319 48 : fQy = newy;
320 48 : fQDx = dx;
321 48 : fQDy = dy;
322 48 : fCurveCount = SkToS8(count);
323 48 : return success;
324 : }
325 :
326 : /////////////////////////////////////////////////////////////////////////
327 :
328 2382 : static inline int SkFDot6UpShift(SkFDot6 x, int upShift) {
329 2382 : SkASSERT((SkLeftShift(x, upShift) >> upShift) == x);
330 2382 : return SkLeftShift(x, upShift);
331 : }
332 :
333 : /* f(1/3) = (8a + 12b + 6c + d) / 27
334 : f(2/3) = (a + 6b + 12c + 8d) / 27
335 :
336 : f(1/3)-b = (8a - 15b + 6c + d) / 27
337 : f(2/3)-c = (a + 6b - 15c + 8d) / 27
338 :
339 : use 16/512 to approximate 1/27
340 : */
341 794 : static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
342 : {
343 : // since our parameters may be negative, we don't use << to avoid ASAN warnings
344 794 : SkFDot6 oneThird = (a*8 - b*15 + 6*c + d) * 19 >> 9;
345 794 : SkFDot6 twoThird = (a + 6*b - c*15 + d*8) * 19 >> 9;
346 :
347 794 : return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
348 : }
349 :
350 408 : bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift) {
351 : SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
352 :
353 : {
354 : #ifdef SK_RASTERIZE_EVEN_ROUNDING
355 408 : x0 = SkScalarRoundToFDot6(pts[0].fX, shift);
356 408 : y0 = SkScalarRoundToFDot6(pts[0].fY, shift);
357 408 : x1 = SkScalarRoundToFDot6(pts[1].fX, shift);
358 408 : y1 = SkScalarRoundToFDot6(pts[1].fY, shift);
359 408 : x2 = SkScalarRoundToFDot6(pts[2].fX, shift);
360 408 : y2 = SkScalarRoundToFDot6(pts[2].fY, shift);
361 408 : x3 = SkScalarRoundToFDot6(pts[3].fX, shift);
362 408 : y3 = SkScalarRoundToFDot6(pts[3].fY, shift);
363 : #else
364 : float scale = float(1 << (shift + 6));
365 : x0 = int(pts[0].fX * scale);
366 : y0 = int(pts[0].fY * scale);
367 : x1 = int(pts[1].fX * scale);
368 : y1 = int(pts[1].fY * scale);
369 : x2 = int(pts[2].fX * scale);
370 : y2 = int(pts[2].fY * scale);
371 : x3 = int(pts[3].fX * scale);
372 : y3 = int(pts[3].fY * scale);
373 : #endif
374 : }
375 :
376 408 : int winding = 1;
377 408 : if (y0 > y3)
378 : {
379 199 : SkTSwap(x0, x3);
380 199 : SkTSwap(x1, x2);
381 199 : SkTSwap(y0, y3);
382 199 : SkTSwap(y1, y2);
383 199 : winding = -1;
384 : }
385 :
386 408 : int top = SkFDot6Round(y0);
387 408 : int bot = SkFDot6Round(y3);
388 :
389 : // are we a zero-height cubic (line)?
390 408 : if (top == bot)
391 11 : return 0;
392 :
393 : // compute number of steps needed (1 << shift)
394 : {
395 : // Can't use (center of curve - center of baseline), since center-of-curve
396 : // need not be the max delta from the baseline (it could even be coincident)
397 : // so we try just looking at the two off-curve points
398 397 : SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
399 397 : SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
400 : // add 1 (by observation)
401 397 : shift = diff_to_shift(dx, dy) + 1;
402 : }
403 : // need at least 1 subdivision for our bias trick
404 397 : SkASSERT(shift > 0);
405 397 : if (shift > MAX_COEFF_SHIFT) {
406 0 : shift = MAX_COEFF_SHIFT;
407 : }
408 :
409 : /* Since our in coming data is initially shifted down by 10 (or 8 in
410 : antialias). That means the most we can shift up is 8. However, we
411 : compute coefficients with a 3*, so the safest upshift is really 6
412 : */
413 397 : int upShift = 6; // largest safe value
414 397 : int downShift = shift + upShift - 10;
415 397 : if (downShift < 0) {
416 339 : downShift = 0;
417 339 : upShift = 10 - shift;
418 : }
419 :
420 397 : fWinding = SkToS8(winding);
421 397 : fCurveCount = SkToS8(SkLeftShift(-1, shift));
422 397 : fCurveShift = SkToU8(shift);
423 397 : fCubicDShift = SkToU8(downShift);
424 :
425 397 : SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift);
426 397 : SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift);
427 397 : SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift);
428 :
429 397 : fCx = SkFDot6ToFixed(x0);
430 397 : fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift
431 397 : fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
432 397 : fCDDDx = 3*D >> (shift - 1); // biased by 2*shift
433 :
434 397 : B = SkFDot6UpShift(3 * (y1 - y0), upShift);
435 397 : C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift);
436 397 : D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift);
437 :
438 397 : fCy = SkFDot6ToFixed(y0);
439 397 : fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift
440 397 : fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
441 397 : fCDDDy = 3*D >> (shift - 1); // biased by 2*shift
442 :
443 397 : fCLastX = SkFDot6ToFixed(x3);
444 397 : fCLastY = SkFDot6ToFixed(y3);
445 :
446 397 : return true;
447 : }
448 :
449 222 : int SkCubicEdge::setCubic(const SkPoint pts[4], int shift) {
450 222 : if (!this->setCubicWithoutUpdate(pts, shift)) {
451 11 : return 0;
452 : }
453 211 : return this->updateCubic();
454 : }
455 :
456 1201 : int SkCubicEdge::updateCubic()
457 : {
458 : int success;
459 1201 : int count = fCurveCount;
460 1201 : SkFixed oldx = fCx;
461 1201 : SkFixed oldy = fCy;
462 : SkFixed newx, newy;
463 1201 : const int ddshift = fCurveShift;
464 1201 : const int dshift = fCubicDShift;
465 :
466 1201 : SkASSERT(count < 0);
467 :
468 15 : do {
469 1216 : if (++count < 0)
470 : {
471 1005 : newx = oldx + (fCDx >> dshift);
472 1005 : fCDx += fCDDx >> ddshift;
473 1005 : fCDDx += fCDDDx;
474 :
475 1005 : newy = oldy + (fCDy >> dshift);
476 1005 : fCDy += fCDDy >> ddshift;
477 1005 : fCDDy += fCDDDy;
478 : }
479 : else // last segment
480 : {
481 : // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
482 211 : newx = fCLastX;
483 211 : newy = fCLastY;
484 : }
485 :
486 : // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
487 : // doesn't always achieve that, so we have to explicitly pin it here.
488 1216 : if (newy < oldy) {
489 0 : newy = oldy;
490 : }
491 :
492 1216 : success = this->updateLine(oldx, oldy, newx, newy);
493 1216 : oldx = newx;
494 1216 : oldy = newy;
495 1216 : } while (count < 0 && !success);
496 :
497 1201 : fCx = newx;
498 1201 : fCy = newy;
499 1201 : fCurveCount = SkToS8(count);
500 1201 : return success;
501 : }
|
