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