| OLD | NEW |
|---|
| (Empty) |
| 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 #include <limits> | |
| 21 | |
| 22 /* | |
| 23 In setLine, setQuadratic, setCubic, the first thing we do is to convert | |
| 24 the points into FDot6. This is modulated by the shift parameter, which | |
| 25 will either be 0, or something like 2 for antialiasing. | |
| 26 | |
| 27 In the float case, we want to turn the float into .6 by saying pt * 64, | |
| 28 or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6). | |
| 29 | |
| 30 In the fixed case, we want to turn the fixed into .6 by saying pt >> 10, | |
| 31 or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift). | |
| 32 */ | |
| 33 | |
| 34 ///////////////////////////////////////////////////////////////////////// | |
| 35 | |
| 36 int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip, | |
| 37 int shift) { | |
| 38 SkFDot6 x0, y0, x1, y1; | |
| 39 | |
| 40 { | |
| 41 #ifdef SK_SCALAR_IS_FLOAT | |
| 42 float scale = float(1 << (shift + 6)); | |
| 43 x0 = int(p0.fX * scale); | |
| 44 y0 = int(p0.fY * scale); | |
| 45 x1 = int(p1.fX * scale); | |
| 46 y1 = int(p1.fY * scale); | |
| 47 #else | |
| 48 shift = 10 - shift; | |
| 49 x0 = p0.fX >> shift; | |
| 50 y0 = p0.fY >> shift; | |
| 51 x1 = p1.fX >> shift; | |
| 52 y1 = p1.fY >> shift; | |
| 53 #endif | |
| 54 } | |
| 55 | |
| 56 int winding = 1; | |
| 57 | |
| 58 if (y0 > y1) { | |
| 59 SkTSwap(x0, x1); | |
| 60 SkTSwap(y0, y1); | |
| 61 winding = -1; | |
| 62 } | |
| 63 | |
| 64 int top = SkFDot6Round(y0); | |
| 65 int bot = SkFDot6Round(y1); | |
| 66 | |
| 67 // are we a zero-height line? | |
| 68 if (top == bot) { | |
| 69 return 0; | |
| 70 } | |
| 71 // are we completely above or below the clip? | |
| 72 if (NULL != clip && (top >= clip->fBottom || bot <= clip->fTop)) { | |
| 73 return 0; | |
| 74 } | |
| 75 | |
| 76 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); | |
| 77 | |
| 78 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, (32 - y0) & 63)); // +
SK_Fixed1/2 | |
| 79 fDX = slope; | |
| 80 #if 0 | |
| 81 // CHANGED FOR CHROME | |
| 82 fFirstY = top; | |
| 83 fLastY = bot - 1; | |
| 84 #else | |
| 85 fFirstY = top; | |
| 86 if (top != (long)fFirstY) { | |
| 87 if (fFirstY < top) { | |
| 88 fFirstY = std::numeric_limits<int16_t>::max(); | |
| 89 } else { | |
| 90 fFirstY = std::numeric_limits<int16_t>::min(); | |
| 91 } | |
| 92 fX -= fDX * (top - (long)fFirstY); | |
| 93 } | |
| 94 fLastY = bot - 1; | |
| 95 if (bot-1 != (long)fLastY) { | |
| 96 if (fLastY < bot-1) { | |
| 97 fLastY = std::numeric_limits<int16_t>::max(); | |
| 98 } else { | |
| 99 fLastY = std::numeric_limits<int16_t>::min(); | |
| 100 } | |
| 101 } | |
| 102 #endif | |
| 103 fCurveCount = 0; | |
| 104 fWinding = SkToS8(winding); | |
| 105 fCurveShift = 0; | |
| 106 | |
| 107 if (clip) { | |
| 108 this->chopLineWithClip(*clip); | |
| 109 } | |
| 110 return 1; | |
| 111 } | |
| 112 | |
| 113 // called from a curve subclass | |
| 114 int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1) | |
| 115 { | |
| 116 SkASSERT(fWinding == 1 || fWinding == -1); | |
| 117 SkASSERT(fCurveCount != 0); | |
| 118 // SkASSERT(fCurveShift != 0); | |
| 119 | |
| 120 y0 >>= 10; | |
| 121 y1 >>= 10; | |
| 122 | |
| 123 SkASSERT(y0 <= y1); | |
| 124 | |
| 125 int top = SkFDot6Round(y0); | |
| 126 int bot = SkFDot6Round(y1); | |
| 127 | |
| 128 // SkASSERT(top >= fFirstY); | |
| 129 | |
| 130 // are we a zero-height line? | |
| 131 if (top == bot) | |
| 132 return 0; | |
| 133 | |
| 134 x0 >>= 10; | |
| 135 x1 >>= 10; | |
| 136 | |
| 137 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0); | |
| 138 | |
| 139 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, (32 - y0) & 63)); // +
SK_Fixed1/2 | |
| 140 fDX = slope; | |
| 141 fFirstY = top; | |
| 142 fLastY = bot - 1; | |
| 143 | |
| 144 return 1; | |
| 145 } | |
| 146 | |
| 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 | |
| 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 | |
| 183 static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy) | |
| 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 5 should give us 1/2 pixel accuracy (assuming our dist is accurat
e...) | |
| 190 // this is chosen by heuristic: make it as big as possible (to minimize segm
ents) | |
| 191 // ... but small enough so that our curves still look smooth | |
| 192 dist = (dist + (1 << 4)) >> 5; | |
| 193 | |
| 194 // each subdivision (shift value) cuts this dist (error) by 1/4 | |
| 195 return (32 - SkCLZ(dist)) >> 1; | |
| 196 } | |
| 197 | |
| 198 int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], const SkIRect* clip, int
shift) | |
| 199 { | |
| 200 SkFDot6 x0, y0, x1, y1, x2, y2; | |
| 201 | |
| 202 { | |
| 203 #ifdef SK_SCALAR_IS_FLOAT | |
| 204 float scale = float(1 << (shift + 6)); | |
| 205 x0 = int(pts[0].fX * scale); | |
| 206 y0 = int(pts[0].fY * scale); | |
| 207 x1 = int(pts[1].fX * scale); | |
| 208 y1 = int(pts[1].fY * scale); | |
| 209 x2 = int(pts[2].fX * scale); | |
| 210 y2 = int(pts[2].fY * scale); | |
| 211 #else | |
| 212 shift = 10 - shift; | |
| 213 x0 = pts[0].fX >> shift; | |
| 214 y0 = pts[0].fY >> shift; | |
| 215 x1 = pts[1].fX >> shift; | |
| 216 y1 = pts[1].fY >> shift; | |
| 217 x2 = pts[2].fX >> shift; | |
| 218 y2 = pts[2].fY >> shift; | |
| 219 #endif | |
| 220 } | |
| 221 | |
| 222 int winding = 1; | |
| 223 if (y0 > y2) | |
| 224 { | |
| 225 SkTSwap(x0, x2); | |
| 226 SkTSwap(y0, y2); | |
| 227 winding = -1; | |
| 228 } | |
| 229 SkASSERT(y0 <= y1 && y1 <= y2); | |
| 230 | |
| 231 int top = SkFDot6Round(y0); | |
| 232 int bot = SkFDot6Round(y2); | |
| 233 | |
| 234 // are we a zero-height quad (line)? | |
| 235 if (top == bot) | |
| 236 return 0; | |
| 237 // are we completely above or below the clip? | |
| 238 if (clip && (top >= clip->fBottom || bot <= clip->fTop)) | |
| 239 return 0; | |
| 240 | |
| 241 // compute number of steps needed (1 << shift) | |
| 242 { | |
| 243 SkFDot6 dx = ((x1 << 1) - x0 - x2) >> 2; | |
| 244 SkFDot6 dy = ((y1 << 1) - y0 - y2) >> 2; | |
| 245 shift = diff_to_shift(dx, dy); | |
| 246 SkASSERT(shift >= 0); | |
| 247 } | |
| 248 // need at least 1 subdivision for our bias trick | |
| 249 if (shift == 0) { | |
| 250 shift = 1; | |
| 251 } else if (shift > MAX_COEFF_SHIFT) { | |
| 252 shift = MAX_COEFF_SHIFT; | |
| 253 } | |
| 254 | |
| 255 fWinding = SkToS8(winding); | |
| 256 fCurveShift = SkToU8(shift); | |
| 257 //fCubicDShift only set for cubics | |
| 258 fCurveCount = SkToS8(1 << shift); | |
| 259 | |
| 260 SkFixed A = SkFDot6ToFixed(x0 - x1 - x1 + x2); | |
| 261 SkFixed B = SkFDot6ToFixed(x1 - x0 + x1 - x0); | |
| 262 | |
| 263 fQx = SkFDot6ToFixed(x0); | |
| 264 fQDx = B + (A >> shift); // biased by shift | |
| 265 fQDDx = A >> (shift - 1); // biased by shift | |
| 266 | |
| 267 A = SkFDot6ToFixed(y0 - y1 - y1 + y2); | |
| 268 B = SkFDot6ToFixed(y1 - y0 + y1 - y0); | |
| 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 if (clip) | |
| 278 { | |
| 279 do { | |
| 280 for (;!this->updateQuadratic();) | |
| 281 ; | |
| 282 } while (!this->intersectsClip(*clip)); | |
| 283 this->chopLineWithClip(*clip); | |
| 284 return 1; | |
| 285 } | |
| 286 return this->updateQuadratic(); | |
| 287 } | |
| 288 | |
| 289 int SkQuadraticEdge::updateQuadratic() | |
| 290 { | |
| 291 int success; | |
| 292 int count = fCurveCount; | |
| 293 SkFixed oldx = fQx; | |
| 294 SkFixed oldy = fQy; | |
| 295 SkFixed dx = fQDx; | |
| 296 SkFixed dy = fQDy; | |
| 297 SkFixed newx, newy; | |
| 298 int shift = fCurveShift; | |
| 299 | |
| 300 SkASSERT(count > 0); | |
| 301 | |
| 302 do { | |
| 303 if (--count > 0) | |
| 304 { | |
| 305 newx = oldx + (dx >> shift); | |
| 306 dx += fQDDx; | |
| 307 newy = oldy + (dy >> shift); | |
| 308 dy += fQDDy; | |
| 309 } | |
| 310 else // last segment | |
| 311 { | |
| 312 newx = fQLastX; | |
| 313 newy = fQLastY; | |
| 314 } | |
| 315 success = this->updateLine(oldx, oldy, newx, newy); | |
| 316 oldx = newx; | |
| 317 oldy = newy; | |
| 318 } while (count > 0 && !success); | |
| 319 | |
| 320 fQx = newx; | |
| 321 fQy = newy; | |
| 322 fQDx = dx; | |
| 323 fQDy = dy; | |
| 324 fCurveCount = SkToS16(count); | |
| 325 return success; | |
| 326 } | |
| 327 | |
| 328 ///////////////////////////////////////////////////////////////////////// | |
| 329 | |
| 330 static inline int SkFDot6UpShift(SkFDot6 x, int upShift) { | |
| 331 SkASSERT((x << upShift >> upShift) == x); | |
| 332 return x << upShift; | |
| 333 } | |
| 334 | |
| 335 /* f(1/3) = (8a + 12b + 6c + d) / 27 | |
| 336 f(2/3) = (a + 6b + 12c + 8d) / 27 | |
| 337 | |
| 338 f(1/3)-b = (8a - 15b + 6c + d) / 27 | |
| 339 f(2/3)-c = (a + 6b - 15c + 8d) / 27 | |
| 340 | |
| 341 use 16/512 to approximate 1/27 | |
| 342 */ | |
| 343 static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d) | |
| 344 { | |
| 345 SkFDot6 oneThird = ((a << 3) - ((b << 4) - b) + 6*c + d) * 19 >> 9; | |
| 346 SkFDot6 twoThird = (a + 6*b - ((c << 4) - c) + (d << 3)) * 19 >> 9; | |
| 347 | |
| 348 return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird)); | |
| 349 } | |
| 350 | |
| 351 int SkCubicEdge::setCubic(const SkPoint pts[4], const SkIRect* clip, int shift) | |
| 352 { | |
| 353 SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3; | |
| 354 | |
| 355 { | |
| 356 #ifdef SK_SCALAR_IS_FLOAT | |
| 357 float scale = float(1 << (shift + 6)); | |
| 358 x0 = int(pts[0].fX * scale); | |
| 359 y0 = int(pts[0].fY * scale); | |
| 360 x1 = int(pts[1].fX * scale); | |
| 361 y1 = int(pts[1].fY * scale); | |
| 362 x2 = int(pts[2].fX * scale); | |
| 363 y2 = int(pts[2].fY * scale); | |
| 364 x3 = int(pts[3].fX * scale); | |
| 365 y3 = int(pts[3].fY * scale); | |
| 366 #else | |
| 367 shift = 10 - shift; | |
| 368 x0 = pts[0].fX >> shift; | |
| 369 y0 = pts[0].fY >> shift; | |
| 370 x1 = pts[1].fX >> shift; | |
| 371 y1 = pts[1].fY >> shift; | |
| 372 x2 = pts[2].fX >> shift; | |
| 373 y2 = pts[2].fY >> shift; | |
| 374 x3 = pts[3].fX >> shift; | |
| 375 y3 = pts[3].fY >> shift; | |
| 376 #endif | |
| 377 } | |
| 378 | |
| 379 int winding = 1; | |
| 380 if (y0 > y3) | |
| 381 { | |
| 382 SkTSwap(x0, x3); | |
| 383 SkTSwap(x1, x2); | |
| 384 SkTSwap(y0, y3); | |
| 385 SkTSwap(y1, y2); | |
| 386 winding = -1; | |
| 387 } | |
| 388 | |
| 389 int top = SkFDot6Round(y0); | |
| 390 int bot = SkFDot6Round(y3); | |
| 391 | |
| 392 // are we a zero-height cubic (line)? | |
| 393 if (top == bot) | |
| 394 return 0; | |
| 395 | |
| 396 // are we completely above or below the clip? | |
| 397 if (clip && (top >= clip->fBottom || bot <= clip->fTop)) | |
| 398 return 0; | |
| 399 | |
| 400 // compute number of steps needed (1 << shift) | |
| 401 { | |
| 402 // Can't use (center of curve - center of baseline), since center-of-cur
ve | |
| 403 // need not be the max delta from the baseline (it could even be coincid
ent) | |
| 404 // so we try just looking at the two off-curve points | |
| 405 SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3); | |
| 406 SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3); | |
| 407 // add 1 (by observation) | |
| 408 shift = diff_to_shift(dx, dy) + 1; | |
| 409 } | |
| 410 // need at least 1 subdivision for our bias trick | |
| 411 SkASSERT(shift > 0); | |
| 412 if (shift > MAX_COEFF_SHIFT) { | |
| 413 shift = MAX_COEFF_SHIFT; | |
| 414 } | |
| 415 | |
| 416 /* Since our in coming data is initially shifted down by 10 (or 8 in | |
| 417 antialias). That means the most we can shift up is 8. However, we | |
| 418 compute coefficients with a 3*, so the safest upshift is really 6 | |
| 419 */ | |
| 420 int upShift = 6; // largest safe value | |
| 421 int downShift = shift + upShift - 10; | |
| 422 if (downShift < 0) { | |
| 423 downShift = 0; | |
| 424 upShift = 10 - shift; | |
| 425 } | |
| 426 | |
| 427 fWinding = SkToS8(winding); | |
| 428 fCurveCount = SkToS8(-1 << shift); | |
| 429 fCurveShift = SkToU8(shift); | |
| 430 fCubicDShift = SkToU8(downShift); | |
| 431 | |
| 432 SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift); | |
| 433 SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift); | |
| 434 SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift); | |
| 435 | |
| 436 fCx = SkFDot6ToFixed(x0); | |
| 437 fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift | |
| 438 fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift | |
| 439 fCDDDx = 3*D >> (shift - 1); // biased by 2*shift | |
| 440 | |
| 441 B = SkFDot6UpShift(3 * (y1 - y0), upShift); | |
| 442 C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift); | |
| 443 D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift); | |
| 444 | |
| 445 fCy = SkFDot6ToFixed(y0); | |
| 446 fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift | |
| 447 fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift | |
| 448 fCDDDy = 3*D >> (shift - 1); // biased by 2*shift | |
| 449 | |
| 450 fCLastX = SkFDot6ToFixed(x3); | |
| 451 fCLastY = SkFDot6ToFixed(y3); | |
| 452 | |
| 453 if (clip) | |
| 454 { | |
| 455 do { | |
| 456 for (;!this->updateCubic();) | |
| 457 ; | |
| 458 } while (!this->intersectsClip(*clip)); | |
| 459 this->chopLineWithClip(*clip); | |
| 460 return 1; | |
| 461 } | |
| 462 return this->updateCubic(); | |
| 463 } | |
| 464 | |
| 465 int SkCubicEdge::updateCubic() | |
| 466 { | |
| 467 int success; | |
| 468 int count = fCurveCount; | |
| 469 SkFixed oldx = fCx; | |
| 470 SkFixed oldy = fCy; | |
| 471 SkFixed newx, newy; | |
| 472 const int ddshift = fCurveShift; | |
| 473 const int dshift = fCubicDShift; | |
| 474 | |
| 475 SkASSERT(count < 0); | |
| 476 | |
| 477 do { | |
| 478 if (++count < 0) | |
| 479 { | |
| 480 newx = oldx + (fCDx >> dshift); | |
| 481 fCDx += fCDDx >> ddshift; | |
| 482 fCDDx += fCDDDx; | |
| 483 | |
| 484 newy = oldy + (fCDy >> dshift); | |
| 485 fCDy += fCDDy >> ddshift; | |
| 486 fCDDy += fCDDDy; | |
| 487 } | |
| 488 else // last segment | |
| 489 { | |
| 490 // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - f
LastX), (oldy + (fCDy >> shift) - fLastY)); | |
| 491 newx = fCLastX; | |
| 492 newy = fCLastY; | |
| 493 } | |
| 494 success = this->updateLine(oldx, oldy, newx, newy); | |
| 495 oldx = newx; | |
| 496 oldy = newy; | |
| 497 } while (count < 0 && !success); | |
| 498 | |
| 499 fCx = newx; | |
| 500 fCy = newy; | |
| 501 fCurveCount = SkToS16(count); | |
| 502 return success; | |
| 503 } | |
| 504 | |
| 505 | |
| 506 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 113827:
Remove the remainder of the skia source code from the Chromium repo.... (Closed)
Base URL: svn://chrome-svn/chrome/trunk/src/