ccpr: Fix very small edges

Fixes a bug in the vertex shader backend where a pixel could be hit
twice on very small, axis-aligned edges.

Improves the coverage calculations to be more accurate when dealing with
very small edges.

Bug: skia:
Change-Id: I4bac191695d7b7d73b6eef9df0fca3539503a965
Reviewed-on: https://skia-review.googlesource.com/111323
Commit-Queue: Chris Dalton <csmartdalton@google.com>
Reviewed-by: Greg Daniel <egdaniel@google.com>

4 files changed, 133 insertions, 53 deletions

diff --git a/src/gpu/ccpr/GrCCCoverageProcessor.cpp b/src/gpu/ccpr/GrCCCoverageProcessor.cpp
index fc4409d40a..8c85a75d81 100644
--- a/src/gpu/ccpr/GrCCCoverageProcessor.cpp
+++ b/src/gpu/ccpr/GrCCCoverageProcessor.cpp
@@ -44,6 +44,41 @@ void GrCCCoverageProcessor::Shader::EmitEdgeDistanceEquation(GrGLSLVertexGeoBuil
     s->codeAppendf("%s = float3(-n, dot(n, %s) - .5);", outputDistanceEquation, leftPt);
 }
 
+void GrCCCoverageProcessor::Shader::CalcEdgeCoverageAtBloatVertex(GrGLSLVertexGeoBuilder* s,
+                                                                  const char* leftPt,
+                                                                  const char* rightPt,
+                                                                  const char* rasterVertexDir,
+                                                                  const char* outputCoverage) {
+    // Here we find an edge's coverage at one corner of a conservative raster bloat box whose center
+    // falls on the edge in question. (A bloat box is axis-aligned and the size of one pixel.) We
+    // always set up coverage so it is -1 at the outermost corner, 0 at the innermost, and -.5 at
+    // the center. Interpolated, these coverage values convert jagged conservative raster edges into
+    // smooth antialiased edges.
+    //
+    // d1 == (P + sign(n) * bloat) dot n                   (Distance at the bloat box vertex whose
+    //    == P dot n + (abs(n.x) + abs(n.y)) * bloatSize    coverage=-1, where the bloat box is
+    //                                                      centered on P.)
+    //
+    // d0 == (P - sign(n) * bloat) dot n                   (Distance at the bloat box vertex whose
+    //    == P dot n - (abs(n.x) + abs(n.y)) * bloatSize    coverage=0, where the bloat box is
+    //                                                      centered on P.)
+    //
+    // d == (P + rasterVertexDir * bloatSize) dot n        (Distance at the bloat box vertex whose
+    //   == P dot n + (rasterVertexDir dot n) * bloatSize   coverage we wish to calculate.)
+    //
+    // coverage == -(d - d0) / (d1 - d0)                   (coverage=-1 at d=d1; coverage=0 at d=d0)
+    //
+    //          == (rasterVertexDir dot n) / (abs(n.x) + abs(n.y)) * -.5 - .5
+    //
+    s->codeAppendf("float2 n = float2(%s.y - %s.y, %s.x - %s.x);",
+                   rightPt, leftPt, leftPt, rightPt);
+    s->codeAppend ("float nwidth = abs(n.x) + abs(n.y);");
+    s->codeAppendf("float t = dot(%s, n);", rasterVertexDir);
+    // The below conditional guarantees we get exactly 1 on the divide when nwidth=t (in case the
+    // GPU divides by multiplying by the reciprocal?) It also guards against NaN when nwidth=0.
+    s->codeAppendf("%s = (abs(t) != nwidth ? t / nwidth : sign(t)) * -.5 - .5;", outputCoverage);
+}
+
 int GrCCCoverageProcessor::Shader::DefineSoftSampleLocations(GrGLSLFPFragmentBuilder* f,
                                                              const char* samplesName) {
     // Standard DX11 sample locations.
diff --git a/src/gpu/ccpr/GrCCCoverageProcessor.h b/src/gpu/ccpr/GrCCCoverageProcessor.h
index bcb9bb7030..698087735c 100644
--- a/src/gpu/ccpr/GrCCCoverageProcessor.h
+++ b/src/gpu/ccpr/GrCCCoverageProcessor.h
@@ -178,7 +178,7 @@ public:
             this->onEmitVaryings(varyingHandler, scope, code, position, inputCoverage, wind);
         }
 
-        void emitFragmentCode(const GrCCCoverageProcessor& proc, GrGLSLFPFragmentBuilder*,
+        void emitFragmentCode(const GrCCCoverageProcessor&, GrGLSLFPFragmentBuilder*,
                               const char* skOutputColor, const char* skOutputCoverage) const;
 
         // Defines an equation ("dot(float3(pt, 1), distance_equation)") that is -1 on the outside
@@ -188,6 +188,16 @@ public:
                                              const char* rightPt,
                                              const char* outputDistanceEquation);
 
