michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkScanPriv.h"
michael@0: #include "SkBlitter.h"
michael@0: #include "SkEdge.h"
michael@0: #include "SkEdgeBuilder.h"
michael@0: #include "SkGeometry.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkQuadClipper.h"
michael@0: #include "SkRasterClip.h"
michael@0: #include "SkRegion.h"
michael@0: #include "SkTemplates.h"
michael@0: #include "SkTSort.h"
michael@0: 
michael@0: #ifdef SK_USE_LEGACY_AA_COVERAGE
michael@0:     #define SK_USE_STD_SORT_FOR_EDGES
michael@0: #endif
michael@0: 
michael@0: #define kEDGE_HEAD_Y    SK_MinS32
michael@0: #define kEDGE_TAIL_Y    SK_MaxS32
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     static void validate_sort(const SkEdge* edge) {
michael@0:         int y = kEDGE_HEAD_Y;
michael@0: 
michael@0:         while (edge->fFirstY != SK_MaxS32) {
michael@0:             edge->validate();
michael@0:             SkASSERT(y <= edge->fFirstY);
michael@0: 
michael@0:             y = edge->fFirstY;
michael@0:             edge = edge->fNext;
michael@0:         }
michael@0:     }
michael@0: #else
michael@0:     #define validate_sort(edge)
michael@0: #endif
michael@0: 
michael@0: static inline void remove_edge(SkEdge* edge) {
michael@0:     edge->fPrev->fNext = edge->fNext;
michael@0:     edge->fNext->fPrev = edge->fPrev;
michael@0: }
michael@0: 
michael@0: static inline void swap_edges(SkEdge* prev, SkEdge* next) {
michael@0:     SkASSERT(prev->fNext == next && next->fPrev == prev);
michael@0: 
michael@0:     // remove prev from the list
michael@0:     prev->fPrev->fNext = next;
michael@0:     next->fPrev = prev->fPrev;
michael@0: 
michael@0:     // insert prev after next
michael@0:     prev->fNext = next->fNext;
michael@0:     next->fNext->fPrev = prev;
michael@0:     next->fNext = prev;
michael@0:     prev->fPrev = next;
michael@0: }
michael@0: 
michael@0: static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, curr_y)) {
michael@0:     SkFixed x = edge->fX;
michael@0: 
michael@0:     for (;;) {
michael@0:         SkEdge* prev = edge->fPrev;
michael@0: 
michael@0:         // add 1 to curr_y since we may have added new edges (built from curves)
michael@0:         // that start on the next scanline
michael@0:         SkASSERT(prev && prev->fFirstY <= curr_y + 1);
michael@0: 
michael@0:         if (prev->fX <= x) {
michael@0:             break;
michael@0:         }
michael@0:         swap_edges(prev, edge);
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void insert_new_edges(SkEdge* newEdge, int curr_y) {
michael@0:     SkASSERT(newEdge->fFirstY >= curr_y);
michael@0: 
michael@0:     while (newEdge->fFirstY == curr_y) {
michael@0:         SkEdge* next = newEdge->fNext;
michael@0:         backward_insert_edge_based_on_x(newEdge  SkPARAM(curr_y));
michael@0:         newEdge = next;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: static void validate_edges_for_y(const SkEdge* edge, int curr_y) {
michael@0:     while (edge->fFirstY <= curr_y) {
michael@0:         SkASSERT(edge->fPrev && edge->fNext);
michael@0:         SkASSERT(edge->fPrev->fNext == edge);
michael@0:         SkASSERT(edge->fNext->fPrev == edge);
michael@0:         SkASSERT(edge->fFirstY <= edge->fLastY);
michael@0: 
michael@0:         SkASSERT(edge->fPrev->fX <= edge->fX);
michael@0:         edge = edge->fNext;
michael@0:     }
michael@0: }
michael@0: #else
michael@0:     #define validate_edges_for_y(edge, curr_y)
michael@0: #endif
michael@0: 
michael@0: #if defined _WIN32 && _MSC_VER >= 1300  // disable warning : local variable used without having been initialized
michael@0: #pragma warning ( push )
michael@0: #pragma warning ( disable : 4701 )
michael@0: #endif
michael@0: 
michael@0: typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
michael@0: #define PREPOST_START   true
michael@0: #define PREPOST_END     false
michael@0: 
michael@0: static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType,
michael@0:                        SkBlitter* blitter, int start_y, int stop_y,
michael@0:                        PrePostProc proc) {
michael@0:     validate_sort(prevHead->fNext);
michael@0: 
michael@0:     int curr_y = start_y;
michael@0:     // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
michael@0:     int windingMask = (fillType & 1) ? 1 : -1;
michael@0: 
michael@0:     for (;;) {
michael@0:         int     w = 0;
michael@0:         int     left SK_INIT_TO_AVOID_WARNING;
michael@0:         bool    in_interval = false;
michael@0:         SkEdge* currE = prevHead->fNext;
michael@0:         SkFixed prevX = prevHead->fX;
michael@0: 
michael@0:         validate_edges_for_y(currE, curr_y);
michael@0: 
michael@0:         if (proc) {
michael@0:             proc(blitter, curr_y, PREPOST_START);    // pre-proc
michael@0:         }
michael@0: 
michael@0:         while (currE->fFirstY <= curr_y) {
michael@0:             SkASSERT(currE->fLastY >= curr_y);
michael@0: 
michael@0:             int x = SkFixedRoundToInt(currE->fX);
michael@0:             w += currE->fWinding;
michael@0:             if ((w & windingMask) == 0) { // we finished an interval
michael@0:                 SkASSERT(in_interval);
michael@0:                 int width = x - left;
michael@0:                 SkASSERT(width >= 0);
michael@0:                 if (width)
michael@0:                     blitter->blitH(left, curr_y, width);
michael@0:                 in_interval = false;
michael@0:             } else if (!in_interval) {
michael@0:                 left = x;
michael@0:                 in_interval = true;
michael@0:             }
michael@0: 
michael@0:             SkEdge* next = currE->fNext;
michael@0:             SkFixed newX;
michael@0: 
michael@0:             if (currE->fLastY == curr_y) {    // are we done with this edge?
michael@0:                 if (currE->fCurveCount < 0) {
michael@0:                     if (((SkCubicEdge*)currE)->updateCubic()) {
michael@0:                         SkASSERT(currE->fFirstY == curr_y + 1);
michael@0: 
michael@0:                         newX = currE->fX;
michael@0:                         goto NEXT_X;
michael@0:                     }
michael@0:                 } else if (currE->fCurveCount > 0) {
michael@0:                     if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
michael@0:                         newX = currE->fX;
michael@0:                         goto NEXT_X;
michael@0:                     }
michael@0:                 }
michael@0:                 remove_edge(currE);
michael@0:             } else {
michael@0:                 SkASSERT(currE->fLastY > curr_y);
michael@0:                 newX = currE->fX + currE->fDX;
michael@0:                 currE->fX = newX;
michael@0:             NEXT_X:
michael@0:                 if (newX < prevX) { // ripple currE backwards until it is x-sorted
michael@0:                     backward_insert_edge_based_on_x(currE  SkPARAM(curr_y));
michael@0:                 } else {
michael@0:                     prevX = newX;
michael@0:                 }
michael@0:             }
michael@0:             currE = next;
michael@0:             SkASSERT(currE);
michael@0:         }
michael@0: 
michael@0:         if (proc) {
michael@0:             proc(blitter, curr_y, PREPOST_END);    // post-proc
michael@0:         }
michael@0: 
michael@0:         curr_y += 1;
michael@0:         if (curr_y >= stop_y) {
michael@0:             break;
michael@0:         }
michael@0:         // now currE points to the first edge with a Yint larger than curr_y
michael@0:         insert_new_edges(currE, curr_y);
michael@0:     }
michael@0: }
michael@0: 
michael@0: // return true if we're done with this edge
michael@0: static bool update_edge(SkEdge* edge, int last_y) {
michael@0:     SkASSERT(edge->fLastY >= last_y);
michael@0:     if (last_y == edge->fLastY) {
michael@0:         if (edge->fCurveCount < 0) {
michael@0:             if (((SkCubicEdge*)edge)->updateCubic()) {
michael@0:                 SkASSERT(edge->fFirstY == last_y + 1);
michael@0:                 return false;
michael@0:             }
michael@0:         } else if (edge->fCurveCount > 0) {
michael@0:             if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
michael@0:                 SkASSERT(edge->fFirstY == last_y + 1);
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: static void walk_convex_edges(SkEdge* prevHead, SkPath::FillType,
michael@0:                               SkBlitter* blitter, int start_y, int stop_y,
michael@0:                               PrePostProc proc) {
michael@0:     validate_sort(prevHead->fNext);
michael@0: 
michael@0:     SkEdge* leftE = prevHead->fNext;
michael@0:     SkEdge* riteE = leftE->fNext;
michael@0:     SkEdge* currE = riteE->fNext;
michael@0: 
michael@0: #if 0
michael@0:     int local_top = leftE->fFirstY;
michael@0:     SkASSERT(local_top == riteE->fFirstY);
michael@0: #else
michael@0:     // our edge choppers for curves can result in the initial edges
michael@0:     // not lining up, so we take the max.
michael@0:     int local_top = SkMax32(leftE->fFirstY, riteE->fFirstY);
michael@0: #endif
michael@0:     SkASSERT(local_top >= start_y);
michael@0: 
michael@0:     for (;;) {
michael@0:         SkASSERT(leftE->fFirstY <= stop_y);
michael@0:         SkASSERT(riteE->fFirstY <= stop_y);
michael@0: 
michael@0:         if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX &&
michael@0:                                       leftE->fDX > riteE->fDX)) {
michael@0:             SkTSwap(leftE, riteE);
michael@0:         }
michael@0: 
michael@0:         int local_bot = SkMin32(leftE->fLastY, riteE->fLastY);
michael@0:         local_bot = SkMin32(local_bot, stop_y - 1);
michael@0:         SkASSERT(local_top <= local_bot);
michael@0: 
michael@0:         SkFixed left = leftE->fX;
michael@0:         SkFixed dLeft = leftE->fDX;
michael@0:         SkFixed rite = riteE->fX;
michael@0:         SkFixed dRite = riteE->fDX;
michael@0:         int count = local_bot - local_top;
michael@0:         SkASSERT(count >= 0);
michael@0:         if (0 == (dLeft | dRite)) {
michael@0:             int L = SkFixedRoundToInt(left);
michael@0:             int R = SkFixedRoundToInt(rite);
michael@0:             if (L < R) {
michael@0:                 count += 1;
michael@0:                 blitter->blitRect(L, local_top, R - L, count);
michael@0:                 left += count * dLeft;
michael@0:                 rite += count * dRite;
michael@0:             }
michael@0:             local_top = local_bot + 1;
michael@0:         } else {
michael@0:             do {
michael@0:                 int L = SkFixedRoundToInt(left);
michael@0:                 int R = SkFixedRoundToInt(rite);
michael@0:                 if (L < R) {
michael@0:                     blitter->blitH(L, local_top, R - L);
michael@0:                 }
michael@0:                 left += dLeft;
michael@0:                 rite += dRite;
michael@0:                 local_top += 1;
michael@0:             } while (--count >= 0);
michael@0:         }
michael@0: 
michael@0:         leftE->fX = left;
michael@0:         riteE->fX = rite;
michael@0: 
michael@0:         if (update_edge(leftE, local_bot)) {
michael@0:             if (currE->fFirstY >= stop_y) {
michael@0:                 break;
michael@0:             }
michael@0:             leftE = currE;
michael@0:             currE = currE->fNext;
michael@0:         }
michael@0:         if (update_edge(riteE, local_bot)) {
michael@0:             if (currE->fFirstY >= stop_y) {
michael@0:                 break;
michael@0:             }
michael@0:             riteE = currE;
michael@0:             currE = currE->fNext;
michael@0:         }
michael@0: 
michael@0:         SkASSERT(leftE);
michael@0:         SkASSERT(riteE);
michael@0: 
michael@0:         // check our bottom clip
michael@0:         SkASSERT(local_top == local_bot + 1);
michael@0:         if (local_top >= stop_y) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // this guy overrides blitH, and will call its proxy blitter with the inverse
michael@0: // of the spans it is given (clipped to the left/right of the cliprect)
michael@0: //
michael@0: // used to implement inverse filltypes on paths
michael@0: //
michael@0: class InverseBlitter : public SkBlitter {
michael@0: public:
michael@0:     void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) {
michael@0:         fBlitter = blitter;
michael@0:         fFirstX = clip.fLeft << shift;
michael@0:         fLastX = clip.fRight << shift;
michael@0:     }
michael@0:     void prepost(int y, bool isStart) {
michael@0:         if (isStart) {
michael@0:             fPrevX = fFirstX;
michael@0:         } else {
michael@0:             int invWidth = fLastX - fPrevX;
michael@0:             if (invWidth > 0) {
michael@0:                 fBlitter->blitH(fPrevX, y, invWidth);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // overrides
michael@0:     virtual void blitH(int x, int y, int width) {
michael@0:         int invWidth = x - fPrevX;
michael@0:         if (invWidth > 0) {
michael@0:             fBlitter->blitH(fPrevX, y, invWidth);
michael@0:         }
michael@0:         fPrevX = x + width;
michael@0:     }
michael@0: 
michael@0:     // we do not expect to get called with these entrypoints
michael@0:     virtual void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) {
michael@0:         SkDEBUGFAIL("blitAntiH unexpected");
michael@0:     }
michael@0:     virtual void blitV(int x, int y, int height, SkAlpha alpha) {
michael@0:         SkDEBUGFAIL("blitV unexpected");
michael@0:     }
michael@0:     virtual void blitRect(int x, int y, int width, int height) {
michael@0:         SkDEBUGFAIL("blitRect unexpected");
michael@0:     }
michael@0:     virtual void blitMask(const SkMask&, const SkIRect& clip) {
michael@0:         SkDEBUGFAIL("blitMask unexpected");
michael@0:     }
michael@0:     virtual const SkBitmap* justAnOpaqueColor(uint32_t* value) {
michael@0:         SkDEBUGFAIL("justAnOpaqueColor unexpected");
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     SkBlitter*  fBlitter;
michael@0:     int         fFirstX, fLastX, fPrevX;
michael@0: };
michael@0: 
michael@0: static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) {
michael@0:     ((InverseBlitter*)blitter)->prepost(y, isStart);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #if defined _WIN32 && _MSC_VER >= 1300
michael@0: #pragma warning ( pop )
michael@0: #endif
michael@0: 
michael@0: #ifdef SK_USE_STD_SORT_FOR_EDGES
michael@0: extern "C" {
michael@0:     static int edge_compare(const void* a, const void* b) {
michael@0:         const SkEdge* edgea = *(const SkEdge**)a;
michael@0:         const SkEdge* edgeb = *(const SkEdge**)b;
michael@0: 
michael@0:         int valuea = edgea->fFirstY;
michael@0:         int valueb = edgeb->fFirstY;
michael@0: 
michael@0:         if (valuea == valueb) {
michael@0:             valuea = edgea->fX;
michael@0:             valueb = edgeb->fX;
michael@0:         }
michael@0: 
michael@0:         // this overflows if valuea >>> valueb or vice-versa
michael@0:         //     return valuea - valueb;
michael@0:         // do perform the slower but safe compares
michael@0:         return (valuea < valueb) ? -1 : (valuea > valueb);
michael@0:     }
michael@0: }
michael@0: #else
michael@0: static bool operator<(const SkEdge& a, const SkEdge& b) {
michael@0:     int valuea = a.fFirstY;
michael@0:     int valueb = b.fFirstY;
michael@0: 
michael@0:     if (valuea == valueb) {
michael@0:         valuea = a.fX;
michael@0:         valueb = b.fX;
michael@0:     }
michael@0: 
michael@0:     return valuea < valueb;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
michael@0: #ifdef SK_USE_STD_SORT_FOR_EDGES
michael@0:     qsort(list, count, sizeof(SkEdge*), edge_compare);
michael@0: #else
michael@0:     SkTQSort(list, list + count - 1);
michael@0: #endif
michael@0: 
michael@0:     // now make the edges linked in sorted order
michael@0:     for (int i = 1; i < count; i++) {
michael@0:         list[i - 1]->fNext = list[i];
michael@0:         list[i]->fPrev = list[i - 1];
michael@0:     }
michael@0: 
michael@0:     *last = list[count - 1];
michael@0:     return list[0];
michael@0: }
michael@0: 
michael@0: // clipRect may be null, even though we always have a clip. This indicates that
michael@0: // the path is contained in the clip, and so we can ignore it during the blit
michael@0: //
michael@0: // clipRect (if no null) has already been shifted up
michael@0: //
michael@0: void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitter,
michael@0:                   int start_y, int stop_y, int shiftEdgesUp,
michael@0:                   const SkRegion& clipRgn) {
michael@0:     SkASSERT(&path && blitter);
michael@0: 
michael@0:     SkEdgeBuilder   builder;
michael@0: 
michael@0:     int count = builder.build(path, clipRect, shiftEdgesUp);
michael@0:     SkEdge**    list = builder.edgeList();
michael@0: 
michael@0:     if (count < 2) {
michael@0:         if (path.isInverseFillType()) {
michael@0:             /*
michael@0:              *  Since we are in inverse-fill, our caller has already drawn above
michael@0:              *  our top (start_y) and will draw below our bottom (stop_y). Thus
michael@0:              *  we need to restrict our drawing to the intersection of the clip
michael@0:              *  and those two limits.
michael@0:              */
michael@0:             SkIRect rect = clipRgn.getBounds();
michael@0:             if (rect.fTop < start_y) {
michael@0:                 rect.fTop = start_y;
michael@0:             }
michael@0:             if (rect.fBottom > stop_y) {
michael@0:                 rect.fBottom = stop_y;
michael@0:             }
michael@0:             if (!rect.isEmpty()) {
michael@0:                 blitter->blitRect(rect.fLeft << shiftEdgesUp,
michael@0:                                   rect.fTop << shiftEdgesUp,
michael@0:                                   rect.width() << shiftEdgesUp,
michael@0:                                   rect.height() << shiftEdgesUp);
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkEdge headEdge, tailEdge, *last;
michael@0:     // this returns the first and last edge after they're sorted into a dlink list
michael@0:     SkEdge* edge = sort_edges(list, count, &last);
michael@0: 
michael@0:     headEdge.fPrev = NULL;
michael@0:     headEdge.fNext = edge;
michael@0:     headEdge.fFirstY = kEDGE_HEAD_Y;
michael@0:     headEdge.fX = SK_MinS32;
michael@0:     edge->fPrev = &headEdge;
michael@0: 
michael@0:     tailEdge.fPrev = last;
michael@0:     tailEdge.fNext = NULL;
michael@0:     tailEdge.fFirstY = kEDGE_TAIL_Y;
michael@0:     last->fNext = &tailEdge;
michael@0: 
michael@0:     // now edge is the head of the sorted linklist
michael@0: 
michael@0:     start_y <<= shiftEdgesUp;
michael@0:     stop_y <<= shiftEdgesUp;
michael@0:     if (clipRect && start_y < clipRect->fTop) {
michael@0:         start_y = clipRect->fTop;
michael@0:     }
michael@0:     if (clipRect && stop_y > clipRect->fBottom) {
michael@0:         stop_y = clipRect->fBottom;
michael@0:     }
michael@0: 
michael@0:     InverseBlitter  ib;
michael@0:     PrePostProc     proc = NULL;
michael@0: 
michael@0:     if (path.isInverseFillType()) {
michael@0:         ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp);
michael@0:         blitter = &ib;
michael@0:         proc = PrePostInverseBlitterProc;
michael@0:     }
michael@0: 
michael@0:     if (path.isConvex() && (NULL == proc)) {
michael@0:         walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, NULL);
michael@0:     } else {
michael@0:         walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
michael@0:     const SkIRect& cr = clip.getBounds();
michael@0:     SkIRect tmp;
michael@0: 
michael@0:     tmp.fLeft = cr.fLeft;
michael@0:     tmp.fRight = cr.fRight;
michael@0:     tmp.fTop = cr.fTop;
michael@0:     tmp.fBottom = ir.fTop;
michael@0:     if (!tmp.isEmpty()) {
michael@0:         blitter->blitRectRegion(tmp, clip);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
michael@0:     const SkIRect& cr = clip.getBounds();
michael@0:     SkIRect tmp;
michael@0: 
michael@0:     tmp.fLeft = cr.fLeft;
michael@0:     tmp.fRight = cr.fRight;
michael@0:     tmp.fTop = ir.fBottom;
michael@0:     tmp.fBottom = cr.fBottom;
michael@0:     if (!tmp.isEmpty()) {
michael@0:         blitter->blitRectRegion(tmp, clip);
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /**
michael@0:  *  If the caller is drawing an inverse-fill path, then it pass true for
michael@0:  *  skipRejectTest, so we don't abort drawing just because the src bounds (ir)
michael@0:  *  is outside of the clip.
michael@0:  */
michael@0: SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip,
michael@0:                              const SkIRect& ir, bool skipRejectTest) {
michael@0:     fBlitter = NULL;     // null means blit nothing
michael@0:     fClipRect = NULL;
michael@0: 
michael@0:     if (clip) {
michael@0:         fClipRect = &clip->getBounds();
michael@0:         if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         if (clip->isRect()) {
michael@0:             if (fClipRect->contains(ir)) {
michael@0:                 fClipRect = NULL;
michael@0:             } else {
michael@0:                 // only need a wrapper blitter if we're horizontally clipped
michael@0:                 if (fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
michael@0:                     fRectBlitter.init(blitter, *fClipRect);
michael@0:                     blitter = &fRectBlitter;
michael@0:                 }
michael@0:             }
michael@0:         } else {
michael@0:             fRgnBlitter.init(blitter, clip);
michael@0:             blitter = &fRgnBlitter;
michael@0:         }
michael@0:     }
michael@0:     fBlitter = blitter;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) {
michael@0:     const int32_t limit = 32767;
michael@0: 
michael@0:     SkIRect limitR;
michael@0:     limitR.set(-limit, -limit, limit, limit);
michael@0:     if (limitR.contains(orig.getBounds())) {
michael@0:         return false;
michael@0:     }
michael@0:     reduced->op(orig, limitR, SkRegion::kIntersect_Op);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkScan::FillPath(const SkPath& path, const SkRegion& origClip,
michael@0:                       SkBlitter* blitter) {
michael@0:     if (origClip.isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Our edges are fixed-point, and don't like the bounds of the clip to
michael@0:     // exceed that. Here we trim the clip just so we don't overflow later on
michael@0:     const SkRegion* clipPtr = &origClip;
michael@0:     SkRegion finiteClip;
michael@0:     if (clip_to_limit(origClip, &finiteClip)) {
michael@0:         if (finiteClip.isEmpty()) {
michael@0:             return;
michael@0:         }
michael@0:         clipPtr = &finiteClip;
michael@0:     }
michael@0:         // don't reference "origClip" any more, just use clipPtr
michael@0: 
michael@0:     SkIRect ir;
michael@0:     path.getBounds().roundOut(&ir);
michael@0:     if (ir.isEmpty()) {
michael@0:         if (path.isInverseFillType()) {
michael@0:             blitter->blitRegion(*clipPtr);
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType());
michael@0: 
michael@0:     blitter = clipper.getBlitter();
michael@0:     if (blitter) {
michael@0:         // we have to keep our calls to blitter in sorted order, so we
michael@0:         // must blit the above section first, then the middle, then the bottom.
michael@0:         if (path.isInverseFillType()) {
michael@0:             sk_blit_above(blitter, ir, *clipPtr);
michael@0:         }
michael@0:         sk_fill_path(path, clipper.getClipRect(), blitter, ir.fTop, ir.fBottom,
michael@0:                      0, *clipPtr);
michael@0:         if (path.isInverseFillType()) {
michael@0:             sk_blit_below(blitter, ir, *clipPtr);
michael@0:         }
michael@0:     } else {
michael@0:         // what does it mean to not have a blitter if path.isInverseFillType???
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
michael@0:                       SkBlitter* blitter) {
michael@0:     SkRegion rgn(ir);
michael@0:     FillPath(path, rgn, blitter);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static int build_tri_edges(SkEdge edge[], const SkPoint pts[],
michael@0:                            const SkIRect* clipRect, SkEdge* list[]) {
michael@0:     SkEdge** start = list;
michael@0: 
michael@0:     if (edge->setLine(pts[0], pts[1], clipRect, 0)) {
michael@0:         *list++ = edge;
michael@0:         edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
michael@0:     }
michael@0:     if (edge->setLine(pts[1], pts[2], clipRect, 0)) {
michael@0:         *list++ = edge;
michael@0:         edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
michael@0:     }
michael@0:     if (edge->setLine(pts[2], pts[0], clipRect, 0)) {
michael@0:         *list++ = edge;
michael@0:     }
michael@0:     return (int)(list - start);
michael@0: }
michael@0: 
michael@0: 
michael@0: static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect,
michael@0:                              SkBlitter* blitter, const SkIRect& ir) {
michael@0:     SkASSERT(pts && blitter);
michael@0: 
michael@0:     SkEdge edgeStorage[3];
michael@0:     SkEdge* list[3];
michael@0: 
michael@0:     int count = build_tri_edges(edgeStorage, pts, clipRect, list);
michael@0:     if (count < 2) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkEdge headEdge, tailEdge, *last;
michael@0: 
michael@0:     // this returns the first and last edge after they're sorted into a dlink list
michael@0:     SkEdge* edge = sort_edges(list, count, &last);
michael@0: 
michael@0:     headEdge.fPrev = NULL;
michael@0:     headEdge.fNext = edge;
michael@0:     headEdge.fFirstY = kEDGE_HEAD_Y;
michael@0:     headEdge.fX = SK_MinS32;
michael@0:     edge->fPrev = &headEdge;
michael@0: 
michael@0:     tailEdge.fPrev = last;
michael@0:     tailEdge.fNext = NULL;
michael@0:     tailEdge.fFirstY = kEDGE_TAIL_Y;
michael@0:     last->fNext = &tailEdge;
michael@0: 
michael@0:     // now edge is the head of the sorted linklist
michael@0:     int stop_y = ir.fBottom;
michael@0:     if (clipRect && stop_y > clipRect->fBottom) {
michael@0:         stop_y = clipRect->fBottom;
michael@0:     }
michael@0:     int start_y = ir.fTop;
michael@0:     if (clipRect && start_y < clipRect->fTop) {
michael@0:         start_y = clipRect->fTop;
michael@0:     }
michael@0:     walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, NULL);
michael@0: //    walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, NULL);
michael@0: }
michael@0: 
michael@0: void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (clip.isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkRect  r;
michael@0:     SkIRect ir;
michael@0:     r.set(pts, 3);
michael@0:     r.round(&ir);
michael@0:     if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkAAClipBlitterWrapper wrap;
michael@0:     const SkRegion* clipRgn;
michael@0:     if (clip.isBW()) {
michael@0:         clipRgn = &clip.bwRgn();
michael@0:     } else {
michael@0:         wrap.init(clip, blitter);
michael@0:         clipRgn = &wrap.getRgn();
michael@0:         blitter = wrap.getBlitter();
michael@0:     }
michael@0: 
michael@0:     SkScanClipper clipper(blitter, clipRgn, ir);
michael@0:     blitter = clipper.getBlitter();
michael@0:     if (NULL != blitter) {
michael@0:         sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
michael@0:     }
michael@0: }