src/third_party/skia/src/core/SkScan_Path.cpp

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