Analytic AntiAlias for Convex Shapes

src/core/SkScan_AAAPath.cpp

+/*
+ * Copyright 2016 The Android Open Source Project
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkAntiRun.h"
+#include "SkBlitter.h"
+#include "SkEdge.h"
+#include "SkEdgeBuilder.h"
+#include "SkGeometry.h"
+#include "SkPath.h"
+#include "SkQuadClipper.h"
+#include "SkRasterClip.h"
+#include "SkRegion.h"
+#include "SkScan.h"
+#include "SkScanPriv.h"
+#include "SkTemplates.h"
+#include "SkTSort.h"
+#include "SkUtils.h"
+
+///////////////////////////////////////////////////////////////////////////////
+
+/*
+
+The following is a high-level overview of our analytic anti-aliasing
+algorithm. We consider a path as a collection of line segments, as
+quadratic/cubic curves are converted to small line segments. Without loss of
+generality, let's assume that the draw region is [0, W] x [0, H].
+
+Our algorithm is based on horizontal scan lines (y = c_i) as the previous
+sampling-based algorithm did. However, our algorithm uses non-equal-spaced
+scan lines, while the previous method always uses equal-spaced scan lines,
+such as (y = 1/2 + 0, 1/2 + 1, 1/2 + 2, ...) in the previous non-AA algorithm,
+and (y = 1/8 + 1/4, 1/8 + 2/4, 1/8 + 3/4, ...) in the previous
+16-supersampling AA algorithm.
+
+Our algorithm contains scan lines y = c_i for c_i that is either:
+
+1. an integer between [0, H]
+
+2. the y value of a line segment endpoint
+
+3. the y value of an intersection of two line segments
+
+For two consecutive scan lines y = c_i, y = c_{i+1}, we analytically computes
+the coverage of this horizontal strip of our path on each pixel. This can be
+done very efficiently because the strip of our path now only consists of
+trapezoids whose top and bottom edges are y = c_i, y = c_{i+1} (this includes
+rectangles and triangles as special cases).
+
+We now describe how the coverage of single pixel is computed against such a
+trapezoid. That coverage is essentially the intersection area of a rectangle
+(e.g., [0, 1] x [c_i, c_{i+1}]) and our trapezoid. However, that intersection
+could be complicated, as shown in the example region A below:
+
++-----------\----+
+|            \  C|
+|             \  |
+\              \ |
+|\      A       \|
+| \              \
+|  \             |
+| B \            |
++----\-----------+
+
+However, we don't have to compute the area of A directly. Instead, we can
+compute the excluded area, which are B and C, quite easily, because they're
+just triangles. In fact, we can prove that an excluded region (take B as an
+example) is either itself a simple trapezoid (including rectangles, triangles,
+and empty regions), or its opposite (the opposite of B is A + C) is a simple
+trapezoid. In any case, we can compute its area efficiently.
+
+In summary, our algorithm has a higher quality because it generates ground-
+truth coverages analytically. It is also faster because it has much fewer
+unnessasary horizontal scan lines. For example, given a triangle path, the
+number of scan lines in our algorithm is only about 3 + H while the
+16-supersampling algorithm has about 4H scan lines.
+
+*/
+
+///////////////////////////////////////////////////////////////////////////////
+
+class AdditiveBlitter : public SkBlitter {
+public:
+    AdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip,
+                    bool isInverse);
+    ~AdditiveBlitter();
+
+    SkBlitter* getRealBlitter();
+
+    void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override;
+    void blitAntiH(int x, int y, const SkAlpha alpha);
+    void blitAntiH(int x, int y, int width, const SkAlpha alpha);
+
+    void blitV(int x, int y, int height, SkAlpha alpha) override {
+        SkDEBUGFAIL("Please call real blitter's blitV instead.");
+    }
+
+    void blitH(int x, int y, int width) override {
+        SkDEBUGFAIL("Please call real blitter's blitH instead.");
+    }
+
+    void blitRect(int x, int y, int width, int height) override {
+        SkDEBUGFAIL("Please call real blitter's blitRect instead.");
+    }
+
+    void blitAntiRect(int x, int y, int width, int height,
+                      SkAlpha leftAlpha, SkAlpha rightAlpha) override {
+        SkDEBUGFAIL("Please call real blitter's blitAntiRect instead.");
+    }
+
+    int getWidth();
+
+private:
+    SkBlitter* fRealBlitter;
+
+    /// Current y coordinate
+    int         fCurrY;
+    /// Widest row of region to be blitted
+    int         fWidth;
+    /// Leftmost x coordinate in any row
+    int         fLeft;
+    /// Initial y coordinate (top of bounds).
+    int         fTop;
+
+    // The next three variables are used to track a circular buffer that
+    // contains the values used in SkAlphaRuns. These variables should only
+    // ever be updated in advanceRuns(), and fRuns should always point to
+    // a valid SkAlphaRuns...
+    int         fRunsToBuffer;
+    void*       fRunsBuffer;
+    int         fCurrentRun;
+    SkAlphaRuns fRuns;
+
+    int         fOffsetX;
+
+    inline bool check(int x, int width) {
+        #ifdef SK_DEBUG
+        if (x < 0 || x + width > fWidth) {
+            SkDebugf("Ignore x = %d, width = %d\n", x, width);
+        }
+        #endif
+        return (x >= 0 && x + width <= fWidth);
+    }
+
+    // extra one to store the zero at the end
+    inline int getRunsSz() const { return (fWidth + 1 + (fWidth + 2)/2) * sizeof(int16_t); }
+
+    // This function updates the fRuns variable to point to the next buffer space
+    // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun
+    // and resets fRuns to point to an empty scanline.
+    inline void advanceRuns() {
+        const size_t kRunsSz = this->getRunsSz();
+        fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer;
+        fRuns.fRuns = reinterpret_cast<int16_t*>(
+            reinterpret_cast<uint8_t*>(fRunsBuffer) + fCurrentRun * kRunsSz);
+        fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1);
+        fRuns.reset(fWidth);
+    }
+
+    inline SkAlpha snapAlpha(SkAlpha alpha) {
+        return alpha > 247 ? 0xFF : alpha < 8 ? 0 : alpha;
+    }
+
+    inline void flush() {
+        if (fCurrY >= fTop) {
+            SkASSERT(fCurrentRun < fRunsToBuffer);
+            for (int x = 0; fRuns.fRuns[x]; x += fRuns.fRuns[x]) {
+                // It seems that blitting 255 or 0 is much faster than blitting 254 or 1
+                fRuns.fAlpha[x] = snapAlpha(fRuns.fAlpha[x]);
+            }
+            if (!fRuns.empty()) {
+                // SkDEBUGCODE(fRuns.dump();)
+                fRealBlitter->blitAntiH(fLeft, fCurrY, fRuns.fAlpha, fRuns.fRuns);
+                this->advanceRuns();
+                fOffsetX = 0;
+            }
+            fCurrY = fTop - 1;
+        }
+    }
+
+    inline void checkY(int y) {
+        if (y != fCurrY) {
+            this->flush();
+            fCurrY = y;
+        }
+    }
+};
+
+AdditiveBlitter::AdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip,
+                                 bool isInverse) {
+    fRealBlitter = realBlitter;
+
+    SkIRect sectBounds;
+    if (isInverse) {
+        // We use the clip bounds instead of the ir, since we may be asked to
+        //draw outside of the rect when we're a inverse filltype
+        sectBounds = clip.getBounds();
+    } else {
+        if (!sectBounds.intersect(ir, clip.getBounds())) {
+            sectBounds.setEmpty();
+        }
+    }
+
+    const int left = sectBounds.left();
+    const int right = sectBounds.right();
+
+    fLeft = left;
+    fWidth = right - left;
+    fTop = sectBounds.top();
+    fCurrY = fTop - 1;
+
+    fRunsToBuffer = realBlitter->requestRowsPreserved();
+    fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz());
+    fCurrentRun = -1;
+
+    this->advanceRuns();
+
+    fOffsetX = 0;
+}
+
+AdditiveBlitter::~AdditiveBlitter() {
+    this->flush();
+}
+
+SkBlitter* AdditiveBlitter::getRealBlitter() {
+    return fRealBlitter;
+}
+
+void AdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) {
+    checkY(y);
+    x -= fLeft;
+
+    if (x < fOffsetX) {
+        fOffsetX = 0;
+    }
+
+    for (int i=0; runs[i]; i += runs[i]) {
+        if (check(x, runs[i])) {
+            fOffsetX = fRuns.add(x, 0, runs[i], 0, antialias[i], fOffsetX);
+        }
+        x += runs[i];
+    }
+}
+
+void AdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
+    checkY(y);
+    x -= fLeft;
+
+    if (x < fOffsetX) {
+        fOffsetX = 0;
+    }
+
+    if (check(x, 1)) {
+        fOffsetX = fRuns.add(x, 0, 1, 0, alpha, fOffsetX);
+    }
+}
+
+void AdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
+    checkY(y);
+    x -= fLeft;
+
+    if (x < fOffsetX) {
+        fOffsetX = 0;
+    }
+
+    if (check(x, width)) {
+        fOffsetX = fRuns.add(x, 0, width, 0, alpha, fOffsetX);
+    }
+}
+
+int AdditiveBlitter::getWidth() { return fWidth; }
+
+///////////////////////////////////////////////////////////////////////////////
+
+// Return the alpha of a trapezoid whose height is 1
+inline SkAlpha trapezoidToAlpha(SkFixed l1, SkFixed l2) {
+    SkASSERT(l1 >= 0 && l2 >= 0);
+    return ((l1 + l2) >> 9);
+}
+
+// Return the alpha of a right-angle triangle whose two right-angle edges are l1, l2
+inline SkAlpha triangleToAlpha(SkFixed l1, SkFixed l2) {
+    SkASSERT(l1 >= 0 && l2 >= 0);
+    // Since l1, l2 <= SK_Fixed1, we should be able to become more accurate in multiplication
+    return SkFixedMul_lowprec(l1, l2) >> 9;
+}
+
+inline SkAlpha getPartialAlpha(SkAlpha alpha, SkFixed partialHeight) {
+    return (alpha * partialHeight) >> 16;
+}
+
+// Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1),
+// approximate (very coarsely) the x coordinate of the intersection.
+inline SkFixed approximateIntersection(SkFixed l1, SkFixed r1, SkFixed l2, SkFixed r2) {
+    if (l1 > r1) { SkTSwap(l1, r1); }
+    if (l2 > r2) { SkTSwap(l2, r2); }
+    return (SkTMax(l1, l2) + SkTMin(r1, r2)) >> 1;
+}
+
+inline void computeAlphaAboveLine(SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkFixed rowHeight) {
+    SkASSERT(l <= r);
+    SkASSERT(l >> 16 == 0);
+    int R = SkFixedCeilToInt(r);
+    if (R == 0) {
+        return;
+    } else if (R == 1) {
+        alphas[0] = getPartialAlpha(((R << 17) - l - r) >> 9, rowHeight);
+    } else {
+        SkFixed first = SK_Fixed1 - l;
+        SkFixed last = r - ((R - 1) << 16);
+        SkFixed alpha16 = SkFixedMul_lowprec(first, SkFixedMul_lowprec(first, dY)) >> 1;
+        for (int i = 0; i < R - 1; i++) {
+            alphas[i] = alpha16 >> 8;
+            alpha16 += dY;
+        }
+        alphas[R - 1] = getPartialAlpha(0xFF, rowHeight) - triangleToAlpha(last, SkFixedMul_lowprec(last, dY));
+    }
+}
+
+inline void computeAlphaBelowLine(SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkFixed rowHeight) {
+    SkASSERT(l <= r);
+    SkASSERT(l >> 16 == 0);
+    int R = SkFixedCeilToInt(r);
+    if (R == 0) {
+        return;
+    } else if (R == 1) {
+        alphas[0] = getPartialAlpha(trapezoidToAlpha(l, r), rowHeight);
+    } else {
+        SkFixed first = SK_Fixed1 - l;
+        SkFixed last = r - ((R - 1) << 16);
+        SkFixed alpha16 = SkFixedMul_lowprec(last, SkFixedMul_lowprec(last, dY)) >> 1;
+        for (int i = R - 1; i > 0; i--) {
+            alphas[i] = alpha16 >> 8;
+            alpha16 += dY;
+        }
+        alphas[0] = getPartialAlpha(0xFF, rowHeight) - triangleToAlpha(first, SkFixedMul_lowprec(first, dY));
+    }
+}
+
+// Blit antialiasing trapzoid (ul, y), (ur, y), (ll, y + rowHeight), (lr, y + rowHeight)
+// ul = upper left, ur = upper rite, ll = lower left, lr = lower rite
+// When rowHeight < SK_Fixed1, blit the partial row with that partial height.
+// lDY is the dY for the left edge (ul, y) - (ll, y + rowHeight),
+// and rDY is the dY for the right edge.
+//
+// NOTE! To increase performance, we use real blitter (without additive alphas)
+// if rowHeight = SK_Fixed1. Therefore, we'll lose information if there are
+// many thin vertical strips within the same pixel.
+void blit_aaa_trapzoid_row(AdditiveBlitter* blitter, int y,
+                           SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr,
+                           SkFixed lDY, SkFixed rDY,
+                           SkFixed rowHeight) {
+    SkASSERT(lDY >= 0 && rDY >= 0); // We should only send in the absolte value
+
+    if (ul > ur) {
+#ifdef SK_DEBUG
+        SkDebugf("ul = %f > ur = %f!\n", SkFixedToFloat(ul), SkFixedToFloat(ur));
+#endif
+        return;
+    }
+
+    // Edge crosses. Approximate it. This should only happend due to precision limit,
+    // so the approximation could be very coarse.
+    if (ll > lr) {
+#ifdef SK_DEBUG
+        SkDebugf("approximate intersection: %d %f %f\n", y,
+                 SkFixedToFloat(ll), SkFixedToFloat(lr));
+#endif
+        ll = lr = approximateIntersection(ul, ll, ur, lr);
+    }
+
+    if (ul == ur && ll == lr) {
+        return; // empty trapzoid
+    }
+
+    bool isFullRow = rowHeight == SK_Fixed1;
+    SkAlpha fullAlpha = getPartialAlpha(0xFF, rowHeight);
+
+    SkFixed joinLeft = SkFixedCeilToFixed(SkTMax(ul, ll));
+    SkFixed joinRite = SkFixedFloorToFixed(SkTMin(ur, lr));
+    if (joinLeft < joinRite) {
+        // There's a strip from joinLeft to joinRite that we can blit at once
+        blit_aaa_trapzoid_row(blitter, y, ul, joinLeft, ll, joinLeft, lDY, SK_MaxS32, rowHeight);
+        if (isFullRow) {
+            blitter->getRealBlitter()->blitH(joinLeft >> 16, y, (joinRite - joinLeft) >> 16);
+        } else {
+            blitter->blitAntiH(joinLeft >> 16, y, (joinRite - joinLeft) >> 16, fullAlpha);
+        }
+        blit_aaa_trapzoid_row(blitter, y, joinRite, ur, joinRite, lr, SK_MaxS32, rDY, rowHeight);
+        return;
+    }
+
+    SkFixed left = SkTMin(ul, ll), rite = SkTMax(ur, lr);
+    int L = SkFixedFloorToInt(left), R = SkFixedCeilToInt(rite);
+    int len = R - L;
+
+    #ifdef SK_DEBUG
+    // SkDebugf("y = %d, len = %d\n", y, len);
+    #endif
+
+    if (len == 1) { // Most of the time, len is 1 so we accelerate it
+        SkAlpha alpha = trapezoidToAlpha(ur - ul, lr - ll);
+        if (isFullRow) {
+            blitter->getRealBlitter()->blitV(L, y, 1, alpha);
+        } else {
+            blitter->blitAntiH(L, y, getPartialAlpha(alpha, rowHeight));
+        }
+        return;
+    }
+
+    SkAutoSMalloc<1024> storage((len + 1) * (sizeof(SkAlpha) * 2 + sizeof(int16_t)));
+    SkAlpha* alphas = (SkAlpha*)storage.get();
+    SkAlpha* tempAlphas = alphas + len + 1;
+    int16_t* runs = (int16_t*)(alphas + (len + 1) * 2);
+
+    // We're going to use the left line ul-ll and the rite line ur-lr
+    // to exclude the area that's not covered by the path.
+    // Swapping (ul, ll) or (ur, lr) won't affect that exclusion
+    // so we'll do that for simplicity.
+    if (ul > ll) { SkTSwap(ul, ll); }
+    if (ur > lr) { SkTSwap(ur, lr); }
+
+    for (int i = 0; i < len; i++) {
+        runs[i] = 1;
+        alphas[i] = fullAlpha;
+    }
+    runs[len] = 0;
+
+    if (ul == ll && ll == L << 16) { // the left edge is vertical integer
+        computeAlphaBelowLine(alphas, ur - (L << 16), lr - (L << 16), rDY, rowHeight);
+    } else if (ur == lr && lr == R << 16) { // the right edge is vertical integer
+        computeAlphaAboveLine(alphas, ul - (L << 16), ll - (L << 16), lDY, rowHeight);
+    } else {
+        int uL = SkFixedFloorToInt(ul);
+        int lL = SkFixedCeilToInt(ll);
+        computeAlphaBelowLine(tempAlphas + uL - L, ul - (uL << 16), ll - (uL << 16),
+                lDY, rowHeight);
+        for (int i = uL; i < lL; i++) {
+            if (alphas[i - L] > tempAlphas[i - L]) {
+                alphas[i - L] -= tempAlphas[i - L];
+            } else {
+                alphas[i - L] = 0;
+            }
+        }
+
+        int uR = SkFixedFloorToInt(ur);
+        int lR = SkFixedCeilToInt(lr);
+        computeAlphaAboveLine(tempAlphas + uR - L, ur - (uR << 16), lr - (uR << 16),
+                rDY, rowHeight);
+        for (int i = uR; i < lR; i++) {
+            if (alphas[i - L] > tempAlphas[i - L]) {
+                alphas[i - L] -= tempAlphas[i - L];
+            } else {
+                alphas[i - L] = 0;
+            }
+        }
+    }
+
+    if (isFullRow) {
+        blitter->getRealBlitter()->blitAntiH(L, y, alphas, runs);
+    } else {
+        blitter->blitAntiH(L, y, alphas, runs);
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+static bool operator<(const SkAnalyticEdge& a, const SkAnalyticEdge& b) {
+    int valuea = a.fUpperY;
+    int valueb = b.fUpperY;
+
+    if (valuea == valueb) {
+        valuea = a.fX;
+        valueb = b.fX;
+    }
+
+    if (valuea == valueb) {
+        valuea = a.fDX;
+        valueb = b.fDX;
+    }
+
+    return valuea < valueb;
+}
+
+static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) {
+    SkTQSort(list, list + count - 1);
+
+    // now make the edges linked in sorted order
+    for (int i = 1; i < count; i++) {
+        list[i - 1]->fNext = list[i];
+        list[i]->fPrev = list[i - 1];
+    }
+
+    *last = list[count - 1];
+    return list[0];
+}
+
+#ifdef SK_DEBUG
+    static void validate_sort(const SkAnalyticEdge* edge) {
+        SkFixed y = SkIntToFixed(-32768);
+
+        while (edge->fUpperY != SK_MaxS32) {
+            edge->validate();
+            SkASSERT(y <= edge->fUpperY);
+
+            y = edge->fUpperY;
+            edge = (SkAnalyticEdge*)edge->fNext;
+        }
+    }
+#else
+    #define validate_sort(edge)
+#endif
+
+// return true if we're done with this edge
+static bool update_edge(SkAnalyticEdge* edge, SkFixed last_y) {
+    if (last_y >= edge->fLowerY) {
+        if (edge->fCurveCount < 0) {
+            if (static_cast<SkAnalyticCubicEdge*>(edge)->updateCubic()) {
+                return false;
+            }
+        } else if (edge->fCurveCount > 0) {
+            if (static_cast<SkAnalyticQuadraticEdge*>(edge)->updateQuadratic()) {
+                return false;
+            }
+        }
+        return true;
+    }
+    SkASSERT(false);
+    return false;
+}
+
+void aaa_walk_convex_edges(SkAnalyticEdge* prevHead, AdditiveBlitter* blitter,
+                           int start_y, int stop_y) {
+    validate_sort((SkAnalyticEdge*)prevHead->fNext);
+
+    SkAnalyticEdge* leftE = (SkAnalyticEdge*) prevHead->fNext;
+    SkAnalyticEdge* riteE = (SkAnalyticEdge*) leftE->fNext;
+    SkAnalyticEdge* currE = (SkAnalyticEdge*) riteE->fNext;
+
+    SkFixed y = SkTMax(leftE->fUpperY, riteE->fUpperY);
+    int local_top = SkFixedFloorToInt(y);
+    SkASSERT(local_top >= start_y);
+
+    #ifdef SK_DEBUG
+    int frac_y_cnt = 0;
+    int total_y_cnt = 0;
+    #endif
+
+    for (;;) {
+        SkASSERT(SkFixedFloorToInt(leftE->fUpperY) <= stop_y);
+        SkASSERT(SkFixedFloorToInt(riteE->fUpperY) <= stop_y);
+
+        if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX &&
+                                      leftE->fDX > riteE->fDX)) {
+            SkTSwap(leftE, riteE);
+        }
+
+        SkFixed local_bot_fixed = SkMin32(leftE->fLowerY, riteE->fLowerY);
+        local_bot_fixed = SkMin32(local_bot_fixed, SkIntToFixed(stop_y + 1));
+
+        SkFixed left = leftE->fX;
+        SkFixed dLeft = leftE->fDX;
+        SkFixed rite = riteE->fX;
+        SkFixed dRite = riteE->fDX;
+        // x may be out of range without snapping due to precision limit
+        SkFixed snappedLeft = SkAnalyticEdge::snapX(left);
+        SkFixed snappedRite = SkAnalyticEdge::snapX(rite);
+        if (0 == (dLeft | dRite)) {
+            int     fullLeft    = SkFixedCeilToInt(snappedLeft);
+            int     fullRite    = SkFixedFloorToInt(snappedRite);
+            SkFixed partialLeft = SkIntToFixed(fullLeft) - snappedLeft;
+            SkFixed partialRite = snappedRite - SkIntToFixed(fullRite);
+            int     fullTop     = SkFixedCeilToInt(y);
+            int     fullBot     = SkFixedFloorToInt(local_bot_fixed);
+            SkFixed partialTop  = SkIntToFixed(fullTop) - y;
+            SkFixed partialBot  = local_bot_fixed - SkIntToFixed(fullBot);
+
+            if (fullRite >= fullLeft) {
+                // Blit all full-height rows from fullTop to fullBot
+                blitter->getRealBlitter()->blitAntiRect(fullLeft - 1, fullTop, fullRite - fullLeft,
+                                                        fullBot - fullTop,
+                                                        partialLeft >> 8, partialRite >> 8);
+
+                if (partialTop > 0) { // blit first partial row
+                    if (partialLeft > 0) {
+                        blitter->blitAntiH(fullLeft - 1, fullTop - 1,
+                                           SkFixedMul_lowprec(partialTop, partialLeft) >> 8);
+                    }
+                    if (partialRite > 0) {
+                        blitter->blitAntiH(fullRite, fullTop - 1,
+                                           SkFixedMul_lowprec(partialTop, partialRite) >> 8);
+                    }
+                    blitter->blitAntiH(fullLeft, fullTop - 1, fullRite - fullLeft, partialTop >> 8);
+                }
+
+                if (partialBot > 0) { // blit last partial row
+                    if (partialLeft > 0) {
+                        blitter->blitAntiH(fullLeft - 1, fullBot,
+                                           SkFixedMul_lowprec(partialBot, partialLeft) >> 8);
+                    }
+                    if (partialRite > 0) {
+                        blitter->blitAntiH(fullRite, fullBot,
+                                           SkFixedMul_lowprec(partialBot, partialRite) >> 8);
+                    }
+                    blitter->blitAntiH(fullLeft, fullBot, fullRite - fullLeft, partialBot >> 8);
+                }
+            } else {
+                if (partialTop > 0) {
+                    blitter->getRealBlitter()->blitV(fullLeft - 1, fullTop - 1, 1,
+                            SkFixedMul_lowprec(partialTop, rite - left) >> 8);
+                }
+                if (partialBot > 0) {
+                    blitter->getRealBlitter()->blitV(fullLeft - 1, fullBot, 1,
+                            SkFixedMul_lowprec(partialBot, snappedRite - snappedLeft) >> 8);
+                }
+                if (fullBot >= fullTop) {
+                    blitter->getRealBlitter()->blitV(fullLeft - 1, fullTop, fullBot - fullTop,
+                            (snappedRite - snappedLeft) >> 8);
+                }
+            }
+
+            y = local_bot_fixed;
+        } else {
+            do {
+                #ifdef SK_DEBUG
+                if ((y >> 16 << 16) != y) {
+                    frac_y_cnt++;
+                    SkDebugf("frac_y = %f\n", SkFixedToFloat(y));
+                }
+                total_y_cnt++;
+                #endif
+
+                local_top = SkFixedFloorToInt(y);
+                SkFixed nextY = SkIntToFixed(local_top + 1);
+                nextY = SkTMin(nextY, local_bot_fixed);
+                SkFixed dY = nextY - y;
+
+                SkFixed nextLeft = left + dLeft;
+                SkFixed nextRite = rite + dRite;
+
+                if (dY != SK_Fixed1) {
+                    nextLeft = left + SkFixedMul_lowprec(dLeft, dY);
+                    nextRite = rite + SkFixedMul_lowprec(dRite, dY);
+                }
+
+                SkFixed snappedNextLeft = SkAnalyticEdge::snapX(nextLeft);
+                SkFixed snappedNextRite = SkAnalyticEdge::snapX(nextRite);
+
+                blit_aaa_trapzoid_row(blitter, local_top, snappedLeft, snappedRite,
+                                      snappedNextLeft, snappedNextRite,
+                                      leftE->fDY, riteE->fDY, nextY - y);
+
+                left = nextLeft;
+                rite = nextRite;
+                snappedLeft = snappedNextLeft;
+                snappedRite = snappedNextRite;
+                y = nextY;
+            } while (y < local_bot_fixed);
+        }
+
+        leftE->fX = left;
+        riteE->fX = rite;
+
+        while (leftE->fLowerY <= y) {
+            if (update_edge(leftE, y)) {
+                if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
+                    goto END_WALK;
+                }
+                leftE = currE;
+                leftE->goY(y);
+                currE = (SkAnalyticEdge*)currE->fNext;
+            }
+        }
+        while (riteE->fLowerY <= y) {
+            if (update_edge(riteE, y)) {
+                if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
+                    goto END_WALK;
+                }
+                riteE = currE;
+                riteE->goY(y);
+                currE = (SkAnalyticEdge*)currE->fNext;
+            }
+        }
+
+        SkASSERT(leftE);
+        SkASSERT(riteE);
+
+        // check our bottom clip
+        SkASSERT(y == local_bot_fixed);
+        if (SkFixedFloorToInt(y) >= stop_y) {
+            break;
+        }
+    }
+
+END_WALK:
+    ;
+    #ifdef SK_DEBUG
+    SkDebugf("frac_y_cnt = %d, total_y_cnt = %d\n", frac_y_cnt, total_y_cnt);
+    #endif
+}
+
+void SkScan::aaa_fill_path(const SkPath& path, const SkIRect* clipRect, AdditiveBlitter* blitter,
+                   int start_y, int stop_y, const SkRegion& clipRgn) {
+    SkASSERT(blitter);
+
+    if (path.isInverseFillType() || !path.isConvex()) {
+        // fall back to supersampling AA
+        GlobalAAConfig::getInstance().fUseAnalyticAA = false;
+        SkScan::AntiFillPath(path, clipRgn, blitter->getRealBlitter(), false);
+        GlobalAAConfig::getInstance().fUseAnalyticAA = true; // turne analytic AA back on
+        return;
+    }
+
+    SkEdgeBuilder   builder;
+
+    // If we're convex, then we need both edges, even the right edge is past the clip
+    const bool canCullToTheRight = !path.isConvex();
+
+    SkASSERT(GlobalAAConfig::getInstance().fUseAnalyticAA);
+    int count = builder.build(path, clipRect, 0, canCullToTheRight, true);
+    SkASSERT(count >= 0);
+
+    SkAnalyticEdge** list = (SkAnalyticEdge**)builder.analyticEdgeList();
+
+    if (0 == count) {
+        if (path.isInverseFillType()) {
+            /*
+             *  Since we are in inverse-fill, our caller has already drawn above
+             *  our top (start_y) and will draw below our bottom (stop_y). Thus
+             *  we need to restrict our drawing to the intersection of the clip
+             *  and those two limits.
+             */
+            SkIRect rect = clipRgn.getBounds();
+            if (rect.fTop < start_y) {
+                rect.fTop = start_y;
+            }
+            if (rect.fBottom > stop_y) {
+                rect.fBottom = stop_y;
+            }
+            if (!rect.isEmpty()) {
+                blitter->blitRect(rect.fLeft, rect.fTop, rect.width(), rect.height());
+            }
+        }
+        return;
+    }
+
+    SkAnalyticEdge headEdge, tailEdge, *last;
+    // this returns the first and last edge after they're sorted into a dlink list
+    SkAnalyticEdge* edge = sort_edges(list, count, &last);
+
+    headEdge.fPrev = nullptr;
+    headEdge.fNext = edge;
+    headEdge.fUpperY = headEdge.fLowerY = SK_MinS32;
+    headEdge.fX = SK_MinS32;
+    headEdge.fDX = 0;
+    headEdge.fDY = SK_MaxS32;
+    headEdge.fUpperX = SK_MinS32;
+    edge->fPrev = &headEdge;
+
+    tailEdge.fPrev = last;
+    tailEdge.fNext = nullptr;
+    tailEdge.fUpperY = tailEdge.fLowerY = SK_MaxS32;
+    headEdge.fX = SK_MaxS32;
+    headEdge.fDX = 0;
+    headEdge.fDY = SK_MaxS32;
+    headEdge.fUpperX = SK_MaxS32;
+    last->fNext = &tailEdge;
+
+    // now edge is the head of the sorted linklist
+
+    if (clipRect && start_y < clipRect->fTop) {
+        start_y = clipRect->fTop;
+    }
+    if (clipRect && stop_y > clipRect->fBottom) {
+        stop_y = clipRect->fBottom;
+    }
+
+    if (!path.isInverseFillType() && path.isConvex()) {
+        SkASSERT(count >= 2);   // convex walker does not handle missing right edges
+        aaa_walk_convex_edges(&headEdge, blitter, start_y, stop_y);
+    } else {
+        SkFAIL("Concave AAA is not yet implemented!");
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkScan::AAAFillPath(const SkPath& path, const SkRegion& origClip, SkBlitter* blitter) {
+    if (origClip.isEmpty()) {
+        return;
+    }
+
+    const bool isInverse = path.isInverseFillType();
+    SkIRect ir;
+    path.getBounds().roundOut(&ir);
+    if (ir.isEmpty()) {
+        if (isInverse) {
+            blitter->blitRegion(origClip);
+        }
+        return;
+    }
+
+    SkIRect clippedIR;
+    if (isInverse) {
+       // If the path is an inverse fill, it's going to fill the entire
+       // clip, and we care whether the entire clip exceeds our limits.
+       clippedIR = origClip.getBounds();
+    } else {
+       if (!clippedIR.intersect(ir, origClip.getBounds())) {
+           return;
+       }
+    }
+
+    // Our antialiasing can't handle a clip larger than 32767, so we restrict
+    // the clip to that limit here. (the runs[] uses int16_t for its index).
+    //
+    // A more general solution (one that could also eliminate the need to
+    // disable aa based on ir bounds (see overflows_short_shift) would be
+    // to tile the clip/target...
+    SkRegion tmpClipStorage;
+    const SkRegion* clipRgn = &origClip;
+    {
+        static const int32_t kMaxClipCoord = 32767;
+        const SkIRect& bounds = origClip.getBounds();
+        if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) {
+            SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord };
+            tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op);
+            clipRgn = &tmpClipStorage;
+        }
+    }
+    // for here down, use clipRgn, not origClip
+
+    SkScanClipper   clipper(blitter, clipRgn, ir);
+    const SkIRect*  clipRect = clipper.getClipRect();
+
+    if (clipper.getBlitter() == nullptr) { // clipped out
+        if (isInverse) {
+            blitter->blitRegion(*clipRgn);
+        }
+        return;
+    }
+
+    // now use the (possibly wrapped) blitter
+    blitter = clipper.getBlitter();
+
+    if (isInverse) {
+        sk_blit_above(blitter, ir, *clipRgn);
+    }
+
+    SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
+
+    AdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse);
+    aaa_fill_path(path, clipRect, &additiveBlitter, ir.fTop, ir.fBottom, *clipRgn);
+
+    if (isInverse) {
+        sk_blit_below(blitter, ir, *clipRgn);
+    }
+}
+
+// This almost copies SkScan::AntiFillPath
+void SkScan::AAAFillPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
+    if (clip.isEmpty()) {
+        return;
+    }
+
+    if (clip.isBW()) {
+        AAAFillPath(path, clip.bwRgn(), blitter);
+    } else {
+        SkRegion        tmp;
+        SkAAClipBlitter aaBlitter;
+
+        tmp.setRect(clip.getBounds());
+        aaBlitter.init(blitter, &clip.aaRgn());
+        AAAFillPath(path, tmp, &aaBlitter);
+    }
+}