Screenspace AA tessellated path rendering.

src/gpu/GrTessellator.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "GrTessellator.h"
 
+#include "GrDefaultGeoProcFactory.h"
 #include "GrPathUtils.h"
 
 #include "SkChunkAlloc.h"
 #include "SkGeometry.h"
 #include "SkPath.h"
 
 #include <stdio.h>
 
 /*
  * There are six stages to the algorithm:

[bsalomon, 2016/08/31 14:19:19]

Can you update this to document the AA steps?

[Stephen White, 2016/08/31 15:16:38]

Done.

  *
  * 1) Linearize the path contours into piecewise linear segments (path_to_contours()).
  * 2) Build a mesh of edges connecting the vertices (build_edges()).
  * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
  * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()).
  * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
  * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_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).
@@ skipping 93 matching lines @@
  * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
  * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
  * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
  * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
  * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
  * an individual Vertex from the path mesh may belong to multiple
  * MonotonePolys, so the original Vertices cannot be re-used.
  */
 
 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
     {}
     SkPoint fPoint;           // Vertex position
     Vertex* fPrev;            // Linked list of contours, then Y-sorted vertices.
     Vertex* fNext;            // "
     Edge*   fFirstEdgeAbove;  // Linked list of edges above this vertex.
     Edge*   fLastEdgeAbove;   // "
     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
 };
 
 /***************************************************************************************/
 
+struct AAParams {
+    bool fTweakAlpha;
+    GrColor fColor;
+};
+
 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
 
 struct Comparator {
     CompareFunc sweep_lt;
     CompareFunc sweep_gt;
 };
 
 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
     return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX;
 }
 
 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
     return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
 }
 
 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) {
     return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX;
 }
 
 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;
     Vertex* fTail;
     void insert(Vertex* v, Vertex* prev, Vertex* next) {
         list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
     }
     void append(Vertex* v) {
         insert(v, fTail, nullptr);
     }
     void prepend(Vertex* v) {
         insert(v, nullptr, fHead);
     }
+    void close() {
+        if (fHead && fTail) {
+            fTail->fNext = fHead;
+            fHead->fPrev = fTail;
+        }
+    }
 };
 
+inline void round(SkPoint* p) {

[bsalomon, 2016/08/31 14:19:19]

Is this rounding to 1/4 pixel values?

[Stephen White, 2016/08/31 15:16:38]

Yes; added a comment.

+    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().
  * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
  * point). For speed, that case is only tested by the callers which require it (e.g.,
  * cleanup_active_edges()). Edges also handle checking for intersection with other edges.
  * Currently, this converts the edges to the parametric form, in order to avoid doing a division
  * until an intersection has been confirmed. This is slightly slower in the "found" case, but
  * a lot faster in the "not found" case.
  *
@@ skipping 81 matching lines @@
         if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
                         : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
             return false;
         }
         double s = sNumer / denom;
         SkASSERT(s >= 0.0 && s <= 1.0);
         p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
         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;
     }
 };
 
 /***************************************************************************************/
 
 struct Poly {
     Poly(Vertex* v, int winding)
         : fFirstVertex(v)
         , fWinding(winding)
         , fHead(nullptr)
@@ skipping 30 matching lines @@
                     edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
                 edge->fUsedInRightPoly = true;
             } else {
                 SkASSERT(!edge->fUsedInLeftPoly);
                 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
                     edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
                 edge->fUsedInLeftPoly = true;
             }
         }
 
