No chop at y extrema for cubics

The new Delta AA scan converter does not need the edge to be updated
with monotonic Y so chopping at y extrema is not necessary. Removing
such chopping brings ~10% performance increase to chalkboard.svg which
has tons of small cubics (the same is true for many svgs I saw).

We didn't remove the chopping for quads because that does not bring
a significant speedup. Moreover, dropping those y extremas would make
our strokecircle animation look a little more wobbly (because we would
have fewer divisions for the quads at the top and bottom of the circle).

Bug: skia:
Change-Id: I3984d2619f9f77269ed24e8cbfa9f1429ebca4a8
Reviewed-on: https://skia-review.googlesource.com/31940
Reviewed-by: Mike Reed <reed@google.com>
Commit-Queue: Yuqian Li <liyuqian@google.com>

7 files changed, 58 insertions, 20 deletions

diff --git a/src/core/SkAnalyticEdge.cpp b/src/core/SkAnalyticEdge.cpp
index 7cb6493f8b..e2da09023d 100644
--- a/src/core/SkAnalyticEdge.cpp
+++ b/src/core/SkAnalyticEdge.cpp
@@ -20,6 +20,14 @@ bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1,
     SkASSERT(fWinding == 1 || fWinding == -1);
     SkASSERT(fCurveCount != 0);
 
+    // We don't chop at y extrema for cubics so the y is not guaranteed to be increasing for them.
+    // In that case, we have to swap x/y and negate the winding.
+    if (y0 > y1) {
+        SkTSwap(x0, x1);
+        SkTSwap(y0, y1);
+        fWinding = -fWinding;
+    }
+
     SkASSERT(y0 <= y1);
 
     SkFDot6 dx = SkFixedToFDot6(x1 - x0);
@@ -48,10 +56,10 @@ bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1,
     return true;
 }
 
-bool SkAnalyticEdge::update(SkFixed last_y) {
+bool SkAnalyticEdge::update(SkFixed last_y, bool sortY) {
     SkASSERT(last_y >= fLowerY); // we shouldn't update edge if last_y < fLowerY
     if (fCurveCount < 0) {
-        return static_cast<SkAnalyticCubicEdge*>(this)->updateCubic();
+        return static_cast<SkAnalyticCubicEdge*>(this)->updateCubic(sortY);
     } else if (fCurveCount > 0) {
         return static_cast<SkAnalyticQuadraticEdge*>(this)->updateQuadratic();
     }
@@ -147,10 +155,10 @@ bool SkAnalyticQuadraticEdge::updateQuadratic() {
     return success;
 }
 
-bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4]) {
+bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4], bool sortY) {
     fRiteE = nullptr;
 
-    if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy)) {
+    if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy, sortY)) {
         return false;
     }
 
@@ -174,10 +182,10 @@ bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4]) {
 
     fSnappedY = fCEdge.fCy;
 
-    return this->updateCubic();
+    return this->updateCubic(sortY);
 }
 
