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 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 return SkLeftShift(value, 16 - 6 - 1); 29 } 30 31 ///////////////////////////////////////////////////////////////////////// 32 33 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 x0 = SkScalarRoundToFDot6(p0.fX, shift); 40 y0 = SkScalarRoundToFDot6(p0.fY, shift); 41 x1 = SkScalarRoundToFDot6(p1.fX, shift); 42 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 int winding = 1; 53 54 if (y0 > y1) { 55 SkTSwap(x0, x1); 56 SkTSwap(y0, y1); 57 winding = -1; 58 } 59 60 int top = SkFDot6Round(y0); 61 int bot = SkFDot6Round(y1); 62 63 // are we a zero-height line? 64 if (top == bot) { 65 return 0; 66 } 67 // are we completely above or below the clip? 68 if (clip && (top >= clip->fBottom || bot <= clip->fTop)) { 69 return 0; 70 } 71 72 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); 73 const SkFDot6 dy = SkEdge_Compute_DY(top, y0); 74 75 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2 76 fDX = slope; 77 fFirstY = top; 78 fLastY = bot - 1; 79 fCurveCount = 0; 80 fWinding = SkToS8(winding); 81 fCurveShift = 0; 82 83 if (clip) { 84 this->chopLineWithClip(*clip); 85 } 86 return 1; 87 } 88 89 // called from a curve subclass 90 int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1) 91 { 92 SkASSERT(fWinding == 1 || fWinding == -1); 93 SkASSERT(fCurveCount != 0); 94 // SkASSERT(fCurveShift != 0); 95 96 y0 >>= 10; 97 y1 >>= 10; 98 99 SkASSERT(y0 <= y1); 100 101 int top = SkFDot6Round(y0); 102 int bot = SkFDot6Round(y1); 103 104 // SkASSERT(top >= fFirstY); 105 106 // are we a zero-height line? 107 if (top == bot) 108 return 0; 109 110 x0 >>= 10; 111 x1 >>= 10; 112 113 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); 114 const SkFDot6 dy = SkEdge_Compute_DY(top, y0); 115 116 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2 117 fDX = slope; 118 fFirstY = top; 119 fLastY = bot - 1; 120 121 return 1; 122 } 123 124 void SkEdge::chopLineWithClip(const SkIRect& clip) 125 { 126 int top = fFirstY; 127 128 SkASSERT(top < clip.fBottom); 129 130 // clip the line to the top 131 if (top < clip.fTop) 132 { 133 SkASSERT(fLastY >= clip.fTop); 134 fX += fDX * (clip.fTop - top); 135 fFirstY = clip.fTop; 136 } 137 } 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 static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy) 149 { 150 dx = SkAbs32(dx); 151 dy = SkAbs32(dy); 152 // return max + min/2 153 if (dx > dy) 154 dx += dy >> 1; 155 else 156 dx = dy + (dx >> 1); 157 return dx; 158 } 159 160 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 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 dist = (dist + (1 << 4)) >> (3 + shiftAA); 175 #endif 176 177 // each subdivision (shift value) cuts this dist (error) by 1/4 178 return (32 - SkCLZ(dist)) >> 1; 179 } 180 181 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 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 SkTSwap(x0, x2); 207 SkTSwap(y0, y2); 208 winding = -1; 209 } 210 SkASSERT(y0 <= y1 && y1 <= y2); 211 212 int top = SkFDot6Round(y0); 213 int bot = SkFDot6Round(y2); 214 215 // are we a zero-height quad (line)? 216 if (top == bot) 217 return 0; 218 219 // compute number of steps needed (1 << shift) 220 { 221 SkFDot6 dx = (SkLeftShift(x1, 1) - x0 - x2) >> 2; 222 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 shift = diff_to_shift(dx, dy, shift); 227 SkASSERT(shift >= 0); 228 } 229 // need at least 1 subdivision for our bias trick 230 if (shift == 0) { 231 shift = 1; 232 } else if (shift > MAX_COEFF_SHIFT) { 233 shift = MAX_COEFF_SHIFT; 234 } 235 236 fWinding = SkToS8(winding); 237 //fCubicDShift only set for cubics 238 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 fCurveShift = SkToU8(shift - 1); 259 260 SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2); // 1/2 the real value 261 SkFixed B = SkFDot6ToFixed(x1 - x0); // 1/2 the real value 262 263 fQx = SkFDot6ToFixed(x0); 264 fQDx = B + (A >> shift); // biased by shift 265 fQDDx = A >> (shift - 1); // biased by shift 266 267 A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2); // 1/2 the real value 268 B = SkFDot6ToFixed(y1 - y0); // 1/2 the real value 269 270 fQy = SkFDot6ToFixed(y0); 271 fQDy = B + (A >> shift); // biased by shift 272 fQDDy = A >> (shift - 1); // biased by shift 273 274 fQLastX = SkFDot6ToFixed(x2); 275 fQLastY = SkFDot6ToFixed(y2); 276 277 return true; 278 } 279 280 int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift) { 281 if (!setQuadraticWithoutUpdate(pts, shift)) { 282 return 0; 283 } 284 return this->updateQuadratic(); 285 } 286 287 int SkQuadraticEdge::updateQuadratic() 288 { 289 int success; 290 int count = fCurveCount; 291 SkFixed oldx = fQx; 292 SkFixed oldy = fQy; 293 SkFixed dx = fQDx; 294 SkFixed dy = fQDy; 295 SkFixed newx, newy; 296 int shift = fCurveShift; 297 298 SkASSERT(count > 0); 299 300 do { 301 if (--count > 0) 302 { 303 newx = oldx + (dx >> shift); 304 dx += fQDDx; 305 newy = oldy + (dy >> shift); 306 dy += fQDDy; 307 } 308 else // last segment 309 { 310 newx = fQLastX; 311 newy = fQLastY; 312 } 313 success = this->updateLine(oldx, oldy, newx, newy); 314 oldx = newx; 315 oldy = newy; 316 } while (count > 0 && !success); 317 318 fQx = newx; 319 fQy = newy; 320 fQDx = dx; 321 fQDy = dy; 322 fCurveCount = SkToS8(count); 323 return success; 324 } 325 326 ///////////////////////////////////////////////////////////////////////// 327 328 static inline int SkFDot6UpShift(SkFDot6 x, int upShift) { 329 SkASSERT((SkLeftShift(x, upShift) >> upShift) == x); 330 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 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 SkFDot6 oneThird = (a*8 - b*15 + 6*c + d) * 19 >> 9; 345 SkFDot6 twoThird = (a + 6*b - c*15 + d*8) * 19 >> 9; 346 347 return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird)); 348 } 349 350 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 x0 = SkScalarRoundToFDot6(pts[0].fX, shift); 356 y0 = SkScalarRoundToFDot6(pts[0].fY, shift); 357 x1 = SkScalarRoundToFDot6(pts[1].fX, shift); 358 y1 = SkScalarRoundToFDot6(pts[1].fY, shift); 359 x2 = SkScalarRoundToFDot6(pts[2].fX, shift); 360 y2 = SkScalarRoundToFDot6(pts[2].fY, shift); 361 x3 = SkScalarRoundToFDot6(pts[3].fX, shift); 362 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 int winding = 1; 377 if (y0 > y3) 378 { 379 SkTSwap(x0, x3); 380 SkTSwap(x1, x2); 381 SkTSwap(y0, y3); 382 SkTSwap(y1, y2); 383 winding = -1; 384 } 385 386 int top = SkFDot6Round(y0); 387 int bot = SkFDot6Round(y3); 388 389 // are we a zero-height cubic (line)? 390 if (top == bot) 391 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 SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3); 399 SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3); 400 // add 1 (by observation) 401 shift = diff_to_shift(dx, dy) + 1; 402 } 403 // need at least 1 subdivision for our bias trick 404 SkASSERT(shift > 0); 405 if (shift > MAX_COEFF_SHIFT) { 406 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 int upShift = 6; // largest safe value 414 int downShift = shift + upShift - 10; 415 if (downShift < 0) { 416 downShift = 0; 417 upShift = 10 - shift; 418 } 419 420 fWinding = SkToS8(winding); 421 fCurveCount = SkToS8(SkLeftShift(-1, shift)); 422 fCurveShift = SkToU8(shift); 423 fCubicDShift = SkToU8(downShift); 424 425 SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift); 426 SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift); 427 SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift); 428 429 fCx = SkFDot6ToFixed(x0); 430 fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift 431 fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 432 fCDDDx = 3*D >> (shift - 1); // biased by 2*shift 433 434 B = SkFDot6UpShift(3 * (y1 - y0), upShift); 435 C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift); 436 D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift); 437 438 fCy = SkFDot6ToFixed(y0); 439 fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift 440 fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 441 fCDDDy = 3*D >> (shift - 1); // biased by 2*shift 442 443 fCLastX = SkFDot6ToFixed(x3); 444 fCLastY = SkFDot6ToFixed(y3); 445 446 return true; 447 } 448 449 int SkCubicEdge::setCubic(const SkPoint pts[4], int shift) { 450 if (!this->setCubicWithoutUpdate(pts, shift)) { 451 return 0; 452 } 453 return this->updateCubic(); 454 } 455 456 int SkCubicEdge::updateCubic() 457 { 458 int success; 459 int count = fCurveCount; 460 SkFixed oldx = fCx; 461 SkFixed oldy = fCy; 462 SkFixed newx, newy; 463 const int ddshift = fCurveShift; 464 const int dshift = fCubicDShift; 465 466 SkASSERT(count < 0); 467 468 do { 469 if (++count < 0) 470 { 471 newx = oldx + (fCDx >> dshift); 472 fCDx += fCDDx >> ddshift; 473 fCDDx += fCDDDx; 474 475 newy = oldy + (fCDy >> dshift); 476 fCDy += fCDDy >> ddshift; 477 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 newx = fCLastX; 483 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 if (newy < oldy) { 489 newy = oldy; 490 } 491 492 success = this->updateLine(oldx, oldy, newx, newy); 493 oldx = newx; 494 oldy = newy; 495 } while (count < 0 && !success); 496 497 fCx = newx; 498 fCy = newy; 499 fCurveCount = SkToS8(count); 500 return success; 501 } 502