Analytic AntiAlias for Convex Shapes

src/core/SkEdge.cpp

Index: src/core/SkEdge.cpp
diff --git a/src/core/SkEdge.cpp b/src/core/SkEdge.cpp
index d91c3e6bce8f26dd0b5283b056ac3882c31846d1..b224c3fc67f8047bd9e10ec32686baa100036d6d 100644
--- a/src/core/SkEdge.cpp
+++ b/src/core/SkEdge.cpp
@@ -477,3 +477,377 @@ int SkCubicEdge::updateCubic()
     fCurveCount = SkToS8(count);
     return success;
 }
+
+///////////////////Analytic Edges///////////////////////////////
+
+int SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip) {

[caryclark, 2016/08/10 13:08:09]

Since this shares so much code with the other setLine, can this call the other,
or call a function common to both?

[liyuqian, 2016/08/16 13:22:05]

Done. I removed the other method and make clip having the default value of
nullptr

+    SkFixed x0, y0, x1, y1;
+
+    x0 = SkScalarToFixed(p0.fX);

[caryclark, 2016/08/10 13:08:10]

SkFixed x0 = ...

[liyuqian, 2016/08/16 13:22:05]

Done.

+    y0 = snapY(SkScalarToFixed(p0.fY));
+    x1 = SkScalarToFixed(p1.fX);
+    y1 = snapY(SkScalarToFixed(p1.fY));
+
+    int winding = 1;
+
+    if (y0 > y1) {
+        SkTSwap(x0, x1);
+        SkTSwap(y0, y1);
+        winding = -1;
+    }
+
+    int top = SkFixedFloorToInt(y0);
+    int bot = SkFixedCeilToInt(y1);
+
+    // are we a zero-height line?
+    if (y0 == y1) {

[caryclark, 2016/08/10 13:08:10]

move test before top, bot

[liyuqian, 2016/08/16 13:22:05]

Done.

+        return 0;
+    }
+    // are we completely above or below the clip?
+    if (clip && (top >= clip->fBottom || bot <= clip->fTop)) {
+        return 0;
+    }
+
+    SkFixed slope = SkFixedDiv(x1 - x0, y1 - y0);
+
+    fX          = x0;
+    fDX         = slope;
+    fUpperX     = x0;
+    fY          = y0;
+    fUpperY     = y0;
+    fLowerY     = y1;
+    fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 - y0, x1 - x0)) : SK_MaxS32;

[caryclark, 2016/08/10 13:08:09]

x1 == x0 ? 

[liyuqian, 2016/08/16 13:22:05]

Done.

+    fCurveCount = 0;
+    fWinding    = SkToS8(winding);
+    fCurveShift = 0;
+
+    if (clip) {
+        this->chopLineWithClip(*clip);
+    }
+    return 1;
+}
+
+int SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
+{
+    y0 = snapY(y0);
+    y1 = snapY(y1);
+    SkASSERT(fWinding == 1 || fWinding == -1);
+    SkASSERT(fCurveCount != 0);
+
+    SkASSERT(y0 <= y1);
+
+    // are we a zero-height line?
+    if (y0 == y1)

[caryclark, 2016/08/10 13:08:10]

add braces around if

[liyuqian, 2016/08/16 13:22:05]

Done.

+        return 0;
+
+    SkFixed slope = SkFixedDiv(x1 - x0, y1 - y0);
+
+    fX          = x0;
+    fDX         = slope;
+    fUpperX     = x0;
+    fY          = y0;
+    fUpperY     = y0;
+    fLowerY     = y1;
+    fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 - y0, x1 - x0)) : SK_MaxS32;

[caryclark, 2016/08/10 13:08:09]

this also shares a lot of code with setline. Can they all share a common
function?

[liyuqian, 2016/08/16 13:22:05]

In my new CL, this probably is not the case as I heavily optimized the
updateLine.

