1 /* libs/graphics/sgl/SkScan_Antihair.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 "SkScan.h" 19 #include "SkBlitter.h" 20 #include "SkColorPriv.h" 21 #include "SkLineClipper.h" 22 #include "SkRegion.h" 23 #include "SkFDot6.h" 24 25 /* Our attempt to compute the worst case "bounds" for the horizontal and 26 vertical cases has some numerical bug in it, and we sometimes undervalue 27 our extends. The bug is that when this happens, we will set the clip to 28 NULL (for speed), and thus draw outside of the clip by a pixel, which might 29 only look bad, but it might also access memory outside of the valid range 30 allcoated for the device bitmap. 31 32 This define enables our fix to outset our "bounds" by 1, thus avoiding the 33 chance of the bug, but at the cost of sometimes taking the rectblitter 34 case (i.e. not setting the clip to NULL) when we might not actually need 35 to. If we can improve/fix the actual calculations, then we can remove this 36 step. 37 */ 38 #define OUTSET_BEFORE_CLIP_TEST true 39 40 #define HLINE_STACK_BUFFER 100 41 42 static inline int SmallDot6Scale(int value, int dot6) { 43 SkASSERT((int16_t)value == value); 44 SkASSERT((unsigned)dot6 <= 64); 45 return SkMulS16(value, dot6) >> 6; 46 } 47 48 //#define TEST_GAMMA 49 50 #ifdef TEST_GAMMA 51 static uint8_t gGammaTable[256]; 52 #define ApplyGamma(table, alpha) (table)[alpha] 53 54 static void build_gamma_table() 55 { 56 static bool gInit = false; 57 58 if (gInit == false) 59 { 60 for (int i = 0; i < 256; i++) 61 { 62 SkFixed n = i * 257; 63 n += n >> 15; 64 SkASSERT(n >= 0 && n <= SK_Fixed1); 65 n = SkFixedSqrt(n); 66 n = n * 255 >> 16; 67 // SkDebugf("morph %d -> %d\n", i, n); 68 gGammaTable[i] = SkToU8(n); 69 } 70 gInit = true; 71 } 72 } 73 #else 74 #define ApplyGamma(table, alpha) SkToU8(alpha) 75 #endif 76 77 /////////////////////////////////////////////////////////////////////////////// 78 79 static void call_hline_blitter(SkBlitter* blitter, int x, int y, int count, U8CPU alpha) 80 { 81 SkASSERT(count > 0); 82 83 int16_t runs[HLINE_STACK_BUFFER + 1]; 84 uint8_t aa[HLINE_STACK_BUFFER]; 85 86 aa[0] = ApplyGamma(gGammaTable, alpha); 87 do { 88 int n = count; 89 if (n > HLINE_STACK_BUFFER) 90 n = HLINE_STACK_BUFFER; 91 92 runs[0] = SkToS16(n); 93 runs[n] = 0; 94 blitter->blitAntiH(x, y, aa, runs); 95 x += n; 96 count -= n; 97 } while (count > 0); 98 } 99 100 static SkFixed hline(int x, int stopx, SkFixed fy, SkFixed /*slope*/, SkBlitter* blitter, int mod64) 101 { 102 SkASSERT(x < stopx); 103 int count = stopx - x; 104 fy += SK_Fixed1/2; 105 106 int y = fy >> 16; 107 uint8_t a = (uint8_t)(fy >> 8); 108 109 // lower line 110 unsigned ma = SmallDot6Scale(a, mod64); 111 if (ma) { 112 call_hline_blitter(blitter, x, y, count, ma); 113 } 114 115 // upper line 116 ma = SmallDot6Scale(255 - a, mod64); 117 if (ma) { 118 call_hline_blitter(blitter, x, y - 1, count, ma); 119 } 120 121 return fy - SK_Fixed1/2; 122 } 123 124 static SkFixed horish(int x, int stopx, SkFixed fy, SkFixed dy, SkBlitter* blitter, int mod64) 125 { 126 SkASSERT(x < stopx); 127 128 #ifdef TEST_GAMMA 129 const uint8_t* gamma = gGammaTable; 130 #endif 131 int16_t runs[2]; 132 uint8_t aa[1]; 133 134 runs[0] = 1; 135 runs[1] = 0; 136 137 fy += SK_Fixed1/2; 138 do { 139 int lower_y = fy >> 16; 140 uint8_t a = (uint8_t)(fy >> 8); 141 unsigned ma = SmallDot6Scale(a, mod64); 142 if (ma) 143 { 144 aa[0] = ApplyGamma(gamma, ma); 145 blitter->blitAntiH(x, lower_y, aa, runs); 146 // the clipping blitters might edit runs, but should not affect us 147 SkASSERT(runs[0] == 1); 148 SkASSERT(runs[1] == 0); 149 } 150 ma = SmallDot6Scale(255 - a, mod64); 151 if (ma) 152 { 153 aa[0] = ApplyGamma(gamma, ma); 154 blitter->blitAntiH(x, lower_y - 1, aa, runs); 155 // the clipping blitters might edit runs, but should not affect us 156 SkASSERT(runs[0] == 1); 157 SkASSERT(runs[1] == 0); 158 } 159 fy += dy; 160 } while (++x < stopx); 161 162 return fy - SK_Fixed1/2; 163 } 164 165 static SkFixed vline(int y, int stopy, SkFixed fx, SkFixed /*slope*/, SkBlitter* blitter, int mod64) 166 { 167 SkASSERT(y < stopy); 168 fx += SK_Fixed1/2; 169 170 int x = fx >> 16; 171 int a = (uint8_t)(fx >> 8); 172 173 unsigned ma = SmallDot6Scale(a, mod64); 174 if (ma) 175 blitter->blitV(x, y, stopy - y, ApplyGamma(gGammaTable, ma)); 176 ma = SmallDot6Scale(255 - a, mod64); 177 if (ma) 178 blitter->blitV(x - 1, y, stopy - y, ApplyGamma(gGammaTable, ma)); 179 180 return fx - SK_Fixed1/2; 181 } 182 183 static SkFixed vertish(int y, int stopy, SkFixed fx, SkFixed dx, SkBlitter* blitter, int mod64) 184 { 185 SkASSERT(y < stopy); 186 #ifdef TEST_GAMMA 187 const uint8_t* gamma = gGammaTable; 188 #endif 189 int16_t runs[3]; 190 uint8_t aa[2]; 191 192 runs[0] = 1; 193 runs[2] = 0; 194 195 fx += SK_Fixed1/2; 196 do { 197 int x = fx >> 16; 198 uint8_t a = (uint8_t)(fx >> 8); 199 200 aa[0] = ApplyGamma(gamma, SmallDot6Scale(255 - a, mod64)); 201 aa[1] = ApplyGamma(gamma, SmallDot6Scale(a, mod64)); 202 // the clippng blitters might overwrite this guy, so we have to reset it each time 203 runs[1] = 1; 204 blitter->blitAntiH(x - 1, y, aa, runs); 205 // the clipping blitters might edit runs, but should not affect us 206 SkASSERT(runs[0] == 1); 207 SkASSERT(runs[2] == 0); 208 fx += dx; 209 } while (++y < stopy); 210 211 return fx - SK_Fixed1/2; 212 } 213 214 typedef SkFixed (*LineProc)(int istart, int istop, SkFixed fstart, SkFixed slope, SkBlitter*, int); 215 216 static inline SkFixed fastfixdiv(SkFDot6 a, SkFDot6 b) 217 { 218 SkASSERT((a << 16 >> 16) == a); 219 SkASSERT(b != 0); 220 return (a << 16) / b; 221 } 222 223 static void do_anti_hairline(SkFDot6 x0, SkFDot6 y0, SkFDot6 x1, SkFDot6 y1, 224 const SkIRect* clip, SkBlitter* blitter) 225 { 226 // check that we're no larger than 511 pixels (so we can do a faster div). 227 // if we are, subdivide and call again 228 229 if (SkAbs32(x1 - x0) > SkIntToFDot6(511) || SkAbs32(y1 - y0) > SkIntToFDot6(511)) 230 { 231 /* instead of (x0 + x1) >> 1, we shift each separately. This is less 232 precise, but avoids overflowing the intermediate result if the 233 values are huge. A better fix might be to clip the original pts 234 directly (i.e. do the divide), so we don't spend time subdividing 235 huge lines at all. 236 */ 237 int hx = (x0 >> 1) + (x1 >> 1); 238 int hy = (y0 >> 1) + (y1 >> 1); 239 do_anti_hairline(x0, y0, hx, hy, clip, blitter); 240 do_anti_hairline(hx, hy, x1, y1, clip, blitter); 241 return; 242 } 243 244 int scaleStart, scaleStop; 245 int istart, istop; 246 SkFixed fstart, slope; 247 LineProc proc; 248 249 if (SkAbs32(x1 - x0) > SkAbs32(y1 - y0)) // mostly horizontal 250 { 251 if (x0 > x1) { // we want to go left-to-right 252 SkTSwap<SkFDot6>(x0, x1); 253 SkTSwap<SkFDot6>(y0, y1); 254 } 255 256 istart = SkFDot6Floor(x0); 257 istop = SkFDot6Ceil(x1); 258 fstart = SkFDot6ToFixed(y0); 259 if (y0 == y1) { // completely horizontal, take fast case 260 slope = 0; 261 proc = hline; 262 } else { 263 slope = fastfixdiv(y1 - y0, x1 - x0); 264 SkASSERT(slope >= -SK_Fixed1 && slope <= SK_Fixed1); 265 fstart += (slope * (32 - (x0 & 63)) + 32) >> 6; 266 proc = horish; 267 } 268 269 SkASSERT(istop > istart); 270 if (istop - istart == 1) { 271 scaleStart = x1 - x0; 272 SkASSERT(scaleStart >= 0 && scaleStart <= 64); 273 scaleStop = 0; 274 } else { 275 scaleStart = 64 - (x0 & 63); 276 scaleStop = x1 & 63; 277 } 278 279 if (clip) 280 { 281 if (istart >= clip->fRight || istop <= clip->fLeft) 282 return; 283 if (istart < clip->fLeft) 284 { 285 fstart += slope * (clip->fLeft - istart); 286 istart = clip->fLeft; 287 scaleStart = 64; 288 } 289 if (istop > clip->fRight) { 290 istop = clip->fRight; 291 scaleStop = 64; 292 } 293 SkASSERT(istart <= istop); 294 if (istart == istop) 295 return; 296 297 // now test if our Y values are completely inside the clip 298 int top, bottom; 299 if (slope >= 0) // T2B 300 { 301 top = SkFixedFloor(fstart - SK_FixedHalf); 302 bottom = SkFixedCeil(fstart + (istop - istart - 1) * slope + SK_FixedHalf); 303 } 304 else // B2T 305 { 306 bottom = SkFixedCeil(fstart + SK_FixedHalf); 307 top = SkFixedFloor(fstart + (istop - istart - 1) * slope - SK_FixedHalf); 308 } 309 #ifdef OUTSET_BEFORE_CLIP_TEST 310 top -= 1; 311 bottom += 1; 312 #endif 313 if (top >= clip->fBottom || bottom <= clip->fTop) 314 return; 315 if (clip->fTop <= top && clip->fBottom >= bottom) 316 clip = NULL; 317 } 318 } 319 else // mostly vertical 320 { 321 if (y0 > y1) // we want to go top-to-bottom 322 { 323 SkTSwap<SkFDot6>(x0, x1); 324 SkTSwap<SkFDot6>(y0, y1); 325 } 326 327 istart = SkFDot6Floor(y0); 328 istop = SkFDot6Ceil(y1); 329 fstart = SkFDot6ToFixed(x0); 330 if (x0 == x1) 331 { 332 if (y0 == y1) { // are we zero length? 333 return; // nothing to do 334 } 335 slope = 0; 336 proc = vline; 337 } 338 else 339 { 340 slope = fastfixdiv(x1 - x0, y1 - y0); 341 SkASSERT(slope <= SK_Fixed1 && slope >= -SK_Fixed1); 342 fstart += (slope * (32 - (y0 & 63)) + 32) >> 6; 343 proc = vertish; 344 } 345 346 SkASSERT(istop > istart); 347 if (istop - istart == 1) { 348 scaleStart = y1 - y0; 349 SkASSERT(scaleStart >= 0 && scaleStart <= 64); 350 scaleStop = 0; 351 } else { 352 scaleStart = 64 - (y0 & 63); 353 scaleStop = y1 & 63; 354 } 355 356 if (clip) 357 { 358 if (istart >= clip->fBottom || istop <= clip->fTop) 359 return; 360 if (istart < clip->fTop) 361 { 362 fstart += slope * (clip->fTop - istart); 363 istart = clip->fTop; 364 scaleStart = 64; 365 } 366 if (istop > clip->fBottom) { 367 istop = clip->fBottom; 368 scaleStop = 64; 369 } 370 SkASSERT(istart <= istop); 371 if (istart == istop) 372 return; 373 374 // now test if our X values are completely inside the clip 375 int left, right; 376 if (slope >= 0) // L2R 377 { 378 left = SkFixedFloor(fstart - SK_FixedHalf); 379 right = SkFixedCeil(fstart + (istop - istart - 1) * slope + SK_FixedHalf); 380 } 381 else // R2L 382 { 383 right = SkFixedCeil(fstart + SK_FixedHalf); 384 left = SkFixedFloor(fstart + (istop - istart - 1) * slope - SK_FixedHalf); 385 } 386 #ifdef OUTSET_BEFORE_CLIP_TEST 387 left -= 1; 388 right += 1; 389 #endif 390 if (left >= clip->fRight || right <= clip->fLeft) 391 return; 392 if (clip->fLeft <= left && clip->fRight >= right) 393 clip = NULL; 394 } 395 } 396 397 SkRectClipBlitter rectClipper; 398 if (clip) 399 { 400 rectClipper.init(blitter, *clip); 401 blitter = &rectClipper; 402 } 403 404 fstart = proc(istart, istart + 1, fstart, slope, blitter, scaleStart); 405 istart += 1; 406 int fullSpans = istop - istart - (scaleStop > 0); 407 if (fullSpans > 0) { 408 fstart = proc(istart, istart + fullSpans, fstart, slope, blitter, 64); 409 } 410 if (scaleStop > 0) { 411 proc(istop - 1, istop, fstart, slope, blitter, scaleStop); 412 } 413 } 414 415 void SkScan::AntiHairLine(const SkPoint& pt0, const SkPoint& pt1, 416 const SkRegion* clip, SkBlitter* blitter) 417 { 418 if (clip && clip->isEmpty()) 419 return; 420 421 SkASSERT(clip == NULL || !clip->getBounds().isEmpty()); 422 423 #ifdef TEST_GAMMA 424 build_gamma_table(); 425 #endif 426 427 SkPoint pts[2] = { pt0, pt1 }; 428 429 if (clip) { 430 SkRect clipBounds; 431 clipBounds.set(clip->getBounds()); 432 /* We perform integral clipping later on, but we do a scalar clip first 433 to ensure that our coordinates are expressible in fixed/integers. 434 435 antialiased hairlines can draw up to 1/2 of a pixel outside of 436 their bounds, so we need to outset the clip before calling the 437 clipper. To make the numerics safer, we outset by a whole pixel, 438 since the 1/2 pixel boundary is important to the antihair blitter, 439 we don't want to risk numerical fate by chopping on that edge. 440 */ 441 clipBounds.inset(-SK_Scalar1, -SK_Scalar1); 442 443 if (!SkLineClipper::IntersectLine(pts, clipBounds, pts)) { 444 return; 445 } 446 } 447 448 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX); 449 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY); 450 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX); 451 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY); 452 453 if (clip) { 454 SkFDot6 left = SkMin32(x0, x1); 455 SkFDot6 top = SkMin32(y0, y1); 456 SkFDot6 right = SkMax32(x0, x1); 457 SkFDot6 bottom = SkMax32(y0, y1); 458 SkIRect ir; 459 460 ir.set( SkFDot6Floor(left) - 1, 461 SkFDot6Floor(top) - 1, 462 SkFDot6Ceil(right) + 1, 463 SkFDot6Ceil(bottom) + 1); 464 465 if (clip->quickReject(ir)) { 466 return; 467 } 468 if (!clip->quickContains(ir)) { 469 SkRegion::Cliperator iter(*clip, ir); 470 const SkIRect* r = &iter.rect(); 471 472 while (!iter.done()) { 473 do_anti_hairline(x0, y0, x1, y1, r, blitter); 474 iter.next(); 475 } 476 return; 477 } 478 // fall through to no-clip case 479 } 480 do_anti_hairline(x0, y0, x1, y1, NULL, blitter); 481 } 482 483 void SkScan::AntiHairRect(const SkRect& rect, const SkRegion* clip, SkBlitter* blitter) 484 { 485 SkPoint p0, p1; 486 487 p0.set(rect.fLeft, rect.fTop); 488 p1.set(rect.fRight, rect.fTop); 489 SkScan::AntiHairLine(p0, p1, clip, blitter); 490 p0.set(rect.fRight, rect.fBottom); 491 SkScan::AntiHairLine(p0, p1, clip, blitter); 492 p1.set(rect.fLeft, rect.fBottom); 493 SkScan::AntiHairLine(p0, p1, clip, blitter); 494 p0.set(rect.fLeft, rect.fTop); 495 SkScan::AntiHairLine(p0, p1, clip, blitter); 496 } 497 498 ////////////////////////////////////////////////////////////////////////////////////////// 499 500 typedef int FDot8; // 24.8 integer fixed point 501 502 static inline FDot8 SkFixedToFDot8(SkFixed x) { 503 return (x + 0x80) >> 8; 504 } 505 506 static void do_scanline(FDot8 L, int top, FDot8 R, U8CPU alpha, SkBlitter* blitter) 507 { 508 SkASSERT(L < R); 509 510 if ((L >> 8) == ((R - 1) >> 8)) // 1x1 pixel 511 { 512 blitter->blitV(L >> 8, top, 1, SkAlphaMul(alpha, R - L)); 513 return; 514 } 515 516 int left = L >> 8; 517 518 if (L & 0xFF) 519 { 520 blitter->blitV(left, top, 1, SkAlphaMul(alpha, 256 - (L & 0xFF))); 521 left += 1; 522 } 523 524 int rite = R >> 8; 525 int width = rite - left; 526 if (width > 0) 527 call_hline_blitter(blitter, left, top, width, alpha); 528 529 if (R & 0xFF) 530 blitter->blitV(rite, top, 1, SkAlphaMul(alpha, R & 0xFF)); 531 } 532 533 static void antifillrect(const SkXRect& xr, SkBlitter* blitter) 534 { 535 FDot8 L = SkFixedToFDot8(xr.fLeft); 536 FDot8 T = SkFixedToFDot8(xr.fTop); 537 FDot8 R = SkFixedToFDot8(xr.fRight); 538 FDot8 B = SkFixedToFDot8(xr.fBottom); 539 540 // check for empty now that we're in our reduced precision space 541 if (L >= R || T >= B) 542 return; 543 544 int top = T >> 8; 545 if (top == ((B - 1) >> 8)) // just one scanline high 546 { 547 do_scanline(L, top, R, B - T - 1, blitter); 548 return; 549 } 550 551 if (T & 0xFF) 552 { 553 do_scanline(L, top, R, 256 - (T & 0xFF), blitter); 554 top += 1; 555 } 556 557 int bot = B >> 8; 558 int height = bot - top; 559 if (height > 0) 560 { 561 int left = L >> 8; 562 if (L & 0xFF) 563 { 564 blitter->blitV(left, top, height, 256 - (L & 0xFF)); 565 left += 1; 566 } 567 int rite = R >> 8; 568 int width = rite - left; 569 if (width > 0) 570 blitter->blitRect(left, top, width, height); 571 if (R & 0xFF) 572 blitter->blitV(rite, top, height, R & 0xFF); 573 } 574 575 if (B & 0xFF) 576 do_scanline(L, bot, R, B & 0xFF, blitter); 577 } 578 579 /////////////////////////////////////////////////////////////////////////////// 580 581 void SkScan::AntiFillXRect(const SkXRect& xr, const SkRegion* clip, 582 SkBlitter* blitter) { 583 if (clip) { 584 SkIRect outerBounds; 585 XRect_roundOut(xr, &outerBounds); 586 587 if (clip->isRect()) { 588 const SkIRect& clipBounds = clip->getBounds(); 589 590 if (clipBounds.contains(outerBounds)) { 591 antifillrect(xr, blitter); 592 } else { 593 SkXRect tmpR; 594 // this keeps our original edges fractional 595 XRect_set(&tmpR, clipBounds); 596 if (tmpR.intersect(xr)) { 597 antifillrect(tmpR, blitter); 598 } 599 } 600 } else { 601 SkRegion::Cliperator clipper(*clip, outerBounds); 602 const SkIRect& rr = clipper.rect(); 603 604 while (!clipper.done()) { 605 SkXRect tmpR; 606 607 // this keeps our original edges fractional 608 XRect_set(&tmpR, rr); 609 if (tmpR.intersect(xr)) { 610 antifillrect(tmpR, blitter); 611 } 612 clipper.next(); 613 } 614 } 615 } else { 616 antifillrect(xr, blitter); 617 } 618 } 619 620 #ifdef SK_SCALAR_IS_FLOAT 621 622 /* This guy takes a float-rect, but with the key improvement that it has 623 already been clipped, so we know that it is safe to convert it into a 624 XRect (fixedpoint), as it won't overflow. 625 */ 626 static void antifillrect(const SkRect& r, SkBlitter* blitter) { 627 SkXRect xr; 628 629 XRect_set(&xr, r); 630 antifillrect(xr, blitter); 631 } 632 633 /* We repeat the clipping logic of AntiFillXRect because the float rect might 634 overflow if we blindly converted it to an XRect. This sucks that we have to 635 repeat the clipping logic, but I don't see how to share the code/logic. 636 637 We clip r (as needed) into one or more (smaller) float rects, and then pass 638 those to our version of antifillrect, which converts it into an XRect and 639 then calls the blit. 640 */ 641 void SkScan::AntiFillRect(const SkRect& origR, const SkRegion* clip, 642 SkBlitter* blitter) { 643 if (clip) { 644 SkRect newR; 645 newR.set(clip->getBounds()); 646 if (!newR.intersect(origR)) { 647 return; 648 } 649 650 SkIRect outerBounds; 651 newR.roundOut(&outerBounds); 652 653 if (clip->isRect()) { 654 antifillrect(newR, blitter); 655 } else { 656 SkRegion::Cliperator clipper(*clip, outerBounds); 657 while (!clipper.done()) { 658 newR.set(clipper.rect()); 659 if (newR.intersect(origR)) { 660 antifillrect(newR, blitter); 661 } 662 clipper.next(); 663 } 664 } 665 } else { 666 antifillrect(origR, blitter); 667 } 668 } 669 670 #endif 671 672 673