-        SkPoint* emit(SkPoint* data) {
+        void* emit(const AAParams* aaParams, void* data) {
             Edge* e = fFirstEdge;
             e->fTop->fPrev = e->fTop->fNext = nullptr;
             VertexList vertices;
             vertices.append(e->fTop);
             while (e != nullptr) {
                 e->fBottom->fPrev = e->fBottom->fNext = nullptr;
                 if (kRight_Side == fSide) {
                     vertices.append(e->fBottom);
                     e = e->fRightPolyNext;
                 } else {
                     vertices.prepend(e->fBottom);
                     e = e->fLeftPolyNext;
                 }
             }
             Vertex* first = vertices.fHead;
             Vertex* v = first->fNext;
             while (v != vertices.fTail) {
                 SkASSERT(v && v->fPrev && v->fNext);
                 Vertex* prev = v->fPrev;
                 Vertex* curr = v;
                 Vertex* next = v->fNext;
                 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
                 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
                 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) {
                         v = v->fNext;
                     } else {
                         v = v->fPrev;
                     }
                 } else {
                     v = v->fNext;
                 }
@@ skipping 35 matching lines @@
                 poly = partner;
             } else {
                 MonotonePoly* m = ALLOC_NEW(MonotonePoly, (e, side), alloc);
                 m->fPrev = fTail;
                 fTail->fNext = m;
                 fTail = m;
             }
         }
         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;
     }
     Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
     Vertex* fFirstVertex;
     int fWinding;
     MonotonePoly* fHead;
     MonotonePoly* fTail;
     Poly* fNext;
     Poly* fPartner;
     int fCount;
 #if LOGGING_ENABLED
     int fID;
 #endif
 };
 
 /***************************************************************************************/
 
 bool coincident(const SkPoint& a, const SkPoint& b) {
     return a == b;
 }
 
 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
     Poly* poly = ALLOC_NEW(Poly, (v, winding), alloc);
     poly->fNext = *head;
     *head = poly;
     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++;
 #endif
     if (prev) {
         prev->fNext = v;
         v->fPrev = prev;
     } else {
         *head = v;
     }
@@ skipping 64 matching lines @@
 
     SkPoint pts[4];
     bool done = false;
     *isLinear = true;
     SkPath::Iter iter(path, false);
     Vertex* prev = nullptr;
     Vertex* head = nullptr;
     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;
         prev->fNext = head;
         *contours++ = head;
         head = prev = nullptr;
     }
     SkAutoConicToQuads converter;
     while (!done) {
         SkPath::Verb verb = iter.next(pts);
@@ skipping 50 matching lines @@
                     head->fPrev = prev;
                     prev->fNext = head;
                     *contours++ = head;
                 }
                 done = true;
                 break;
         }
     }
 }
 
-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:
             SkASSERT(false);
             return false;
     }
 }
 
-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);
 }
 
 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) {
     if (v->fFirstEdgeAbove) {
         *left = v->fFirstEdgeAbove->fLeft;
         *right = v->fLastEdgeAbove->fRight;
         return;
     }
     Edge* next = nullptr;
     Edge* prev;
@@ skipping 19 matching lines @@
              edge->isLeftOf(next->fBottom))) {
             break;
         }
         prev = next;
     }
     *left = prev;
     *right = next;
 }
 
 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);
         }
     } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
         Edge* left;
         Edge* right;
         find_enclosing_edges(edge, activeEdges, c, &left, &right);
         insert_edge(edge, left, activeEdges);
     }
 }
@@ skipping 48 matching lines @@
         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
 }
 
 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
     if (edge->fWinding != 0) {
         return;
     }
     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);
     }
 }
 
 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
 
 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
     remove_edge_below(edge);
     edge->fTop = v;
     edge->recompute();
@@ skipping 116 matching lines @@
         Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
         insert_edge_below(newEdge, v, c);
         insert_edge_above(newEdge, edge->fBottom, c);
         set_bottom(edge, v, activeEdges, c);
         cleanup_active_edges(edge, activeEdges, c, alloc);
         fix_active_state(newEdge, activeEdges, c);
         merge_collinear_edges(newEdge, activeEdges, c);
     }
 }
 
+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);
         edge = next;
     }
     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
         Edge* next = edge->fNextEdgeBelow;
         set_top(edge, dst, nullptr, c);
         edge = next;
     }
     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;
     if (!edge || !other) {
         return nullptr;
     }
     if (edge->intersect(*other, &p)) {
         Vertex* v;
         LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
         if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
@@ skipping 15 matching lines @@
             }
             while (c.sweep_lt(nextV->fPoint, p)) {
                 nextV = nextV->fNext;
             }
             Vertex* prevV = nextV->fPrev;
             if (coincident(prevV->fPoint, p)) {
                 v = prevV;
             } 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);
 #if LOGGING_ENABLED
                 v->fID = (nextV->fID + prevV->fID) * 0.5f;
 #endif
                 v->fPrev = prevV;
                 v->fNext = nextV;
                 prevV->fNext = v;
                 nextV->fPrev = v;
             }
             split_edge(edge, v, activeEdges, c, alloc);
             split_edge(other, v, activeEdges, c, alloc);
         }
         return v;
     }
     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) {
                     contours[i] = nullptr;
                     break;
                 }
                 v->fPrev->fNext = v->fNext;
                 v->fNext->fPrev = v->fPrev;
                 if (contours[i] == v) {
                     contours[i] = v->fNext;
@@ skipping 19 matching lines @@
 }
 
 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
 
 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAlloc& alloc) {
     Vertex* vertices = nullptr;
     Vertex* prev = nullptr;
     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;
             } else {
                 vertices = v;
             }
             prev = v;
             v = vNext;
             if (v == contours[i]) break;
         }