+        // Calculates an edge's coverage at a conservative raster vertex. The edge is defined by two
+        // clockwise-ordered points, 'leftPt' and 'rightPt'. 'rasterVertexDir' is a pair of +/-1
+        // values that point in the direction of conservative raster bloat, starting from an
+        // endpoint.
+        //
+        // Coverage values ramp from -1 (completely outside the edge) to 0 (completely inside).
+        static void CalcEdgeCoverageAtBloatVertex(GrGLSLVertexGeoBuilder*, const char* leftPt,
+                                                  const char* rightPt, const char* rasterVertexDir,
+                                                  const char* outputCoverage);
+
         virtual ~Shader() {}
 
     protected:
diff --git a/src/gpu/ccpr/GrCCCoverageProcessor_GSImpl.cpp b/src/gpu/ccpr/GrCCCoverageProcessor_GSImpl.cpp
index 224533b298..fe541483b6 100644
--- a/src/gpu/ccpr/GrCCCoverageProcessor_GSImpl.cpp
+++ b/src/gpu/ccpr/GrCCCoverageProcessor_GSImpl.cpp
@@ -267,13 +267,11 @@ public:
         g->codeAppendf("float2 left = pts[%s > 0 ? sk_InvocationID : nextidx];", wind.c_str());
         g->codeAppendf("float2 right = pts[%s > 0 ? nextidx : sk_InvocationID];", wind.c_str());
 
-        Shader::EmitEdgeDistanceEquation(g, "left", "right", "float3 edge_distance_equation");
-
         // Which quadrant does the vector from left -> right fall into?
         g->codeAppend ("float2 qlr = sign(right - left);");
         g->codeAppend ("float2x2 outer_pts = float2x2(left - bloat * qlr, right + bloat * qlr);");
-        g->codeAppend ("half2 outer_coverage = edge_distance_equation.xy * outer_pts + "
-                                              "edge_distance_equation.z;");
+        g->codeAppend ("half outer_coverage;");
+        Shader::CalcEdgeCoverageAtBloatVertex(g, "left", "right", "qlr", "outer_coverage");
 
         g->codeAppend ("float2 d1 = float2(qlr.y, -qlr.x);");
         g->codeAppend ("float2 d2 = d1;");
@@ -287,14 +285,14 @@ public:
         // invocation emits a different edge. Emit negative coverage that subtracts the appropiate
         // amount back out from the hull we drew above.
         g->codeAppend ("if (!aligned) {");
-        g->codeAppendf(    "%s(outer_pts[0], outer_coverage[0]);", emitVertexFn);
+        g->codeAppendf(    "%s(outer_pts[0], -1 - outer_coverage);", emitVertexFn);
         g->codeAppend ("}");
         g->codeAppendf("%s(left + bloat * d1, -1);", emitVertexFn);
         g->codeAppendf("%s(left - bloat * d2, 0);", emitVertexFn);
         g->codeAppendf("%s(right + bloat * d2, -1);", emitVertexFn);
         g->codeAppendf("%s(right - bloat * d1, 0);", emitVertexFn);
         g->codeAppend ("if (!aligned) {");
-        g->codeAppendf(    "%s(outer_pts[1], outer_coverage[1]);", emitVertexFn);
+        g->codeAppendf(    "%s(outer_pts[1], outer_coverage);", emitVertexFn);
         g->codeAppend ("}");
 
         g->configure(InputType::kLines, OutputType::kTriangleStrip, 6, 3);
diff --git a/src/gpu/ccpr/GrCCCoverageProcessor_VSImpl.cpp b/src/gpu/ccpr/GrCCCoverageProcessor_VSImpl.cpp
index 4ac6443322..4c3bb67a93 100644
--- a/src/gpu/ccpr/GrCCCoverageProcessor_VSImpl.cpp
+++ b/src/gpu/ccpr/GrCCCoverageProcessor_VSImpl.cpp
@@ -89,24 +89,38 @@ protected:
     typedef GrGLSLGeometryProcessor INHERITED;
 };
 
+static constexpr int kVertexData_LeftNeighborIdShift = 9;
+static constexpr int kVertexData_RightNeighborIdShift = 7;
+static constexpr int kVertexData_BloatIdxShift = 5;
+static constexpr int kVertexData_InvertCoverageBit = 1 << 4;
+static constexpr int kVertexData_IsEdgeBit = 1 << 3;
+static constexpr int kVertexData_IsHullBit = 1 << 2;
+
 /**
  * Vertex data tells the shader how to offset vertices for conservative raster, and how/whether to
  * calculate initial coverage values for edges. See VSHullAndEdgeImpl.
  */
