Screenspace AA tessellated path rendering.

src/gpu/GrTessellator.cpp

Index: src/gpu/GrTessellator.cpp
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index ccffa9ffbeed21b29156e96c8d8e4cffe82e06c7..9ce1a739df8dff27b24d3364da825fa35928ca24 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -7,6 +7,7 @@
 
 #include "GrTessellator.h"
 
+#include "GrDefaultGeoProcFactory.h"
 #include "GrPathUtils.h"
 
 #include "SkChunkAlloc.h"
@@ -16,7 +17,7 @@
 #include <stdio.h>
 
 /*
- * There are six stages to the algorithm:
+ * There are six stages to the basic algorithm:
  *
  * 1) Linearize the path contours into piecewise linear segments (path_to_contours()).
  * 2) Build a mesh of edges connecting the vertices (build_edges()).
@@ -25,6 +26,16 @@
  * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
  * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()).
  *
+ * For screenspace antialiasing, the algorithm is modified as follows:
+ *
+ * Run steps 1-5 above to produce polygons.
+ * 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()).
+ * 5c) Simplify boundaries to remove "pointy" vertices which cause inversions (simplify_boundary()).
+ * 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
+ *     new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a new
+ *     antialiased mesh from those vertices (boundary_to_aa_mesh()).
+ * Run steps 3-6 above on the new mesh, and produce antialiased triangles.
+ *
  * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
  * of vertices (and the necessity of inserting new vertices on intersection).
  *
@@ -130,11 +141,12 @@ void list_remove(T* t, T** head, T** tail) {
  */
 
 struct Vertex {
-  Vertex(const SkPoint& point)
+  Vertex(const SkPoint& point, uint8_t alpha)
     : fPoint(point), fPrev(nullptr), fNext(nullptr)
     , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
     , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
     , fProcessed(false)
+    , fAlpha(alpha)
 #if LOGGING_ENABLED
     , fID (-1.0f)
 #endif
@@ -147,6 +159,7 @@ struct Vertex {
     Edge*   fFirstEdgeBelow;  // Linked list of edges below this vertex.
     Edge*   fLastEdgeBelow;   // "
     bool    fProcessed;       // Has this vertex been seen in simplify()?
+    uint8_t fAlpha;
 #if LOGGING_ENABLED
     float   fID;              // Identifier used for logging.
 #endif
@@ -154,6 +167,11 @@ struct Vertex {
 
 /***************************************************************************************/
 
+struct AAParams {
+    bool fTweakAlpha;
+    GrColor fColor;
+};
+
 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
 
 struct Comparator {
@@ -177,33 +195,43 @@ bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) {
     return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY;
 }
 
-inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) {
-    *data++ = v->fPoint;
-    return data;
+inline void* emit_vertex(Vertex* v, const AAParams* aaParams, void* data) {
+    if (!aaParams) {
+        SkPoint* d = static_cast<SkPoint*>(data);
+        *d++ = v->fPoint;
+        return d;
+    }
+    if (aaParams->fTweakAlpha) {
+        auto d = static_cast<GrDefaultGeoProcFactory::PositionColorAttr*>(data);
+        d->fPosition = v->fPoint;
+        d->fColor = SkAlphaMulQ(aaParams->fColor, v->fAlpha);
+        d++;
+        return d;
+    }
+    auto d = static_cast<GrDefaultGeoProcFactory::PositionColorCoverageAttr*>(data);
+    d->fPosition = v->fPoint;
+    d->fColor = aaParams->fColor;
+    d->fCoverage = GrNormalizeByteToFloat(v->fAlpha);
+    d++;
+    return d;
 }
 
-SkPoint* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, SkPoint* data) {
-#if WIREFRAME
-    data = emit_vertex(v0, data);
-    data = emit_vertex(v1, data);
-    data = emit_vertex(v1, data);
-    data = emit_vertex(v2, data);
-    data = emit_vertex(v2, data);
-    data = emit_vertex(v0, data);
+void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, const AAParams* aaParams, void* data) {
+#if TESSELLATOR_WIREFRAME
+    data = emit_vertex(v0, aaParams, data);
+    data = emit_vertex(v1, aaParams, data);
+    data = emit_vertex(v1, aaParams, data);
+    data = emit_vertex(v2, aaParams, data);
+    data = emit_vertex(v2, aaParams, data);
+    data = emit_vertex(v0, aaParams, data);
 #else
-    data = emit_vertex(v0, data);
-    data = emit_vertex(v1, data);
-    data = emit_vertex(v2, data);
+    data = emit_vertex(v0, aaParams, data);
+    data = emit_vertex(v1, aaParams, data);
+    data = emit_vertex(v2, aaParams, data);
 #endif
     return data;
 }
 
-struct EdgeList {
-    EdgeList() : fHead(nullptr), fTail(nullptr) {}
-    Edge* fHead;
-    Edge* fTail;
-};
-
 struct VertexList {
     VertexList() : fHead(nullptr), fTail(nullptr) {}
     Vertex* fHead;
@@ -217,8 +245,21 @@ struct VertexList {
     void prepend(Vertex* v) {
         insert(v, nullptr, fHead);
     }
+    void close() {
+        if (fHead && fTail) {
+            fTail->fNext = fHead;
+            fHead->fPrev = fTail;
+        }
+    }
 };
 
+// Round to nearest quarter-pixel. This is used for screenspace tessellation.
+
+inline void round(SkPoint* p) {
+    p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
+    p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
+}
+
 /**
  * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
  * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
@@ -320,8 +361,33 @@ struct Edge {
         p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
         return true;
     }
-    bool isActive(EdgeList* activeEdges) const {
-        return activeEdges && (fLeft || fRight || activeEdges->fHead == this);
+};
+
+struct EdgeList {
+    EdgeList() : fHead(nullptr), fTail(nullptr), fNext(nullptr), fCount(0) {}
+    Edge* fHead;
+    Edge* fTail;
+    EdgeList* fNext;
+    int fCount;
+    void insert(Edge* edge, Edge* prev, Edge* next) {
+        list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
+        fCount++;
+    }
+    void append(Edge* e) {
+        insert(e, fTail, nullptr);
+    }
+    void remove(Edge* edge) {
+        list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
+        fCount--;
+    }
+    void close() {
+        if (fHead && fTail) {
+            fTail->fRight = fHead;
+            fHead->fLeft = fTail;
+        }
+    }
+    bool contains(Edge* edge) const {
+        return edge->fLeft || edge->fRight || fHead == edge;
     }
 };
 
@@ -372,7 +438,7 @@ struct Poly {
             }
         }
 
-        SkPoint* emit(SkPoint* data) {
+        void* emit(const AAParams* aaParams, void* data) {
             Edge* e = fFirstEdge;
             e->fTop->fPrev = e->fTop->fNext = nullptr;
             VertexList vertices;
@@ -399,7 +465,7 @@ struct Poly {
                 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
                 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
                 if (ax * by - ay * bx >= 0.0) {
-                    data = emit_triangle(prev, curr, next, data);
+                    data = emit_triangle(prev, curr, next, aaParams, data);
                     v->fPrev->fNext = v->fNext;
                     v->fNext->fPrev = v->fPrev;
                     if (v->fPrev == first) {
@@ -455,13 +521,13 @@ struct Poly {
         }
         return poly;
     }
-    SkPoint* emit(SkPoint *data) {
+    void* emit(const AAParams* aaParams, void *data) {
         if (fCount < 3) {
             return data;
         }
         LOG("emit() %d, size %d\n", fID, fCount);
         for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
-            data = m->emit(data);
+            data = m->emit(aaParams, data);
         }
         return data;
     }
@@ -491,9 +557,16 @@ Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
     return poly;
 }
 
+EdgeList* new_contour(EdgeList** head, SkChunkAlloc& alloc) {
+    EdgeList* contour = ALLOC_NEW(EdgeList, (), alloc);
+    contour->fNext = *head;
+    *head = contour;
+    return contour;
+}
+
 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head,
                                 SkChunkAlloc& alloc) {
-    Vertex* v = ALLOC_NEW(Vertex, (p), alloc);
+    Vertex* v = ALLOC_NEW(Vertex, (p, 255), alloc);
 #if LOGGING_ENABLED
     static float gID = 0.0f;
     v->fID = gID++;
@@ -578,7 +651,7 @@ void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
     if (path.isInverseFillType()) {
         SkPoint quad[4];
         clipBounds.toQuad(quad);
-        for (int i = 3; i >= 0; i--) {
+        for (int i = 0; i < 4; i++) {
             prev = append_point_to_contour(quad[i], prev, &head, alloc);
         }
         head->fPrev = prev;
@@ -649,14 +722,18 @@ void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
     }
 }
 
-inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
+inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) {
+    if (!poly) {
+        return false;
+    }
+    int winding = poly->fWinding;
     switch (fillType) {
         case SkPath::kWinding_FillType:
             return winding != 0;
         case SkPath::kEvenOdd_FillType:
             return (winding & 1) != 0;
         case SkPath::kInverseWinding_FillType:
-            return winding == 1;
+            return winding == -1;
         case SkPath::kInverseEvenOdd_FillType:
             return (winding & 1) == 1;
         default:
@@ -665,8 +742,9 @@ inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
     }
 }
 
-Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
-    int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
+Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c,
+               int winding_scale = 1) {
+    int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? winding_scale : -winding_scale;
     Vertex* top = winding < 0 ? next : prev;
     Vertex* bottom = winding < 0 ? prev : next;
     return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
@@ -674,15 +752,15 @@ Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
 
 void remove_edge(Edge* edge, EdgeList* edges) {
     LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
-    SkASSERT(edge->isActive(edges));
-    list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
+    SkASSERT(edges->contains(edge));
+    edges->remove(edge);
 }
 
 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
     LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
-    SkASSERT(!edge->isActive(edges));
+    SkASSERT(!edges->contains(edge));
     Edge* next = prev ? prev->fRight : edges->fHead;
-    list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
+    edges->insert(edge, prev, next);
 }
 
 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
@@ -722,7 +800,7 @@ void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef
 }
 
 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
-    if (edge->isActive(activeEdges)) {
+    if (activeEdges && activeEdges->contains(edge)) {
         if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
             remove_edge(edge, activeEdges);
         }
@@ -791,7 +869,7 @@ void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
     LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
     remove_edge_above(edge);
     remove_edge_below(edge);
-    if (edge->isActive(edges)) {
+    if (edges && edges->contains(edge)) {
         remove_edge(edge, edges);
     }
 }
@@ -928,9 +1006,24 @@ void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC
     }
 }
 
+Edge* connect(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator c,
+              int winding_scale = 1) {
+    Edge* edge = new_edge(prev, next, alloc, c, winding_scale);
+    if (edge->fWinding > 0) {
+        insert_edge_below(edge, prev, c);
+        insert_edge_above(edge, next, c);
+    } else {
+        insert_edge_below(edge, next, c);
+        insert_edge_above(edge, prev, c);
+    }
+    merge_collinear_edges(edge, nullptr, c);
+    return edge;
+}
+
 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkChunkAlloc& alloc) {
     LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY,
         src->fID, dst->fID);
+    dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha);
     for (Edge* edge = src->fFirstEdgeAbove; edge;) {
         Edge* next = edge->fNextEdgeAbove;
         set_bottom(edge, dst, nullptr, c);
@@ -944,6 +1037,11 @@ void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh
     list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
 }
 
+uint8_t max_edge_alpha(Edge* a, Edge* b) {
+    return SkTMax(SkTMax(a->fTop->fAlpha, a->fBottom->fAlpha),
+                  SkTMax(b->fTop->fAlpha, b->fBottom->fAlpha));
+}
+
 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
                                SkChunkAlloc& alloc) {
     SkPoint p;
@@ -979,7 +1077,8 @@ Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
             } else if (coincident(nextV->fPoint, p)) {
                 v = nextV;
             } else {
-                v = ALLOC_NEW(Vertex, (p), alloc);
+                uint8_t alpha = max_edge_alpha(edge, other);
+                v = ALLOC_NEW(Vertex, (p, alpha), alloc);
                 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
                     prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
                     nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
@@ -999,10 +1098,13 @@ Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
     return nullptr;
 }
 
-void sanitize_contours(Vertex** contours, int contourCnt) {
+void sanitize_contours(Vertex** contours, int contourCnt, bool approximate) {
     for (int i = 0; i < contourCnt; ++i) {
         SkASSERT(contours[i]);
         for (Vertex* v = contours[i];;) {
+            if (approximate) {
+                round(&v->fPoint);
+            }
             if (coincident(v->fPrev->fPoint, v->fPoint)) {
                 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
                 if (v->fPrev == v) {
@@ -1042,15 +1144,7 @@ Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll
     for (int i = 0; i < contourCnt; ++i) {
         for (Vertex* v = contours[i]; v != nullptr;) {
             Vertex* vNext = v->fNext;
-            Edge* edge = new_edge(v->fPrev, v, alloc, c);
-            if (edge->fWinding > 0) {
-                insert_edge_below(edge, v->fPrev, c);
-                insert_edge_above(edge, v, c);
-            } else {
-                insert_edge_below(edge, v, c);
-                insert_edge_above(edge, v->fPrev, c);
-            }
-            merge_collinear_edges(edge, nullptr, c);
+            connect(v->fPrev, v, alloc, c);
             if (prev) {
                 prev->fNext = v;
                 v->fPrev = prev;
@@ -1145,7 +1239,7 @@ void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
             continue;
         }
 #if LOGGING_ENABLED
-        LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
+        LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
 #endif
         Edge* leftEnclosingEdge = nullptr;
         Edge* rightEnclosingEdge = nullptr;
@@ -1175,6 +1269,12 @@ void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
 
             }
         } while (restartChecks);
+        if (v->fAlpha == 0) {
+            if ((leftEnclosingEdge && leftEnclosingEdge->fWinding < 0) &&
+                (rightEnclosingEdge && rightEnclosingEdge->fWinding > 0)) {
+                v->fAlpha = max_edge_alpha(leftEnclosingEdge, rightEnclosingEdge);
+            }
+        }
         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
             remove_edge(e, &activeEdges);
         }
@@ -1198,7 +1298,7 @@ Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
             continue;
         }
 #if LOGGING_ENABLED
-        LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
+        LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
 #endif
         Edge* leftEnclosingEdge = nullptr;
         Edge* rightEnclosingEdge = nullptr;
@@ -1298,18 +1398,220 @@ Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
     return polys;
 }
 
-// This is a driver function which calls stages 2-5 in turn.
+bool is_boundary_edge(Edge* edge, SkPath::FillType fillType) {
+    return apply_fill_type(fillType, edge->fLeftPoly) !=
+           apply_fill_type(fillType, edge->fRightPoly);
+}
 
-Poly* contours_to_polys(Vertex** contours, int contourCnt, const SkRect& pathBounds,
-                        SkChunkAlloc& alloc) {
-    Comparator c;
-    if (pathBounds.width() > pathBounds.height()) {
-        c.sweep_lt = sweep_lt_horiz;
-        c.sweep_gt = sweep_gt_horiz;
-    } else {
-        c.sweep_lt = sweep_lt_vert;
-        c.sweep_gt = sweep_gt_vert;
+bool is_boundary_start(Edge* edge, SkPath::FillType fillType) {
+    return !apply_fill_type(fillType, edge->fLeftPoly) &&
+            apply_fill_type(fillType, edge->fRightPoly);
+}
+
+Vertex* remove_non_boundary_edges(Vertex* vertices, SkPath::FillType fillType,
+                                  SkChunkAlloc& alloc) {
+    for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
+        for (Edge* e = v->fFirstEdgeBelow; e != nullptr;) {
+            Edge* next = e->fNextEdgeBelow;
+            if (!is_boundary_edge(e, fillType)) {
+                remove_edge_above(e);
+                remove_edge_below(e);
+            }
+            e = next;
+        }
     }
+    return vertices;
+}
+
+// This is different from Edge::intersect, in that it intersects lines, not line segments.
+bool intersect(const Edge& a, const Edge& b, SkPoint* point) {
+    double denom = a.fDX * b.fDY - a.fDY * b.fDX;
+    if (denom == 0.0) {
+        return false;
+    }
+    double scale = 1.0f / denom;
+    point->fX = SkDoubleToScalar((b.fDX * a.fC - a.fDX * b.fC) * scale);
+    point->fY = SkDoubleToScalar((b.fDY * a.fC - a.fDY * b.fC) * scale);
+    round(point);
+    return true;
+}
+
+void get_edge_normal(const Edge* e, SkVector* normal) {
+    normal->setNormalize(SkDoubleToScalar(e->fDX) * e->fWinding,
+                         SkDoubleToScalar(e->fDY) * e->fWinding);
+}
+
+// Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions
+// and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
+// invert on stroking.
+
+void simplify_boundary(EdgeList* boundary, Comparator& c, SkChunkAlloc& alloc) {
+    Edge* prevEdge = boundary->fTail;
+    SkVector prevNormal;
+    get_edge_normal(prevEdge, &prevNormal);
+    for (Edge* e = boundary->fHead; e != nullptr;) {
+        Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom;
+        Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop;
+        double dist = e->dist(prev->fPoint);
+        SkVector normal;
+        get_edge_normal(e, &normal);
+        float denom = 0.25f * static_cast<float>(e->fDX * e->fDX + e->fDY * e->fDY);
+        if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) {
+            Edge* join = new_edge(prev, next, alloc, c);
+            insert_edge(join, e, boundary);
+            remove_edge(prevEdge, boundary);
+            remove_edge(e, boundary);
+            if (join->fLeft && join->fRight) {
+                prevEdge = join->fLeft;
+                e = join;
+            } else {
+                prevEdge = boundary->fTail;
+                e = boundary->fHead; // join->fLeft ? join->fLeft : join;
+            }
+            get_edge_normal(prevEdge, &prevNormal);
+        } else {
+            prevEdge = e;
+            prevNormal = normal;
+            e = e->fRight;
+        }
+    }
+}
+
+// Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to
+// find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
+// new antialiased mesh from those vertices.
+
+void boundary_to_aa_mesh(EdgeList* boundary, VertexList* mesh, Comparator& c, SkChunkAlloc& alloc) {
+    EdgeList outerContour;
+    Edge* prevEdge = boundary->fTail;
+    float radius = 0.5f;
+    double offset = radius * sqrt(prevEdge->fDX * prevEdge->fDX + prevEdge->fDY * prevEdge->fDY)
+                           * prevEdge->fWinding;
+    Edge prevInner(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
+    prevInner.fC -= offset;
+    Edge prevOuter(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
+    prevOuter.fC += offset;
+    VertexList innerVertices;
+    VertexList outerVertices;
+    SkScalar innerCount = SK_Scalar1, outerCount = SK_Scalar1;
+    for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
+        double offset = radius * sqrt(e->fDX * e->fDX + e->fDY * e->fDY) * e->fWinding;
+        Edge inner(e->fTop, e->fBottom, e->fWinding);
+        inner.fC -= offset;
+        Edge outer(e->fTop, e->fBottom, e->fWinding);
+        outer.fC += offset;
+        SkPoint innerPoint, outerPoint;
+        if (intersect(prevInner, inner, &innerPoint) &&
+            intersect(prevOuter, outer, &outerPoint)) {
+            Vertex* innerVertex = ALLOC_NEW(Vertex, (innerPoint, 255), alloc);
+            Vertex* outerVertex = ALLOC_NEW(Vertex, (outerPoint, 0), alloc);
+            if (innerVertices.fTail && outerVertices.fTail) {
+                Edge innerEdge(innerVertices.fTail, innerVertex, 1);
+                Edge outerEdge(outerVertices.fTail, outerVertex, 1);
+                SkVector innerNormal;
+                get_edge_normal(&innerEdge, &innerNormal);
+                SkVector outerNormal;
+                get_edge_normal(&outerEdge, &outerNormal);
+                SkVector normal;
+                get_edge_normal(prevEdge, &normal);
+                if (normal.dot(innerNormal) < 0) {
+                    innerPoint += innerVertices.fTail->fPoint * innerCount;
+                    innerCount++;
+                    innerPoint *= SkScalarInvert(innerCount);
+                    innerVertices.fTail->fPoint = innerVertex->fPoint = innerPoint;
+                } else {
+                    innerCount = SK_Scalar1;
+                }
+                if (normal.dot(outerNormal) < 0) {
+                    outerPoint += outerVertices.fTail->fPoint * outerCount;
+                    outerCount++;
+                    outerPoint *= SkScalarInvert(outerCount);
+                    outerVertices.fTail->fPoint = outerVertex->fPoint = outerPoint;
+                } else {
+                    outerCount = SK_Scalar1;
+                }
+            }
+            innerVertices.append(innerVertex);
+            outerVertices.append(outerVertex);
+            prevEdge = e;
+        }
+        prevInner = inner;
+        prevOuter = outer;
+    }
+    innerVertices.close();
+    outerVertices.close();
+
+    Vertex* innerVertex = innerVertices.fHead;
+    Vertex* outerVertex = outerVertices.fHead;
+    // Alternate clockwise and counterclockwise polys, so the tesselator
+    // doesn't cancel out the interior edges.
+    if (!innerVertex || !outerVertex) {
+        return;
+    }
+    do {
+        connect(outerVertex->fNext, outerVertex, alloc, c);
+        connect(innerVertex->fNext, innerVertex, alloc, c, 2);
+        connect(innerVertex, outerVertex->fNext, alloc, c, 2);
+        connect(outerVertex, innerVertex, alloc, c, 2);
+        Vertex* innerNext = innerVertex->fNext;
+        Vertex* outerNext = outerVertex->fNext;
+        mesh->append(innerVertex);
+        mesh->append(outerVertex);
+        innerVertex = innerNext;
+        outerVertex = outerNext;
+    } while (innerVertex != innerVertices.fHead && outerVertex != outerVertices.fHead);
+}
+
+void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkChunkAlloc& alloc) {
+    bool down = is_boundary_start(e, fillType);
+    while (e) {
+        e->fWinding = down ? 1 : -1;
+        Edge* next;
+        boundary->append(e);
+        if (down) {
+            // Find outgoing edge, in clockwise order.
+            if ((next = e->fNextEdgeAbove)) {
+                down = false;
+            } else if ((next = e->fBottom->fLastEdgeBelow)) {
+                down = true;
+            } else if ((next = e->fPrevEdgeAbove)) {
+                down = false;
+            }
+        } else {
+            // Find outgoing edge, in counter-clockwise order.
+            if ((next = e->fPrevEdgeBelow)) {
+                down = true;
+            } else if ((next = e->fTop->fFirstEdgeAbove)) {
+                down = false;
+            } else if ((next = e->fNextEdgeBelow)) {
+                down = true;
+            }
+        }
+        remove_edge_above(e);
+        remove_edge_below(e);
+        e = next;
+    }
+}
+
+// Stage 5b: Extract boundary edges.
+
+EdgeList* extract_boundaries(Vertex* vertices, SkPath::FillType fillType, SkChunkAlloc& alloc) {
+    LOG("extracting boundaries\n");
+    vertices = remove_non_boundary_edges(vertices, fillType, alloc);
+    EdgeList* boundaries = nullptr;
+    for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
+        while (v->fFirstEdgeBelow) {
+            EdgeList* boundary = new_contour(&boundaries, alloc);
+            extract_boundary(boundary, v->fFirstEdgeBelow, fillType, alloc);
+        }
+    }
+    return boundaries;
+}
+
+// This is a driver function which calls stages 2-5 in turn.
+
+Vertex* contours_to_mesh(Vertex** contours, int contourCnt, bool antialias,
+                         Comparator& c, SkChunkAlloc& alloc) {
 #if LOGGING_ENABLED
     for (int i = 0; i < contourCnt; ++i) {
         Vertex* v = contours[i];
@@ -1320,27 +1622,69 @@ Poly* contours_to_polys(Vertex** contours, int contourCnt, const SkRect& pathBou
         }
     }
 #endif
-    sanitize_contours(contours, contourCnt);
-    Vertex* vertices = build_edges(contours, contourCnt, c, alloc);
-    if (!vertices) {
+    sanitize_contours(contours, contourCnt, antialias);
+    return build_edges(contours, contourCnt, c, alloc);
+}
+
+Poly* mesh_to_polys(Vertex** vertices, SkPath::FillType fillType, Comparator& c,
+                    SkChunkAlloc& alloc) {
+    if (!vertices || !*vertices) {
         return nullptr;
     }
 
     // Sort vertices in Y (secondarily in X).
-    merge_sort(&vertices, c);
-    merge_coincident_vertices(&vertices, c, alloc);
+    merge_sort(vertices, c);
+    merge_coincident_vertices(vertices, c, alloc);
 #if LOGGING_ENABLED
-    for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
+    for (Vertex* v = *vertices; v != nullptr; v = v->fNext) {
         static float gID = 0.0f;
         v->fID = gID++;
     }
 #endif
-    simplify(vertices, c, alloc);
-    return tessellate(vertices, alloc);
+    simplify(*vertices, c, alloc);
+    return tessellate(*vertices, alloc);
+}
+
+Poly* contours_to_polys(Vertex** contours, int contourCnt, SkPath::FillType fillType,
+                        const SkRect& pathBounds, bool antialias,
+                        SkChunkAlloc& alloc) {
+    Comparator c;
+    if (pathBounds.width() > pathBounds.height()) {
+        c.sweep_lt = sweep_lt_horiz;
+        c.sweep_gt = sweep_gt_horiz;
+    } else {
+        c.sweep_lt = sweep_lt_vert;
+        c.sweep_gt = sweep_gt_vert;
+    }
+    Vertex* mesh = contours_to_mesh(contours, contourCnt, antialias, c, alloc);
+    Poly* polys = mesh_to_polys(&mesh, fillType, c, alloc);
+    if (antialias) {
+        EdgeList* boundaries = extract_boundaries(mesh, fillType, alloc);
+        VertexList aaMesh;
+        for (EdgeList* boundary = boundaries; boundary != nullptr; boundary = boundary->fNext) {
+            simplify_boundary(boundary, c, alloc);
+            if (boundary->fCount > 2) {
+                boundary_to_aa_mesh(boundary, &aaMesh, c, alloc);
+            }
+        }
+        return mesh_to_polys(&aaMesh.fHead, SkPath::kWinding_FillType, c, alloc);
+    }
+    return polys;
+}
+
+// Stage 6: Triangulate the monotone polygons into a vertex buffer.
+void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, const AAParams* aaParams,
+                         void* data) {
+    for (Poly* poly = polys; poly; poly = poly->fNext) {
+        if (apply_fill_type(fillType, poly)) {
+            data = poly->emit(aaParams, data);
+        }
+    }
+    return data;
 }
 
 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
-                    int contourCnt, SkChunkAlloc& alloc, bool* isLinear) {
+                    int contourCnt, SkChunkAlloc& alloc, bool antialias, bool* isLinear) {
     SkPath::FillType fillType = path.getFillType();
     if (SkPath::IsInverseFillType(fillType)) {
         contourCnt++;
@@ -1348,7 +1692,8 @@ Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo
     SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]);
 
     path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinear);
-    return contours_to_polys(contours.get(), contourCnt, path.getBounds(), alloc);
+    return contours_to_polys(contours.get(), contourCnt, path.getFillType(), path.getBounds(),
+                             antialias, alloc);
 }
 
 void get_contour_count_and_size_estimate(const SkPath& path, SkScalar tolerance, int* contourCnt,
@@ -1373,7 +1718,7 @@ void get_contour_count_and_size_estimate(const SkPath& path, SkScalar tolerance,
 int count_points(Poly* polys, SkPath::FillType fillType) {
     int count = 0;
     for (Poly* poly = polys; poly; poly = poly->fNext) {
-        if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
+        if (apply_fill_type(fillType, poly) && poly->fCount >= 3) {
             count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3);
         }
     }
@@ -1387,7 +1732,8 @@ namespace GrTessellator {
 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
 
 int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
-                    VertexAllocator* vertexAllocator, bool* isLinear) {
+                    VertexAllocator* vertexAllocator, bool antialias, const GrColor& color,
+                    bool canTweakAlphaForCoverage, bool* isLinear) {
     int contourCnt;
     int sizeEstimate;
     get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstimate);
@@ -1396,26 +1742,28 @@ int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBo
         return 0;
     }
     SkChunkAlloc alloc(sizeEstimate);
-    Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, isLinear);
+    Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias,
+                                isLinear);
     SkPath::FillType fillType = path.getFillType();
     int count = count_points(polys, fillType);
     if (0 == count) {
         return 0;
     }
 
-    SkPoint* verts = vertexAllocator->lock(count);
+    void* verts = vertexAllocator->lock(count);
     if (!verts) {
         SkDebugf("Could not allocate vertices\n");
         return 0;
     }
-    SkPoint* end = verts;
-    for (Poly* poly = polys; poly; poly = poly->fNext) {
-        if (apply_fill_type(fillType, poly->fWinding)) {
-            end = poly->emit(end);
-        }
-    }
-    int actualCount = static_cast<int>(end - verts);
-    LOG("actual count: %d\n", actualCount);
+
+    LOG("emitting %d verts\n", count);
+    AAParams aaParams;
+    aaParams.fTweakAlpha = canTweakAlphaForCoverage;
+    aaParams.fColor = color;
+
+    void* end = polys_to_triangles(polys, fillType, antialias ? &aaParams : nullptr, verts);
+    int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts))
+                                       / vertexAllocator->stride());
     SkASSERT(actualCount <= count);
     vertexAllocator->unlock(actualCount);
     return actualCount;
@@ -1431,7 +1779,7 @@ int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBou
     }
     SkChunkAlloc alloc(sizeEstimate);
     bool isLinear;
-    Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, &isLinear);
+    Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear);
     SkPath::FillType fillType = path.getFillType();
     int count = count_points(polys, fillType);
     if (0 == count) {
@@ -1444,9 +1792,9 @@ int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBou
     SkPoint* points = new SkPoint[count];
     SkPoint* pointsEnd = points;
     for (Poly* poly = polys; poly; poly = poly->fNext) {
-        if (apply_fill_type(fillType, poly->fWinding)) {
+        if (apply_fill_type(fillType, poly)) {
             SkPoint* start = pointsEnd;
-            pointsEnd = poly->emit(pointsEnd);
+            pointsEnd = static_cast<SkPoint*>(poly->emit(nullptr, pointsEnd));
             while (start != pointsEnd) {
                 vertsEnd->fPos = *start;
                 vertsEnd->fWinding = poly->fWinding;