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