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