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