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 401 // If we're convex, then we need both edges, even the right edge is past the clip 402 const bool canCullToTheRight = !path.isConvex(); 403 404 SkIRect* builderClip = pathContainedInClip ? nullptr : &shiftedClip; 405 int count = builder.build(path, builderClip, shiftEdgesUp, canCullToTheRight); 406 SkASSERT(count >= 0); 407 408 SkEdge** list = builder.edgeList(); 409 410 if (0 == count) { 411 if (path.isInverseFillType()) { 412 /* 413 * Since we are in inverse-fill, our caller has already drawn above 414 * our top (start_y) and will draw below our bottom (stop_y). Thus 415 * we need to restrict our drawing to the intersection of the clip 416 * and those two limits. 417 */ 418 SkIRect rect = clipRect; 419 if (rect.fTop < start_y) { 420 rect.fTop = start_y; 421 } 422 if (rect.fBottom > stop_y) { 423 rect.fBottom = stop_y; 424 } 425 if (!rect.isEmpty()) { 426 blitter->blitRect(rect.fLeft << shiftEdgesUp, 427 rect.fTop << shiftEdgesUp, 428 rect.width() << shiftEdgesUp, 429 rect.height() << shiftEdgesUp); 430 } 431 } 432 return; 433 } 434 435 SkEdge headEdge, tailEdge, *last; 436 // this returns the first and last edge after they're sorted into a dlink list 437 SkEdge* edge = sort_edges(list, count, &last); 438 439 headEdge.fPrev = nullptr; 440 headEdge.fNext = edge; 441 headEdge.fFirstY = kEDGE_HEAD_Y; 442 headEdge.fX = SK_MinS32; 443 edge->fPrev = &headEdge; 444 445 tailEdge.fPrev = last; 446 tailEdge.fNext = nullptr; 447 tailEdge.fFirstY = kEDGE_TAIL_Y; 448 last->fNext = &tailEdge; 449 450 // now edge is the head of the sorted linklist 451 452 start_y = SkLeftShift(start_y, shiftEdgesUp); 453 stop_y = SkLeftShift(stop_y, shiftEdgesUp); 454 if (!pathContainedInClip && start_y < shiftedClip.fTop) { 455 start_y = shiftedClip.fTop; 456 } 457 if (!pathContainedInClip && stop_y > shiftedClip.fBottom) { 458 stop_y = shiftedClip.fBottom; 459 } 460 461 InverseBlitter ib; 462 PrePostProc proc = nullptr; 463 464 if (path.isInverseFillType()) { 465 ib.setBlitter(blitter, clipRect, shiftEdgesUp); 466 blitter = &ib; 467 proc = PrePostInverseBlitterProc; 468 } 469 470 if (path.isConvex() && (nullptr == proc)) { 471 SkASSERT(count >= 2); // convex walker does not handle missing right edges 472 walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, nullptr); 473 } else { 474 walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc, 475 shiftedClip.right()); 476 } 477 } 478 479 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) { 480 const SkIRect& cr = clip.getBounds(); 481 SkIRect tmp; 482 483 tmp.fLeft = cr.fLeft; 484 tmp.fRight = cr.fRight; 485 tmp.fTop = cr.fTop; 486 tmp.fBottom = ir.fTop; 487 if (!tmp.isEmpty()) { 488 blitter->blitRectRegion(tmp, clip); 489 } 490 } 491 492 void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) { 493 const SkIRect& cr = clip.getBounds(); 494 SkIRect tmp; 495 496 tmp.fLeft = cr.fLeft; 497 tmp.fRight = cr.fRight; 498 tmp.fTop = ir.fBottom; 499 tmp.fBottom = cr.fBottom; 500 if (!tmp.isEmpty()) { 501 blitter->blitRectRegion(tmp, clip); 502 } 503 } 504 505 /////////////////////////////////////////////////////////////////////////////// 506 507 /** 508 * If the caller is drawing an inverse-fill path, then it pass true for 509 * skipRejectTest, so we don't abort drawing just because the src bounds (ir) 510 * is outside of the clip. 511 */ 512 SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip, 513 const SkIRect& ir, bool skipRejectTest) { 514 fBlitter = nullptr; // null means blit nothing 515 fClipRect = nullptr; 516 517 if (clip) { 518 fClipRect = &clip->getBounds(); 519 if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out 520 return; 521 } 522 523 if (clip->isRect()) { 524 if (fClipRect->contains(ir)) { 525 #ifdef SK_DEBUG 526 fRectClipCheckBlitter.init(blitter, *fClipRect); 527 blitter = &fRectClipCheckBlitter; 528 #endif 529 fClipRect = nullptr; 530 } else { 531 // only need a wrapper blitter if we're horizontally clipped 532 if (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 /** 565 * Variants of SkScalarRoundToInt, identical to SkDScalarRoundToInt except when the input fraction 566 * is 0.5. When SK_RASTERIZE_EVEN_ROUNDING is enabled, we must bias the result before rounding to 567 * account for potential FDot6 rounding edge-cases. 568 */ 569 #ifdef SK_RASTERIZE_EVEN_ROUNDING 570 static const double kRoundBias = 0.5 / SK_FDot6One; 571 #else 572 static const double kRoundBias = 0.0; 573 #endif 574 575 /** 576 * Round the value down. This is used to round the top and left of a rectangle, 577 * and corresponds to the way the scan converter treats the top and left edges. 578 */ 579 static inline int round_down_to_int(SkScalar x) { 580 double xx = x; 581 xx -= 0.5 + kRoundBias; 582 return (int)ceil(xx); 583 } 584 585 /** 586 * Round the value up. This is used to round the bottom and right of a rectangle, 587 * and corresponds to the way the scan converter treats the bottom and right edges. 588 */ 589 static inline int round_up_to_int(SkScalar x) { 590 double xx = x; 591 xx += 0.5 + kRoundBias; 592 return (int)floor(xx); 593 } 594 595 /** 596 * Variant of SkRect::round() that explicitly performs the rounding step (i.e. floor(x + 0.5)) 597 * using double instead of SkScalar (float). It does this by calling SkDScalarRoundToInt(), 598 * which may be slower than calling SkScalarRountToInt(), but gives slightly more accurate 599 * results. Also rounds top and left using double, flooring when the fraction is exactly 0.5f. 600 * 601 * e.g. 602 * SkScalar left = 0.5f; 603 * int ileft = SkScalarRoundToInt(left); 604 * SkASSERT(0 == ileft); // <--- fails 605 * int ileft = round_down_to_int(left); 606 * SkASSERT(0 == ileft); // <--- succeeds 607 * SkScalar right = 0.49999997f; 608 * int iright = SkScalarRoundToInt(right); 609 * SkASSERT(0 == iright); // <--- fails 610 * iright = SkDScalarRoundToInt(right); 611 * SkASSERT(0 == iright); // <--- succeeds 612 * 613 * 614 * If using SK_RASTERIZE_EVEN_ROUNDING, we need to ensure we account for edges bounded by this 615 * rect being rounded to FDot6 format before being later rounded to an integer. For example, a 616 * value like 0.499 can be below 0.5, but round to 0.5 as FDot6, which would finally round to 617 * the integer 1, instead of just rounding to 0. 618 * 619 * To handle this, a small bias of half an FDot6 increment is added before actually rounding to 620 * an integer value. This simulates the rounding of SkScalarRoundToFDot6 without incurring the 621 * range loss of converting to FDot6 format first, preserving the integer range for the SkIRect. 622 * Thus, bottom and right are rounded in this manner (biased up), ensuring the rect is large 623 * enough. 624 */ 625 static void round_asymmetric_to_int(const SkRect& src, SkIRect* dst) { 626 SkASSERT(dst); 627 dst->set(round_down_to_int(src.fLeft), round_down_to_int(src.fTop), 628 round_up_to_int(src.fRight), round_up_to_int(src.fBottom)); 629 } 630 631 void SkScan::FillPath(const SkPath& path, const SkRegion& origClip, 632 SkBlitter* blitter) { 633 if (origClip.isEmpty()) { 634 return; 635 } 636 637 // Our edges are fixed-point, and don't like the bounds of the clip to 638 // exceed that. Here we trim the clip just so we don't overflow later on 639 const SkRegion* clipPtr = &origClip; 640 SkRegion finiteClip; 641 if (clip_to_limit(origClip, &finiteClip)) { 642 if (finiteClip.isEmpty()) { 643 return; 644 } 645 clipPtr = &finiteClip; 646 } 647 // don't reference "origClip" any more, just use clipPtr 648 649 SkIRect ir; 650 // We deliberately call round_asymmetric_to_int() instead of round(), since we can't afford 651 // to generate a bounds that is tighter than the corresponding SkEdges. The edge code basically 652 // converts the floats to fixed, and then "rounds". If we called round() instead of 653 // round_asymmetric_to_int() here, we could generate the wrong ir for values like 0.4999997. 654 round_asymmetric_to_int(path.getBounds(), &ir); 655 if (ir.isEmpty()) { 656 if (path.isInverseFillType()) { 657 blitter->blitRegion(*clipPtr); 658 } 659 return; 660 } 661 662 SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType()); 663 664 blitter = clipper.getBlitter(); 665 if (blitter) { 666 // we have to keep our calls to blitter in sorted order, so we 667 // must blit the above section first, then the middle, then the bottom. 668 if (path.isInverseFillType()) { 669 sk_blit_above(blitter, ir, *clipPtr); 670 } 671 SkASSERT(clipper.getClipRect() == nullptr || 672 *clipper.getClipRect() == clipPtr->getBounds()); 673 sk_fill_path(path, clipPtr->getBounds(), blitter, ir.fTop, ir.fBottom, 674 0, clipper.getClipRect() == nullptr); 675 if (path.isInverseFillType()) { 676 sk_blit_below(blitter, ir, *clipPtr); 677 } 678 } else { 679 // what does it mean to not have a blitter if path.isInverseFillType??? 680 } 681 } 682 683 void SkScan::FillPath(const SkPath& path, const SkIRect& ir, 684 SkBlitter* blitter) { 685 SkRegion rgn(ir); 686 FillPath(path, rgn, blitter); 687 } 688 689 /////////////////////////////////////////////////////////////////////////////// 690 691 static int build_tri_edges(SkEdge edge[], const SkPoint pts[], 692 const SkIRect* clipRect, SkEdge* list[]) { 693 SkEdge** start = list; 694 695 if (edge->setLine(pts[0], pts[1], clipRect, 0)) { 696 *list++ = edge; 697 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 698 } 699 if (edge->setLine(pts[1], pts[2], clipRect, 0)) { 700 *list++ = edge; 701 edge = (SkEdge*)((char*)edge + sizeof(SkEdge)); 702 } 703 if (edge->setLine(pts[2], pts[0], clipRect, 0)) { 704 *list++ = edge; 705 } 706 return (int)(list - start); 707 } 708 709 710 static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect, 711 SkBlitter* blitter, const SkIRect& ir) { 712 SkASSERT(pts && blitter); 713 714 SkEdge edgeStorage[3]; 715 SkEdge* list[3]; 716 717 int count = build_tri_edges(edgeStorage, pts, clipRect, list); 718 if (count < 2) { 719 return; 720 } 721 722 SkEdge headEdge, tailEdge, *last; 723 724 // this returns the first and last edge after they're sorted into a dlink list 725 SkEdge* edge = sort_edges(list, count, &last); 726 727 headEdge.fPrev = nullptr; 728 headEdge.fNext = edge; 729 headEdge.fFirstY = kEDGE_HEAD_Y; 730 headEdge.fX = SK_MinS32; 731 edge->fPrev = &headEdge; 732 733 tailEdge.fPrev = last; 734 tailEdge.fNext = nullptr; 735 tailEdge.fFirstY = kEDGE_TAIL_Y; 736 last->fNext = &tailEdge; 737 738 // now edge is the head of the sorted linklist 739 int stop_y = ir.fBottom; 740 if (clipRect && stop_y > clipRect->fBottom) { 741 stop_y = clipRect->fBottom; 742 } 743 int start_y = ir.fTop; 744 if (clipRect && start_y < clipRect->fTop) { 745 start_y = clipRect->fTop; 746 } 747 walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr); 748 // walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr); 749 } 750 751 void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip, 752 SkBlitter* blitter) { 753 if (clip.isEmpty()) { 754 return; 755 } 756 757 SkRect r; 758 SkIRect ir; 759 r.set(pts, 3); 760 r.round(&ir); 761 if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) { 762 return; 763 } 764 765 SkAAClipBlitterWrapper wrap; 766 const SkRegion* clipRgn; 767 if (clip.isBW()) { 768 clipRgn = &clip.bwRgn(); 769 } else { 770 wrap.init(clip, blitter); 771 clipRgn = &wrap.getRgn(); 772 blitter = wrap.getBlitter(); 773 } 774 775 SkScanClipper clipper(blitter, clipRgn, ir); 776 blitter = clipper.getBlitter(); 777 if (blitter) { 778 sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir); 779 } 780 } 781