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..c7a61175de002c96b17715a1807d869c8dcb979b 100644
--- a/src/core/SkEdge.cpp
+++ b/src/core/SkEdge.cpp
@@ -477,3 +477,390 @@ int SkCubicEdge::updateCubic()
     fCurveCount = SkToS8(count);
     return success;
 }
+
+///////////////////Analytic Edges///////////////////////////////
+
+static const int kInverseTableSize = 1024; // SK_FDot6One * 16

[reed1, 2016/08/18 20:31:01]

Does this impl use shared functions form SkEdge.cpp, or could we move it to its
own impl file? I ask, since SkEdge.cpp was already modestly big, and this makes
it much larger. Not critical.

[liyuqian, 2016/08/22 15:30:48]

Nothing shared. I'll create a new cpp file.

+
+struct FDot6InverseTable {
+    SkFixed storage[kInverseTableSize * 2 + 1];
+    SkFixed* table = storage + kInverseTableSize;
+
+    FDot6InverseTable() {
+        for (SkFDot6 i=-kInverseTableSize; i<kInverseTableSize; i++) {
+            if (i != 0) {

[reed1, 2016/08/18 20:31:00]

nit: is it any faster to just have 2 loops, so we don't have to check for i == 0
on each iteration? (does the compiler already make that optimization?)

[liyuqian, 2016/08/22 15:30:48]

Not sure. Since this code is run once during the start, I didn't tune its
performance. Also, I don't know if nanobench can test this run-once-at-start
code.

+                table[i] = SkFDot6Div(SK_FDot6One, i);
+            }
+        }
+    }
+};
+
+class QuickFDot6Inverse {
+private:
+    static FDot6InverseTable table;

[reed1, 2016/08/18 20:31:00]

nit: static variables are gPrefixedWIthAG.

[liyuqian, 2016/08/22 15:30:48]

Done.

+public:
+    inline static SkFixed lookup(SkFDot6 x) {

[reed1, 2016/08/18 20:31:00]

nit: static methods are Capitalized.

[liyuqian, 2016/08/22 15:30:48]

Done.

+        SkASSERT(SkAbs32(x) <= kInverseTableSize);
+        return table.table[x];
+    }
+};
+
+FDot6InverseTable QuickFDot6Inverse::table;

[reed1, 2016/08/18 20:31:01]

Chrome won't allow us to have a complex constructor. I suspect you'll need to
precompute the table, and check it in as a const table. Typically, we add that
in a separate file, e.g.

// new file

const SkFixed gInverse1KFixedTable[] = {
    0x..., ...
};

/*
Here is the code that builds the table...
*/

[liyuqian, 2016/08/22 15:30:48]

Done.

