xref: /external/skia/src/gpu/geometry/GrAATriangulator.cpp

/*
 * Copyright 2020 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/gpu/geometry/GrAATriangulator.h"

#include "src/gpu/BufferWriter.h"
#include "src/gpu/GrEagerVertexAllocator.h"
#include <queue>
#include <vector>
#include <unordered_map>

#if TRIANGULATOR_LOGGING
#define TESS_LOG SkDebugf
#define DUMP_MESH(MESH) (MESH).dump()
#else
#define TESS_LOG(...)
#define DUMP_MESH(MESH)
#endif

constexpr static float kCosMiterAngle = 0.97f; // Corresponds to an angle of ~14 degrees.

using EdgeType = GrTriangulator::EdgeType;
using Vertex = GrTriangulator::Vertex;
using VertexList = GrTriangulator::VertexList;
using Line = GrTriangulator::Line;
using Edge = GrTriangulator::Edge;
using EdgeList = GrTriangulator::EdgeList;
using Poly = GrTriangulator::Poly;
using Comparator = GrTriangulator::Comparator;
using SSEdge = GrAATriangulator::SSEdge;
using EventList = GrAATriangulator::EventList;
using Event = GrAATriangulator::Event;
using EventComparator = GrAATriangulator::EventComparator;

struct SSVertex {
    SSVertex(Vertex* v) : fVertex(v), fPrev(nullptr), fNext(nullptr) {}
    Vertex* fVertex;
    SSEdge* fPrev;
    SSEdge* fNext;
};

struct GrAATriangulator::SSEdge {
    SSEdge(Edge* edge, SSVertex* prev, SSVertex* next)
      : fEdge(edge), fEvent(nullptr), fPrev(prev), fNext(next) {
    }
    Edge*     fEdge;
    Event*    fEvent;
    SSVertex* fPrev;
    SSVertex* fNext;
};

typedef std::unordered_map<Vertex*, SSVertex*> SSVertexMap;
typedef std::vector<SSEdge*> SSEdgeList;
typedef std::priority_queue<Event*, std::vector<Event*>, EventComparator> EventPQ;

struct GrAATriangulator::EventList : EventPQ {
    EventList(EventComparator comparison) : EventPQ(comparison) {
    }
};

void GrAATriangulator::makeEvent(SSEdge* e, EventList* events) const {
    Vertex* prev = e->fPrev->fVertex;
    Vertex* next = e->fNext->fVertex;
    if (prev == next || !prev->fPartner || !next->fPartner) {
        return;
    }
    Edge bisector1(prev, prev->fPartner, 1, EdgeType::kConnector);
    Edge bisector2(next, next->fPartner, 1, EdgeType::kConnector);
    SkPoint p;
    uint8_t alpha;
    if (bisector1.intersect(bisector2, &p, &alpha)) {
        TESS_LOG("found edge event for %g, %g (original %g -> %g), "
                 "will collapse to %g,%g alpha %d\n",
                  prev->fID, next->fID, e->fEdge->fTop->fID, e->fEdge->fBottom->fID, p.fX, p.fY,
                  alpha);
        e->fEvent = fAlloc->make<Event>(e, p, alpha);
        events->push(e->fEvent);
    }
}

void GrAATriangulator::makeEvent(SSEdge* edge, Vertex* v, SSEdge* other, Vertex* dest,
                                 EventList* events, const Comparator& c) const {
    if (!v->fPartner) {
        return;
    }
    Vertex* top = edge->fEdge->fTop;
    Vertex* bottom = edge->fEdge->fBottom;
    if (!top || !bottom ) {
        return;
    }
    Line line = edge->fEdge->fLine;
    line.fC = -(dest->fPoint.fX * line.fA  + dest->fPoint.fY * line.fB);
    Edge bisector(v, v->fPartner, 1, EdgeType::kConnector);
    SkPoint p;
    uint8_t alpha = dest->fAlpha;
    if (line.intersect(bisector.fLine, &p) && !c.sweep_lt(p, top->fPoint) &&
                                               c.sweep_lt(p, bottom->fPoint)) {
        TESS_LOG("found p edge event for %g, %g (original %g -> %g), "
                 "will collapse to %g,%g alpha %d\n",
                 dest->fID, v->fID, top->fID, bottom->fID, p.fX, p.fY, alpha);
        edge->fEvent = fAlloc->make<Event>(edge, p, alpha);
        events->push(edge->fEvent);
    }
}

void GrAATriangulator::connectPartners(VertexList* mesh, const Comparator& c) {
    for (Vertex* outer = mesh->fHead; outer; outer = outer->fNext) {
        if (Vertex* inner = outer->fPartner) {
            if ((inner->fPrev || inner->fNext) && (outer->fPrev || outer->fNext)) {
                // Connector edges get zero winding, since they're only structural (i.e., to ensure
                // no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding
                // number.
                this->makeConnectingEdge(outer, inner, EdgeType::kConnector, c, 0);
                inner->fPartner = outer->fPartner = nullptr;
            }
        }
    }
}

static void dump_skel(const SSEdgeList& ssEdges) {
#if TRIANGULATOR_LOGGING
    for (SSEdge* edge : ssEdges) {
        if (edge->fEdge) {
            TESS_LOG("skel edge %g -> %g",
                edge->fPrev->fVertex->fID,
                edge->fNext->fVertex->fID);
            if (edge->fEdge->fTop && edge->fEdge->fBottom) {
                TESS_LOG(" (original %g -> %g)\n",
                         edge->fEdge->fTop->fID,
                         edge->fEdge->fBottom->fID);
            } else {
                TESS_LOG("\n");
            }
        }
    }
#endif
}

void GrAATriangulator::removeNonBoundaryEdges(const VertexList& mesh) const {
    TESS_LOG("removing non-boundary edges\n");
    EdgeList activeEdges;
    for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) {
        if (!v->isConnected()) {
            continue;
        }
        Edge* leftEnclosingEdge;
        Edge* rightEnclosingEdge;
        FindEnclosingEdges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
        bool prevFilled = leftEnclosingEdge && this->applyFillType(leftEnclosingEdge->fWinding);
        for (Edge* e = v->fFirstEdgeAbove; e;) {
            Edge* next = e->fNextEdgeAbove;
            activeEdges.remove(e);
            bool filled = this->applyFillType(e->fWinding);
            if (filled == prevFilled) {
                e->disconnect();
            }
            prevFilled = filled;
            e = next;
        }
        Edge* prev = leftEnclosingEdge;
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
            if (prev) {
                e->fWinding += prev->fWinding;
            }
            activeEdges.insert(e, prev);
            prev = e;
        }
    }
}

// Note: this is the normal to the edge, but not necessarily unit length.
static void get_edge_normal(const Edge* e, SkVector* normal) {
    normal->set(SkDoubleToScalar(e->fLine.fA),
                SkDoubleToScalar(e->fLine.fB));
}

// 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 GrAATriangulator::simplifyBoundary(EdgeList* boundary, const Comparator& c) {
    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 distPrev = e->dist(prev->fPoint);
        double distNext = prevEdge->dist(next->fPoint);
        SkVector normal;
        get_edge_normal(e, &normal);
        constexpr double kQuarterPixelSq = 0.25f * 0.25f;
        if (prev == next) {
            boundary->remove(prevEdge);
            boundary->remove(e);
            prevEdge = boundary->fTail;
            e = boundary->fHead;
            if (prevEdge) {
                get_edge_normal(prevEdge, &prevNormal);
            }
        } else if (prevNormal.dot(normal) < 0.0 &&
            (distPrev * distPrev <= kQuarterPixelSq || distNext * distNext <= kQuarterPixelSq)) {
            Edge* join = this->makeEdge(prev, next, EdgeType::kInner, c);
            if (prev->fPoint != next->fPoint) {
                join->fLine.normalize();
                join->fLine = join->fLine * join->fWinding;
            }
            boundary->insert(join, e);
            boundary->remove(prevEdge);
            boundary->remove(e);
            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 GrAATriangulator::connectSSEdge(Vertex* v, Vertex* dest, const Comparator& c) {
    if (v == dest) {
        return;
    }
    TESS_LOG("ss_connecting vertex %g to vertex %g\n", v->fID, dest->fID);
    if (v->fSynthetic) {
        this->makeConnectingEdge(v, dest, EdgeType::kConnector, c, 0);
    } else if (v->fPartner) {
        TESS_LOG("setting %g's partner to %g ", v->fPartner->fID, dest->fID);
        TESS_LOG("and %g's partner to null\n", v->fID);
        v->fPartner->fPartner = dest;
        v->fPartner = nullptr;
    }
}

void GrAATriangulator::Event::apply(VertexList* mesh, const Comparator& c, EventList* events,
                                    GrAATriangulator* triangulator) {
    if (!fEdge) {
        return;
    }
    Vertex* prev = fEdge->fPrev->fVertex;
    Vertex* next = fEdge->fNext->fVertex;
    SSEdge* prevEdge = fEdge->fPrev->fPrev;
    SSEdge* nextEdge = fEdge->fNext->fNext;
    if (!prevEdge || !nextEdge || !prevEdge->fEdge || !nextEdge->fEdge) {
        return;
    }
    Vertex* dest = triangulator->makeSortedVertex(fPoint, fAlpha, mesh, prev, c);
    dest->fSynthetic = true;
    SSVertex* ssv = triangulator->fAlloc->make<SSVertex>(dest);
    TESS_LOG("collapsing %g, %g (original edge %g -> %g) to %g (%g, %g) alpha %d\n",
             prev->fID, next->fID, fEdge->fEdge->fTop->fID, fEdge->fEdge->fBottom->fID, dest->fID,
             fPoint.fX, fPoint.fY, fAlpha);
    fEdge->fEdge = nullptr;

    triangulator->connectSSEdge(prev, dest, c);
    triangulator->connectSSEdge(next, dest, c);

    prevEdge->fNext = nextEdge->fPrev = ssv;
    ssv->fPrev = prevEdge;
    ssv->fNext = nextEdge;
    if (!prevEdge->fEdge || !nextEdge->fEdge) {
        return;
    }
    if (prevEdge->fEvent) {
        prevEdge->fEvent->fEdge = nullptr;
    }
    if (nextEdge->fEvent) {
        nextEdge->fEvent->fEdge = nullptr;
    }
    if (prevEdge->fPrev == nextEdge->fNext) {
        triangulator->connectSSEdge(prevEdge->fPrev->fVertex, dest, c);
        prevEdge->fEdge = nextEdge->fEdge = nullptr;
    } else {
        triangulator->computeBisector(prevEdge->fEdge, nextEdge->fEdge, dest);
        SkASSERT(prevEdge != fEdge && nextEdge != fEdge);
        if (dest->fPartner) {
            triangulator->makeEvent(prevEdge, events);
            triangulator->makeEvent(nextEdge, events);
        } else {
            triangulator->makeEvent(prevEdge, prevEdge->fPrev->fVertex, nextEdge, dest, events, c);
            triangulator->makeEvent(nextEdge, nextEdge->fNext->fVertex, prevEdge, dest, events, c);
        }
    }
}

static bool is_overlap_edge(Edge* e) {
    if (e->fType == EdgeType::kOuter) {
        return e->fWinding != 0 && e->fWinding != 1;
    } else if (e->fType == EdgeType::kInner) {
        return e->fWinding != 0 && e->fWinding != -2;
    } else {
        return false;
    }
}

// This is a stripped-down version of tessellate() which computes edges which
// join two filled regions, which represent overlap regions, and collapses them.
bool GrAATriangulator::collapseOverlapRegions(VertexList* mesh, const Comparator& c,
                                              EventComparator comp) {
    TESS_LOG("\nfinding overlap regions\n");
    EdgeList activeEdges;
    EventList events(comp);
    SSVertexMap ssVertices;
    SSEdgeList ssEdges;
    for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
        if (!v->isConnected()) {
            continue;
        }
        Edge* leftEnclosingEdge;
        Edge* rightEnclosingEdge;
        FindEnclosingEdges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
        for (Edge* e = v->fLastEdgeAbove; e && e != leftEnclosingEdge;) {
            Edge* prev = e->fPrevEdgeAbove ? e->fPrevEdgeAbove : leftEnclosingEdge;
            activeEdges.remove(e);
            bool leftOverlap = prev && is_overlap_edge(prev);
            bool rightOverlap = is_overlap_edge(e);
            bool isOuterBoundary = e->fType == EdgeType::kOuter &&
                                   (!prev || prev->fWinding == 0 || e->fWinding == 0);
            if (prev) {
                e->fWinding -= prev->fWinding;
            }
            if (leftOverlap && rightOverlap) {
                TESS_LOG("found interior overlap edge %g -> %g, disconnecting\n",
                         e->fTop->fID, e->fBottom->fID);
                e->disconnect();
            } else if (leftOverlap || rightOverlap) {
                TESS_LOG("found overlap edge %g -> %g%s\n",
                         e->fTop->fID, e->fBottom->fID,
                         isOuterBoundary ? ", is outer boundary" : "");
                Vertex* prevVertex = e->fWinding < 0 ? e->fBottom : e->fTop;
                Vertex* nextVertex = e->fWinding < 0 ? e->fTop : e->fBottom;
                SSVertex* ssPrev = ssVertices[prevVertex];
                if (!ssPrev) {
                    ssPrev = ssVertices[prevVertex] = fAlloc->make<SSVertex>(prevVertex);
                }
                SSVertex* ssNext = ssVertices[nextVertex];
                if (!ssNext) {
                    ssNext = ssVertices[nextVertex] = fAlloc->make<SSVertex>(nextVertex);
                }
                SSEdge* ssEdge = fAlloc->make<SSEdge>(e, ssPrev, ssNext);
                ssEdges.push_back(ssEdge);
//                SkASSERT(!ssPrev->fNext && !ssNext->fPrev);
                ssPrev->fNext = ssNext->fPrev = ssEdge;
                this->makeEvent(ssEdge, &events);
                if (!isOuterBoundary) {
                    e->disconnect();
                } else {
                    SkASSERT(e->fType != EdgeType::kConnector);
                    // Ensure winding values match expected scale for the edge type. During merging of
                    // collinear edges in overlap regions, windings are summed and so could exceed the
                    // expected +/-1 for outer and +/-2 for inner that is used to fill properly during
                    // subsequent polygon generation.
                    e->fWinding = SkScalarCopySign(e->fType == EdgeType::kInner ? 2 : 1,
                                                   e->fWinding);
                }
            }
            e = prev;
        }
        Edge* prev = leftEnclosingEdge;
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
            if (prev) {
                e->fWinding += prev->fWinding;
            }
            activeEdges.insert(e, prev);
            prev = e;
        }
    }
    bool complex = events.size() > 0;

    TESS_LOG("\ncollapsing overlap regions\n");
    TESS_LOG("skeleton before:\n");
    dump_skel(ssEdges);
    while (events.size() > 0) {
        Event* event = events.top();
        events.pop();
        event->apply(mesh, c, &events, this);
    }
    TESS_LOG("skeleton after:\n");
    dump_skel(ssEdges);
    for (SSEdge* edge : ssEdges) {
        if (Edge* e = edge->fEdge) {
            this->makeConnectingEdge(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c, 0);
        }
    }
    return complex;
}

static bool inversion(Vertex* prev, Vertex* next, Edge* origEdge, const Comparator& c) {
    if (!prev || !next) {
        return true;
    }
    int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
    return winding != origEdge->fWinding;
}

// 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 GrAATriangulator::strokeBoundary(EdgeList* boundary, VertexList* innerMesh,
                                      const Comparator& c) {
    TESS_LOG("\nstroking boundary\n");
    // A boundary with fewer than 3 edges is degenerate.
    if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) {
        return;
    }
    Edge* prevEdge = boundary->fTail;
    Vertex* prevV = prevEdge->fWinding > 0 ? prevEdge->fTop : prevEdge->fBottom;
    SkVector prevNormal;
    get_edge_normal(prevEdge, &prevNormal);
    double radius = 0.5;
    Line prevInner(prevEdge->fLine);
    prevInner.fC -= radius;
    Line prevOuter(prevEdge->fLine);
    prevOuter.fC += radius;
    VertexList innerVertices;
    VertexList outerVertices;
    bool innerInversion = true;
    bool outerInversion = true;
    for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
        Vertex* v = e->fWinding > 0 ? e->fTop : e->fBottom;
        SkVector normal;
        get_edge_normal(e, &normal);
        Line inner(e->fLine);
        inner.fC -= radius;
        Line outer(e->fLine);
        outer.fC += radius;
        SkPoint innerPoint, outerPoint;
        TESS_LOG("stroking vertex %g (%g, %g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
        if (!prevEdge->fLine.nearParallel(e->fLine) && prevInner.intersect(inner, &innerPoint) &&
            prevOuter.intersect(outer, &outerPoint)) {
            float cosAngle = normal.dot(prevNormal);
            if (cosAngle < -kCosMiterAngle) {
                Vertex* nextV = e->fWinding > 0 ? e->fBottom : e->fTop;

                // This is a pointy vertex whose angle is smaller than the threshold; miter it.
                Line bisector(innerPoint, outerPoint);
                Line tangent(v->fPoint, v->fPoint + SkPoint::Make(bisector.fA, bisector.fB));
                if (tangent.fA == 0 && tangent.fB == 0) {
                    continue;
                }
                tangent.normalize();
                Line innerTangent(tangent);
                Line outerTangent(tangent);
                innerTangent.fC -= 0.5;
                outerTangent.fC += 0.5;
                SkPoint innerPoint1, innerPoint2, outerPoint1, outerPoint2;
                if (prevNormal.cross(normal) > 0) {
                    // Miter inner points
                    if (!innerTangent.intersect(prevInner, &innerPoint1) ||
                        !innerTangent.intersect(inner, &innerPoint2) ||
                        !outerTangent.intersect(bisector, &outerPoint)) {
                        continue;
                    }
                    Line prevTangent(prevV->fPoint,
                                     prevV->fPoint + SkVector::Make(prevOuter.fA, prevOuter.fB));
                    Line nextTangent(nextV->fPoint,
                                     nextV->fPoint + SkVector::Make(outer.fA, outer.fB));
                    if (prevTangent.dist(outerPoint) > 0) {
                        bisector.intersect(prevTangent, &outerPoint);
                    }
                    if (nextTangent.dist(outerPoint) < 0) {
                        bisector.intersect(nextTangent, &outerPoint);
                    }
                    outerPoint1 = outerPoint2 = outerPoint;
                } else {
                    // Miter outer points
                    if (!outerTangent.intersect(prevOuter, &outerPoint1) ||
                        !outerTangent.intersect(outer, &outerPoint2)) {
                        continue;
                    }
                    Line prevTangent(prevV->fPoint,
                                     prevV->fPoint + SkVector::Make(prevInner.fA, prevInner.fB));
                    Line nextTangent(nextV->fPoint,
                                     nextV->fPoint + SkVector::Make(inner.fA, inner.fB));
                    if (prevTangent.dist(innerPoint) > 0) {
                        bisector.intersect(prevTangent, &innerPoint);
                    }
                    if (nextTangent.dist(innerPoint) < 0) {
                        bisector.intersect(nextTangent, &innerPoint);
                    }
                    innerPoint1 = innerPoint2 = innerPoint;
                }
                if (!innerPoint1.isFinite() || !innerPoint2.isFinite() ||
                    !outerPoint1.isFinite() || !outerPoint2.isFinite()) {
                    continue;
                }
                TESS_LOG("inner (%g, %g), (%g, %g), ",
                         innerPoint1.fX, innerPoint1.fY, innerPoint2.fX, innerPoint2.fY);
                TESS_LOG("outer (%g, %g), (%g, %g)\n",
                         outerPoint1.fX, outerPoint1.fY, outerPoint2.fX, outerPoint2.fY);
                Vertex* innerVertex1 = fAlloc->make<Vertex>(innerPoint1, 255);
                Vertex* innerVertex2 = fAlloc->make<Vertex>(innerPoint2, 255);
                Vertex* outerVertex1 = fAlloc->make<Vertex>(outerPoint1, 0);
                Vertex* outerVertex2 = fAlloc->make<Vertex>(outerPoint2, 0);
                innerVertex1->fPartner = outerVertex1;
                innerVertex2->fPartner = outerVertex2;
                outerVertex1->fPartner = innerVertex1;
                outerVertex2->fPartner = innerVertex2;
                if (!inversion(innerVertices.fTail, innerVertex1, prevEdge, c)) {
                    innerInversion = false;
                }
                if (!inversion(outerVertices.fTail, outerVertex1, prevEdge, c)) {
                    outerInversion = false;
                }
                innerVertices.append(innerVertex1);
                innerVertices.append(innerVertex2);
                outerVertices.append(outerVertex1);
                outerVertices.append(outerVertex2);
            } else {
                TESS_LOG("inner (%g, %g), ", innerPoint.fX, innerPoint.fY);
                TESS_LOG("outer (%g, %g)\n", outerPoint.fX, outerPoint.fY);
                Vertex* innerVertex = fAlloc->make<Vertex>(innerPoint, 255);
                Vertex* outerVertex = fAlloc->make<Vertex>(outerPoint, 0);
                innerVertex->fPartner = outerVertex;
                outerVertex->fPartner = innerVertex;
                if (!inversion(innerVertices.fTail, innerVertex, prevEdge, c)) {
                    innerInversion = false;
                }
                if (!inversion(outerVertices.fTail, outerVertex, prevEdge, c)) {
                    outerInversion = false;
                }
                innerVertices.append(innerVertex);
                outerVertices.append(outerVertex);
            }
        }
        prevInner = inner;
        prevOuter = outer;
        prevV = v;
        prevEdge = e;
        prevNormal = normal;
    }
    if (!inversion(innerVertices.fTail, innerVertices.fHead, prevEdge, c)) {
        innerInversion = false;
    }
    if (!inversion(outerVertices.fTail, outerVertices.fHead, prevEdge, c)) {
        outerInversion = false;
    }
    // Outer edges get 1 winding, and inner edges get -2 winding. This ensures that the interior
    // is always filled (1 + -2 = -1 for normal cases, 1 + 2 = 3 for thin features where the
    // interior inverts).
    // For total inversion cases, the shape has now reversed handedness, so invert the winding
    // so it will be detected during collapseOverlapRegions().
    int innerWinding = innerInversion ? 2 : -2;
    int outerWinding = outerInversion ? -1 : 1;
    for (Vertex* v = innerVertices.fHead; v && v->fNext; v = v->fNext) {
        this->makeConnectingEdge(v, v->fNext, EdgeType::kInner, c, innerWinding);
    }
    this->makeConnectingEdge(innerVertices.fTail, innerVertices.fHead, EdgeType::kInner, c,
                             innerWinding);
    for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) {
        this->makeConnectingEdge(v, v->fNext, EdgeType::kOuter, c, outerWinding);
    }
    this->makeConnectingEdge(outerVertices.fTail, outerVertices.fHead, EdgeType::kOuter, c,
                             outerWinding);
    innerMesh->append(innerVertices);
    fOuterMesh.append(outerVertices);
}

void GrAATriangulator::extractBoundary(EdgeList* boundary, Edge* e) const {
    TESS_LOG("\nextracting boundary\n");
    bool down = this->applyFillType(e->fWinding);
    Vertex* start = down ? e->fTop : e->fBottom;
    do {
        e->fWinding = down ? 1 : -1;
        Edge* next;
        e->fLine.normalize();
        e->fLine = e->fLine * e->fWinding;
        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;
            }
        }
        e->disconnect();
        e = next;
    } while (e && (down ? e->fTop : e->fBottom) != start);
}

// Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh.

void GrAATriangulator::extractBoundaries(const VertexList& inMesh, VertexList* innerVertices,
                                         const Comparator& c) {
    this->removeNonBoundaryEdges(inMesh);
    for (Vertex* v = inMesh.fHead; v; v = v->fNext) {
        while (v->fFirstEdgeBelow) {
            EdgeList boundary;
            this->extractBoundary(&boundary, v->fFirstEdgeBelow);
            this->simplifyBoundary(&boundary, c);
            this->strokeBoundary(&boundary, innerVertices, c);
        }
    }
}

std::tuple<Poly*, bool> GrAATriangulator::tessellate(const VertexList& mesh, const Comparator& c) {
    VertexList innerMesh;
    this->extractBoundaries(mesh, &innerMesh, c);
    SortMesh(&innerMesh, c);
    SortMesh(&fOuterMesh, c);
    this->mergeCoincidentVertices(&innerMesh, c);
    bool was_complex = this->mergeCoincidentVertices(&fOuterMesh, c);
    auto result = this->simplify(&innerMesh, c);
    if (result == SimplifyResult::kFailed) {
        return { nullptr, false };
    }
    was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex;
    result = this->simplify(&fOuterMesh, c);
    if (result == SimplifyResult::kFailed) {
        return { nullptr, false };
    }
    was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex;
    TESS_LOG("\ninner mesh before:\n");
    DUMP_MESH(innerMesh);
    TESS_LOG("\nouter mesh before:\n");
    DUMP_MESH(fOuterMesh);
    EventComparator eventLT(EventComparator::Op::kLessThan);
    EventComparator eventGT(EventComparator::Op::kGreaterThan);
    was_complex = this->collapseOverlapRegions(&innerMesh, c, eventLT) || was_complex;
    was_complex = this->collapseOverlapRegions(&fOuterMesh, c, eventGT) || was_complex;
    if (was_complex) {
        TESS_LOG("found complex mesh; taking slow path\n");
        VertexList aaMesh;
        TESS_LOG("\ninner mesh after:\n");
        DUMP_MESH(innerMesh);
        TESS_LOG("\nouter mesh after:\n");
        DUMP_MESH(fOuterMesh);
        this->connectPartners(&fOuterMesh, c);
        this->connectPartners(&innerMesh, c);
        SortedMerge(&innerMesh, &fOuterMesh, &aaMesh, c);
        TESS_LOG("\nmerged mesh:\n");
        DUMP_MESH(aaMesh);
        this->mergeCoincidentVertices(&aaMesh, c);
        result = this->simplify(&aaMesh, c);
        if (result == SimplifyResult::kFailed) {
            return { nullptr, false };
        }
        TESS_LOG("combined and simplified mesh:\n");
        DUMP_MESH(aaMesh);
        fOuterMesh.fHead = fOuterMesh.fTail = nullptr;
        return this->GrTriangulator::tessellate(aaMesh, c);
    } else {
        TESS_LOG("no complex polygons; taking fast path\n");
        return this->GrTriangulator::tessellate(innerMesh, c);
    }
}

int GrAATriangulator::polysToAATriangles(Poly* polys,
                                         GrEagerVertexAllocator* vertexAllocator) const {
    int64_t count64 = CountPoints(polys, SkPathFillType::kWinding);
    // Count the points from the outer mesh.
    for (Vertex* v = fOuterMesh.fHead; v; v = v->fNext) {
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
            count64 += TRIANGULATOR_WIREFRAME ? 12 : 6;
        }
    }
    if (0 == count64 || count64 > SK_MaxS32) {
        return 0;
    }
    int count = count64;

    size_t vertexStride = sizeof(SkPoint) + sizeof(float);
    skgpu::VertexWriter verts = vertexAllocator->lockWriter(vertexStride, count);
    if (!verts) {
        SkDebugf("Could not allocate vertices\n");
        return 0;
    }

    TESS_LOG("emitting %d verts\n", count);
    skgpu::BufferWriter::Mark start = verts.mark();
    verts = this->polysToTriangles(polys, SkPathFillType::kWinding, std::move(verts));
    // Emit the triangles from the outer mesh.
    for (Vertex* v = fOuterMesh.fHead; v; v = v->fNext) {
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
            Vertex* v0 = e->fTop;
            Vertex* v1 = e->fBottom;
            Vertex* v2 = e->fBottom->fPartner;
            Vertex* v3 = e->fTop->fPartner;
            verts = this->emitTriangle(v0, v1, v2, 0/*winding*/, std::move(verts));
            verts = this->emitTriangle(v0, v2, v3, 0/*winding*/, std::move(verts));
        }
    }

    int actualCount = static_cast<int>((verts.mark() - start) / vertexStride);
    SkASSERT(actualCount <= count);
    vertexAllocator->unlock(actualCount);
    return actualCount;
}