1 /* libs/graphics/sgl/SkEdge.cpp 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** You may obtain a copy of the License at 8 ** 9 ** http://www.apache.org/licenses/LICENSE-2.0 10 ** 11 ** Unless required by applicable law or agreed to in writing, software 12 ** distributed under the License is distributed on an "AS IS" BASIS, 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 ** See the License for the specific language governing permissions and 15 ** limitations under the License. 16 */ 17 18 #include "SkEdge.h" 19 #include "SkFDot6.h" 20 21 /* 22 In setLine, setQuadratic, setCubic, the first thing we do is to convert 23 the points into FDot6. This is modulated by the shift parameter, which 24 will either be 0, or something like 2 for antialiasing. 25 26 In the float case, we want to turn the float into .6 by saying pt * 64, 27 or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6). 28 29 In the fixed case, we want to turn the fixed into .6 by saying pt >> 10, 30 or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift). 31 */ 32 33 ///////////////////////////////////////////////////////////////////////// 34 35 int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip, 36 int shift) { 37 SkFDot6 x0, y0, x1, y1; 38 39 { 40 #ifdef SK_SCALAR_IS_FLOAT 41 float scale = float(1 << (shift + 6)); 42 x0 = int(p0.fX * scale); 43 y0 = int(p0.fY * scale); 44 x1 = int(p1.fX * scale); 45 y1 = int(p1.fY * scale); 46 #else 47 shift = 10 - shift; 48 x0 = p0.fX >> shift; 49 y0 = p0.fY >> shift; 50 x1 = p1.fX >> shift; 51 y1 = p1.fY >> shift; 52 #endif 53 } 54 55 int winding = 1; 56 57 if (y0 > y1) { 58 SkTSwap(x0, x1); 59 SkTSwap(y0, y1); 60 winding = -1; 61 } 62 63 int top = SkFDot6Round(y0); 64 int bot = SkFDot6Round(y1); 65 66 // are we a zero-height line? 67 if (top == bot) { 68 return 0; 69 } 70 // are we completely above or below the clip? 71 if (NULL != clip && (top >= clip->fBottom || bot <= clip->fTop)) { 72 return 0; 73 } 74 75 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); 76 77 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, (32 - y0) & 63)); // + SK_Fixed1/2 78 fDX = slope; 79 fFirstY = top; 80 fLastY = bot - 1; 81 fCurveCount = 0; 82 fWinding = SkToS8(winding); 83 fCurveShift = 0; 84 85 if (clip) { 86 this->chopLineWithClip(*clip); 87 } 88 return 1; 89 } 90 91 // called from a curve subclass 92 int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1) 93 { 94 SkASSERT(fWinding == 1 || fWinding == -1); 95 SkASSERT(fCurveCount != 0); 96 // SkASSERT(fCurveShift != 0); 97 98 y0 >>= 10; 99 y1 >>= 10; 100 101 SkASSERT(y0 <= y1); 102 103 int top = SkFDot6Round(y0); 104 int bot = SkFDot6Round(y1); 105 106 // SkASSERT(top >= fFirstY); 107 108 // are we a zero-height line? 109 if (top == bot) 110 return 0; 111 112 x0 >>= 10; 113 x1 >>= 10; 114 115 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); 116 117 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, (32 - y0) & 63)); // + 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_SCALAR_IS_FLOAT 182 float scale = float(1 << (shift + 6)); 183 x0 = int(pts[0].fX * scale); 184 y0 = int(pts[0].fY * scale); 185 x1 = int(pts[1].fX * scale); 186 y1 = int(pts[1].fY * scale); 187 x2 = int(pts[2].fX * scale); 188 y2 = int(pts[2].fY * scale); 189 #else 190 shift = 10 - shift; 191 x0 = pts[0].fX >> shift; 192 y0 = pts[0].fY >> shift; 193 x1 = pts[1].fX >> shift; 194 y1 = pts[1].fY >> shift; 195 x2 = pts[2].fX >> shift; 196 y2 = pts[2].fY >> shift; 197 #endif 198 } 199 200 int winding = 1; 201 if (y0 > y2) 202 { 203 SkTSwap(x0, x2); 204 SkTSwap(y0, y2); 205 winding = -1; 206 } 207 SkASSERT(y0 <= y1 && y1 <= y2); 208 209 int top = SkFDot6Round(y0); 210 int bot = SkFDot6Round(y2); 211 212 // are we a zero-height quad (line)? 213 if (top == bot) 214 return 0; 215 216 // compute number of steps needed (1 << shift) 217 { 218 SkFDot6 dx = ((x1 << 1) - x0 - x2) >> 2; 219 SkFDot6 dy = ((y1 << 1) - y0 - y2) >> 2; 220 shift = diff_to_shift(dx, dy); 221 SkASSERT(shift >= 0); 222 } 223 // need at least 1 subdivision for our bias trick 224 if (shift == 0) { 225 shift = 1; 226 } else if (shift > MAX_COEFF_SHIFT) { 227 shift = MAX_COEFF_SHIFT; 228 } 229 230 fWinding = SkToS8(winding); 231 fCurveShift = SkToU8(shift); 232 //fCubicDShift only set for cubics 233 fCurveCount = SkToS8(1 << shift); 234 235 SkFixed A = SkFDot6ToFixed(x0 - x1 - x1 + x2); 236 SkFixed B = SkFDot6ToFixed(x1 - x0 + x1 - x0); 237 238 fQx = SkFDot6ToFixed(x0); 239 fQDx = B + (A >> shift); // biased by shift 240 fQDDx = A >> (shift - 1); // biased by shift 241 242 A = SkFDot6ToFixed(y0 - y1 - y1 + y2); 243 B = SkFDot6ToFixed(y1 - y0 + y1 - y0); 244 245 fQy = SkFDot6ToFixed(y0); 246 fQDy = B + (A >> shift); // biased by shift 247 fQDDy = A >> (shift - 1); // biased by shift 248 249 fQLastX = SkFDot6ToFixed(x2); 250 fQLastY = SkFDot6ToFixed(y2); 251 252 return this->updateQuadratic(); 253 } 254 255 int SkQuadraticEdge::updateQuadratic() 256 { 257 int success; 258 int count = fCurveCount; 259 SkFixed oldx = fQx; 260 SkFixed oldy = fQy; 261 SkFixed dx = fQDx; 262 SkFixed dy = fQDy; 263 SkFixed newx, newy; 264 int shift = fCurveShift; 265 266 SkASSERT(count > 0); 267 268 do { 269 if (--count > 0) 270 { 271 newx = oldx + (dx >> shift); 272 dx += fQDDx; 273 newy = oldy + (dy >> shift); 274 dy += fQDDy; 275 } 276 else // last segment 277 { 278 newx = fQLastX; 279 newy = fQLastY; 280 } 281 success = this->updateLine(oldx, oldy, newx, newy); 282 oldx = newx; 283 oldy = newy; 284 } while (count > 0 && !success); 285 286 fQx = newx; 287 fQy = newy; 288 fQDx = dx; 289 fQDy = dy; 290 fCurveCount = SkToS8(count); 291 return success; 292 } 293 294 ///////////////////////////////////////////////////////////////////////// 295 296 static inline int SkFDot6UpShift(SkFDot6 x, int upShift) { 297 SkASSERT((x << upShift >> upShift) == x); 298 return x << upShift; 299 } 300 301 /* f(1/3) = (8a + 12b + 6c + d) / 27 302 f(2/3) = (a + 6b + 12c + 8d) / 27 303 304 f(1/3)-b = (8a - 15b + 6c + d) / 27 305 f(2/3)-c = (a + 6b - 15c + 8d) / 27 306 307 use 16/512 to approximate 1/27 308 */ 309 static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d) 310 { 311 SkFDot6 oneThird = ((a << 3) - ((b << 4) - b) + 6*c + d) * 19 >> 9; 312 SkFDot6 twoThird = (a + 6*b - ((c << 4) - c) + (d << 3)) * 19 >> 9; 313 314 return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird)); 315 } 316 317 int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift) 318 { 319 SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3; 320 321 { 322 #ifdef SK_SCALAR_IS_FLOAT 323 float scale = float(1 << (shift + 6)); 324 x0 = int(pts[0].fX * scale); 325 y0 = int(pts[0].fY * scale); 326 x1 = int(pts[1].fX * scale); 327 y1 = int(pts[1].fY * scale); 328 x2 = int(pts[2].fX * scale); 329 y2 = int(pts[2].fY * scale); 330 x3 = int(pts[3].fX * scale); 331 y3 = int(pts[3].fY * scale); 332 #else 333 shift = 10 - shift; 334 x0 = pts[0].fX >> shift; 335 y0 = pts[0].fY >> shift; 336 x1 = pts[1].fX >> shift; 337 y1 = pts[1].fY >> shift; 338 x2 = pts[2].fX >> shift; 339 y2 = pts[2].fY >> shift; 340 x3 = pts[3].fX >> shift; 341 y3 = pts[3].fY >> shift; 342 #endif 343 } 344 345 int winding = 1; 346 if (y0 > y3) 347 { 348 SkTSwap(x0, x3); 349 SkTSwap(x1, x2); 350 SkTSwap(y0, y3); 351 SkTSwap(y1, y2); 352 winding = -1; 353 } 354 355 int top = SkFDot6Round(y0); 356 int bot = SkFDot6Round(y3); 357 358 // are we a zero-height cubic (line)? 359 if (top == bot) 360 return 0; 361 362 // are we completely above or below the clip? 363 if (clip && (top >= clip->fBottom || bot <= clip->fTop)) 364 return 0; 365 366 // compute number of steps needed (1 << shift) 367 { 368 // Can't use (center of curve - center of baseline), since center-of-curve 369 // need not be the max delta from the baseline (it could even be coincident) 370 // so we try just looking at the two off-curve points 371 SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3); 372 SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3); 373 // add 1 (by observation) 374 shift = diff_to_shift(dx, dy) + 1; 375 } 376 // need at least 1 subdivision for our bias trick 377 SkASSERT(shift > 0); 378 if (shift > MAX_COEFF_SHIFT) { 379 shift = MAX_COEFF_SHIFT; 380 } 381 382 /* Since our in coming data is initially shifted down by 10 (or 8 in 383 antialias). That means the most we can shift up is 8. However, we 384 compute coefficients with a 3*, so the safest upshift is really 6 385 */ 386 int upShift = 6; // largest safe value 387 int downShift = shift + upShift - 10; 388 if (downShift < 0) { 389 downShift = 0; 390 upShift = 10 - shift; 391 } 392 393 fWinding = SkToS8(winding); 394 fCurveCount = SkToS8(-1 << shift); 395 fCurveShift = SkToU8(shift); 396 fCubicDShift = SkToU8(downShift); 397 398 SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift); 399 SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift); 400 SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift); 401 402 fCx = SkFDot6ToFixed(x0); 403 fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift 404 fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 405 fCDDDx = 3*D >> (shift - 1); // biased by 2*shift 406 407 B = SkFDot6UpShift(3 * (y1 - y0), upShift); 408 C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift); 409 D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift); 410 411 fCy = SkFDot6ToFixed(y0); 412 fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift 413 fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift 414 fCDDDy = 3*D >> (shift - 1); // biased by 2*shift 415 416 fCLastX = SkFDot6ToFixed(x3); 417 fCLastY = SkFDot6ToFixed(y3); 418 419 if (clip) 420 { 421 do { 422 if (!this->updateCubic()) { 423 return 0; 424 } 425 } while (!this->intersectsClip(*clip)); 426 this->chopLineWithClip(*clip); 427 return 1; 428 } 429 return this->updateCubic(); 430 } 431 432 int SkCubicEdge::updateCubic() 433 { 434 int success; 435 int count = fCurveCount; 436 SkFixed oldx = fCx; 437 SkFixed oldy = fCy; 438 SkFixed newx, newy; 439 const int ddshift = fCurveShift; 440 const int dshift = fCubicDShift; 441 442 SkASSERT(count < 0); 443 444 do { 445 if (++count < 0) 446 { 447 newx = oldx + (fCDx >> dshift); 448 fCDx += fCDDx >> ddshift; 449 fCDDx += fCDDDx; 450 451 newy = oldy + (fCDy >> dshift); 452 fCDy += fCDDy >> ddshift; 453 fCDDy += fCDDDy; 454 } 455 else // last segment 456 { 457 // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY)); 458 newx = fCLastX; 459 newy = fCLastY; 460 } 461 success = this->updateLine(oldx, oldy, newx, newy); 462 oldx = newx; 463 oldy = newy; 464 } while (count < 0 && !success); 465 466 fCx = newx; 467 fCy = newy; 468 fCurveCount = SkToS8(count); 469 return success; 470 } 471 472 473 474