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