+
+    return 1;
+}
+
+void SkAnalyticEdge::chopLineWithClip(const SkIRect& clip)
+{
+    int top = SkFixedFloorToInt(fUpperY);
+
+    SkASSERT(top < clip.fBottom);
+
+    // clip the line to the clip top
+    if (top < clip.fTop)
+    {

[caryclark, 2016/08/10 13:08:09]

brace on same line as if

[liyuqian, 2016/08/16 13:22:05]

Done.

+        SkASSERT(SkFixedCeilToInt(fLowerY) > clip.fTop);
+        SkFixed newY = SkIntToFixed(clip.fTop);
+        this->goY(newY);
+        fUpperY = newY;
+    }
+}
+
+int SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3])
+{
+    SkFDot6 x0, y0, x1, y1, x2, y2;
+
+    x0 = SkScalarToFixed(pts[0].fX);

[caryclark, 2016/08/10 13:08:09]

SkFDot6 x0 = ...

[liyuqian, 2016/08/16 13:22:05]

Done.

+    y0 = SkScalarToFixed(pts[0].fY);
+    x1 = SkScalarToFixed(pts[1].fX);
+    y1 = SkScalarToFixed(pts[1].fY);
+    x2 = SkScalarToFixed(pts[2].fX);
+    y2 = SkScalarToFixed(pts[2].fY);
+
+    int winding = 1;
+    if (y0 > y2)
+    {
+        SkTSwap(x0, x2);
+        SkTSwap(y0, y2);
+        winding = -1;
+    }
+    SkASSERT(y0 <= y1 && y1 <= y2);
+
+    int top = SkFixedFloorToInt(y0);
+    int bot = SkFixedCeilToInt(y2);
+
+    // are we a zero-height quad (line)?
+    if (top == bot)

[caryclark, 2016/08/10 13:08:09]

add braces

[liyuqian, 2016/08/16 13:22:05]

Done.

+        return 0;
+
+    int shift;
+    // compute number of steps needed (1 << shift)
+    {
+        // The dx, dy here are 4 times larger so we get the right shift
+        // from 4x4 supersampling's diff_to_shift function
+        SkFDot6 dx = SkFixedToFDot6((SkLeftShift(x1, 1) - x0 - x2));
+        SkFDot6 dy = SkFixedToFDot6((SkLeftShift(y1, 1) - y0 - y2));
+        shift = diff_to_shift(dx, dy);
+        SkASSERT(shift >= 0);
+    }
+    // need at least 1 subdivision for our bias trick
+    if (shift == 0) {
+        shift = 1;
+    } else if (shift > MAX_COEFF_SHIFT) {
+        shift = MAX_COEFF_SHIFT;
+    }

[caryclark, 2016/08/10 13:08:09]

Out of curiosity, is this any less efficient and more readable as

shift = SkTMax(1, SkTMin(shift, MAX_COEFF_SHIFT));

?

[liyuqian, 2016/08/16 13:22:05]

I'm not sure. Maybe shift = SkTPin(shift, 1, MAX_COEFF_SHIFT) is even simpler.
Anyway, I don't think setQuadratic is a performance bottleneck so I'll adopt
your cleaner implementation. (I was copying from the old code anyway so I don't
know why the old code is like this.)

+
+    fWinding    = SkToS8(winding);
+    //fCubicDShift only set for cubics
+    fCurveCount = SkToS8(1 << shift);
+
+    /*
+     *  We want to reformulate into polynomial form, to make it clear how we
+     *  should forward-difference.
+     *
+     *  p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
+     *
+     *  A = p0 - 2p1 + p2
+     *  B = 2(p1 - p0)
+     *  C = p0
+     *
+     *  Our caller must have constrained our inputs (p0..p2) to all fit into
+     *  16.16. However, as seen above, we sometimes compute values that can be
+     *  larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
+     *  A and B at 1/2 of their actual value, and just apply a 2x scale during
+     *  application in updateQuadratic(). Hence we store (shift - 1) in
+     *  fCurveShift.
+     */
+
+    fCurveShift = SkToU8(shift - 1);
+
+    SkFixed A = (x0 - x1 - x1 + x2) >> 1;  // 1/2 the real value
+    SkFixed B = x1 - x0;                   // 1/2 the real value
+
+    fQx     = x0;
+    fQDx    = B + (A >> shift);     // biased by shift
+    fQDDx   = A >> (shift - 1);     // biased by shift
+
+    A = (y0 - y1 - y1 + y2) >> 1;  // 1/2 the real value
+    B = y1 - y0;                   // 1/2 the real value
+
+    fQy     = y0;
+    fQDy    = B + (A >> shift);     // biased by shift
+    fQDDy   = A >> (shift - 1);     // biased by shift
+
+    fQLastX = x2;
+    fQLastY = y2;
+
+    fSnappedX = fQx;
+    fSnappedY = fQy;
+
+    return this->updateQuadratic();
+}
+
+int SkAnalyticQuadraticEdge::updateQuadratic()
+{
+    int     success = 0; // initialize to fail!
+    int     count = fCurveCount;
+    SkFixed oldx = fQx;
+    SkFixed oldy = fQy;
+    SkFixed dx = fQDx;
+    SkFixed dy = fQDy;
+    SkFixed newx, newy, newSnappedX, newSnappedY;
+    int     shift = fCurveShift;
+
+    SkASSERT(count > 0);
+
+    do {
+        if (--count > 0)
+        {
+            newx    = oldx + (dx >> shift);
+            dx    += fQDDx;
+            newy    = oldy + (dy >> shift);
+            dy    += fQDDy;
+            if (SkAbs32(dy) >= SK_Fixed1 * 2) { // only snap when dy is large enough
+                newSnappedY = SkTMin<SkFixed>(fQLastY, SkFixedRoundToFixed(newy));
+                newSnappedX = newx + SkFixedMul(SkFixedDiv(dx, dy), newSnappedY - newy);
+            } else {
+                newSnappedY = newy;
+                newSnappedX = newx;
+            }
+        }
+        else    // last segment
+        {
+            newx    = fQLastX;
+            newy    = fQLastY;
+            newSnappedY = newy;
+            newSnappedX = newx;
+        }
+        if (newSnappedY > fSnappedY) {
+            success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY);
+        }
+        oldx = newx;
+        oldy = newy;
+    } while (count > 0 && !success);
+
+    SkASSERT(newSnappedY <= fQLastY);
+
+    fQx         = newx;
+    fQy         = newy;
+    fQDx        = dx;
+    fQDy        = dy;
+    fSnappedX   = newSnappedX;
+    fSnappedY   = newSnappedY;
+    fCurveCount = SkToS8(count);
+    return success;
+}
+
+int SkAnalyticCubicEdge::setCubic(const SkPoint pts[4]) {
+    SkFixed x0, y0, x1, y1, x2, y2, x3, y3;
+
+    x0 = SkScalarToFixed(pts[0].fX);
+    y0 = SkScalarToFixed(pts[0].fY);
+    x1 = SkScalarToFixed(pts[1].fX);
+    y1 = SkScalarToFixed(pts[1].fY);
+    x2 = SkScalarToFixed(pts[2].fX);
+    y2 = SkScalarToFixed(pts[2].fY);
+    x3 = SkScalarToFixed(pts[3].fX);
+    y3 = SkScalarToFixed(pts[3].fY);
+
+    int winding = 1;
+    if (y0 > y3)
+    {
+        SkTSwap(x0, x3);
+        SkTSwap(x1, x2);
+        SkTSwap(y0, y3);
+        SkTSwap(y1, y2);
+        winding = -1;
+    }
+
+    int top = SkFixedFloorToInt(y0);
+    int bot = SkFixedCeilToInt(y3);
+
+    // are we a zero-height cubic (line)?
+    if (top == bot)
+        return 0;
+
+    int shift;
+    // compute number of steps needed (1 << shift)
+    {
+        // The dx, dy here are 4 times larger so we get the right shift
+        // from 4x4 supersampling's diff_to_shift function
+
+        // Can't use (center of curve - center of baseline), since center-of-curve
+        // need not be the max delta from the baseline (it could even be coincident)
+        // so we try just looking at the two off-curve points
+        SkFDot6 dx = cubic_delta_from_line(SkFixedToFDot6(x0 << 2),SkFixedToFDot6(x1 << 2),
+                                           SkFixedToFDot6(x2 << 2), SkFixedToFDot6(x3 << 2));
+        SkFDot6 dy = cubic_delta_from_line(SkFixedToFDot6(y0 << 2), SkFixedToFDot6(y1 << 2),
+                                           SkFixedToFDot6(y2 << 2), SkFixedToFDot6(y3 << 2));
+        // add 1 (by observation)
+        shift = diff_to_shift(dx, dy) + 1;
+    }
+    // need at least 1 subdivision for our bias trick
+    SkASSERT(shift > 0);
+    if (shift > MAX_COEFF_SHIFT) {
+        shift = MAX_COEFF_SHIFT;
+    }
+
+    /*  Since our in coming data is initially shifted down by 10 (or 8 in
+        antialias). That means the most we can shift up is 8. However, we
+        compute coefficients with a 3*, so the safest upshift is really 6
+    */
+    int upShift = 6;    // largest safe value
+    int downShift = shift + upShift - 10;
+    if (downShift < 0) {
+        downShift = 0;
+        upShift = 10 - shift;
+    }
+
+    fWinding    = SkToS8(winding);
+    fCurveCount = SkToS8(SkLeftShift(-1, shift));
+    fCurveShift = SkToU8(shift);
+    fCubicDShift = SkToU8(downShift);
+
+    SkFixed B = SkFDot6UpShift(SkFixedToFDot6(3 * (x1 - x0)), upShift);
+    SkFixed C = SkFDot6UpShift(SkFixedToFDot6(3 * (x0 - x1 - x1 + x2)), upShift);
+    SkFixed D = SkFDot6UpShift(SkFixedToFDot6(x3 + 3 * (x1 - x2) - x0), upShift);
+
+    fCx     = x0;
+    fCDx    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
+    fCDDx   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
+    fCDDDx  = 3*D >> (shift - 1);                   // biased by 2*shift
+
+    B = SkFDot6UpShift(SkFixedToFDot6(3 * (y1 - y0)), upShift);
+    C = SkFDot6UpShift(SkFixedToFDot6(3 * (y0 - y1 - y1 + y2)), upShift);
+    D = SkFDot6UpShift(SkFixedToFDot6(y3 + 3 * (y1 - y2) - y0), upShift);
+
+    fCy     = y0;
+    fCDy    = B + (C >> shift) + (D >> 2*shift);    // biased by shift
+    fCDDy   = 2*C + (3*D >> (shift - 1));           // biased by 2*shift
+    fCDDDy  = 3*D >> (shift - 1);                   // biased by 2*shift
+
+    fCLastX = x3;
+    fCLastY = y3;
+
+    return this->updateCubic();
+}
+
+int SkAnalyticCubicEdge::updateCubic()
+{
+    int     success;
+    int     count = fCurveCount;
+    SkFixed oldx = fCx;
+    SkFixed oldy = fCy;
+    SkFixed newx, newy;
+    const int ddshift = fCurveShift;
+    const int dshift = fCubicDShift;
+
+    SkASSERT(count < 0);
+
+    do {
+        if (++count < 0)
+        {
+            newx    = oldx + (fCDx >> dshift);
+            fCDx    += fCDDx >> ddshift;
+            fCDDx   += fCDDDx;
+
+            newy    = oldy + (fCDy >> dshift);
+            fCDy    += fCDDy >> ddshift;
+            fCDDy   += fCDDDy;
+        }
+        else    // last segment
+        {
+        //  SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
+            newx    = fCLastX;
+            newy    = fCLastY;
+        }
+
+        // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
+        // doesn't always achieve that, so we have to explicitly pin it here.
+        if (newy < oldy) {
+            newy = oldy;
+        }
+
+        success = this->updateLine(oldx, oldy, newx, newy);
+        oldx = newx;
+        oldy = newy;
+    } while (count < 0 && !success);
+
+    fCx         = newx;
+    fCy         = newy;
+    fCurveCount = SkToS8(count);
+    return success;
+}