1 /* 2 * Copyright 2016 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkAnalyticEdge.h" 9 #include "SkAntiRun.h" 10 #include "SkAutoMalloc.h" 11 #include "SkBlitter.h" 12 #include "SkEdge.h" 13 #include "SkEdgeBuilder.h" 14 #include "SkGeometry.h" 15 #include "SkPath.h" 16 #include "SkQuadClipper.h" 17 #include "SkRasterClip.h" 18 #include "SkRegion.h" 19 #include "SkScan.h" 20 #include "SkScanPriv.h" 21 #include "SkTSort.h" 22 #include "SkTemplates.h" 23 #include "SkUtils.h" 24 25 /////////////////////////////////////////////////////////////////////////////// 26 27 /* 28 29 The following is a high-level overview of our analytic anti-aliasing 30 algorithm. We consider a path as a collection of line segments, as 31 quadratic/cubic curves are converted to small line segments. Without loss of 32 generality, let's assume that the draw region is [0, W] x [0, H]. 33 34 Our algorithm is based on horizontal scan lines (y = c_i) as the previous 35 sampling-based algorithm did. However, our algorithm uses non-equal-spaced 36 scan lines, while the previous method always uses equal-spaced scan lines, 37 such as (y = 1/2 + 0, 1/2 + 1, 1/2 + 2, ...) in the previous non-AA algorithm, 38 and (y = 1/8 + 1/4, 1/8 + 2/4, 1/8 + 3/4, ...) in the previous 39 16-supersampling AA algorithm. 40 41 Our algorithm contains scan lines y = c_i for c_i that is either: 42 43 1. an integer between [0, H] 44 45 2. the y value of a line segment endpoint 46 47 3. the y value of an intersection of two line segments 48 49 For two consecutive scan lines y = c_i, y = c_{i+1}, we analytically computes 50 the coverage of this horizontal strip of our path on each pixel. This can be 51 done very efficiently because the strip of our path now only consists of 52 trapezoids whose top and bottom edges are y = c_i, y = c_{i+1} (this includes 53 rectangles and triangles as special cases). 54 55 We now describe how the coverage of single pixel is computed against such a 56 trapezoid. That coverage is essentially the intersection area of a rectangle 57 (e.g., [0, 1] x [c_i, c_{i+1}]) and our trapezoid. However, that intersection 58 could be complicated, as shown in the example region A below: 59 60 +-----------\----+ 61 | \ C| 62 | \ | 63 \ \ | 64 |\ A \| 65 | \ \ 66 | \ | 67 | B \ | 68 +----\-----------+ 69 70 However, we don't have to compute the area of A directly. Instead, we can 71 compute the excluded area, which are B and C, quite easily, because they're 72 just triangles. In fact, we can prove that an excluded region (take B as an 73 example) is either itself a simple trapezoid (including rectangles, triangles, 74 and empty regions), or its opposite (the opposite of B is A + C) is a simple 75 trapezoid. In any case, we can compute its area efficiently. 76 77 In summary, our algorithm has a higher quality because it generates ground- 78 truth coverages analytically. It is also faster because it has much fewer 79 unnessasary horizontal scan lines. For example, given a triangle path, the 80 number of scan lines in our algorithm is only about 3 + H while the 81 16-supersampling algorithm has about 4H scan lines. 82 83 */ 84 85 /////////////////////////////////////////////////////////////////////////////// 86 87 static inline void addAlpha(SkAlpha* alpha, SkAlpha delta) { 88 SkASSERT(*alpha + (int)delta <= 256); 89 *alpha = SkAlphaRuns::CatchOverflow(*alpha + (int)delta); 90 } 91 92 static inline void safelyAddAlpha(SkAlpha* alpha, SkAlpha delta) { 93 *alpha = SkTMin(0xFF, *alpha + (int)delta); 94 } 95 96 class AdditiveBlitter : public SkBlitter { 97 public: 98 ~AdditiveBlitter() override {} 99 100 virtual SkBlitter* getRealBlitter(bool forceRealBlitter = false) = 0; 101 102 virtual void blitAntiH(int x, int y, const SkAlpha antialias[], int len) = 0; 103 virtual void blitAntiH(int x, int y, const SkAlpha alpha) = 0; 104 virtual void blitAntiH(int x, int y, int width, const SkAlpha alpha) = 0; 105 106 void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override { 107 SkDEBUGFAIL("Please call real blitter's blitAntiH instead."); 108 } 109 110 void blitV(int x, int y, int height, SkAlpha alpha) override { 111 SkDEBUGFAIL("Please call real blitter's blitV instead."); 112 } 113 114 void blitH(int x, int y, int width) override { 115 SkDEBUGFAIL("Please call real blitter's blitH instead."); 116 } 117 118 void blitRect(int x, int y, int width, int height) override { 119 SkDEBUGFAIL("Please call real blitter's blitRect instead."); 120 } 121 122 void blitAntiRect(int x, int y, int width, int height, 123 SkAlpha leftAlpha, SkAlpha rightAlpha) override { 124 SkDEBUGFAIL("Please call real blitter's blitAntiRect instead."); 125 } 126 127 virtual int getWidth() = 0; 128 129 // Flush the additive alpha cache if floor(y) and floor(nextY) is different 130 // (i.e., we'll start working on a new pixel row). 131 virtual void flush_if_y_changed(SkFixed y, SkFixed nextY) = 0; 132 }; 133 134 // We need this mask blitter because it significantly accelerates small path filling. 135 class MaskAdditiveBlitter : public AdditiveBlitter { 136 public: 137 MaskAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, 138 bool isInverse); 139 ~MaskAdditiveBlitter() override { 140 fRealBlitter->blitMask(fMask, fClipRect); 141 } 142 143 // Most of the time, we still consider this mask blitter as the real blitter 144 // so we can accelerate blitRect and others. But sometimes we want to return 145 // the absolute real blitter (e.g., when we fall back to the old code path). 146 SkBlitter* getRealBlitter(bool forceRealBlitter) override { 147 return forceRealBlitter ? fRealBlitter : this; 148 } 149 150 // Virtual function is slow. So don't use this. Directly add alpha to the mask instead. 151 void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override; 152 153 // Allowing following methods are used to blit rectangles during aaa_walk_convex_edges 154 // Since there aren't many rectangles, we can still bear the slow speed of virtual functions. 155 void blitAntiH(int x, int y, const SkAlpha alpha) override; 156 void blitAntiH(int x, int y, int width, const SkAlpha alpha) override; 157 void blitV(int x, int y, int height, SkAlpha alpha) override; 158 void blitRect(int x, int y, int width, int height) override; 159 void blitAntiRect(int x, int y, int width, int height, 160 SkAlpha leftAlpha, SkAlpha rightAlpha) override; 161 162 // The flush is only needed for RLE (RunBasedAdditiveBlitter) 163 void flush_if_y_changed(SkFixed y, SkFixed nextY) override {} 164 165 int getWidth() override { return fClipRect.width(); } 166 167 static bool canHandleRect(const SkIRect& bounds) { 168 int width = bounds.width(); 169 if (width > MaskAdditiveBlitter::kMAX_WIDTH) { 170 return false; 171 } 172 int64_t rb = SkAlign4(width); 173 // use 64bits to detect overflow 174 int64_t storage = rb * bounds.height(); 175 176 return (width <= MaskAdditiveBlitter::kMAX_WIDTH) && 177 (storage <= MaskAdditiveBlitter::kMAX_STORAGE); 178 } 179 180 // Return a pointer where pointer[x] corresonds to the alpha of (x, y) 181 inline uint8_t* getRow(int y) { 182 if (y != fY) { 183 fY = y; 184 fRow = fMask.fImage + (y - fMask.fBounds.fTop) * fMask.fRowBytes - fMask.fBounds.fLeft; 185 } 186 return fRow; 187 } 188 189 private: 190 // so we don't try to do very wide things, where the RLE blitter would be faster 191 static const int kMAX_WIDTH = 32; 192 static const int kMAX_STORAGE = 1024; 193 194 SkBlitter* fRealBlitter; 195 SkMask fMask; 196 SkIRect fClipRect; 197 // we add 2 because we can write 1 extra byte at either end due to precision error 198 uint32_t fStorage[(kMAX_STORAGE >> 2) + 2]; 199 200 uint8_t* fRow; 201 int fY; 202 }; 203 204 MaskAdditiveBlitter::MaskAdditiveBlitter( 205 SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, bool isInverse) { 206 SkASSERT(canHandleRect(ir)); 207 SkASSERT(!isInverse); 208 209 fRealBlitter = realBlitter; 210 211 fMask.fImage = (uint8_t*)fStorage + 1; // There's 1 extra byte at either end of fStorage 212 fMask.fBounds = ir; 213 fMask.fRowBytes = ir.width(); 214 fMask.fFormat = SkMask::kA8_Format; 215 216 fY = ir.fTop - 1; 217 fRow = nullptr; 218 219 fClipRect = ir; 220 if (!fClipRect.intersect(clip.getBounds())) { 221 SkASSERT(0); 222 fClipRect.setEmpty(); 223 } 224 225 memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 2); 226 } 227 228 void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { 229 SkFAIL("Don't use this; directly add alphas to the mask."); 230 } 231 232 void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { 233 SkASSERT(x >= fMask.fBounds.fLeft -1); 234 addAlpha(&this->getRow(y)[x], alpha); 235 } 236 237 void MaskAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { 238 SkASSERT(x >= fMask.fBounds.fLeft -1); 239 uint8_t* row = this->getRow(y); 240 for (int i = 0; i < width; ++i) { 241 addAlpha(&row[x + i], alpha); 242 } 243 } 244 245 void MaskAdditiveBlitter::blitV(int x, int y, int height, SkAlpha alpha) { 246 if (alpha == 0) { 247 return; 248 } 249 SkASSERT(x >= fMask.fBounds.fLeft -1); 250 // This must be called as if this is a real blitter. 251 // So we directly set alpha rather than adding it. 252 uint8_t* row = this->getRow(y); 253 for (int i = 0; i < height; ++i) { 254 row[x] = alpha; 255 row += fMask.fRowBytes; 256 } 257 } 258 259 void MaskAdditiveBlitter::blitRect(int x, int y, int width, int height) { 260 SkASSERT(x >= fMask.fBounds.fLeft -1); 261 // This must be called as if this is a real blitter. 262 // So we directly set alpha rather than adding it. 263 uint8_t* row = this->getRow(y); 264 for (int i = 0; i < height; ++i) { 265 memset(row + x, 0xFF, width); 266 row += fMask.fRowBytes; 267 } 268 } 269 270 void MaskAdditiveBlitter::blitAntiRect(int x, int y, int width, int height, 271 SkAlpha leftAlpha, SkAlpha rightAlpha) { 272 blitV(x, y, height, leftAlpha); 273 blitV(x + 1 + width, y, height, rightAlpha); 274 blitRect(x + 1, y, width, height); 275 } 276 277 class RunBasedAdditiveBlitter : public AdditiveBlitter { 278 public: 279 RunBasedAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, 280 bool isInverse); 281 ~RunBasedAdditiveBlitter() override; 282 283 SkBlitter* getRealBlitter(bool forceRealBlitter) override; 284 285 void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override; 286 void blitAntiH(int x, int y, const SkAlpha alpha) override; 287 void blitAntiH(int x, int y, int width, const SkAlpha alpha) override; 288 289 int getWidth() override; 290 291 void flush_if_y_changed(SkFixed y, SkFixed nextY) override { 292 if (SkFixedFloorToInt(y) != SkFixedFloorToInt(nextY)) { 293 this->flush(); 294 } 295 } 296 297 protected: 298 SkBlitter* fRealBlitter; 299 300 /// Current y coordinate 301 int fCurrY; 302 /// Widest row of region to be blitted 303 int fWidth; 304 /// Leftmost x coordinate in any row 305 int fLeft; 306 /// Initial y coordinate (top of bounds). 307 int fTop; 308 309 // The next three variables are used to track a circular buffer that 310 // contains the values used in SkAlphaRuns. These variables should only 311 // ever be updated in advanceRuns(), and fRuns should always point to 312 // a valid SkAlphaRuns... 313 int fRunsToBuffer; 314 void* fRunsBuffer; 315 int fCurrentRun; 316 SkAlphaRuns fRuns; 317 318 int fOffsetX; 319 320 inline bool check(int x, int width) const { 321 #ifdef SK_DEBUG 322 if (x < 0 || x + width > fWidth) { 323 // SkDebugf("Ignore x = %d, width = %d\n", x, width); 324 } 325 #endif 326 return (x >= 0 && x + width <= fWidth); 327 } 328 329 // extra one to store the zero at the end 330 inline int getRunsSz() const { return (fWidth + 1 + (fWidth + 2)/2) * sizeof(int16_t); } 331 332 // This function updates the fRuns variable to point to the next buffer space 333 // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun 334 // and resets fRuns to point to an empty scanline. 335 inline void advanceRuns() { 336 const size_t kRunsSz = this->getRunsSz(); 337 fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer; 338 fRuns.fRuns = reinterpret_cast<int16_t*>( 339 reinterpret_cast<uint8_t*>(fRunsBuffer) + fCurrentRun * kRunsSz); 340 fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1); 341 fRuns.reset(fWidth); 342 } 343 344 // Blitting 0xFF and 0 is much faster so we snap alphas close to them 345 inline SkAlpha snapAlpha(SkAlpha alpha) { 346 return alpha > 247 ? 0xFF : alpha < 8 ? 0 : alpha; 347 } 348 349 inline void flush() { 350 if (fCurrY >= fTop) { 351 SkASSERT(fCurrentRun < fRunsToBuffer); 352 for (int x = 0; fRuns.fRuns[x]; x += fRuns.fRuns[x]) { 353 // It seems that blitting 255 or 0 is much faster than blitting 254 or 1 354 fRuns.fAlpha[x] = snapAlpha(fRuns.fAlpha[x]); 355 } 356 if (!fRuns.empty()) { 357 // SkDEBUGCODE(fRuns.dump();) 358 fRealBlitter->blitAntiH(fLeft, fCurrY, fRuns.fAlpha, fRuns.fRuns); 359 this->advanceRuns(); 360 fOffsetX = 0; 361 } 362 fCurrY = fTop - 1; 363 } 364 } 365 366 inline void checkY(int y) { 367 if (y != fCurrY) { 368 this->flush(); 369 fCurrY = y; 370 } 371 } 372 }; 373 374 RunBasedAdditiveBlitter::RunBasedAdditiveBlitter( 375 SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, bool isInverse) { 376 fRealBlitter = realBlitter; 377 378 SkIRect sectBounds; 379 if (isInverse) { 380 // We use the clip bounds instead of the ir, since we may be asked to 381 //draw outside of the rect when we're a inverse filltype 382 sectBounds = clip.getBounds(); 383 } else { 384 if (!sectBounds.intersect(ir, clip.getBounds())) { 385 sectBounds.setEmpty(); 386 } 387 } 388 389 const int left = sectBounds.left(); 390 const int right = sectBounds.right(); 391 392 fLeft = left; 393 fWidth = right - left; 394 fTop = sectBounds.top(); 395 fCurrY = fTop - 1; 396 397 fRunsToBuffer = realBlitter->requestRowsPreserved(); 398 fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz()); 399 fCurrentRun = -1; 400 401 this->advanceRuns(); 402 403 fOffsetX = 0; 404 } 405 406 RunBasedAdditiveBlitter::~RunBasedAdditiveBlitter() { 407 this->flush(); 408 } 409 410 SkBlitter* RunBasedAdditiveBlitter::getRealBlitter(bool forceRealBlitter) { 411 return fRealBlitter; 412 } 413 414 void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { 415 checkY(y); 416 x -= fLeft; 417 418 if (x < 0) { 419 len += x; 420 antialias -= x; 421 x = 0; 422 } 423 len = SkTMin(len, fWidth - x); 424 SkASSERT(check(x, len)); 425 426 if (x < fOffsetX) { 427 fOffsetX = 0; 428 } 429 430 fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run 431 for (int i = 0; i < len; i += fRuns.fRuns[x + i]) { 432 for (int j = 1; j < fRuns.fRuns[x + i]; j++) { 433 fRuns.fRuns[x + i + j] = 1; 434 fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i]; 435 } 436 fRuns.fRuns[x + i] = 1; 437 } 438 for (int i = 0; i < len; ++i) { 439 addAlpha(&fRuns.fAlpha[x + i], antialias[i]); 440 } 441 } 442 void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { 443 checkY(y); 444 x -= fLeft; 445 446 if (x < fOffsetX) { 447 fOffsetX = 0; 448 } 449 450 if (this->check(x, 1)) { 451 fOffsetX = fRuns.add(x, 0, 1, 0, alpha, fOffsetX); 452 } 453 } 454 455 void RunBasedAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { 456 checkY(y); 457 x -= fLeft; 458 459 if (x < fOffsetX) { 460 fOffsetX = 0; 461 } 462 463 if (this->check(x, width)) { 464 fOffsetX = fRuns.add(x, 0, width, 0, alpha, fOffsetX); 465 } 466 } 467 468 int RunBasedAdditiveBlitter::getWidth() { return fWidth; } 469 470 // This exists specifically for concave path filling. 471 // In those cases, we can easily accumulate alpha greater than 0xFF. 472 class SafeRLEAdditiveBlitter : public RunBasedAdditiveBlitter { 473 public: 474 SafeRLEAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, 475 bool isInverse) : RunBasedAdditiveBlitter(realBlitter, ir, clip, isInverse) {} 476 477 void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override; 478 void blitAntiH(int x, int y, const SkAlpha alpha) override; 479 void blitAntiH(int x, int y, int width, const SkAlpha alpha) override; 480 }; 481 482 void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) { 483 checkY(y); 484 x -= fLeft; 485 486 if (x < 0) { 487 len += x; 488 antialias -= x; 489 x = 0; 490 } 491 len = SkTMin(len, fWidth - x); 492 SkASSERT(check(x, len)); 493 494 if (x < fOffsetX) { 495 fOffsetX = 0; 496 } 497 498 fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run 499 for (int i = 0; i < len; i += fRuns.fRuns[x + i]) { 500 for (int j = 1; j < fRuns.fRuns[x + i]; j++) { 501 fRuns.fRuns[x + i + j] = 1; 502 fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i]; 503 } 504 fRuns.fRuns[x + i] = 1; 505 } 506 for (int i = 0; i < len; ++i) { 507 safelyAddAlpha(&fRuns.fAlpha[x + i], antialias[i]); 508 } 509 } 510 511 void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) { 512 checkY(y); 513 x -= fLeft; 514 515 if (x < fOffsetX) { 516 fOffsetX = 0; 517 } 518 519 if (check(x, 1)) { 520 // Break the run 521 fOffsetX = fRuns.add(x, 0, 1, 0, 0, fOffsetX); 522 safelyAddAlpha(&fRuns.fAlpha[x], alpha); 523 } 524 } 525 526 void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) { 527 checkY(y); 528 x -= fLeft; 529 530 if (x < fOffsetX) { 531 fOffsetX = 0; 532 } 533 534 if (check(x, width)) { 535 // Break the run 536 fOffsetX = fRuns.add(x, 0, width, 0, 0, fOffsetX); 537 for(int i = x; i < x + width; i += fRuns.fRuns[i]) { 538 safelyAddAlpha(&fRuns.fAlpha[i], alpha); 539 } 540 } 541 } 542 543 /////////////////////////////////////////////////////////////////////////////// 544 545 // Return the alpha of a trapezoid whose height is 1 546 static inline SkAlpha trapezoidToAlpha(SkFixed l1, SkFixed l2) { 547 SkASSERT(l1 >= 0 && l2 >= 0); 548 return (l1 + l2) >> 9; 549 } 550 551 // The alpha of right-triangle (a, a*b), in 16 bits 552 static inline SkFixed partialTriangleToAlpha16(SkFixed a, SkFixed b) { 553 SkASSERT(a <= SK_Fixed1); 554 // SkFixedMul(SkFixedMul(a, a), b) >> 1 555 // return ((((a >> 8) * (a >> 8)) >> 8) * (b >> 8)) >> 1; 556 return (a >> 11) * (a >> 11) * (b >> 11); 557 } 558 559 // The alpha of right-triangle (a, a*b) 560 static inline SkAlpha partialTriangleToAlpha(SkFixed a, SkFixed b) { 561 return partialTriangleToAlpha16(a, b) >> 8; 562 } 563 564 static inline SkAlpha getPartialAlpha(SkAlpha alpha, SkFixed partialHeight) { 565 return SkToU8(SkFixedRoundToInt(alpha * partialHeight)); 566 } 567 568 static inline SkAlpha getPartialAlpha(SkAlpha alpha, SkAlpha fullAlpha) { 569 return ((uint16_t)alpha * fullAlpha) >> 8; 570 } 571 572 // For SkFixed that's close to SK_Fixed1, we can't convert it to alpha by just shifting right. 573 // For example, when f = SK_Fixed1, right shifting 8 will get 256, but we need 255. 574 // This is rarely the problem so we'll only use this for blitting rectangles. 575 static inline SkAlpha f2a(SkFixed f) { 576 SkASSERT(f <= SK_Fixed1); 577 return getPartialAlpha(0xFF, f); 578 } 579 580 // Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1), 581 // approximate (very coarsely) the x coordinate of the intersection. 582 static inline SkFixed approximateIntersection(SkFixed l1, SkFixed r1, SkFixed l2, SkFixed r2) { 583 if (l1 > r1) { SkTSwap(l1, r1); } 584 if (l2 > r2) { SkTSwap(l2, r2); } 585 return (SkTMax(l1, l2) + SkTMin(r1, r2)) >> 1; 586 } 587 588 // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0] 589 static inline void computeAlphaAboveLine(SkAlpha* alphas, SkFixed l, SkFixed r, 590 SkFixed dY, SkAlpha fullAlpha) { 591 SkASSERT(l <= r); 592 SkASSERT(l >> 16 == 0); 593 int R = SkFixedCeilToInt(r); 594 if (R == 0) { 595 return; 596 } else if (R == 1) { 597 alphas[0] = getPartialAlpha(((R << 17) - l - r) >> 9, fullAlpha); 598 } else { 599 SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle 600 SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle 601 SkFixed firstH = SkFixedMul(first, dY); // vertical edge of the left-most triangle 602 alphas[0] = SkFixedMul(first, firstH) >> 9; // triangle alpha 603 SkFixed alpha16 = firstH + (dY >> 1); // rectangle plus triangle 604 for (int i = 1; i < R - 1; ++i) { 605 alphas[i] = alpha16 >> 8; 606 alpha16 += dY; 607 } 608 alphas[R - 1] = fullAlpha - partialTriangleToAlpha(last, dY); 609 } 610 } 611 612 // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0] 613 static inline void computeAlphaBelowLine( 614 SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkAlpha fullAlpha) { 615 SkASSERT(l <= r); 616 SkASSERT(l >> 16 == 0); 617 int R = SkFixedCeilToInt(r); 618 if (R == 0) { 619 return; 620 } else if (R == 1) { 621 alphas[0] = getPartialAlpha(trapezoidToAlpha(l, r), fullAlpha); 622 } else { 623 SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle 624 SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle 625 SkFixed lastH = SkFixedMul(last, dY); // vertical edge of the right-most triangle 626 alphas[R-1] = SkFixedMul(last, lastH) >> 9; // triangle alpha 627 SkFixed alpha16 = lastH + (dY >> 1); // rectangle plus triangle 628 for (int i = R - 2; i > 0; i--) { 629 alphas[i] = alpha16 >> 8; 630 alpha16 += dY; 631 } 632 alphas[0] = fullAlpha - partialTriangleToAlpha(first, dY); 633 } 634 } 635 636 // Note that if fullAlpha != 0xFF, we'll multiply alpha by fullAlpha 637 static SK_ALWAYS_INLINE void blit_single_alpha(AdditiveBlitter* blitter, int y, int x, 638 SkAlpha alpha, SkAlpha fullAlpha, SkAlpha* maskRow, 639 bool isUsingMask, bool noRealBlitter, bool needSafeCheck) { 640 if (isUsingMask) { 641 if (fullAlpha == 0xFF && !noRealBlitter) { // noRealBlitter is needed for concave paths 642 maskRow[x] = alpha; 643 } else if (needSafeCheck) { 644 safelyAddAlpha(&maskRow[x], getPartialAlpha(alpha, fullAlpha)); 645 } else { 646 addAlpha(&maskRow[x], getPartialAlpha(alpha, fullAlpha)); 647 } 648 } else { 649 if (fullAlpha == 0xFF && !noRealBlitter) { 650 blitter->getRealBlitter()->blitV(x, y, 1, alpha); 651 } else { 652 blitter->blitAntiH(x, y, getPartialAlpha(alpha, fullAlpha)); 653 } 654 } 655 } 656 657 static SK_ALWAYS_INLINE void blit_two_alphas(AdditiveBlitter* blitter, int y, int x, 658 SkAlpha a1, SkAlpha a2, SkAlpha fullAlpha, SkAlpha* maskRow, 659 bool isUsingMask, bool noRealBlitter, bool needSafeCheck) { 660 if (isUsingMask) { 661 if (needSafeCheck) { 662 safelyAddAlpha(&maskRow[x], a1); 663 safelyAddAlpha(&maskRow[x + 1], a2); 664 } else { 665 addAlpha(&maskRow[x], a1); 666 addAlpha(&maskRow[x + 1], a2); 667 } 668 } else { 669 if (fullAlpha == 0xFF && !noRealBlitter) { 670 blitter->getRealBlitter()->blitAntiH2(x, y, a1, a2); 671 } else { 672 blitter->blitAntiH(x, y, a1); 673 blitter->blitAntiH(x + 1, y, a2); 674 } 675 } 676 } 677 678 // It's important that this is inline. Otherwise it'll be much slower. 679 static SK_ALWAYS_INLINE void blit_full_alpha(AdditiveBlitter* blitter, int y, int x, int len, 680 SkAlpha fullAlpha, SkAlpha* maskRow, bool isUsingMask, 681 bool noRealBlitter, bool needSafeCheck) { 682 if (isUsingMask) { 683 for (int i = 0; i < len; ++i) { 684 if (needSafeCheck) { 685 safelyAddAlpha(&maskRow[x + i], fullAlpha); 686 } else { 687 addAlpha(&maskRow[x + i], fullAlpha); 688 } 689 } 690 } else { 691 if (fullAlpha == 0xFF && !noRealBlitter) { 692 blitter->getRealBlitter()->blitH(x, y, len); 693 } else { 694 blitter->blitAntiH(x, y, len, fullAlpha); 695 } 696 } 697 } 698 699 static void blit_aaa_trapezoid_row(AdditiveBlitter* blitter, int y, 700 SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr, 701 SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha, SkAlpha* maskRow, 702 bool isUsingMask, bool noRealBlitter, bool needSafeCheck) { 703 int L = SkFixedFloorToInt(ul), R = SkFixedCeilToInt(lr); 704 int len = R - L; 705 706 if (len == 1) { 707 SkAlpha alpha = trapezoidToAlpha(ur - ul, lr - ll); 708 blit_single_alpha(blitter, y, L, alpha, fullAlpha, maskRow, isUsingMask, noRealBlitter, 709 needSafeCheck); 710 return; 711 } 712 713 // SkDebugf("y = %d, len = %d, ul = %f, ur = %f, ll = %f, lr = %f\n", y, len, 714 // SkFixedToFloat(ul), SkFixedToFloat(ur), SkFixedToFloat(ll), SkFixedToFloat(lr)); 715 716 const int kQuickLen = 31; 717 // This is faster than SkAutoSMalloc<1024> 718 char quickMemory[(sizeof(SkAlpha) * 2 + sizeof(int16_t)) * (kQuickLen + 1)]; 719 SkAlpha* alphas; 720 721 if (len <= kQuickLen) { 722 alphas = (SkAlpha*)quickMemory; 723 } else { 724 alphas = new SkAlpha[(len + 1) * (sizeof(SkAlpha) * 2 + sizeof(int16_t))]; 725 } 726 727 SkAlpha* tempAlphas = alphas + len + 1; 728 int16_t* runs = (int16_t*)(alphas + (len + 1) * 2); 729 730 for (int i = 0; i < len; ++i) { 731 runs[i] = 1; 732 alphas[i] = fullAlpha; 733 } 734 runs[len] = 0; 735 736 int uL = SkFixedFloorToInt(ul); 737 int lL = SkFixedCeilToInt(ll); 738 if (uL + 2 == lL) { // We only need to compute two triangles, accelerate this special case 739 SkFixed first = SkIntToFixed(uL) + SK_Fixed1 - ul; 740 SkFixed second = ll - ul - first; 741 SkAlpha a1 = fullAlpha - partialTriangleToAlpha(first, lDY); 742 SkAlpha a2 = partialTriangleToAlpha(second, lDY); 743 alphas[0] = alphas[0] > a1 ? alphas[0] - a1 : 0; 744 alphas[1] = alphas[1] > a2 ? alphas[1] - a2 : 0; 745 } else { 746 computeAlphaBelowLine(tempAlphas + uL - L, ul - SkIntToFixed(uL), ll - SkIntToFixed(uL), 747 lDY, fullAlpha); 748 for (int i = uL; i < lL; ++i) { 749 if (alphas[i - L] > tempAlphas[i - L]) { 750 alphas[i - L] -= tempAlphas[i - L]; 751 } else { 752 alphas[i - L] = 0; 753 } 754 } 755 } 756 757 int uR = SkFixedFloorToInt(ur); 758 int lR = SkFixedCeilToInt(lr); 759 if (uR + 2 == lR) { // We only need to compute two triangles, accelerate this special case 760 SkFixed first = SkIntToFixed(uR) + SK_Fixed1 - ur; 761 SkFixed second = lr - ur - first; 762 SkAlpha a1 = partialTriangleToAlpha(first, rDY); 763 SkAlpha a2 = fullAlpha - partialTriangleToAlpha(second, rDY); 764 alphas[len-2] = alphas[len-2] > a1 ? alphas[len-2] - a1 : 0; 765 alphas[len-1] = alphas[len-1] > a2 ? alphas[len-1] - a2 : 0; 766 } else { 767 computeAlphaAboveLine(tempAlphas + uR - L, ur - SkIntToFixed(uR), lr - SkIntToFixed(uR), 768 rDY, fullAlpha); 769 for (int i = uR; i < lR; ++i) { 770 if (alphas[i - L] > tempAlphas[i - L]) { 771 alphas[i - L] -= tempAlphas[i - L]; 772 } else { 773 alphas[i - L] = 0; 774 } 775 } 776 } 777 778 if (isUsingMask) { 779 for (int i = 0; i < len; ++i) { 780 if (needSafeCheck) { 781 safelyAddAlpha(&maskRow[L + i], alphas[i]); 782 } else { 783 addAlpha(&maskRow[L + i], alphas[i]); 784 } 785 } 786 } else { 787 if (fullAlpha == 0xFF && !noRealBlitter) { 788 // Real blitter is faster than RunBasedAdditiveBlitter 789 blitter->getRealBlitter()->blitAntiH(L, y, alphas, runs); 790 } else { 791 blitter->blitAntiH(L, y, alphas, len); 792 } 793 } 794 795 if (len > kQuickLen) { 796 delete [] alphas; 797 } 798 } 799 800 static SK_ALWAYS_INLINE void blit_trapezoid_row(AdditiveBlitter* blitter, int y, 801 SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr, 802 SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha, 803 SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter = false, 804 bool needSafeCheck = false) { 805 SkASSERT(lDY >= 0 && rDY >= 0); // We should only send in the absolte value 806 807 if (ul > ur) { 808 #ifdef SK_DEBUG 809 // SkDebugf("ul = %f > ur = %f!\n", SkFixedToFloat(ul), SkFixedToFloat(ur)); 810 #endif 811 return; 812 } 813 814 // Edge crosses. Approximate it. This should only happend due to precision limit, 815 // so the approximation could be very coarse. 816 if (ll > lr) { 817 #ifdef SK_DEBUG 818 // SkDebugf("approximate intersection: %d %f %f\n", y, 819 // SkFixedToFloat(ll), SkFixedToFloat(lr)); 820 #endif 821 ll = lr = approximateIntersection(ul, ll, ur, lr); 822 } 823 824 if (ul == ur && ll == lr) { 825 return; // empty trapzoid 826 } 827 828 // We're going to use the left line ul-ll and the rite line ur-lr 829 // to exclude the area that's not covered by the path. 830 // Swapping (ul, ll) or (ur, lr) won't affect that exclusion 831 // so we'll do that for simplicity. 832 if (ul > ll) { SkTSwap(ul, ll); } 833 if (ur > lr) { SkTSwap(ur, lr); } 834 835 SkFixed joinLeft = SkFixedCeilToFixed(ll); 836 SkFixed joinRite = SkFixedFloorToFixed(ur); 837 if (joinLeft <= joinRite) { // There's a rect from joinLeft to joinRite that we can blit 838 if (ul < joinLeft) { 839 int len = SkFixedCeilToInt(joinLeft - ul); 840 if (len == 1) { 841 SkAlpha alpha = trapezoidToAlpha(joinLeft - ul, joinLeft - ll); 842 blit_single_alpha(blitter, y, ul >> 16, alpha, fullAlpha, maskRow, isUsingMask, 843 noRealBlitter, needSafeCheck); 844 } else if (len == 2) { 845 SkFixed first = joinLeft - SK_Fixed1 - ul; 846 SkFixed second = ll - ul - first; 847 SkAlpha a1 = partialTriangleToAlpha(first, lDY); 848 SkAlpha a2 = fullAlpha - partialTriangleToAlpha(second, lDY); 849 blit_two_alphas(blitter, y, ul >> 16, a1, a2, fullAlpha, maskRow, isUsingMask, 850 noRealBlitter, needSafeCheck); 851 } else { 852 blit_aaa_trapezoid_row(blitter, y, ul, joinLeft, ll, joinLeft, lDY, SK_MaxS32, 853 fullAlpha, maskRow, isUsingMask, noRealBlitter, 854 needSafeCheck); 855 } 856 } 857 // SkAAClip requires that we blit from left to right. 858 // Hence we must blit [ul, joinLeft] before blitting [joinLeft, joinRite] 859 if (joinLeft < joinRite) { 860 blit_full_alpha(blitter, y, SkFixedFloorToInt(joinLeft), 861 SkFixedFloorToInt(joinRite - joinLeft), 862 fullAlpha, maskRow, isUsingMask, noRealBlitter, needSafeCheck); 863 } 864 if (lr > joinRite) { 865 int len = SkFixedCeilToInt(lr - joinRite); 866 if (len == 1) { 867 SkAlpha alpha = trapezoidToAlpha(ur - joinRite, lr - joinRite); 868 blit_single_alpha(blitter, y, joinRite >> 16, alpha, fullAlpha, maskRow, 869 isUsingMask, noRealBlitter, needSafeCheck); 870 } else if (len == 2) { 871 SkFixed first = joinRite + SK_Fixed1 - ur; 872 SkFixed second = lr - ur - first; 873 SkAlpha a1 = fullAlpha - partialTriangleToAlpha(first, rDY); 874 SkAlpha a2 = partialTriangleToAlpha(second, rDY); 875 blit_two_alphas(blitter, y, joinRite >> 16, a1, a2, fullAlpha, maskRow, 876 isUsingMask, noRealBlitter, needSafeCheck); 877 } else { 878 blit_aaa_trapezoid_row(blitter, y, joinRite, ur, joinRite, lr, SK_MaxS32, rDY, 879 fullAlpha, maskRow, isUsingMask, noRealBlitter, 880 needSafeCheck); 881 } 882 } 883 } else { 884 blit_aaa_trapezoid_row(blitter, y, ul, ur, ll, lr, lDY, rDY, fullAlpha, maskRow, 885 isUsingMask, noRealBlitter, needSafeCheck); 886 } 887 } 888 889 /////////////////////////////////////////////////////////////////////////////// 890 891 static bool operator<(const SkAnalyticEdge& a, const SkAnalyticEdge& b) { 892 int valuea = a.fUpperY; 893 int valueb = b.fUpperY; 894 895 if (valuea == valueb) { 896 valuea = a.fX; 897 valueb = b.fX; 898 } 899 900 if (valuea == valueb) { 901 valuea = a.fDX; 902 valueb = b.fDX; 903 } 904 905 return valuea < valueb; 906 } 907 908 static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) { 909 SkTQSort(list, list + count - 1); 910 911 // now make the edges linked in sorted order 912 for (int i = 1; i < count; ++i) { 913 list[i - 1]->fNext = list[i]; 914 list[i]->fPrev = list[i - 1]; 915 } 916 917 *last = list[count - 1]; 918 return list[0]; 919 } 920 921 #ifdef SK_DEBUG 922 static void validate_sort(const SkAnalyticEdge* edge) { 923 SkFixed y = SkIntToFixed(-32768); 924 925 while (edge->fUpperY != SK_MaxS32) { 926 edge->validate(); 927 SkASSERT(y <= edge->fUpperY); 928 929 y = edge->fUpperY; 930 edge = (SkAnalyticEdge*)edge->fNext; 931 } 932 } 933 #else 934 #define validate_sort(edge) 935 #endif 936 937 // return true if we're done with this edge 938 static bool update_edge(SkAnalyticEdge* edge, SkFixed last_y) { 939 if (last_y >= edge->fLowerY) { 940 if (edge->fCurveCount < 0) { 941 if (static_cast<SkAnalyticCubicEdge*>(edge)->updateCubic()) { 942 return false; 943 } 944 } else if (edge->fCurveCount > 0) { 945 if (static_cast<SkAnalyticQuadraticEdge*>(edge)->updateQuadratic()) { 946 return false; 947 } 948 } 949 return true; 950 } 951 SkASSERT(false); 952 return false; 953 } 954 955 // For an edge, we consider it smooth if the Dx doesn't change much, and Dy is large enough 956 // For curves that are updating, the Dx is not changing much if fQDx/fCDx and fQDy/fCDy are 957 // relatively large compared to fQDDx/QCDDx and fQDDy/fCDDy 958 static inline bool isSmoothEnough(SkAnalyticEdge* thisEdge, SkAnalyticEdge* nextEdge, int stop_y) { 959 if (thisEdge->fCurveCount < 0) { 960 const SkCubicEdge& cEdge = static_cast<SkAnalyticCubicEdge*>(thisEdge)->fCEdge; 961 int ddshift = cEdge.fCurveShift; 962 return SkAbs32(cEdge.fCDx) >> 1 >= SkAbs32(cEdge.fCDDx) >> ddshift && 963 SkAbs32(cEdge.fCDy) >> 1 >= SkAbs32(cEdge.fCDDy) >> ddshift && 964 // current Dy is (fCDy - (fCDDy >> ddshift)) >> dshift 965 (cEdge.fCDy - (cEdge.fCDDy >> ddshift)) >> cEdge.fCubicDShift >= SK_Fixed1; 966 } else if (thisEdge->fCurveCount > 0) { 967 const SkQuadraticEdge& qEdge = static_cast<SkAnalyticQuadraticEdge*>(thisEdge)->fQEdge; 968 return SkAbs32(qEdge.fQDx) >> 1 >= SkAbs32(qEdge.fQDDx) && 969 SkAbs32(qEdge.fQDy) >> 1 >= SkAbs32(qEdge.fQDDy) && 970 // current Dy is (fQDy - fQDDy) >> shift 971 (qEdge.fQDy - qEdge.fQDDy) >> qEdge.fCurveShift 972 >= SK_Fixed1; 973 } 974 return SkAbs32(nextEdge->fDX - thisEdge->fDX) <= SK_Fixed1 && // DDx should be small 975 nextEdge->fLowerY - nextEdge->fUpperY >= SK_Fixed1; // Dy should be large 976 } 977 978 // Check if the leftE and riteE are changing smoothly in terms of fDX. 979 // If yes, we can later skip the fractional y and directly jump to integer y. 980 static inline bool isSmoothEnough(SkAnalyticEdge* leftE, SkAnalyticEdge* riteE, 981 SkAnalyticEdge* currE, int stop_y) { 982 if (currE->fUpperY >= stop_y << 16) { 983 return false; // We're at the end so we won't skip anything 984 } 985 if (leftE->fLowerY + SK_Fixed1 < riteE->fLowerY) { 986 return isSmoothEnough(leftE, currE, stop_y); // Only leftE is changing 987 } else if (leftE->fLowerY > riteE->fLowerY + SK_Fixed1) { 988 return isSmoothEnough(riteE, currE, stop_y); // Only riteE is changing 989 } 990 991 // Now both edges are changing, find the second next edge 992 SkAnalyticEdge* nextCurrE = currE->fNext; 993 if (nextCurrE->fUpperY >= stop_y << 16) { // Check if we're at the end 994 return false; 995 } 996 if (*nextCurrE < *currE) { 997 SkTSwap(currE, nextCurrE); 998 } 999 return isSmoothEnough(leftE, currE, stop_y) && isSmoothEnough(riteE, nextCurrE, stop_y); 1000 } 1001 1002 static inline void aaa_walk_convex_edges(SkAnalyticEdge* prevHead, 1003 AdditiveBlitter* blitter, int start_y, int stop_y, SkFixed leftBound, SkFixed riteBound, 1004 bool isUsingMask) { 1005 validate_sort((SkAnalyticEdge*)prevHead->fNext); 1006 1007 SkAnalyticEdge* leftE = (SkAnalyticEdge*) prevHead->fNext; 1008 SkAnalyticEdge* riteE = (SkAnalyticEdge*) leftE->fNext; 1009 SkAnalyticEdge* currE = (SkAnalyticEdge*) riteE->fNext; 1010 1011 SkFixed y = SkTMax(leftE->fUpperY, riteE->fUpperY); 1012 1013 #ifdef SK_DEBUG 1014 int frac_y_cnt = 0; 1015 int total_y_cnt = 0; 1016 #endif 1017 1018 for (;;) { 1019 // We have to check fLowerY first because some edges might be alone (e.g., there's only 1020 // a left edge but no right edge in a given y scan line) due to precision limit. 1021 while (leftE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges 1022 if (update_edge(leftE, y)) { 1023 if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) { 1024 goto END_WALK; 1025 } 1026 leftE = currE; 1027 currE = (SkAnalyticEdge*)currE->fNext; 1028 } 1029 } 1030 while (riteE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges 1031 if (update_edge(riteE, y)) { 1032 if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) { 1033 goto END_WALK; 1034 } 1035 riteE = currE; 1036 currE = (SkAnalyticEdge*)currE->fNext; 1037 } 1038 } 1039 1040 SkASSERT(leftE); 1041 SkASSERT(riteE); 1042 1043 // check our bottom clip 1044 if (SkFixedFloorToInt(y) >= stop_y) { 1045 break; 1046 } 1047 1048 SkASSERT(SkFixedFloorToInt(leftE->fUpperY) <= stop_y); 1049 SkASSERT(SkFixedFloorToInt(riteE->fUpperY) <= stop_y); 1050 1051 leftE->goY(y); 1052 riteE->goY(y); 1053 1054 if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX && 1055 leftE->fDX > riteE->fDX)) { 1056 SkTSwap(leftE, riteE); 1057 } 1058 1059 SkFixed local_bot_fixed = SkMin32(leftE->fLowerY, riteE->fLowerY); 1060 if (isSmoothEnough(leftE, riteE, currE, stop_y)) { 1061 local_bot_fixed = SkFixedCeilToFixed(local_bot_fixed); 1062 } 1063 local_bot_fixed = SkMin32(local_bot_fixed, SkIntToFixed(stop_y)); 1064 1065 SkFixed left = SkTMax(leftBound, leftE->fX); 1066 SkFixed dLeft = leftE->fDX; 1067 SkFixed rite = SkTMin(riteBound, riteE->fX); 1068 SkFixed dRite = riteE->fDX; 1069 if (0 == (dLeft | dRite)) { 1070 int fullLeft = SkFixedCeilToInt(left); 1071 int fullRite = SkFixedFloorToInt(rite); 1072 SkFixed partialLeft = SkIntToFixed(fullLeft) - left; 1073 SkFixed partialRite = rite - SkIntToFixed(fullRite); 1074 int fullTop = SkFixedCeilToInt(y); 1075 int fullBot = SkFixedFloorToInt(local_bot_fixed); 1076 SkFixed partialTop = SkIntToFixed(fullTop) - y; 1077 SkFixed partialBot = local_bot_fixed - SkIntToFixed(fullBot); 1078 if (fullTop > fullBot) { // The rectangle is within one pixel height... 1079 partialTop -= (SK_Fixed1 - partialBot); 1080 partialBot = 0; 1081 } 1082 1083 if (fullRite >= fullLeft) { 1084 if (partialTop > 0) { // blit first partial row 1085 if (partialLeft > 0) { 1086 blitter->blitAntiH(fullLeft - 1, fullTop - 1, 1087 f2a(SkFixedMul(partialTop, partialLeft))); 1088 } 1089 blitter->blitAntiH(fullLeft, fullTop - 1, fullRite - fullLeft, 1090 f2a(partialTop)); 1091 if (partialRite > 0) { 1092 blitter->blitAntiH(fullRite, fullTop - 1, 1093 f2a(SkFixedMul(partialTop, partialRite))); 1094 } 1095 blitter->flush_if_y_changed(y, y + partialTop); 1096 } 1097 1098 // Blit all full-height rows from fullTop to fullBot 1099 if (fullBot > fullTop && 1100 // SkAAClip cannot handle the empty rect so check the non-emptiness here 1101 // (bug chromium:662800) 1102 (fullRite > fullLeft || f2a(partialLeft) > 0 || f2a(partialRite) > 0)) { 1103 blitter->getRealBlitter()->blitAntiRect(fullLeft - 1, fullTop, 1104 fullRite - fullLeft, fullBot - fullTop, 1105 f2a(partialLeft), f2a(partialRite)); 1106 } 1107 1108 if (partialBot > 0) { // blit last partial row 1109 if (partialLeft > 0) { 1110 blitter->blitAntiH(fullLeft - 1, fullBot, 1111 f2a(SkFixedMul(partialBot, partialLeft))); 1112 } 1113 blitter->blitAntiH(fullLeft, fullBot, fullRite - fullLeft, f2a(partialBot)); 1114 if (partialRite > 0) { 1115 blitter->blitAntiH(fullRite, fullBot, 1116 f2a(SkFixedMul(partialBot, partialRite))); 1117 } 1118 } 1119 } else { // left and rite are within the same pixel 1120 if (partialTop > 0) { 1121 blitter->blitAntiH(fullLeft - 1, fullTop - 1, 1, 1122 f2a(SkFixedMul(partialTop, rite - left))); 1123 blitter->flush_if_y_changed(y, y + partialTop); 1124 } 1125 if (fullBot > fullTop) { 1126 blitter->getRealBlitter()->blitV(fullLeft - 1, fullTop, fullBot - fullTop, 1127 f2a(rite - left)); 1128 } 1129 if (partialBot > 0) { 1130 blitter->blitAntiH(fullLeft - 1, fullBot, 1, 1131 f2a(SkFixedMul(partialBot, rite - left))); 1132 } 1133 } 1134 1135 y = local_bot_fixed; 1136 } else { 1137 // The following constant are used to snap X 1138 // We snap X mainly for speedup (no tiny triangle) and 1139 // avoiding edge cases caused by precision errors 1140 const SkFixed kSnapDigit = SK_Fixed1 >> 4; 1141 const SkFixed kSnapHalf = kSnapDigit >> 1; 1142 const SkFixed kSnapMask = (-1 ^ (kSnapDigit - 1)); 1143 left += kSnapHalf; rite += kSnapHalf; // For fast rounding 1144 1145 // Number of blit_trapezoid_row calls we'll have 1146 int count = SkFixedCeilToInt(local_bot_fixed) - SkFixedFloorToInt(y); 1147 #ifdef SK_DEBUG 1148 total_y_cnt += count; 1149 frac_y_cnt += ((int)(y & 0xFFFF0000) != y); 1150 if ((int)(y & 0xFFFF0000) != y) { 1151 // SkDebugf("frac_y = %f\n", SkFixedToFloat(y)); 1152 } 1153 #endif 1154 1155 // If we're using mask blitter, we advance the mask row in this function 1156 // to save some "if" condition checks. 1157 SkAlpha* maskRow = nullptr; 1158 if (isUsingMask) { 1159 maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16); 1160 } 1161 1162 // Instead of writing one loop that handles both partial-row blit_trapezoid_row 1163 // and full-row trapezoid_row together, we use the following 3-stage flow to 1164 // handle partial-row blit and full-row blit separately. It will save us much time 1165 // on changing y, left, and rite. 1166 if (count > 1) { 1167 if ((int)(y & 0xFFFF0000) != y) { // There's a partial-row on the top 1168 count--; 1169 SkFixed nextY = SkFixedCeilToFixed(y + 1); 1170 SkFixed dY = nextY - y; 1171 SkFixed nextLeft = left + SkFixedMul(dLeft, dY); 1172 SkFixed nextRite = rite + SkFixedMul(dRite, dY); 1173 SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound && 1174 (nextLeft & kSnapMask) >= leftBound && 1175 (nextRite & kSnapMask) <= riteBound); 1176 blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask, 1177 nextLeft & kSnapMask, nextRite & kSnapMask, leftE->fDY, riteE->fDY, 1178 getPartialAlpha(0xFF, dY), maskRow, isUsingMask); 1179 blitter->flush_if_y_changed(y, nextY); 1180 left = nextLeft; rite = nextRite; y = nextY; 1181 } 1182 1183 while (count > 1) { // Full rows in the middle 1184 count--; 1185 if (isUsingMask) { 1186 maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16); 1187 } 1188 SkFixed nextY = y + SK_Fixed1, nextLeft = left + dLeft, nextRite = rite + dRite; 1189 SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound && 1190 (nextLeft & kSnapMask) >= leftBound && 1191 (nextRite & kSnapMask) <= riteBound); 1192 blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask, 1193 nextLeft & kSnapMask, nextRite & kSnapMask, 1194 leftE->fDY, riteE->fDY, 0xFF, maskRow, isUsingMask); 1195 blitter->flush_if_y_changed(y, nextY); 1196 left = nextLeft; rite = nextRite; y = nextY; 1197 } 1198 } 1199 1200 if (isUsingMask) { 1201 maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16); 1202 } 1203 1204 SkFixed dY = local_bot_fixed - y; // partial-row on the bottom 1205 SkASSERT(dY <= SK_Fixed1); 1206 // Smooth jumping to integer y may make the last nextLeft/nextRite out of bound. 1207 // Take them back into the bound here. 1208 // Note that we substract kSnapHalf later so we have to add them to leftBound/riteBound 1209 SkFixed nextLeft = SkTMax(left + SkFixedMul(dLeft, dY), leftBound + kSnapHalf); 1210 SkFixed nextRite = SkTMin(rite + SkFixedMul(dRite, dY), riteBound + kSnapHalf); 1211 SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound && 1212 (nextLeft & kSnapMask) >= leftBound && (nextRite & kSnapMask) <= riteBound); 1213 blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask, 1214 nextLeft & kSnapMask, nextRite & kSnapMask, leftE->fDY, riteE->fDY, 1215 getPartialAlpha(0xFF, dY), maskRow, isUsingMask); 1216 blitter->flush_if_y_changed(y, local_bot_fixed); 1217 left = nextLeft; rite = nextRite; y = local_bot_fixed; 1218 left -= kSnapHalf; rite -= kSnapHalf; 1219 } 1220 1221 leftE->fX = left; 1222 riteE->fX = rite; 1223 leftE->fY = riteE->fY = y; 1224 } 1225 1226 END_WALK: 1227 ; 1228 #ifdef SK_DEBUG 1229 // SkDebugf("frac_y_cnt = %d, total_y_cnt = %d\n", frac_y_cnt, total_y_cnt); 1230 #endif 1231 } 1232 1233 /////////////////////////////////////////////////////////////////////////////// 1234 1235 static inline void updateNextNextY(SkFixed y, SkFixed nextY, SkFixed* nextNextY) { 1236 *nextNextY = y > nextY && y < *nextNextY ? y : *nextNextY; 1237 } 1238 1239 static inline void checkIntersection(const SkAnalyticEdge* edge, SkFixed nextY, SkFixed* nextNextY) 1240 { 1241 if (edge->fPrev->fPrev && edge->fPrev->fX + edge->fPrev->fDX > edge->fX + edge->fDX) { 1242 *nextNextY = nextY + (SK_Fixed1 >> SkAnalyticEdge::kDefaultAccuracy); 1243 } 1244 } 1245 1246 static void insert_new_edges(SkAnalyticEdge* newEdge, SkFixed y, SkFixed* nextNextY) { 1247 if (newEdge->fUpperY > y) { 1248 updateNextNextY(newEdge->fUpperY, y, nextNextY); 1249 return; 1250 } 1251 SkAnalyticEdge* prev = newEdge->fPrev; 1252 if (prev->fX <= newEdge->fX) { 1253 while (newEdge->fUpperY <= y) { 1254 checkIntersection(newEdge, y, nextNextY); 1255 updateNextNextY(newEdge->fLowerY, y, nextNextY); 1256 newEdge = newEdge->fNext; 1257 } 1258 updateNextNextY(newEdge->fUpperY, y, nextNextY); 1259 return; 1260 } 1261 // find first x pos to insert 1262 SkAnalyticEdge* start = backward_insert_start(prev, newEdge->fX); 1263 //insert the lot, fixing up the links as we go 1264 do { 1265 SkAnalyticEdge* next = newEdge->fNext; 1266 do { 1267 if (start->fNext == newEdge) { 1268 goto nextEdge; 1269 } 1270 SkAnalyticEdge* after = start->fNext; 1271 if (after->fX >= newEdge->fX) { 1272 break; 1273 } 1274 SkASSERT(start != after); 1275 start = after; 1276 } while (true); 1277 remove_edge(newEdge); 1278 insert_edge_after(newEdge, start); 1279 nextEdge: 1280 checkIntersection(newEdge, y, nextNextY); 1281 updateNextNextY(newEdge->fLowerY, y, nextNextY); 1282 start = newEdge; 1283 newEdge = next; 1284 } while (newEdge->fUpperY <= y); 1285 updateNextNextY(newEdge->fUpperY, y, nextNextY); 1286 } 1287 1288 static void validate_edges_for_y(const SkAnalyticEdge* edge, SkFixed y) { 1289 #ifdef SK_DEBUG 1290 while (edge->fUpperY <= y) { 1291 SkASSERT(edge->fPrev && edge->fNext); 1292 SkASSERT(edge->fPrev->fNext == edge); 1293 SkASSERT(edge->fNext->fPrev == edge); 1294 SkASSERT(edge->fUpperY <= edge->fLowerY); 1295 SkASSERT(edge->fPrev->fPrev == nullptr || edge->fPrev->fX <= edge->fX); 1296 edge = edge->fNext; 1297 } 1298 #endif 1299 } 1300 1301 // Return true if prev->fX, next->fX are too close in the current pixel row. 1302 static inline bool edges_too_close(SkAnalyticEdge* prev, SkAnalyticEdge* next, SkFixed lowerY) { 1303 // Note that even if the following test failed, the edges might still be very close to each 1304 // other at some point within the current pixel row because of prev->fDX and next->fDX. 1305 // However, to handle that case, we have to sacrafice more performance. 1306 // I think the current quality is good enough (mainly by looking at Nebraska-StateSeal.svg) 1307 // so I'll ignore fDX for performance tradeoff. 1308 return next && prev && next->fUpperY < lowerY && prev->fX >= next->fX - SkAbs32(next->fDX); 1309 // The following is more accurate but also slower. 1310 // return (prev && prev->fPrev && next && next->fNext != nullptr && next->fUpperY < lowerY && 1311 // prev->fX + SkAbs32(prev->fDX) >= next->fX - SkAbs32(next->fDX)); 1312 } 1313 1314 // This function exists for the case where the previous rite edge is removed because 1315 // its fLowerY <= nextY 1316 static inline bool edges_too_close(int prevRite, SkFixed ul, SkFixed ll) { 1317 return prevRite > SkFixedFloorToInt(ul) || prevRite > SkFixedFloorToInt(ll); 1318 } 1319 1320 static inline void blit_saved_trapezoid(SkAnalyticEdge* leftE, SkFixed lowerY, 1321 SkFixed lowerLeft, SkFixed lowerRite, 1322 AdditiveBlitter* blitter, SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter, 1323 SkFixed leftClip, SkFixed rightClip) { 1324 SkAnalyticEdge* riteE = leftE->fRiteE; 1325 SkASSERT(riteE); 1326 SkASSERT(riteE->fNext == nullptr || leftE->fSavedY == riteE->fSavedY); 1327 SkASSERT(SkFixedFloorToInt(lowerY - 1) == SkFixedFloorToInt(leftE->fSavedY)); 1328 int y = SkFixedFloorToInt(leftE->fSavedY); 1329 // Instead of using f2a(lowerY - leftE->fSavedY), we use the following fullAlpha 1330 // to elimiate cumulative error: if there are many fractional y scan lines within the 1331 // same row, the former may accumulate the rounding error while the later won't. 1332 SkAlpha fullAlpha = f2a(lowerY - SkIntToFixed(y)) - f2a(leftE->fSavedY - SkIntToFixed(y)); 1333 // We need fSavedDY because the (quad or cubic) edge might be updated 1334 blit_trapezoid_row(blitter, y, 1335 SkTMax(leftE->fSavedX, leftClip), SkTMin(riteE->fSavedX, rightClip), 1336 SkTMax(lowerLeft, leftClip), SkTMin(lowerRite, rightClip), 1337 leftE->fSavedDY, riteE->fSavedDY, fullAlpha, maskRow, isUsingMask, 1338 noRealBlitter || 1339 (fullAlpha == 0xFF && (edges_too_close(leftE->fPrev, leftE, lowerY) 1340 || edges_too_close(riteE, riteE->fNext, lowerY))), 1341 true); 1342 leftE->fRiteE = nullptr; 1343 } 1344 1345 static inline void deferred_blit(SkAnalyticEdge* leftE, SkAnalyticEdge* riteE, 1346 SkFixed left, SkFixed leftDY, // don't save leftE->fX/fDY as they may have been updated 1347 SkFixed y, SkFixed nextY, bool isIntegralNextY, bool leftEnds, bool riteEnds, 1348 AdditiveBlitter* blitter, SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter, 1349 SkFixed leftClip, SkFixed rightClip, int yShift) { 1350 if (leftE->fRiteE && leftE->fRiteE != riteE) { 1351 // leftE's right edge changed. Blit the saved trapezoid. 1352 SkASSERT(leftE->fRiteE->fNext == nullptr || leftE->fRiteE->fY == y); 1353 blit_saved_trapezoid(leftE, y, left, leftE->fRiteE->fX, 1354 blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip); 1355 } 1356 if (!leftE->fRiteE) { 1357 // Save and defer blitting the trapezoid 1358 SkASSERT(riteE->fRiteE == nullptr); 1359 SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY); 1360 SkASSERT(riteE->fNext == nullptr || riteE->fY == y); 1361 leftE->saveXY(left, y, leftDY); 1362 riteE->saveXY(riteE->fX, y, riteE->fDY); 1363 leftE->fRiteE = riteE; 1364 } 1365 SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY); 1366 riteE->goY(nextY, yShift); 1367 // Always blit when edges end or nextY is integral 1368 if (isIntegralNextY || leftEnds || riteEnds) { 1369 blit_saved_trapezoid(leftE, nextY, leftE->fX, riteE->fX, 1370 blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip); 1371 } 1372 } 1373 1374 static void aaa_walk_edges(SkAnalyticEdge* prevHead, SkAnalyticEdge* nextTail, 1375 SkPath::FillType fillType, AdditiveBlitter* blitter, int start_y, int stop_y, 1376 SkFixed leftClip, SkFixed rightClip, bool isUsingMask, bool forceRLE, bool useDeferred, 1377 bool skipIntersect) { 1378 prevHead->fX = prevHead->fUpperX = leftClip; 1379 nextTail->fX = nextTail->fUpperX = rightClip; 1380 SkFixed y = SkTMax(prevHead->fNext->fUpperY, SkIntToFixed(start_y)); 1381 SkFixed nextNextY = SK_MaxS32; 1382 1383 { 1384 SkAnalyticEdge* edge; 1385 for(edge = prevHead->fNext; edge->fUpperY <= y; edge = edge->fNext) { 1386 edge->goY(y); 1387 updateNextNextY(edge->fLowerY, y, &nextNextY); 1388 } 1389 updateNextNextY(edge->fUpperY, y, &nextNextY); 1390 } 1391 1392 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 1393 int windingMask = (fillType & 1) ? 1 : -1; 1394 1395 bool isInverse = SkPath::IsInverseFillType(fillType); 1396 1397 if (isInverse && SkIntToFixed(start_y) != y) { 1398 int width = SkFixedFloorToInt(rightClip - leftClip); 1399 if (SkFixedFloorToInt(y) != start_y) { 1400 blitter->getRealBlitter()->blitRect(SkFixedFloorToInt(leftClip), start_y, 1401 width, SkFixedFloorToInt(y) - start_y); 1402 start_y = SkFixedFloorToInt(y); 1403 } 1404 SkAlpha* maskRow = isUsingMask ? static_cast<MaskAdditiveBlitter*>(blitter)->getRow(start_y) 1405 : nullptr; 1406 blit_full_alpha(blitter, start_y, SkFixedFloorToInt(leftClip), width, 1407 f2a(y - SkIntToFixed(start_y)), maskRow, isUsingMask, false, false); 1408 } 1409 1410 while (true) { 1411 int w = 0; 1412 bool in_interval = isInverse; 1413 SkFixed prevX = prevHead->fX; 1414 SkFixed nextY = SkTMin(nextNextY, SkFixedCeilToFixed(y + 1)); 1415 bool isIntegralNextY = (nextY & (SK_Fixed1 - 1)) == 0; 1416 SkAnalyticEdge* currE = prevHead->fNext; 1417 SkAnalyticEdge* leftE = prevHead; 1418 SkFixed left = leftClip; 1419 SkFixed leftDY = 0; 1420 bool leftEnds = false; 1421 int prevRite = SkFixedFloorToInt(leftClip); 1422 1423 nextNextY = SK_MaxS32; 1424 1425 SkASSERT((nextY & ((SK_Fixed1 >> 2) - 1)) == 0); 1426 int yShift = 0; 1427 if ((nextY - y) & (SK_Fixed1 >> 2)) { 1428 yShift = 2; 1429 nextY = y + (SK_Fixed1 >> 2); 1430 } else if ((nextY - y) & (SK_Fixed1 >> 1)) { 1431 yShift = 1; 1432 SkASSERT(nextY == y + (SK_Fixed1 >> 1)); 1433 } 1434 1435 SkAlpha fullAlpha = f2a(nextY - y); 1436 1437 // If we're using mask blitter, we advance the mask row in this function 1438 // to save some "if" condition checks. 1439 SkAlpha* maskRow = nullptr; 1440 if (isUsingMask) { 1441 maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(SkFixedFloorToInt(y)); 1442 } 1443 1444 SkASSERT(currE->fPrev == prevHead); 1445 validate_edges_for_y(currE, y); 1446 1447 // Even if next - y == SK_Fixed1, we can still break the left-to-right order requirement 1448 // of the SKAAClip: |\| (two trapezoids with overlapping middle wedges) 1449 bool noRealBlitter = forceRLE; // forceRLE && (nextY - y != SK_Fixed1); 1450 1451 while (currE->fUpperY <= y) { 1452 SkASSERT(currE->fLowerY >= nextY); 1453 SkASSERT(currE->fY == y); 1454 1455 w += currE->fWinding; 1456 bool prev_in_interval = in_interval; 1457 in_interval = !(w & windingMask) == isInverse; 1458 1459 bool isLeft = in_interval && !prev_in_interval; 1460 bool isRite = !in_interval && prev_in_interval; 1461 bool currEnds = currE->fLowerY == nextY; 1462 1463 if (useDeferred) { 1464 if (currE->fRiteE && !isLeft) { 1465 // currE is a left edge previously, but now it's not. 1466 // Blit the trapezoid between fSavedY and y. 1467 SkASSERT(currE->fRiteE->fY == y); 1468 blit_saved_trapezoid(currE, y, currE->fX, currE->fRiteE->fX, 1469 blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip); 1470 } 1471 if (leftE->fRiteE == currE && !isRite) { 1472 // currE is a right edge previously, but now it's not. 1473 // Moreover, its corresponding leftE doesn't change (otherwise we'll handle it 1474 // in the previous if clause). Hence we blit the trapezoid. 1475 blit_saved_trapezoid(leftE, y, left, currE->fX, 1476 blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip); 1477 } 1478 } 1479 1480 if (isRite) { 1481 if (useDeferred) { 1482 deferred_blit(leftE, currE, left, leftDY, y, nextY, isIntegralNextY, 1483 leftEnds, currEnds, blitter, maskRow, isUsingMask, noRealBlitter, 1484 leftClip, rightClip, yShift); 1485 } else { 1486 SkFixed rite = currE->fX; 1487 currE->goY(nextY, yShift); 1488 leftE->fX = SkTMax(leftClip, leftE->fX); 1489 rite = SkTMin(rightClip, rite); 1490 currE->fX = SkTMin(rightClip, currE->fX); 1491 blit_trapezoid_row(blitter, y >> 16, left, rite, leftE->fX, currE->fX, 1492 leftDY, currE->fDY, fullAlpha, maskRow, isUsingMask, 1493 noRealBlitter || (fullAlpha == 0xFF && ( 1494 edges_too_close(prevRite, left, leftE->fX) || 1495 edges_too_close(currE, currE->fNext, nextY) 1496 )), 1497 true); 1498 prevRite = SkFixedCeilToInt(SkTMax(rite, currE->fX)); 1499 } 1500 } else { 1501 if (isLeft) { 1502 left = SkTMax(currE->fX, leftClip); 1503 leftDY = currE->fDY; 1504 leftE = currE; 1505 leftEnds = leftE->fLowerY == nextY; 1506 } 1507 currE->goY(nextY, yShift); 1508 } 1509 1510 1511 SkAnalyticEdge* next = currE->fNext; 1512 SkFixed newX; 1513 1514 while (currE->fLowerY <= nextY) { 1515 if (currE->fCurveCount < 0) { 1516 SkAnalyticCubicEdge* cubicEdge = (SkAnalyticCubicEdge*)currE; 1517 cubicEdge->keepContinuous(); 1518 if (!cubicEdge->updateCubic()) { 1519 break; 1520 } 1521 } else if (currE->fCurveCount > 0) { 1522 SkAnalyticQuadraticEdge* quadEdge = (SkAnalyticQuadraticEdge*)currE; 1523 quadEdge->keepContinuous(); 1524 if (!quadEdge->updateQuadratic()) { 1525 break; 1526 } 1527 } else { 1528 break; 1529 } 1530 } 1531 SkASSERT(currE->fY == nextY); 1532 1533 if (currE->fLowerY <= nextY) { 1534 remove_edge(currE); 1535 } else { 1536 updateNextNextY(currE->fLowerY, nextY, &nextNextY); 1537 newX = currE->fX; 1538 SkASSERT(currE->fLowerY > nextY); 1539 if (newX < prevX) { // ripple currE backwards until it is x-sorted 1540 // If the crossing edge is a right edge, blit the saved trapezoid. 1541 if (leftE->fRiteE == currE && useDeferred) { 1542 SkASSERT(leftE->fY == nextY && currE->fY == nextY); 1543 blit_saved_trapezoid(leftE, nextY, leftE->fX, currE->fX, 1544 blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip); 1545 } 1546 backward_insert_edge_based_on_x(currE); 1547 } else { 1548 prevX = newX; 1549 } 1550 if (!skipIntersect) { 1551 checkIntersection(currE, nextY, &nextNextY); 1552 } 1553 } 1554 1555 currE = next; 1556 SkASSERT(currE); 1557 } 1558 1559 // was our right-edge culled away? 1560 if (in_interval) { 1561 if (useDeferred) { 1562 deferred_blit(leftE, nextTail, left, leftDY, y, nextY, isIntegralNextY, 1563 leftEnds, false, blitter, maskRow, isUsingMask, noRealBlitter, 1564 leftClip, rightClip, yShift); 1565 } else { 1566 blit_trapezoid_row(blitter, y >> 16, 1567 left, rightClip, 1568 SkTMax(leftClip, leftE->fX), rightClip, 1569 leftDY, 0, fullAlpha, maskRow, isUsingMask, 1570 noRealBlitter || 1571 (fullAlpha == 0xFF && edges_too_close(leftE->fPrev, leftE, nextY)), 1572 true); 1573 } 1574 } 1575 1576 if (forceRLE) { 1577 ((RunBasedAdditiveBlitter*)blitter)->flush_if_y_changed(y, nextY); 1578 } 1579 1580 y = nextY; 1581 if (y >= SkIntToFixed(stop_y)) { 1582 break; 1583 } 1584 1585 // now currE points to the first edge with a fUpperY larger than the previous y 1586 insert_new_edges(currE, y, &nextNextY); 1587 } 1588 } 1589 1590 static SK_ALWAYS_INLINE void aaa_fill_path(const SkPath& path, const SkIRect& clipRect, 1591 AdditiveBlitter* blitter, int start_y, int stop_y, bool pathContainedInClip, 1592 bool isUsingMask, bool forceRLE) { // forceRLE implies that SkAAClip is calling us 1593 SkASSERT(blitter); 1594 1595 SkEdgeBuilder builder; 1596 1597 // If we're convex, then we need both edges, even the right edge is past the clip 1598 const bool canCullToTheRight = !path.isConvex(); 1599 1600 SkASSERT(gSkUseAnalyticAA.load()); 1601 const SkIRect* builderClip = pathContainedInClip ? nullptr : &clipRect; 1602 int count = builder.build(path, builderClip, 0, canCullToTheRight, true); 1603 SkASSERT(count >= 0); 1604 1605 SkAnalyticEdge** list = (SkAnalyticEdge**)builder.analyticEdgeList(); 1606 1607 SkIRect rect = clipRect; 1608 if (0 == count) { 1609 if (path.isInverseFillType()) { 1610 /* 1611 * Since we are in inverse-fill, our caller has already drawn above 1612 * our top (start_y) and will draw below our bottom (stop_y). Thus 1613 * we need to restrict our drawing to the intersection of the clip 1614 * and those two limits. 1615 */ 1616 if (rect.fTop < start_y) { 1617 rect.fTop = start_y; 1618 } 1619 if (rect.fBottom > stop_y) { 1620 rect.fBottom = stop_y; 1621 } 1622 if (!rect.isEmpty()) { 1623 blitter->getRealBlitter()->blitRect(rect.fLeft, rect.fTop, 1624 rect.width(), rect.height()); 1625 } 1626 } 1627 return; 1628 } 1629 1630 SkAnalyticEdge headEdge, tailEdge, *last; 1631 // this returns the first and last edge after they're sorted into a dlink list 1632 SkAnalyticEdge* edge = sort_edges(list, count, &last); 1633 1634 headEdge.fRiteE = nullptr; 1635 headEdge.fPrev = nullptr; 1636 headEdge.fNext = edge; 1637 headEdge.fUpperY = headEdge.fLowerY = SK_MinS32; 1638 headEdge.fX = SK_MinS32; 1639 headEdge.fDX = 0; 1640 headEdge.fDY = SK_MaxS32; 1641 headEdge.fUpperX = SK_MinS32; 1642 edge->fPrev = &headEdge; 1643 1644 tailEdge.fRiteE = nullptr; 1645 tailEdge.fPrev = last; 1646 tailEdge.fNext = nullptr; 1647 tailEdge.fUpperY = tailEdge.fLowerY = SK_MaxS32; 1648 tailEdge.fX = SK_MaxS32; 1649 tailEdge.fDX = 0; 1650 tailEdge.fDY = SK_MaxS32; 1651 tailEdge.fUpperX = SK_MaxS32; 1652 last->fNext = &tailEdge; 1653 1654 // now edge is the head of the sorted linklist 1655 1656 if (!pathContainedInClip && start_y < clipRect.fTop) { 1657 start_y = clipRect.fTop; 1658 } 1659 if (!pathContainedInClip && stop_y > clipRect.fBottom) { 1660 stop_y = clipRect.fBottom; 1661 } 1662 1663 SkFixed leftBound = SkIntToFixed(rect.fLeft); 1664 SkFixed rightBound = SkIntToFixed(rect.fRight); 1665 if (isUsingMask) { 1666 // If we're using mask, then we have to limit the bound within the path bounds. 1667 // Otherwise, the edge drift may access an invalid address inside the mask. 1668 SkIRect ir; 1669 path.getBounds().roundOut(&ir); 1670 leftBound = SkTMax(leftBound, SkIntToFixed(ir.fLeft)); 1671 rightBound = SkTMin(rightBound, SkIntToFixed(ir.fRight)); 1672 } 1673 1674 if (!path.isInverseFillType() && path.isConvex()) { 1675 SkASSERT(count >= 2); // convex walker does not handle missing right edges 1676 aaa_walk_convex_edges(&headEdge, blitter, start_y, stop_y, 1677 leftBound, rightBound, isUsingMask); 1678 } else { 1679 // Only use deferred blitting if there are many edges. 1680 bool useDeferred = count > 1681 (SkFixedFloorToInt(tailEdge.fPrev->fLowerY - headEdge.fNext->fUpperY) + 1) * 4; 1682 1683 // We skip intersection computation if there are many points which probably already 1684 // give us enough fractional scan lines. 1685 bool skipIntersect = path.countPoints() > (stop_y - start_y) * 2; 1686 1687 aaa_walk_edges(&headEdge, &tailEdge, path.getFillType(), blitter, start_y, stop_y, 1688 leftBound, rightBound, isUsingMask, forceRLE, useDeferred, skipIntersect); 1689 } 1690 } 1691 1692 /////////////////////////////////////////////////////////////////////////////// 1693 1694 static int overflows_short_shift(int value, int shift) { 1695 const int s = 16 + shift; 1696 return (SkLeftShift(value, s) >> s) - value; 1697 } 1698 1699 /** 1700 Would any of the coordinates of this rectangle not fit in a short, 1701 when left-shifted by shift? 1702 */ 1703 static int rect_overflows_short_shift(SkIRect rect, int shift) { 1704 SkASSERT(!overflows_short_shift(8191, 2)); 1705 SkASSERT(overflows_short_shift(8192, 2)); 1706 SkASSERT(!overflows_short_shift(32767, 0)); 1707 SkASSERT(overflows_short_shift(32768, 0)); 1708 1709 // Since we expect these to succeed, we bit-or together 1710 // for a tiny extra bit of speed. 1711 return overflows_short_shift(rect.fLeft, 2) | 1712 overflows_short_shift(rect.fRight, 2) | 1713 overflows_short_shift(rect.fTop, 2) | 1714 overflows_short_shift(rect.fBottom, 2); 1715 } 1716 1717 static bool fitsInsideLimit(const SkRect& r, SkScalar max) { 1718 const SkScalar min = -max; 1719 return r.fLeft > min && r.fTop > min && 1720 r.fRight < max && r.fBottom < max; 1721 } 1722 1723 static bool safeRoundOut(const SkRect& src, SkIRect* dst, int32_t maxInt) { 1724 const SkScalar maxScalar = SkIntToScalar(maxInt); 1725 1726 if (fitsInsideLimit(src, maxScalar)) { 1727 src.roundOut(dst); 1728 return true; 1729 } 1730 return false; 1731 } 1732 1733 void SkScan::AAAFillPath(const SkPath& path, const SkRegion& origClip, SkBlitter* blitter, 1734 bool forceRLE) { 1735 if (origClip.isEmpty()) { 1736 return; 1737 } 1738 1739 const bool isInverse = path.isInverseFillType(); 1740 SkIRect ir; 1741 if (!safeRoundOut(path.getBounds(), &ir, SK_MaxS32 >> 2)) { 1742 return; 1743 } 1744 if (ir.isEmpty()) { 1745 if (isInverse) { 1746 blitter->blitRegion(origClip); 1747 } 1748 return; 1749 } 1750 1751 SkIRect clippedIR; 1752 if (isInverse) { 1753 // If the path is an inverse fill, it's going to fill the entire 1754 // clip, and we care whether the entire clip exceeds our limits. 1755 clippedIR = origClip.getBounds(); 1756 } else { 1757 if (!clippedIR.intersect(ir, origClip.getBounds())) { 1758 return; 1759 } 1760 } 1761 // If the intersection of the path bounds and the clip bounds 1762 // will overflow 32767 when << by 2, our SkFixed will overflow, 1763 // so draw without antialiasing. 1764 if (rect_overflows_short_shift(clippedIR, 2)) { 1765 SkScan::FillPath(path, origClip, blitter); 1766 return; 1767 } 1768 1769 // Our antialiasing can't handle a clip larger than 32767, so we restrict 1770 // the clip to that limit here. (the runs[] uses int16_t for its index). 1771 // 1772 // A more general solution (one that could also eliminate the need to 1773 // disable aa based on ir bounds (see overflows_short_shift) would be 1774 // to tile the clip/target... 1775 SkRegion tmpClipStorage; 1776 const SkRegion* clipRgn = &origClip; 1777 { 1778 static const int32_t kMaxClipCoord = 32767; 1779 const SkIRect& bounds = origClip.getBounds(); 1780 if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) { 1781 SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord }; 1782 tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op); 1783 clipRgn = &tmpClipStorage; 1784 } 1785 } 1786 // for here down, use clipRgn, not origClip 1787 1788 SkScanClipper clipper(blitter, clipRgn, ir); 1789 const SkIRect* clipRect = clipper.getClipRect(); 1790 1791 if (clipper.getBlitter() == nullptr) { // clipped out 1792 if (isInverse) { 1793 blitter->blitRegion(*clipRgn); 1794 } 1795 return; 1796 } 1797 1798 // now use the (possibly wrapped) blitter 1799 blitter = clipper.getBlitter(); 1800 1801 if (isInverse) { 1802 sk_blit_above(blitter, ir, *clipRgn); 1803 } 1804 1805 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 1806 1807 if (MaskAdditiveBlitter::canHandleRect(ir) && !isInverse && !forceRLE) { 1808 MaskAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse); 1809 aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom, 1810 clipRect == nullptr, true, forceRLE); 1811 } else if (!isInverse && path.isConvex()) { 1812 RunBasedAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse); 1813 aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom, 1814 clipRect == nullptr, false, forceRLE); 1815 } else { 1816 SafeRLEAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse); 1817 aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom, 1818 clipRect == nullptr, false, forceRLE); 1819 } 1820 1821 if (isInverse) { 1822 sk_blit_below(blitter, ir, *clipRgn); 1823 } 1824 } 1825 1826 // This almost copies SkScan::AntiFillPath 1827 void SkScan::AAAFillPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) { 1828 if (clip.isEmpty()) { 1829 return; 1830 } 1831 1832 if (clip.isBW()) { 1833 AAAFillPath(path, clip.bwRgn(), blitter); 1834 } else { 1835 SkRegion tmp; 1836 SkAAClipBlitter aaBlitter; 1837 1838 tmp.setRect(clip.getBounds()); 1839 aaBlitter.init(blitter, &clip.aaRgn()); 1840 AAAFillPath(path, tmp, &aaBlitter, true); 1841 } 1842 } 1843