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