-static constexpr int32_t pack_vertex_data(int32_t bloatIdx, int32_t edgeData,
-                                          int32_t cornerVertexID, int32_t cornerIdx) {
-    return (bloatIdx << 6) | (edgeData << 4) | (cornerVertexID << 2) | cornerIdx;
+static constexpr int32_t pack_vertex_data(int32_t leftNeighborID, int32_t rightNeighborID,
+                                          int32_t bloatIdx, int32_t cornerID,
+                                          int32_t extraData = 0) {
+    return (leftNeighborID << kVertexData_LeftNeighborIdShift) |
+           (rightNeighborID << kVertexData_RightNeighborIdShift) |
+           (bloatIdx << kVertexData_BloatIdxShift) |
+           cornerID | extraData;
 }
 
-static constexpr int32_t hull_vertex_data(int32_t cornerIdx, int32_t cornerVertexID, int n) {
-    return pack_vertex_data((cornerIdx + (2 == cornerVertexID ? 1 : n - 1)) % n, 0, cornerVertexID,
-                            cornerIdx);
+static constexpr int32_t hull_vertex_data(int32_t cornerID, int32_t bloatIdx, int n) {
+    return pack_vertex_data((cornerID + n - 1) % n, (cornerID + 1) % n, bloatIdx, cornerID,
+                            kVertexData_IsHullBit);
 }
 
-static constexpr int32_t edge_vertex_data(int32_t edgeID, int32_t endptIdx, int32_t endptVertexID,
+static constexpr int32_t edge_vertex_data(int32_t edgeID, int32_t endptIdx, int32_t bloatIdx,
                                           int n) {
-    return pack_vertex_data(0 == endptIdx ? (edgeID + 1) % n : edgeID, (endptIdx << 1) | 1,
-                            endptVertexID, 0 == endptIdx ? edgeID : (edgeID + 1) % n);
+    return pack_vertex_data(0 == endptIdx ? (edgeID + 1) % n : edgeID,
+                            0 == endptIdx ? (edgeID + 1) % n : edgeID,
+                            bloatIdx, 0 == endptIdx ? edgeID : (edgeID + 1) % n,
+                            kVertexData_IsEdgeBit |
+                            (!endptIdx ? kVertexData_InvertCoverageBit : 0));
 }
 
 static constexpr int32_t kHull3AndEdgeVertices[] = {
@@ -251,55 +265,78 @@ public:
         // Reverse all indices if the wind is counter-clockwise: [0, 1, 2] -> [2, 1, 0].
         v->codeAppendf("int clockwise_indices = wind > 0 ? %s : 0x%x - %s;",
                        proc.getAttrib(kAttribIdx_VertexData).fName,
-                       ((fNumSides - 1) << 6) | (0xf << 2) | (fNumSides - 1),
+                       ((fNumSides - 1) << kVertexData_LeftNeighborIdShift) |
+                       ((fNumSides - 1) << kVertexData_RightNeighborIdShift) |
+                       (((1 << kVertexData_RightNeighborIdShift) - 1) ^ 3) |
+                       (fNumSides - 1),
                        proc.getAttrib(kAttribIdx_VertexData).fName);
 
         // Here we generate conservative raster geometry for the input polygon. It is the convex
         // hull of N pixel-size boxes, one centered on each the input points. Each corner has three
         // vertices, where one or two may cause degenerate triangles. The vertex data tells us how
-        // to offset each vertex. Triangle edges are also handled here (see kHull3AndEdgeIndices).
-        // For more details on conservative raster, see:
+        // to offset each vertex. For more details on conservative raster, see:
         // https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter42.html
+        //
+        // Triangle edges are also handled here using the same concept (see kHull3AndEdgeVertices).
         v->codeAppendf("float2 corner = %s[clockwise_indices & 3];", hullPts);
-        v->codeAppendf("float2 bloatpoint = %s[clockwise_indices >> 6];", hullPts);
-        v->codeAppend ("float2 vertexbloat = float2(bloatpoint.y > corner.y ? -bloat : +bloat, "
-                                                   "bloatpoint.x > corner.x ? +bloat : -bloat);");
-
-        v->codeAppendf("if ((1 << 2) == (%s & (3 << 2))) {",
-                       proc.getAttrib(kAttribIdx_VertexData).fName);
-                           // We are the corner's middle vertex (of 3).
-        v->codeAppend (    "vertexbloat = float2(-vertexbloat.y, vertexbloat.x);");
-        v->codeAppend ("}");
-
-        v->codeAppendf("if ((2 << 2) == (%s & (3 << 2))) {",
-                       proc.getAttrib(kAttribIdx_VertexData).fName);
-                           // We are the corner's third vertex (of 3).
-        v->codeAppend (    "vertexbloat = -vertexbloat;");
+        v->codeAppendf("float2 left = %s[clockwise_indices >> %i];",
+                       hullPts, kVertexData_LeftNeighborIdShift);
+        v->codeAppendf("float2 right = %s[(clockwise_indices >> %i) & 3];",
+                       hullPts, kVertexData_RightNeighborIdShift);
+
+        v->codeAppend ("float2 leftbloat = sign(corner - left);");
+        v->codeAppend ("leftbloat = float2(0 != leftbloat.y ? leftbloat.y : leftbloat.x, "
+                                          "0 != leftbloat.x ? -leftbloat.x : -leftbloat.y);");
+
+        v->codeAppend ("float2 rightbloat = sign(right - corner);");
+        v->codeAppend ("rightbloat = float2(0 != rightbloat.y ? rightbloat.y : rightbloat.x, "
+                                           "0 != rightbloat.x ? -rightbloat.x : -rightbloat.y);");
+
+        v->codeAppend ("bool2 left_right_notequal = notEqual(leftbloat, rightbloat);");
+
+        // At each corner of the polygon, our hull will have either 1, 2, or 3 vertices. We begin
+        // with the first hull vertex (leftbloat), then continue rotating 90 degrees clockwise until
+        // we reach the desired vertex for this invocation. Corners with less than 3 corresponding
+        // hull vertices will result in redundant vertices and degenerate triangles.
+        v->codeAppend ("float2 bloatdir = leftbloat;");
+        v->codeAppendf("int bloatidx = (%s >> %i) & 3;",
+                       proc.getAttrib(kAttribIdx_VertexData).fName, kVertexData_BloatIdxShift);
+        v->codeAppend ("switch (bloatidx) {");
+        v->codeAppend (    "case 2:");
+        v->codeAppendf(        "if (all(left_right_notequal)) {");
+        v->codeAppend (            "bloatdir = float2(-bloatdir.y, +bloatdir.x);");
+        v->codeAppend (        "}");
+                               // fallthru.
+        v->codeAppend (    "case 1:");
+        v->codeAppendf(        "if (any(left_right_notequal)) {");
+        v->codeAppend (            "bloatdir = float2(-bloatdir.y, +bloatdir.x);");
+        v->codeAppend (        "}");
+                               // fallthru.
         v->codeAppend ("}");
 
-        v->codeAppend ("float2 vertex = corner + vertexbloat;");
-        gpArgs->fPositionVar.set(kFloat2_GrSLType, "vertex");
-
-        if (4 == fNumSides) {
-            // We don't generate edges around 4-sided polygons.
-            return nullptr; // Known hull vertices don't need an initial coverage value.
+        // For triangles, we also emit coverage in order to handle edges and corners.
+        const char* coverage = nullptr;
+        if (3 == fNumSides) {
+            v->codeAppend ("half coverage;");
+            Shader::CalcEdgeCoverageAtBloatVertex(v, "left", "corner", "bloatdir", "coverage");
+            v->codeAppendf("if (0 != (%s & %i)) {", // Are we the opposite endpoint of an edge?
+                           proc.getAttrib(kAttribIdx_VertexData).fName,
+                           kVertexData_InvertCoverageBit);
+            v->codeAppend (    "coverage = -1 - coverage;");
+            v->codeAppend ("}");
+
+            v->codeAppendf("if (0 != (%s & %i)) {", // Are we a hull vertex?
+                           proc.getAttrib(kAttribIdx_VertexData).fName, kVertexData_IsHullBit);
+            v->codeAppend (    "coverage = +1;"); // Hull coverage is +1 all around.
+            v->codeAppend ("}");
+
+            coverage = "coverage";
         }
 
-        // Find coverage for edge vertices.
-        Shader::EmitEdgeDistanceEquation(v, "bloatpoint", "corner",
-                                         "float3 edge_distance_equation");
-        v->codeAppend ("half coverage = dot(edge_distance_equation.xy, vertex) + "
-                                       "edge_distance_equation.z;");
-        v->codeAppendf("if (0 == (%s & (1 << 5))) {", proc.getAttrib(kAttribIdx_VertexData).fName);
-                           // We are the opposite endpoint. Invert coverage.
-        v->codeAppend (    "coverage = -1 - coverage;");
-        v->codeAppend ("}");
-        v->codeAppendf("if (0 == (%s & (1 << 4))) {", proc.getAttrib(kAttribIdx_VertexData).fName);
-                           // We are actually a hull vertex. Hull coverage is +1 all around.
-        v->codeAppend (    "coverage = +1;");
-        v->codeAppend ("}");
+        v->codeAppend ("float2 vertex = corner + bloatdir * bloat;");
+        gpArgs->fPositionVar.set(kFloat2_GrSLType, "vertex");
 
-        return "coverage";
+        return coverage;
     }
 
 private: