New analytic AA scan converter using delta (I call it DAA for now)

DAA is:

1. Much simpler than AAA.
   SkScan_AAAPath.cpp is about 1700 lines.
   SkScan_DAAPath.cpp is about 300 lines.
   The whole DAA CL is only about 800 lines.

2. Much faster than AAA for complicated paths.
   The speedup applies to GL backend (including ccpr)!
   Here's the frame time of 'SampleApp --slide Chart' on macbook pro:
     AAA-raster: 33ms
     DAA-raster: 21ms
     AAA-gl:     30ms
     DAA-gl:     20ms
     AAA-ccpr:   18ms
     DAA-ccpr:   12ms
   My linux desktop doesn't have SSE3 so the speedup is smaller
   (~25% for Chart). I believe that DAA is so fast that I can enable
   it for any paths (AAA is not enabled by default for complicated
   paths because it is slow; hence our older supersampling scan
   converter is used for stroking on Chart for AAA-xxx config.)

3. The SkCoverageDelta is suitable for threaded backend with
   out-of-order concurrent scan conversion as commented in the source
   code. Maybe we can also just send deltas to GPU.

4. Similar to most analytic path renderers, the quality is on the best
   ground-truth level, unless there are intersections within a pixel.
   The intersections look good to my eyes although theoretically that
   could be arbitrary far from the ground truth (see my AAA slides).

5. For simple paths, such as circle, triangle, rrect, etc., DAA is
   slower than AAA. But DAA is faster than our older supersampling
   scan converter in most cases. As those simple paths usually don't
   constitute the bottleneck of a picture (skp or svg), I strongly
   recommend use DAA.

6. DAA also heavily favors blitMask so it may work quite well with
   SkRasterPipeline and SkRasterPipelineBlitter.

Finally, please check https://skia-review.googlesource.com/c/22420/
which accelerate DAA by specializing blitCoverageDeltas for
SkARGB32_Blitter and SkARGB32_Black_Blitter. It brings a little(<5%)
speedup. But I couldn't figure out how to reduce the duplicate code
so I don't intend to land it.

Bug: skia:
Change-Id: I3b7ed6a727447922e645b1acb737a506e7c09a4c
Reviewed-on: https://skia-review.googlesource.com/19666
Reviewed-by: Mike Reed <reed@google.com>
Reviewed-by: Cary Clark <caryclark@google.com>
Commit-Queue: Yuqian Li <liyuqian@google.com>

1 files changed, 218 insertions, 0 deletions

diff --git a/src/core/SkCoverageDelta.h b/src/core/SkCoverageDelta.h
new file mode 100644
index 0000000000..e0ecb9d7e6
--- /dev/null
+++ b/src/core/SkCoverageDelta.h
@@ -0,0 +1,218 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkCoverageDelta_DEFINED
+#define SkCoverageDelta_DEFINED
+
+#include "SkArenaAlloc.h"
+#include "SkFixed.h"
+#include "SkMask.h"
+#include "SkTSort.h"
+#include "SkUtils.h"
+
+// Future todo: maybe we can make fX and fDelta 16-bit long to speed it up a little bit.
+struct SkCoverageDelta {
+    int     fX;     // the y coordinate will be implied in SkCoverageDeltaList
+    SkFixed fDelta; // the amount that the alpha changed
+
+    // Sort according to fX
+    bool operator<(const SkCoverageDelta& other) const {
+        return fX < other.fX;
+    }
+};
+
+// All the arguments needed for SkBlitter::blitAntiRect
+struct SkAntiRect {
+    int     fX;
+    int     fY;
+    int     fWidth;
+    int     fHeight;
+    SkAlpha fLeftAlpha;
+    SkAlpha fRightAlpha;
+};
+
+using SkCoverageDeltaAllocator = SkSTArenaAlloc<256>;
+
+// A list of SkCoverageDelta with y from top() to bottom().
+// For each row y, there are count(y) number of deltas.
+// You can ask whether they are sorted or not by sorted(y), and you can sort them by sort(y).
+// Once sorted, getDelta(y, i) should return the i-th leftmost delta on row y.
+class SkCoverageDeltaList {
+public:
+    // We can store INIT_ROW_SIZE deltas per row (i.e., per y-scanline) initially
+    static constexpr int INIT_ROW_SIZE = 32;
+    static constexpr int RESERVED_HEIGHT = 128; // reserve this many rows on stack memory
+
+    SkCoverageDeltaList(SkCoverageDeltaAllocator* alloc, int top, int bottom, bool forceRLE);
+
+    inline int  top() const { return fTop; }
+    inline int  bottom() const { return fBottom; }
+    inline bool forceRLE() const { return fForceRLE; }
+    inline int  count(int y) const { this->checkY(y); return fCounts[y]; }
+    inline bool sorted(int y) const { this->checkY(y); return fSorted[y]; }
+    inline void addDelta(int x, int y, SkFixed delta) { this->push_back(y, {x, delta}); }
+
+    inline const SkCoverageDelta& getDelta(int y, int i) const {
+        this->checkY(y);
+        SkASSERT(i < fCounts[y]);
+        return fRows[y][i];
+    }
+
+    // It might be better to sort right before blitting to make the memory hot
+    inline void sort(int y) {
+        this->checkY(y);
+        if (!fSorted[y]) {
+            SkTQSort(fRows[y], fRows[y] + fCounts[y] - 1);
+            fSorted[y] = true;
+        }
+    }
+
+    inline const SkAntiRect& getAntiRect() const { return fAntiRect; }
+    inline void setAntiRect(int x, int y, int width, int height,
+            SkAlpha leftAlpha, SkAlpha rightAlpha) {
+        fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
+    }
+
+    inline void push_back(int y, const SkCoverageDelta& delta) {
+        this->checkY(y);
+        if (fCounts[y] == fMaxCounts[y]) {
+            fMaxCounts[y] *= 2;
+            SkCoverageDelta* newRow = fAlloc->makeArrayDefault<SkCoverageDelta>(fMaxCounts[y]);
+            memcpy(newRow, fRows[y], sizeof(SkCoverageDelta) * fCounts[y]);
+            fRows[y] = newRow;
+        }
+        SkASSERT(fCounts[y] < fMaxCounts[y]);
+        fRows[y][fCounts[y]++] = delta;
+        fSorted[y] = fSorted[y] && (fCounts[y] == 1 || delta.fX >= fRows[y][fCounts[y] - 2].fX);
+    }
+
+private:
+    SkCoverageDeltaAllocator*   fAlloc;
+    SkCoverageDelta**           fRows;
+    bool*                       fSorted;
+    int*                        fCounts;
+    int*                        fMaxCounts;
+    int                         fTop;
+    int                         fBottom;
+    SkAntiRect                  fAntiRect;
+    bool                        fForceRLE;
+
+    SkCoverageDelta             fReservedStorage[RESERVED_HEIGHT * INIT_ROW_SIZE];
+    SkCoverageDelta*            fReservedRows[RESERVED_HEIGHT];
+    bool                        fReservedSorted[RESERVED_HEIGHT];
+    int                         fReservedCounts[RESERVED_HEIGHT];
+    int                         fReservedMaxCounts[RESERVED_HEIGHT];
+
+    inline void checkY(int y) const { SkASSERT(y >= fTop && y < fBottom); }
+};
+
+class SkCoverageDeltaMask {
+public:
+    // 1 for precision error, 1 for boundary delta (e.g., -SK_Fixed1 at fBounds.fRight + 1)
+    static constexpr int PADDING        = 2;
+
+    static constexpr int SIMD_WIDTH     = 8;
+    static constexpr int SUITABLE_WIDTH = 32;
+    static constexpr int MAX_MASK_SIZE  = 2048;
+
+    // Expand PADDING on both sides, and make it a multiple of SIMD_WIDTH
+    static int  ExpandWidth(int width);
+    static bool CanHandle(const SkIRect& bounds);   // whether bounds fits into MAX_MASK_SIZE
+    static bool Suitable(const SkIRect& bounds);    // CanHandle(bounds) && width <= SUITABLE_WIDTH
+
+    SkCoverageDeltaMask(const SkIRect& bounds);
+
+    inline int              top()       const { return fBounds.fTop; }
+    inline int              bottom()    const { return fBounds.fBottom; }
+    inline SkAlpha*         getMask()         { return fMask; }
+    inline const SkIRect&   getBounds() const { return fBounds; }
+
+    inline void             addDelta (int x, int y, SkFixed delta) { this->delta(x, y) += delta; }
+    inline SkFixed&         delta    (int x, int y) {
+        this->checkX(x);
+        this->checkY(y);
+        return fDeltas[this->index(x, y)];
+    }
+
+    inline void setAntiRect(int x, int y, int width, int height,
+                            SkAlpha leftAlpha, SkAlpha rightAlpha) {
+        fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
+    }
+
+    inline SkMask prepareSkMask() {
+        SkMask mask;
+        mask.fImage     = fMask;
+        mask.fBounds    = fBounds;
+        mask.fRowBytes  = fBounds.width();
+        mask.fFormat    = SkMask::kA8_Format;
+        return mask;
+    }
+
+    void convertCoverageToAlpha(bool isEvenOdd, bool isInverse, bool isConvex);
+
+private:
+    SkIRect     fBounds;
+    SkFixed     fDeltaStorage[MAX_MASK_SIZE];
+    SkFixed*    fDeltas;
+    SkAlpha     fMask[MAX_MASK_SIZE];
+    int         fExpandedWidth;
+    SkAntiRect  fAntiRect;
+
+    inline int  index(int x, int y) const { return y * fExpandedWidth + x; }
+    inline void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); }
+    inline void checkX(int x) const {
+        SkASSERT(x >= fBounds.fLeft - PADDING && x < fBounds.fRight + PADDING);
+    }
+};
+
+static SK_ALWAYS_INLINE SkAlpha CoverageToAlpha(SkFixed coverage, bool isEvenOdd, bool isInverse) {
+    SkAlpha result;
+    if (isEvenOdd) {
+        SkFixed mod17 = coverage & 0x1ffff;
+        SkFixed mod16 = coverage & 0xffff;
+        result = SkTPin(SkAbs32((mod16 << 1) - mod17) >> 8, 0, 255);
+    } else {
+        result = SkTPin(SkAbs32(coverage) >> 8, 0, 255);
+    }
+    return isInverse ? 255 - result : result;
+}
+
+template<typename T>
+static SK_ALWAYS_INLINE T CoverageToAlpha(T coverage, bool isEvenOdd, bool isInverse) {
+    T t0(0), t255(255);
+    T result;
+    if (isEvenOdd) {
+        T mod17 = coverage & 0x1ffff;
+        T mod16 = coverage & 0xffff;
+        result = ((mod16 << 1) - mod17).abs() >> 8;
+    } else {
+        result = coverage.abs() >> 8;;
+    }
+    result = T::Min(result, t255);
+    result = T::Max(result, t0);
+    return isInverse ? 255 - result : result;
+}
+
+// For convex paths (including inverse mode), the coverage is guaranteed to be
+// between [-SK_Fixed1, SK_Fixed1] so we can skip isEvenOdd and SkTPin.
+static SK_ALWAYS_INLINE SkAlpha ConvexCoverageToAlpha(SkFixed coverage, bool isInverse) {
+    SkASSERT(coverage >= -SK_Fixed1 && coverage <= SK_Fixed1);
+    int result = SkAbs32(coverage) >> 8;
+    result -= (result >> 8); // 256 to 255
+    return isInverse ? 255 - result : result;
+}
+
+template<typename T>
+static SK_ALWAYS_INLINE T ConvexCoverageToAlpha(T coverage, bool isInverse) {
+    // allTrue is not implemented
+    // SkASSERT((coverage >= 0).allTrue() && (coverage <= SK_Fixed1).allTrue());
+    T result = coverage.abs() >> 8;
+    result -= (result >> 8); // 256 to 255
+    return isInverse ? 255 - result : result;
+}
+
+#endif