1 /* 2 * Copyright 2006 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 "SkScanPriv.h" 9 #include "SkBlitter.h" 10 #include "SkEdge.h" 11 #include "SkEdgeBuilder.h" 12 #include "SkGeometry.h" 13 #include "SkPath.h" 14 #include "SkQuadClipper.h" 15 #include "SkRasterClip.h" 16 #include "SkRectPriv.h" 17 #include "SkRegion.h" 18 #include "SkTemplates.h" 19 #include "SkTSort.h" 20 21 #define kEDGE_HEAD_Y SK_MinS32 22 #define kEDGE_TAIL_Y SK_MaxS32 23 24 #ifdef SK_DEBUG 25 static void validate_sort(const SkEdge* edge) { 26 int y = kEDGE_HEAD_Y; 27 28 while (edge->fFirstY != SK_MaxS32) { 29 edge->validate(); 30 SkASSERT(y <= edge->fFirstY); 31 32 y = edge->fFirstY; 33 edge = edge->fNext; 34 } 35 } 36 #else 37 #define validate_sort(edge) 38 #endif 39 40 static void insert_new_edges(SkEdge* newEdge, int curr_y) { 41 if (newEdge->fFirstY != curr_y) { 42 return; 43 } 44 SkEdge* prev = newEdge->fPrev; 45 if (prev->fX <= newEdge->fX) { 46 return; 47 } 48 // find first x pos to insert 49 SkEdge* start = backward_insert_start(prev, newEdge->fX); 50 // insert the lot, fixing up the links as we go 51 do { 52 SkEdge* next = newEdge->fNext; 53 do { 54 if (start->fNext == newEdge) { 55 goto nextEdge; 56 } 57 SkEdge* after = start->fNext; 58 if (after->fX >= newEdge->fX) { 59 break; 60 } 61 start = after; 62 } while (true); 63 remove_edge(newEdge); 64 insert_edge_after(newEdge, start); 65 nextEdge: 66 start = newEdge; 67 newEdge = next; 68 } while (newEdge->fFirstY == curr_y); 69 } 70 71 #ifdef SK_DEBUG 72 static void validate_edges_for_y(const SkEdge* edge, int curr_y) { 73 while (edge->fFirstY <= curr_y) { 74 SkASSERT(edge->fPrev && edge->fNext); 75 SkASSERT(edge->fPrev->fNext == edge); 76 SkASSERT(edge->fNext->fPrev == edge); 77 SkASSERT(edge->fFirstY <= edge->fLastY); 78 79 SkASSERT(edge->fPrev->fX <= edge->fX); 80 edge = edge->fNext; 81 } 82 } 83 #else 84 #define validate_edges_for_y(edge, curr_y) 85 #endif 86 87 #if defined _WIN32 // disable warning : local variable used without having been initialized 88 #pragma warning ( push ) 89 #pragma warning ( disable : 4701 ) 90 #endif 91 92 typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline); 93 #define PREPOST_START true 94 #define PREPOST_END false 95 96 static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType, 97 SkBlitter* blitter, int start_y, int stop_y, 98 PrePostProc proc, int rightClip) { 99 validate_sort(prevHead->fNext); 100 101 int curr_y = start_y; 102 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 103 int windingMask = (fillType & 1) ? 1 : -1; 104 105 for (;;) { 106 int w = 0; 107 int left SK_INIT_TO_AVOID_WARNING; 108 bool in_interval = false; 109 SkEdge* currE = prevHead->fNext; 110 SkFixed prevX = prevHead->fX; 111 112 validate_edges_for_y(currE, curr_y); 113 114 if (proc) { 115 proc(blitter, curr_y, PREPOST_START); // pre-proc 116 } 117 118 while (currE->fFirstY <= curr_y) { 119 SkASSERT(currE->fLastY >= curr_y); 120 121 int x = SkFixedRoundToInt(currE->fX); 122 w += currE->fWinding; 123 if ((w & windingMask) == 0) { // we finished an interval 124 SkASSERT(in_interval); 125 int width = x - left; 126 SkASSERT(width >= 0); 127 if (width) 128 blitter->blitH(left, curr_y, width); 129 in_interval = false; 130 } else if (!in_interval) { 131 left = x; 132 in_interval = true; 133 } 134 135 SkEdge* next = currE->fNext; 136 SkFixed newX; 137 138 if (currE->fLastY == curr_y) { // are we done with this edge? 139 if (currE->fCurveCount < 0) { 140 if (((SkCubicEdge*)currE)->updateCubic()) { 141 SkASSERT(currE->fFirstY == curr_y + 1); 142 143 newX = currE->fX; 144 goto NEXT_X; 145 } 146 } else if (currE->fCurveCount > 0) { 147 if (((SkQuadraticEdge*)currE)->updateQuadratic()) { 148 newX = currE->fX; 149 goto NEXT_X; 150 } 151 } 152 remove_edge(currE); 153 } else { 154 SkASSERT(currE->fLastY > curr_y); 155 newX = currE->fX + currE->fDX; 156 currE->fX = newX; 157 NEXT_X: 158 if (newX < prevX) { // ripple currE backwards until it is x-sorted 159 backward_insert_edge_based_on_x(currE); 160 } else { 161 prevX = newX; 162 } 163 } 164 currE = next; 165 SkASSERT(currE); 166 } 167 168 // was our right-edge culled away? 169 if (in_interval) { 170 int width = rightClip - left; 171 if (width > 0) { 172 blitter->blitH(left, curr_y, width); 173 } 174 } 175 176 if (proc) { 177 proc(blitter, curr_y, PREPOST_END); // post-proc 178 } 179 180 curr_y += 1; 181 if (curr_y >= stop_y) { 182 break; 183 } 184 // now currE points to the first edge with a Yint larger than curr_y 185 insert_new_edges(currE, curr_y); 186 } 187 } 188 189 // return true if we're NOT done with this edge 190 static bool update_edge(SkEdge* edge, int last_y) { 191 SkASSERT(edge->fLastY >= last_y); 192 if (last_y == edge->fLastY) { 193 if (edge->fCurveCount < 0) { 194 if (((SkCubicEdge*)edge)->updateCubic()) { 195 SkASSERT(edge->fFirstY == last_y + 1); 196 return true; 197 } 198 } else if (edge->fCurveCount > 0) { 199 if (((SkQuadraticEdge*)edge)->updateQuadratic()) { 200 SkASSERT(edge->fFirstY == last_y + 1); 201 return true; 202 } 203 } 204 return false; 205 } 206 return true; 207 } 208 209 static void walk_convex_edges(SkEdge* prevHead, SkPath::FillType, 210 SkBlitter* blitter, int start_y, int stop_y, 211 PrePostProc proc) { 212 validate_sort(prevHead->fNext); 213 214 SkEdge* leftE = prevHead->fNext; 215 SkEdge* riteE = leftE->fNext; 216 SkEdge* currE = riteE->fNext; 217 218 #if 0 219 int local_top = leftE->fFirstY; 220 SkASSERT(local_top == riteE->fFirstY); 221 #else 222 // our edge choppers for curves can result in the initial edges 223 // not lining up, so we take the max. 224 int local_top = SkMax32(leftE->fFirstY, riteE->fFirstY); 225 #endif 226 SkASSERT(local_top >= start_y); 227 228 for (;;) { 229 SkASSERT(leftE->fFirstY <= stop_y); 230 SkASSERT(riteE->fFirstY <= stop_y); 231 232 if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX && 233 leftE->fDX > riteE->fDX)) { 234 SkTSwap(leftE, riteE); 235 } 236 237 int local_bot = SkMin32(leftE->fLastY, riteE->fLastY); 238 local_bot = SkMin32(local_bot, stop_y - 1); 239 SkASSERT(local_top <= local_bot); 240 241 SkFixed left = leftE->fX; 242 SkFixed dLeft = leftE->fDX; 243 SkFixed rite = riteE->fX; 244 SkFixed dRite = riteE->fDX; 245 int count = local_bot - local_top; 246 SkASSERT(count >= 0); 247 if (0 == (dLeft | dRite)) { 248 int L = SkFixedRoundToInt(left); 249 int R = SkFixedRoundToInt(rite); 250 if (L < R) { 251 count += 1; 252 blitter->blitRect(L, local_top, R - L, count); 253 } 254 local_top = local_bot + 1; 255 } else { 256 do { 257 int L = SkFixedRoundToInt(left); 258 int R = SkFixedRoundToInt(rite); 259 if (L < R) { 260 blitter->blitH(L, local_top, R - L); 261 } 262 left += dLeft; 263 rite += dRite; 264 local_top += 1; 265 } while (--count >= 0); 266 } 267 268 leftE->fX = left; 269 riteE->fX = rite; 270 271 if (!update_edge(leftE, local_bot)) { 272 if (currE->fFirstY >= stop_y) { 273 break; 274 } 275 leftE = currE; 276 currE = currE->fNext; 277 } 278 if (!update_edge(riteE, local_bot)) { 279 if (currE->fFirstY >= stop_y) { 280 break; 281 } 282 riteE = currE; 283 currE = currE->fNext; 284 } 285 286 SkASSERT(leftE); 287 SkASSERT(riteE); 288 289 // check our bottom clip 290 SkASSERT(local_top == local_bot + 1); 291 if (local_top >= stop_y) { 292 break; 293 } 294 } 295 } 296 297 /////////////////////////////////////////////////////////////////////////////// 298 299 // this guy overrides blitH, and will call its proxy blitter with the inverse 300 // of the spans it is given (clipped to the left/right of the cliprect) 301 // 302 // used to implement inverse filltypes on paths 303 // 304 class InverseBlitter : public SkBlitter { 305 public: 306 void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) { 307 fBlitter = blitter; 308 fFirstX = clip.fLeft << shift; 309 fLastX = clip.fRight << shift; 310 } 311 void prepost(int y, bool isStart) { 312 if (isStart) { 313 fPrevX = fFirstX; 314 } else { 315 int invWidth = fLastX - fPrevX; 316 if (invWidth > 0) { 317 fBlitter->blitH(fPrevX, y, invWidth); 318 } 319 } 320 } 321 322 // overrides 323 void blitH(int x, int y, int width) override { 324 int invWidth = x - fPrevX; 325 if (invWidth > 0) { 326 fBlitter->blitH(fPrevX, y, invWidth); 327 } 328 fPrevX = x + width; 329 } 330 331 // we do not expect to get called with these entrypoints 332 void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) override { 333 SkDEBUGFAIL("blitAntiH unexpected"); 334 } 335 void blitV(int x, int y, int height, SkAlpha alpha) override { 336 SkDEBUGFAIL("blitV unexpected"); 337 } 338 void blitRect(int x, int y, int width, int height) override { 339 SkDEBUGFAIL("blitRect unexpected"); 340 } 341 void blitMask(const SkMask&, const SkIRect& clip) override { 342 SkDEBUGFAIL("blitMask unexpected"); 343 } 344 const SkPixmap* justAnOpaqueColor(uint32_t* value) override { 345 SkDEBUGFAIL("justAnOpaqueColor unexpected"); 346 return nullptr; 347 } 348 349 private: 350 SkBlitter* fBlitter; 351 int fFirstX, fLastX, fPrevX; 352 }; 353 354 static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) { 355 ((InverseBlitter*)blitter)->prepost(y, isStart); 356 } 357 358 /////////////////////////////////////////////////////////////////////////////// 359 360 #if defined _WIN32 361 #pragma warning ( pop ) 362 #endif 363 364 static bool operator<(const SkEdge& a, const SkEdge& b) { 365 int valuea = a.fFirstY; 366 int valueb = b.fFirstY; 367 368 if (valuea == valueb) { 369 valuea = a.fX; 370 valueb = b.fX; 371 } 372 373 return valuea < valueb; 374 } 375 376 static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) { 377 SkTQSort(list, list + count - 1); 378 379 // now make the edges linked in sorted order 380 for (int i = 1; i < count; i++) { 381 list[i - 1]->fNext = list[i]; 382 list[i]->fPrev = list[i - 1]; 383 } 384 385 *last = list[count - 1]; 386 return list[0]; 387 } 388 389 // clipRect has not been shifted up 390 void sk_fill_path(const SkPath& path, const SkIRect& clipRect, SkBlitter* blitter, 391 int start_y, int stop_y, int shiftEdgesUp, bool pathContainedInClip) { 392 SkASSERT(blitter); 393 394 SkIRect shiftedClip = clipRect; 395 shiftedClip.fLeft = SkLeftShift(shiftedClip.fLeft, shiftEdgesUp); 396 shiftedClip.fRight = SkLeftShift(shiftedClip.fRight, shiftEdgesUp); 397 shiftedClip.fTop = SkLeftShift(shiftedClip.fTop, shiftEdgesUp); 398 shiftedClip.fBottom = SkLeftShift(shiftedClip.fBottom, shiftEdgesUp); 399 400 SkEdgeBuilder builder; 401 int count = builder.build_edges(path, &shiftedClip, shiftEdgesUp, pathContainedInClip); 402 SkEdge** list = builder.edgeList(); 403 404 if (0 == count) { 405 if (path.isInverseFillType()) { 406 /* 407 * Since we are in inverse-fill, our caller has already drawn above 408 * our top (start_y) and will draw below our bottom (stop_y). Thus 409 * we need to restrict our drawing to the intersection of the clip 410 * and those two limits. 411 */ 412 SkIRect rect = clipRect; 413 if (rect.fTop < start_y) { 414 rect.fTop = start_y; 415 } 416 if (rect.fBottom > stop_y) { 417 rect.fBottom = stop_y; 418 } 419 if (!rect.isEmpty()) { 420 blitter->blitRect(rect.fLeft << shiftEdgesUp, 421 rect.fTop << shiftEdgesUp, 422 rect.width() << shiftEdgesUp, 423 rect.height() << shiftEdgesUp); 424 } 425 } 426 return; 427 } 428 429 SkEdge headEdge, tailEdge, *last; 430 // this returns the first and last edge after they're sorted into a dlink list 431 SkEdge* edge = sort_edges(list, count, &last); 432 433 headEdge.fPrev = nullptr; 434 headEdge.fNext = edge; 435 headEdge.fFirstY = kEDGE_HEAD_Y; 436 headEdge.fX = SK_MinS32; 437 edge->fPrev = &headEdge; 438 439 tailEdge.fPrev = last; 440 tailEdge.fNext = nullptr; 441 tailEdge.fFirstY = kEDGE_TAIL_Y; 442 last->fNext = &tailEdge; 443 444 // now edge is the head of the sorted linklist 445 446 start_y = SkLeftShift(start_y, shiftEdgesUp); 447 stop_y = SkLeftShift(stop_y, shiftEdgesUp); 448 if (!pathContainedInClip && start_y < shiftedClip.fTop) { 449 start_y = shiftedClip.fTop; 450 } 451 if (!pathContainedInClip && stop_y > shiftedClip.fBottom) { 452 stop_y = shiftedClip.fBottom; 453 } 454 455 InverseBlitter ib; 456 PrePostProc proc = nullptr; 457 458 if (path.isInverseFillType()) { 459 ib.setBlitter(blitter, clipRect, shiftEdgesUp); 460 blitter = &ib; 461 proc = PrePostInverseBlitterProc; 462 } 463 464 // count >= 2 is required as the convex walker does not handle missing right edges 465 if (path.isConvex() && (nullptr == proc) && count >= 2) { 466 walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, nullptr); 467 } else { 468 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc, 469 shiftedClip.right()); 470 } 471 } 472 473 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) { 474 const SkIRect& cr = clip.getBounds(); 475 SkIRect tmp; 476 477 tmp.fLeft = cr.fLeft; 478 tmp.fRight = cr.fRight; 479 tmp.fTop = cr.fTop; 480 tmp.fBottom = ir.fTop; 481 if (!tmp.isEmpty()) { 482 blitter->blitRectRegion(tmp, clip); 483 } 484 } 485 486 void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) { 487 const SkIRect& cr = clip.getBounds(); 488 SkIRect tmp; 489 490 tmp.fLeft = cr.fLeft; 491 tmp.fRight = cr.fRight; 492 tmp.fTop = ir.fBottom; 493 tmp.fBottom = cr.fBottom; 494 if (!tmp.isEmpty()) { 495 blitter->blitRectRegion(tmp, clip); 496 } 497 } 498 499 /////////////////////////////////////////////////////////////////////////////// 500 501 /** 502 * If the caller is drawing an inverse-fill path, then it pass true for 503 * skipRejectTest, so we don't abort drawing just because the src bounds (ir) 504 * is outside of the clip. 505 */ 506 SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip, 507 const SkIRect& ir, bool skipRejectTest, bool irPreClipped) { 508 fBlitter = nullptr; // null means blit nothing 509 fClipRect = nullptr; 510 511 if (clip) { 512 fClipRect = &clip->getBounds(); 513 if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out 514 return; 515 } 516 517 if (clip->isRect()) { 518 if (!irPreClipped && fClipRect->contains(ir)) { 519 #ifdef SK_DEBUG 520 fRectClipCheckBlitter.init(blitter, *fClipRect); 521 blitter = &fRectClipCheckBlitter; 522 #endif 523 fClipRect = nullptr; 524 } else { 525 // only need a wrapper blitter if we're horizontally clipped 526 if (irPreClipped || 527 fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) { 528 fRectBlitter.init(blitter, *fClipRect); 529 blitter = &fRectBlitter; 530 } else { 531 #ifdef SK_DEBUG 532 fRectClipCheckBlitter.init(blitter, *fClipRect); 533 blitter = &fRectClipCheckBlitter; 534 #endif 535 } 536 } 537 } else { 538 fRgnBlitter.init(blitter, clip); 539 blitter = &fRgnBlitter; 540 } 541 } 542 fBlitter = blitter; 543 } 544 545 /////////////////////////////////////////////////////////////////////////////// 546 547 static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) { 548 const int32_t limit = 32767; 549 550 SkIRect limitR; 551 limitR.set(-limit, -limit, limit, limit); 552 if (limitR.contains(orig.getBounds())) { 553 return false; 554 } 555 reduced->op(orig, limitR, SkRegion::kIntersect_Op); 556 return true; 557 } 558 559 /** 560 * Variants of SkScalarRoundToInt, identical to SkDScalarRoundToInt except when the input fraction 561 * is 0.5. When SK_RASTERIZE_EVEN_ROUNDING is enabled, we must bias the result before rounding to 562 * account for potential FDot6 rounding edge-cases. 563 */ 564 #ifdef SK_RASTERIZE_EVEN_ROUNDING 565 static const double kRoundBias = 0.5 / SK_FDot6One; 566 #else 567 static const double kRoundBias = 0.0; 568 #endif 569 570 /** 571 * Round the value down. This is used to round the top and left of a rectangle, 572 * and corresponds to the way the scan converter treats the top and left edges. 573 */ 574 static inline int round_down_to_int(SkScalar x) { 575 double xx = x; 576 xx -= 0.5 + kRoundBias; 577 return sk_double_saturate2int(ceil(xx)); 578 } 579 580 /** 581 * Round the value up. This is used to round the bottom and right of a rectangle, 582 * and corresponds to the way the scan converter treats the bottom and right edges. 583 */ 584 static inline int round_up_to_int(SkScalar x) { 585 double xx = x; 586 xx += 0.5 + kRoundBias; 587 return sk_double_saturate2int(floor(xx)); 588 } 589 590 /** 591 * Variant of SkRect::round() that explicitly performs the rounding step (i.e. floor(x + 0.5)) 592 * using double instead of SkScalar (float). It does this by calling SkDScalarRoundToInt(), 593 * which may be slower than calling SkScalarRountToInt(), but gives slightly more accurate 594 * results. Also rounds top and left using double, flooring when the fraction is exactly 0.5f. 595 * 596 * e.g. 597 * SkScalar left = 0.5f; 598 * int ileft = SkScalarRoundToInt(left); 599 * SkASSERT(0 == ileft); // <--- fails 600 * int ileft = round_down_to_int(left); 601 * SkASSERT(0 == ileft); // <--- succeeds 602 * SkScalar right = 0.49999997f; 603 * int iright = SkScalarRoundToInt(right); 604 * SkASSERT(0 == iright); // <--- fails 605 * iright = SkDScalarRoundToInt(right); 606 * SkASSERT(0 == iright); // <--- succeeds 607 * 608 * 609 * If using SK_RASTERIZE_EVEN_ROUNDING, we need to ensure we account for edges bounded by this 610 * rect being rounded to FDot6 format before being later rounded to an integer. For example, a 611 * value like 0.499 can be below 0.5, but round to 0.5 as FDot6, which would finally round to 612 * the integer 1, instead of just rounding to 0. 613 * 614 * To handle this, a small bias of half an FDot6 increment is added before actually rounding to 615 * an integer value. This simulates the rounding of SkScalarRoundToFDot6 without incurring the 616 * range loss of converting to FDot6 format first, preserving the integer range for the SkIRect. 617 * Thus, bottom and right are rounded in this manner (biased up), ensuring the rect is large 618 * enough. 619 */ 620 static void round_asymmetric_to_int(const SkRect& src, SkIRect* dst) { 621 SkASSERT(dst); 622 dst->set(round_down_to_int(src.fLeft), round_down_to_int(src.fTop), 623 round_up_to_int(src.fRight), round_up_to_int(src.fBottom)); 624 } 625 626 void SkScan::FillPath(const SkPath& path, const SkRegion& origClip, 627 SkBlitter* blitter) { 628 if (origClip.isEmpty()) { 629 return; 630 } 631 632 // Our edges are fixed-point, and don't like the bounds of the clip to 633 // exceed that. Here we trim the clip just so we don't overflow later on 634 const SkRegion* clipPtr = &origClip; 635 SkRegion finiteClip; 636 if (clip_to_limit(origClip, &finiteClip)) { 637 if (finiteClip.isEmpty()) { 638 return; 639 } 640 clipPtr = &finiteClip; 641 } 642 // don't reference "origClip" any more, just use clipPtr 643 644 645 SkRect bounds = path.getBounds(); 646 bool irPreClipped = false; 647 if (!SkRectPriv::MakeLargeS32().contains(bounds)) { 648 if (!bounds.intersect(SkRectPriv::MakeLargeS32())) { 649 bounds.setEmpty(); 650 } 651 irPreClipped = true; 652 } 653 SkIRect ir; 654 // We deliberately call round_asymmetric_to_int() instead of round(), since we can't afford 655 // to generate a bounds that is tighter than the corresponding SkEdges. The edge code basically 656 // converts the floats to fixed, and then "rounds". If we called round() instead of 657 // round_asymmetric_to_int() here, we could generate the wrong ir for values like 0.4999997. 658 round_asymmetric_to_int(bounds, &ir); 659 if (ir.isEmpty()) { 660 if (path.isInverseFillType()) { 661 blitter->blitRegion(*clipPtr); 662 } 663 return; 664 } 665 666 SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType(), irPreClipped); 667 668 blitter = clipper.getBlitter(); 669 if (blitter) { 670 // we have to keep our calls to blitter in sorted order, so we 671 // must blit the above section first, then the middle, then the bottom. 672 if (path.isInverseFillType()) { 673 sk_blit_above(blitter, ir, *clipPtr); 674 } 675 SkASSERT(clipper.getClipRect() == nullptr || 676 *clipper.getClipRect() == clipPtr->getBounds()); 677 sk_fill_path(path, clipPtr->getBounds(), blitter, ir.fTop, ir.fBottom, 678 0, clipper.getClipRect() == nullptr); 679 if (path.isInverseFillType()) { 680 sk_blit_below(blitter, ir, *clipPtr); 681 } 682 } else { 683 // what does it mean to not have a blitter if path.isInverseFillType??? 684 } 685 } 686 687 void SkScan::FillPath(const SkPath& path, const SkIRect& ir, 688 SkBlitter* blitter) { 689 SkRegion rgn(ir); 690 FillPath(path, rgn, blitter); 691 } 692 693 /////////////////////////////////////////////////////////////////////////////// 694 695 static int build_tri_edges(SkEdge edge[], const SkPoint pts[], 696 const SkIRect* clipRect, SkEdge* list[]) { 697 SkEdge** start = list; 698 699 if (edge->setLine(pts[0], pts[1], clipRect, 0)) { 700 *list++ = edge; 701 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 702 } 703 if (edge->setLine(pts[1], pts[2], clipRect, 0)) { 704 *list++ = edge; 705 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 706 } 707 if (edge->setLine(pts[2], pts[0], clipRect, 0)) { 708 *list++ = edge; 709 } 710 return (int)(list - start); 711 } 712 713 714 static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect, 715 SkBlitter* blitter, const SkIRect& ir) { 716 SkASSERT(pts && blitter); 717 718 SkEdge edgeStorage[3]; 719 SkEdge* list[3]; 720 721 int count = build_tri_edges(edgeStorage, pts, clipRect, list); 722 if (count < 2) { 723 return; 724 } 725 726 SkEdge headEdge, tailEdge, *last; 727 728 // this returns the first and last edge after they're sorted into a dlink list 729 SkEdge* edge = sort_edges(list, count, &last); 730 731 headEdge.fPrev = nullptr; 732 headEdge.fNext = edge; 733 headEdge.fFirstY = kEDGE_HEAD_Y; 734 headEdge.fX = SK_MinS32; 735 edge->fPrev = &headEdge; 736 737 tailEdge.fPrev = last; 738 tailEdge.fNext = nullptr; 739 tailEdge.fFirstY = kEDGE_TAIL_Y; 740 last->fNext = &tailEdge; 741 742 // now edge is the head of the sorted linklist 743 int stop_y = ir.fBottom; 744 if (clipRect && stop_y > clipRect->fBottom) { 745 stop_y = clipRect->fBottom; 746 } 747 int start_y = ir.fTop; 748 if (clipRect && start_y < clipRect->fTop) { 749 start_y = clipRect->fTop; 750 } 751 walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr); 752 // walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr); 753 } 754 755 void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip, 756 SkBlitter* blitter) { 757 if (clip.isEmpty()) { 758 return; 759 } 760 761 SkRect r; 762 r.set(pts, 3); 763 // If r is too large (larger than can easily fit in SkFixed) then we need perform geometric 764 // clipping. This is a bit of work, so we just call the general FillPath() to handle it. 765 // Use FixedMax/2 as the limit so we can subtract two edges and still store that in Fixed. 766 const SkScalar limit = SK_MaxS16 >> 1; 767 if (!SkRect::MakeLTRB(-limit, -limit, limit, limit).contains(r)) { 768 SkPath path; 769 path.addPoly(pts, 3, false); 770 FillPath(path, clip, blitter); 771 return; 772 } 773 774 SkIRect ir = r.round(); 775 if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) { 776 return; 777 } 778 779 SkAAClipBlitterWrapper wrap; 780 const SkRegion* clipRgn; 781 if (clip.isBW()) { 782 clipRgn = &clip.bwRgn(); 783 } else { 784 wrap.init(clip, blitter); 785 clipRgn = &wrap.getRgn(); 786 blitter = wrap.getBlitter(); 787 } 788 789 SkScanClipper clipper(blitter, clipRgn, ir); 790 blitter = clipper.getBlitter(); 791 if (blitter) { 792 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir); 793 } 794 } 795