+
+inline SkFixed quickSkFDot6Div(SkFDot6 a, SkFDot6 b) {

[reed1, 2016/08/18 20:31:00]

Would this optimized version of FDot6Div also help the other callers? Perhaps it
could be landed as a separate CL... (with its own unittest)

[reed1, 2016/08/18 20:31:01]

'static' is more important than 'inline' (I think), since as written this
creates a global symbol.

[liyuqian, 2016/08/22 15:30:48]

Done.

[liyuqian, 2016/08/22 15:30:48]

Maybe. But so far, SkEdge.cpp/h is the only place that uses SkFDot6Div. Do you
still want to land it as a separate CL considering that?

+    if (SkAbs32(b) < kInverseTableSize) {
+        #ifdef SK_DEBUG
+        SkFixed directAnswer = SkFDot6Div(a, b);
+        // a has already been right shifted by 10,
+        // maximum inverse of FDot6 is 1 << 8 << 16 (which is 64 * SK_Fixed1),
+        // so we're safe to directly multiply them together (8 - 10 < 0)
+        SkFixed ourAnswer = (a * QuickFDot6Inverse::lookup(b)) >> 6;
+        SkASSERT(
+            (directAnswer == 0 && ourAnswer == 0) ||
+            SkFixedDiv(SkAbs32(directAnswer - ourAnswer), SkAbs32(directAnswer)) <= 1 << 10
+        );
+        #endif
+        return SkFixedMul_lowprec(SkFDot6ToFixed(a), QuickFDot6Inverse::lookup(b));
+    } else {
+        return SkFDot6Div(a, b);
+    }
+}
+
+// This will become a bottleneck for small ovals rendering if we call SkFixedDiv twice here.
+// Therefore, we'll let the outter function compute the slope once and send in the value.
+// Moreover, we'll compute fDY by quickly lookup the inverse table (if possible).
+bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1, SkFixed slope)
+{

[reed1, 2016/08/18 20:31:00]

nit: skia places the { on the same line as the function name

[liyuqian, 2016/08/22 15:30:48]

Done.

+    // Since we send in the slope, we can no longer snap y inside this function.
+    // If we don't send in the slope, or we do some more sophisticated snapping, this function
+    // could be a performance bottleneck.
+    SkASSERT(fWinding == 1 || fWinding == -1);
+    SkASSERT(fCurveCount != 0);
+
+    SkASSERT(y0 <= y1);
+
+    SkFDot6 dx = SkFixedToFDot6(x1 - x0);
+    SkFDot6 dy = SkFixedToFDot6(y1 - y0);
+
+    // are we a zero-height line?
+    if (dy == 0) {
+        return false;
+    }
+
+    SkASSERT(slope < SK_MaxS32);
+
+    SkFDot6     absSlope = SkAbs32(SkFixedToFDot6(slope));
+    fX          = x0;
+    fDX         = slope;
+    fUpperX     = x0;
+    fY          = y0;
+    fUpperY     = y0;
+    fLowerY     = y1;
+    fDY         = (absSlope | dx) == 0
+                  ? SK_MaxS32
+                  : absSlope < kInverseTableSize
+                    ? QuickFDot6Inverse::lookup(absSlope)
+                    : SkAbs32(quickSkFDot6Div(dy, dx));
+
+    return true;
+}
+
+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) {
+        SkASSERT(SkFixedCeilToInt(fLowerY) > clip.fTop);
+        SkFixed newY = SkIntToFixed(clip.fTop);
+        this->goY(newY);
+        fUpperY = newY;
+    }
+}
+
+int SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3])
+{

[reed1, 2016/08/18 20:31:00]

interesting. appears that much of this impl is the same as SkQuadraticEdge. Is
that the case? I wonder if there is some way to share code / macro / etc. ?

[liyuqian, 2016/08/22 15:30:48]

Done.

+    SkFixed x0 = SkScalarToFixed(pts[0].fX);
+    SkFixed y0 = SkScalarToFixed(pts[0].fY);
+    SkFixed x1 = SkScalarToFixed(pts[1].fX);
+    SkFixed y1 = SkScalarToFixed(pts[1].fY);
+    SkFixed x2 = SkScalarToFixed(pts[2].fX);
+    SkFixed 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) {
+        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
+    shift = SkTPin(shift, 1, MAX_COEFF_SHIFT);
+
+    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 {
+        SkFixed slope;
+        if (--count > 0)
+        {
+            newx    = oldx + (dx >> shift);
+            newy    = oldy + (dy >> shift);
+            slope = dy >> 10 > 0 ? quickSkFDot6Div(dx >> 10, dy >> 10) : SK_MaxS32;
+            if (SkAbs32(dy) >= SK_Fixed1 * 2) { // only snap when dy is large enough
+                newSnappedY = SkTMin<SkFixed>(fQLastY, SkFixedRoundToFixed(newy));
+                newSnappedX = newx + SkFixedMul_lowprec(slope, newSnappedY - newy);
+            } else {
+                newSnappedY = newy;
+                newSnappedX = newx;
+            }
+            dx    += fQDDx;
+            dy    += fQDDy;
+        }
+        else    // last segment
+        {
+            newx    = fQLastX;
+            newy    = fQLastY;
+            newSnappedY = newy;
+            newSnappedX = newx;
+            slope = (newSnappedY - fSnappedY) >> 10
+                    ? quickSkFDot6Div((newx - fSnappedX) >> 10, (newy - fSnappedY) >> 10)
+                    : SK_MaxS32;
+        }
+        if (slope < SK_MaxS32) {
+            success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope);
+        }
+        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,
+                SkFixedToFDot6(newy - oldy) == 0 ? SK_MaxS32 :
+                        SkFDot6Div(SkFixedToFDot6(newx - oldx), SkFixedToFDot6(newy - oldy)));
+        oldx = newx;
+        oldy = newy;
+    } while (count < 0 && !success);
+
+    fCx         = newx;
+    fCy         = newy;
+    fCurveCount = SkToS8(count);
+    return success;
+}