@@ skipping 74 matching lines @@
 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
 
 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
     LOG("simplifying complex polygons\n");
     EdgeList activeEdges;
     for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             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;
         bool restartChecks;
         do {
             restartChecks = false;
             find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
             if (v->fFirstEdgeBelow) {
                 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = edge->fNextEdgeBelow) {
                     if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
                     if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
                 }
             } else {
                 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
                                                         &activeEdges, c, alloc)) {
                     if (c.sweep_lt(pv->fPoint, v->fPoint)) {
                         v = pv;
                     }
                     restartChecks = true;
                 }
 
             }
         } 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);
         }
         Edge* leftEdge = leftEnclosingEdge;
         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
             insert_edge(e, leftEdge, &activeEdges);
             leftEdge = e;
         }
         v->fProcessed = true;
     }
 }
 
 // Stage 5: Tessellate the simplified mesh into monotone polygons.
 
 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
     LOG("tessellating simple polygons\n");
     EdgeList activeEdges;
     Poly* polys = nullptr;
     for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             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;
         find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
         Poly* leftPoly = nullptr;
         Poly* rightPoly = nullptr;
         if (v->fFirstEdgeAbove) {
             leftPoly = v->fFirstEdgeAbove->fLeftPoly;
             rightPoly = v->fLastEdgeAbove->fRightPoly;
         } else {
@@ skipping 79 matching lines @@
         LOG("\nactive edges:\n");
         for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
             LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
                 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
         }
 #endif
     }
     return polys;
 }
 
+bool is_boundary_edge(Edge* edge, SkPath::FillType fillType) {
+    return apply_fill_type(fillType, edge->fLeftPoly) !=
+           apply_fill_type(fillType, edge->fRightPoly);
+}
+
+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);
+}
+
+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;
+        }
+    }
+}
+
+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.
 
-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;
-    }
+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];
         SkASSERT(v);
         LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
         for (v = v->fNext; v != contours[i]; v = v->fNext) {
             LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
         }
     }
 #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++;
     }
     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,
                                          int* sizeEstimate) {
     int maxPts = GrPathUtils::worstCasePointCount(path, contourCnt, tolerance);
     if (maxPts <= 0) {
         *contourCnt = 0;
         return;
     }
     if (maxPts > ((int)SK_MaxU16 + 1)) {
         SkDebugf("Path not rendered, too many verts (%d)\n", maxPts);
         *contourCnt = 0;
         return;
     }
     // For the initial size of the chunk allocator, estimate based on the point count:
     // one vertex per point for the initial passes, plus two for the vertices in the
     // resulting Polys, since the same point may end up in two Polys.  Assume minimal
     // connectivity of one Edge per Vertex (will grow for intersections).
     *sizeEstimate = maxPts * (3 * sizeof(Vertex) + sizeof(Edge));
 }
 
 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);
         }
     }
     return count;
 }
 
 } // namespace
 
 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);
     if (contourCnt <= 0) {
         *isLinear = true;
         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;
 }
 
 int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
                    GrTessellator::WindingVertex** verts) {
     int contourCnt;
     int sizeEstimate;
     get_contour_count_and_size_estimate(path, tolerance, &contourCnt, &sizeEstimate);
     if (contourCnt <= 0) {
         return 0;
     }
     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) {
         *verts = nullptr;
         return 0;
     }
 
     *verts = new GrTessellator::WindingVertex[count];
     GrTessellator::WindingVertex* vertsEnd = *verts;
     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;
                 ++start;
                 ++vertsEnd;
             }
         }
     }
     int actualCount = static_cast<int>(vertsEnd - *verts);
     SkASSERT(actualCount <= count);
     SkASSERT(pointsEnd - points == actualCount);
     delete[] points;
     return actualCount;
 }
 
 } // namespace