-bool SkAnalyticCubicEdge::updateCubic() {
+bool SkAnalyticCubicEdge::updateCubic(bool sortY) {
     int     success;
     int     count = fCurveCount;
     SkFixed oldx = fCEdge.fCx;
@@ -205,14 +213,14 @@ bool SkAnalyticCubicEdge::updateCubic() {
 
         // 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) {
+        if (sortY && newy < oldy) {
             newy = oldy;
         }
 
         SkFixed newSnappedY = SnapY(newy);
         // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint
         // doesn't always achieve that, so we have to explicitly pin it here.
-        if (fCEdge.fCLastY < newSnappedY) {
+        if (sortY && fCEdge.fCLastY < newSnappedY) {
             newSnappedY = fCEdge.fCLastY;
             count = 0;
         }
diff --git a/src/core/SkAnalyticEdge.h b/src/core/SkAnalyticEdge.h
index 533d769c55..13f62571a9 100644
--- a/src/core/SkAnalyticEdge.h
+++ b/src/core/SkAnalyticEdge.h
@@ -81,7 +81,7 @@ struct SkAnalyticEdge {
     inline bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope);
 
     // return true if we're NOT done with this edge
-    bool update(SkFixed last_y);
+    bool update(SkFixed last_y, bool sortY = true);
 
 #ifdef SK_DEBUG
     void dump() const {
@@ -124,8 +124,8 @@ struct SkAnalyticCubicEdge : public SkAnalyticEdge {
 
     SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping
 
-    bool setCubic(const SkPoint pts[4]);
-    bool updateCubic();
+    bool setCubic(const SkPoint pts[4], bool sortY = true);
+    bool updateCubic(bool sortY = true);
     inline void keepContinuous() {
         SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1);
         fCEdge.fCx = fX;
@@ -223,7 +223,11 @@ struct SkCubic : public SkBezier {
     SkPoint fP3;
 
     bool set(const SkPoint pts[4]){
-        if (IsEmpty(pts[0].fY, pts[3].fY)) {
+        // We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be
+        // monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just
+        // checking IsEmpty(pts[0].fY, pts[3].fY).
+        if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) &&
+                IsEmpty(pts[2].fY, pts[3].fY)) {
             return false;
         }
         fCount = 4;
diff --git a/src/core/SkEdge.cpp b/src/core/SkEdge.cpp
index f8e8d98b5d..1bb8e9e0d4 100644
--- a/src/core/SkEdge.cpp
+++ b/src/core/SkEdge.cpp
@@ -347,7 +347,7 @@ static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
     return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
 }
 
-bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift) {
+bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift, bool sortY) {
     SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
 
     {
@@ -374,7 +374,7 @@ bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift) {
     }
 
     int winding = 1;
-    if (y0 > y3)
+    if (sortY && y0 > y3)
     {
         SkTSwap(x0, x3);
         SkTSwap(x1, x2);
@@ -387,7 +387,7 @@ bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift) {
     int bot = SkFDot6Round(y3);
 
     // are we a zero-height cubic (line)?
-    if (top == bot)
+    if (sortY && top == bot)
         return 0;
 
     // compute number of steps needed (1 << shift)
diff --git a/src/core/SkEdge.h b/src/core/SkEdge.h
index 9be9325521..509c0c448a 100644
--- a/src/core/SkEdge.h
+++ b/src/core/SkEdge.h
@@ -80,7 +80,7 @@ struct SkCubicEdge : public SkEdge {
     SkFixed fCDDDx, fCDDDy;
     SkFixed fCLastX, fCLastY;
 
-    bool setCubicWithoutUpdate(const SkPoint pts[4], int shiftUp);
+    bool setCubicWithoutUpdate(const SkPoint pts[4], int shiftUp, bool sortY = true);
     int setCubic(const SkPoint pts[4], int shiftUp);
     int updateCubic();
 };
diff --git a/src/core/SkEdgeBuilder.cpp b/src/core/SkEdgeBuilder.cpp
index 7a02187470..1ba9e1d993 100644
--- a/src/core/SkEdgeBuilder.cpp
+++ b/src/core/SkEdgeBuilder.cpp
@@ -427,6 +427,10 @@ int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp,
                     }
                 } break;
                 case SkPath::kCubic_Verb: {
+                    if (fEdgeType == kBezier) {
+                        this->addCubic(pts);
+                        break;
+                    }
                     SkPoint monoY[10];
                     int n = SkChopCubicAtYExtrema(pts, monoY);
                     for (int i = 0; i <= n; i++) {
diff --git a/src/core/SkEdgeBuilder.h b/src/core/SkEdgeBuilder.h
index b876fcf5e5..a549e15681 100644
--- a/src/core/SkEdgeBuilder.h
+++ b/src/core/SkEdgeBuilder.h
@@ -21,8 +21,19 @@ class SkPath;
 class SkEdgeBuilder {
 public:
     enum EdgeType {
+        // Used in supersampling or non-AA scan coverter; it stores only integral y coordinates.
         kEdge,
+
+        // Used in Analytic AA scan converter; it uses SkFixed to store fractional y.
         kAnalyticEdge,
+
+        // Used in Delta AA scan converter; it's a super-light wrapper of SkPoint, which can then be
+        // used to construct SkAnalyticEdge (kAnalyticEdge) later. We use kBezier to save the memory
+        // allocation time (a SkBezier is much lighter than SkAnalyticEdge or SkEdge). Note that
+        // Delta AA only has to deal with one SkAnalyticEdge at a time (whereas Analytic AA has to
+        // deal with all SkAnalyticEdges at the same time). Thus for Delta AA, we only need to
+        // allocate memory for n SkBeziers and 1 SkAnalyticEdge. (Analytic AA need to allocate
+        // memory for n SkAnalyticEdges.)
         kBezier
     };
 
@@ -76,6 +87,8 @@ public:
     void addCubic(const SkPoint pts[]);
     void addClipper(SkEdgeClipper*);
 
+    EdgeType edgeType() const { return fEdgeType; }
+
     int buildPoly(const SkPath& path, const SkIRect* clip, int shiftUp, bool clipToTheRight);
 
     inline void addPolyLine(SkPoint pts[], char* &edge, size_t edgeSize, char** &edgePtr,
diff --git a/src/core/SkScan_DAAPath.cpp b/src/core/SkScan_DAAPath.cpp
index 68bc15de57..de24e49bcd 100644
--- a/src/core/SkScan_DAAPath.cpp
+++ b/src/core/SkScan_DAAPath.cpp
@@ -226,21 +226,27 @@ void gen_alpha_deltas(const SkPath& path, const SkRegion& clipRgn, Deltas& resul
         SkAnalyticEdge* currE   = &storage;
         bool edgeSet            = false;
 
+        int originalWinding = 1;
+        bool sortY = true;
         switch (bezier->fCount) {
             case 2: {
                 edgeSet = currE->setLine(bezier->fP0, bezier->fP1);
+                originalWinding = currE->fWinding;
                 break;
             }
             case 3: {
                 SkQuad* quad = static_cast<SkQuad*>(bezier);
                 SkPoint pts[3] = {quad->fP0, quad->fP1, quad->fP2};
                 edgeSet = static_cast<SkAnalyticQuadraticEdge*>(currE)->setQuadratic(pts);
+                originalWinding = static_cast<SkAnalyticQuadraticEdge*>(currE)->fQEdge.fWinding;
                 break;
             }
             case 4: {
+                sortY = false;
                 SkCubic* cubic = static_cast<SkCubic*>(bezier);
                 SkPoint pts[4] = {cubic->fP0, cubic->fP1, cubic->fP2, cubic->fP3};
-                edgeSet = static_cast<SkAnalyticCubicEdge*>(currE)->setCubic(pts);
+                edgeSet = static_cast<SkAnalyticCubicEdge*>(currE)->setCubic(pts, sortY);
+                originalWinding = static_cast<SkAnalyticCubicEdge*>(currE)->fCEdge.fWinding;
                 break;
             }
         }
@@ -259,7 +265,9 @@ void gen_alpha_deltas(const SkPath& path, const SkRegion& clipRgn, Deltas& resul
             if (lowerCeil <= upperFloor + SK_Fixed1) { // only one row is affected by the currE
                 SkFixed rowHeight = currE->fLowerY - currE->fUpperY;
                 SkFixed nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight);
-                add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
+                if (iy >= clipRect.fTop && iy < clipRect.fBottom) {
+                    add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
+                }
                 continue;
             }
 
@@ -296,12 +304,13 @@ void gen_alpha_deltas(const SkPath& path, const SkRegion& clipRgn, Deltas& resul
             }
 
             // last partial row
-            if (SkIntToFixed(iy) < currE->fLowerY) {
+            if (SkIntToFixed(iy) < currE->fLowerY && iy >= clipRect.fTop && iy < clipRect.fBottom) {
                 rowHeight = currE->fLowerY - SkIntToFixed(iy);
                 nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight);
                 add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result);
             }
-        } while (currE->update(currE->fLowerY));
+        // Intended assignment to fWinding to restore the maybe-negated winding (during updateLine)
+        } while ((currE->fWinding = originalWinding) && currE->update(currE->fLowerY, sortY));
     }
 }