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