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 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 value << (16 - 6 - 1); 30 } 31 32 ///////////////////////////////////////////////////////////////////////// 33 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 int 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 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 int 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 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 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 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 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 = ((x1 << 1) - x0 - x2) >> 2; 218 SkFDot6 dy = ((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 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 314 static inline int SkFDot6UpShift(SkFDot6 x, int upShift) { 315 SkASSERT((x << upShift >> upShift) == x); 316 return 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 */ 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 335 int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift) 336 { 337 SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3; 338 339 { 340 #ifdef SK_RASTERIZE_EVEN_ROUNDING 341 x0 = SkScalarRoundToFDot6(pts[0].fX, shift); 342 y0 = SkScalarRoundToFDot6(pts[0].fY, shift); 343 x1 = SkScalarRoundToFDot6(pts[1].fX, shift); 344 y1 = SkScalarRoundToFDot6(pts[1].fY, shift); 345 x2 = SkScalarRoundToFDot6(pts[2].fX, shift); 346 y2 = SkScalarRoundToFDot6(pts[2].fY, shift); 347 x3 = SkScalarRoundToFDot6(pts[3].fX, shift); 348 y3 = SkScalarRoundToFDot6(pts[3].fY, shift); 349 #else 350 float scale = float(1 << (shift + 6)); 351 x0 = int(pts[0].fX * scale); 352 y0 = int(pts[0].fY * scale); 353 x1 = int(pts[1].fX * scale); 354 y1 = int(pts[1].fY * scale); 355 x2 = int(pts[2].fX * scale); 356 y2 = int(pts[2].fY * scale); 357 x3 = int(pts[3].fX * scale); 358 y3 = int(pts[3].fY * scale); 359 #endif 360 } 361 362 int winding = 1; 363 if (y0 > y3) 364 { 365 SkTSwap(x0, x3); 366 SkTSwap(x1, x2); 367 SkTSwap(y0, y3); 368 SkTSwap(y1, y2); 369 winding = -1; 370 } 371 372 int top = SkFDot6Round(y0); 373 int bot = SkFDot6Round(y3); 374 375 // are we a zero-height cubic (line)? 376 if (top == bot) 377 return 0; 378 379 // are we completely above or below the clip? 380 if (clip && (top >= clip->fBottom || bot <= clip->fTop)) 381 return 0; 382 383 // compute number of steps needed (1 << shift) 384 { 385 // Can't use (center of curve - center of baseline), since center-of-curve 386 // need not be the max delta from the baseline (it could even be coincident) 387 // so we try just looking at the two off-curve points 388 SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3); 389 SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3); 390 // add 1 (by observation) 391 shift = diff_to_shift(dx, dy) + 1; 392 } 393 // need at least 1 subdivision for our bias trick 394 SkASSERT(shift > 0); 395 if (shift > MAX_COEFF_SHIFT) { 396 shift = MAX_COEFF_SHIFT; 397 } 398 399 /* Since our in coming data is initially shifted down by 10 (or 8 in 400 antialias). That means the most we can shift up is 8. However, we 401 compute coefficients with a 3*, so the safest upshift is really 6 402 */ 403 int upShift = 6; // largest safe value 404 int downShift = shift + upShift - 10; 405 if (downShift < 0) { 406 downShift = 0; 407 upShift = 10 - shift; 408 } 409 410 fWinding = SkToS8(winding); 411 fCurveCount = SkToS8(-1 << shift); 412 fCurveShift = SkToU8(shift); 413 fCubicDShift = SkToU8(downShift); 414 415 SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift); 416 SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift); 417 SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift); 418 419 fCx = SkFDot6ToFixed(x0); 420 fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift 421 fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 422 fCDDDx = 3*D >> (shift - 1); // biased by 2*shift 423 424 B = SkFDot6UpShift(3 * (y1 - y0), upShift); 425 C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift); 426 D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift); 427 428 fCy = SkFDot6ToFixed(y0); 429 fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift 430 fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 431 fCDDDy = 3*D >> (shift - 1); // biased by 2*shift 432 433 fCLastX = SkFDot6ToFixed(x3); 434 fCLastY = SkFDot6ToFixed(y3); 435 436 if (clip) 437 { 438 do { 439 if (!this->updateCubic()) { 440 return 0; 441 } 442 } while (!this->intersectsClip(*clip)); 443 this->chopLineWithClip(*clip); 444 return 1; 445 } 446 return this->updateCubic(); 447 } 448 449 int SkCubicEdge::updateCubic() 450 { 451 int success; 452 int count = fCurveCount; 453 SkFixed oldx = fCx; 454 SkFixed oldy = fCy; 455 SkFixed newx, newy; 456 const int ddshift = fCurveShift; 457 const int dshift = fCubicDShift; 458 459 SkASSERT(count < 0); 460 461 do { 462 if (++count < 0) 463 { 464 newx = oldx + (fCDx >> dshift); 465 fCDx += fCDDx >> ddshift; 466 fCDDx += fCDDDx; 467 468 newy = oldy + (fCDy >> dshift); 469 fCDy += fCDDy >> ddshift; 470 fCDDy += fCDDDy; 471 } 472 else // last segment 473 { 474 // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY)); 475 newx = fCLastX; 476 newy = fCLastY; 477 } 478 479 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint 480 // doesn't always achieve that, so we have to explicitly pin it here. 481 if (newy < oldy) { 482 newy = oldy; 483 } 484 485 success = this->updateLine(oldx, oldy, newx, newy); 486 oldx = newx; 487 oldy = newy; 488 } while (count < 0 && !success); 489 490 fCx = newx; 491 fCy = newy; 492 fCurveCount = SkToS8(count); 493 return success; 494 } 495