renderer/src/gr_triangulator.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.
 *
 * Initial import from
 * skia:c2a399a74da523ec445f1202367764d04b5df2ec@src/gpu/ganesh/geometry/GrTriangulator.h
 * Last synced to
 * skia:fee7272f5bc258d2b4199c7ed133a72d996c0fb0@src/gpu/ganesh/geometry/GrTriangulator.cpp
 *
 * Copyright 2023 Rive
 */

#include "gr_triangulator.hpp"

#include "rive/renderer/stack_vector.hpp"
#include <algorithm>

#if !defined(SK_ENABLE_OPTIMIZE_SIZE)

#if TRIANGULATOR_LOGGING
#define TESS_LOG printf
#define DUMP_MESH(M) (M).dump()
#else
#define TESS_LOG(...)
#define DUMP_MESH(M)
#endif

namespace rive
{
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 MonotonePoly = GrTriangulator::MonotonePoly;
using Comparator = GrTriangulator::Comparator;

static bool is_finite(Vec2D pt)
{
    float accum = 0;
    accum *= pt.x;
    accum *= pt.y;

    // accum is either NaN or it is finite (zero).
    assert(0 == accum || std::isnan(accum));

    // value==value will be true iff value is not NaN
    // TODO: is it faster to say !accum or accum==accum?
    return !std::isnan(accum);
}

template <class T, T* T::* Prev, T* T::* Next>
static void list_insert(T* t, T* prev, T* next, T** head, T** tail)
{
    t->*Prev = prev;
    t->*Next = next;
    if (prev)
    {
        prev->*Next = t;
    }
    else if (head)
    {
        *head = t;
    }
    if (next)
    {
        next->*Prev = t;
    }
    else if (tail)
    {
        *tail = t;
    }
}

template <class T, T* T::* Prev, T* T::* Next>
static void list_remove(T* t, T** head, T** tail)
{
    if (t->*Prev)
    {
        t->*Prev->*Next = t->*Next;
    }
    else if (head)
    {
        *head = t->*Next;
    }
    if (t->*Next)
    {
        t->*Next->*Prev = t->*Prev;
    }
    else if (tail)
    {
        *tail = t->*Prev;
    }
    t->*Prev = t->*Next = nullptr;
}

typedef bool (*CompareFunc)(const Vec2D& a, const Vec2D& b);

static bool sweep_lt_horiz(const Vec2D& a, const Vec2D& b)
{
    return a.x < b.x || (a.x == b.x && a.y > b.y);
}

static bool sweep_lt_vert(const Vec2D& a, const Vec2D& b)
{
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

bool GrTriangulator::Comparator::sweep_lt(const Vec2D& a, const Vec2D& b) const
{
    return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b)
                                                : sweep_lt_vert(a, b);
}

template <typename Sink>
static size_t emit_triangle(Vertex* v0,
                            Vertex* v1,
                            Vertex* v2,
                            int16_t riveWeight,
                            Sink* sink)
{
    TESS_LOG("emit_triangle %g (%g, %g) %d\n",
             v0->fID,
             v0->fPoint.x,
             v0->fPoint.y,
             v0->fAlpha);
    TESS_LOG("              %g (%g, %g) %d\n",
             v1->fID,
             v1->fPoint.x,
             v1->fPoint.y,
             v1->fAlpha);
    TESS_LOG("              %g (%g, %g) %d\n",
             v2->fID,
             v2->fPoint.x,
             v2->fPoint.y,
             v2->fAlpha);
    sink->emitTriangle(v0->fPoint, v1->fPoint, v2->fPoint, riveWeight);
    return 3;
}

void GrTriangulator::VertexList::insert(Vertex* v, Vertex* prev, Vertex* next)
{
    list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v,
                                                        prev,
                                                        next,
                                                        &fHead,
                                                        &fTail);
}

void GrTriangulator::VertexList::remove(Vertex* v)
{
    list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail);
}

// Round to nearest quarter-pixel. This is used for screenspace tessellation.

#if 0
static inline void round(Vec2D* p)
{
    p->x = SkScalarRoundToScalar(p->x * 4.0f) * 0.25f;
    p->y = SkScalarRoundToScalar(p->y * 4.0f) * 0.25f;
}
#endif

static inline float double_to_clamped_scalar(double d)
{
    // Clamps large values to what's finitely representable when cast back to a
    // float.
    static const double kMaxLimit = (double)std::numeric_limits<float>::max();
    // It's not perfect, but a using a value larger than float_min helps protect
    // from denormalized values and ill-conditions in intermediate calculations
    // on coordinates.
    static const double kNearZeroLimit =
        16 * (double)std::numeric_limits<float>::min();
    if (std::abs(d) < kNearZeroLimit)
    {
        d = 0.f;
    }
    return static_cast<float>(std::max(-kMaxLimit, std::min(d, kMaxLimit)));
}

#if 0
bool GrTriangulator::Line::intersect(const Line& other, Vec2D* point) const
{
    double denom = fA * other.fB - fB * other.fA;
    if (denom == 0.0)
    {
        return false;
    }
    double scale = 1.0 / denom;
    point->x = double_to_clamped_scalar((fB * other.fC - other.fB * fC) * scale);
    point->y = double_to_clamped_scalar((other.fA * fC - fA * other.fC) * scale);
    round(point);
    return point->isFinite();
}
#endif

// If the edge's vertices differ by many orders of magnitude, the computed line
// equation can have significant error in its distance and intersection tests.
// To avoid this, we recursively subdivide long edges and effectively perform a
// binary search to perform a more accurate intersection test.
static bool edge_line_needs_recursion(const Vec2D& p0, const Vec2D& p1)
{
    // ilogbf(0) returns an implementation-defined constant, but we are choosing
    // to saturate negative exponents to 0 for comparisons sake. We're only
    // trying to recurse on lines with very large coordinates.
    int expDiffX = std::abs((std::abs(p0.x) < 1.f ? 0 : std::ilogbf(p0.x)) -
                            (std::abs(p1.x) < 1.f ? 0 : std::ilogbf(p1.x)));
    int expDiffY = std::abs((std::abs(p0.y) < 1.f ? 0 : std::ilogbf(p0.y)) -
                            (std::abs(p1.y) < 1.f ? 0 : std::ilogbf(p1.y)));
    // Differ by more than 2^20, or roughly a factor of one million.
    return expDiffX > 20 || expDiffY > 20;
}

static bool recursive_edge_intersect(const Line& u,
                                     Vec2D u0,
                                     Vec2D u1,
                                     const Line& v,
                                     Vec2D v0,
                                     Vec2D v1,
                                     Vec2D* p,
                                     double* s,
                                     double* t)
{
    // First check if the bounding boxes of [u0,u1] intersects [v0,v1]. If they
    // do not, then the two line segments cannot intersect in their domain (even
    // if the lines themselves might).
    // - don't use AABB::intersect since the vertices aren't sorted and
    // horiz/vertical lines
    //   appear as empty rects, which then never "intersect" according to AABB.
    if (std::min(u0.x, u1.x) > std::max(v0.x, v1.x) ||
        std::max(u0.x, u1.x) < std::min(v0.x, v1.x) ||
        std::min(u0.y, u1.y) > std::max(v0.y, v1.y) ||
        std::max(u0.y, u1.y) < std::min(v0.y, v1.y))
    {
        return false;
    }

    // Compute intersection based on current segment vertices; if an
    // intersection is found but the vertices differ too much in magnitude, we
    // recurse using the midpoint of the segment to reject false positives. We
    // don't currently try to avoid false negatives (e.g. large magnitude line
    // reports no intersection but there is one).
    double denom = u.fA * v.fB - u.fB * v.fA;
    if (denom == 0.0)
    {
        return false;
    }
    double dx = static_cast<double>(v0.x) - u0.x;
    double dy = static_cast<double>(v0.y) - u0.y;
    double sNumer = dy * v.fB + dx * v.fA;
    double tNumer = dy * u.fB + dx * u.fA;
    // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
    // This saves us doing the divide below unless absolutely necessary.
    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;
    }

    *s = sNumer / denom;
    *t = tNumer / denom;
    assert(*s >= 0.0 && *s <= 1.0 && *t >= 0.0 && *t <= 1.0);

    const bool uNeedsSplit = edge_line_needs_recursion(u0, u1);
    const bool vNeedsSplit = edge_line_needs_recursion(v0, v1);
    if (!uNeedsSplit && !vNeedsSplit)
    {
        p->x = double_to_clamped_scalar(u0.x - (*s) * u.fB);
        p->y = double_to_clamped_scalar(u0.y + (*s) * u.fA);
        return true;
    }
    else
    {
        double sScale = 1.0, sShift = 0.0;
        double tScale = 1.0, tShift = 0.0;

        if (uNeedsSplit)
        {
            Vec2D uM = {(float)(0.5 * u0.x + 0.5 * u1.x),
                        (float)(0.5 * u0.y + 0.5 * u1.y)};
            sScale = 0.5;
            if (*s >= 0.5)
            {
                u0 = uM;
                sShift = 0.5;
            }
            else
            {
                u1 = uM;
            }
        }
        if (vNeedsSplit)
        {
            Vec2D vM = {(float)(0.5 * v0.x + 0.5 * v1.x),
                        (float)(0.5 * v0.y + 0.5 * v1.y)};
            tScale = 0.5;
            if (*t >= 0.5)
            {
                v0 = vM;
                tShift = 0.5;
            }
            else
            {
                v1 = vM;
            }
        }

        // Just recompute both lines, even if only one was split; we're already
        // in a slow path.
        if (recursive_edge_intersect(Line(u0, u1),
                                     u0,
                                     u1,
                                     Line(v0, v1),
                                     v0,
                                     v1,
                                     p,
                                     s,
                                     t))
        {
            // Adjust s and t back to full range
            *s = sScale * (*s) + sShift;
            *t = tScale * (*t) + tShift;
            return true;
        }
        else
        {
            // False positive
            return false;
        }
    }
}

bool GrTriangulator::Edge::intersect(const Edge& other,
                                     Vec2D* p,
                                     uint8_t* alpha) const
{
    TESS_LOG("intersecting %g -> %g with %g -> %g\n",
             fTop->fID,
             fBottom->fID,
             other.fTop->fID,
             other.fBottom->fID);
    if (fTop == other.fTop || fBottom == other.fBottom ||
        fTop == other.fBottom || fBottom == other.fTop)
    {
        // If the two edges share a vertex by construction, they have already
        // been split and shouldn't be considered "intersecting" anymore.
        return false;
    }

    double s, t; // needed to interpolate vertex alpha
    const bool intersects = recursive_edge_intersect(fLine,
                                                     fTop->fPoint,
                                                     fBottom->fPoint,
                                                     other.fLine,
                                                     other.fTop->fPoint,
                                                     other.fBottom->fPoint,
                                                     p,
                                                     &s,
                                                     &t);
    if (!intersects)
    {
        return false;
    }

    if (alpha)
    {
        if (fType == EdgeType::kInner || other.fType == EdgeType::kInner)
        {
            // If the intersection is on any interior edge, it needs to stay
            // fully opaque or later triangulation could leech transparency into
            // the inner fill region.
            *alpha = 255;
        }
        else if (fType == EdgeType::kOuter && other.fType == EdgeType::kOuter)
        {
            // Trivially, the intersection will be fully transparent since since
            // it is by construction on the outer edge.
            *alpha = 0;
        }
        else
        {
            // Could be two connectors crossing, or a connector crossing an
            // outer edge. Take the max interpolated alpha
            assert(fType == EdgeType::kConnector ||
                   other.fType == EdgeType::kConnector);
            *alpha = std::max((1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha,
                              (1.0 - t) * other.fTop->fAlpha +
                                  t * other.fBottom->fAlpha);
        }
    }
    return true;
}

void GrTriangulator::EdgeList::insert(Edge* edge, Edge* prev, Edge* next)
{
    list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge,
                                                   prev,
                                                   next,
                                                   &fHead,
                                                   &fTail);
}

bool GrTriangulator::EdgeList::remove(Edge* edge)
{
    TESS_LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
    // assert(this->contains(edge));  // Leave this here for future debugging.
    if (!this->contains(edge))
    {
        return false;
    }
    list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
    return true;
}

void GrTriangulator::MonotonePoly::addEdge(Edge* edge)
{
    if (fSide == Side::kRight)
    {
        assert(!edge->fUsedInRightPoly);
        list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
            edge,
            fLastEdge,
            nullptr,
            &fFirstEdge,
            &fLastEdge);
        edge->fUsedInRightPoly = true;
    }
    else
    {
        assert(!edge->fUsedInLeftPoly);
        list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
            edge,
            fLastEdge,
            nullptr,
            &fFirstEdge,
            &fLastEdge);
        edge->fUsedInLeftPoly = true;
    }
}

template <typename Sink>
size_t GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly,
                                        bool negateWinding,
                                        gpu::WindingFaces windingFaces,
                                        Sink* sink) const
{
    // GrTriangulator and Rive unfortunately have opposite winding senses.
    int16_t riveWeight = -monotonePoly->fWinding;
    assert(riveWeight != 0);
    if (negateWinding)
    {
        riveWeight = -riveWeight;
    }
    if ((riveWeight < 0 &&
         !enums::is_flag_set(windingFaces, gpu::WindingFaces::negative)) ||
        (riveWeight >= 0 &&
         !enums::is_flag_set(windingFaces, gpu::WindingFaces::positive)))
    {
        return 0;
    }
    Edge* e = monotonePoly->fFirstEdge;
    VertexList vertices;
    vertices.append(e->fTop);
    int count = 1;
    while (e != nullptr)
    {
        if (Side::kRight == monotonePoly->fSide)
        {
            vertices.append(e->fBottom);
            e = e->fRightPolyNext;
        }
        else
        {
            vertices.prepend(e->fBottom);
            e = e->fLeftPolyNext;
        }
        count++;
    }
    Vertex* first = vertices.fHead;
    Vertex* v = first->fNext;
    size_t vertexCount = 0;
    while (v != vertices.fTail)
    {
        assert(v && v->fPrev && v->fNext);
        Vertex* prev = v->fPrev;
        Vertex* curr = v;
        Vertex* next = v->fNext;
        if (count == 3)
        {
            vertexCount += emitTriangle(prev, curr, next, riveWeight, sink);
            break;
        }
        double ax = static_cast<double>(curr->fPoint.x) - prev->fPoint.x;
        double ay = static_cast<double>(curr->fPoint.y) - prev->fPoint.y;
        double bx = static_cast<double>(next->fPoint.x) - curr->fPoint.x;
        double by = static_cast<double>(next->fPoint.y) - curr->fPoint.y;
        if (ax * by - ay * bx >= 0.0)
        {
            vertexCount += emitTriangle(prev, curr, next, riveWeight, sink);
            v->fPrev->fNext = v->fNext;
            v->fNext->fPrev = v->fPrev;
            count--;
            if (v->fPrev == first)
            {
                v = v->fNext;
            }
            else
            {
                v = v->fPrev;
            }
        }
        else
        {
            v = v->fNext;
        }
    }
    return vertexCount;
}

template <typename Sink>
size_t GrTriangulator::emitTriangle(Vertex* prev,
                                    Vertex* curr,
                                    Vertex* next,
                                    int16_t riveWeight,
                                    Sink* sink) const
{
    return emit_triangle(prev, curr, next, riveWeight, sink);
}

GrTriangulator::Poly::Poly(Vertex* v, int winding) :
    fFirstVertex(v),
    fWinding(winding),
    fHead(nullptr),
    fTail(nullptr),
    fNext(nullptr),
    fPartner(nullptr),
    fCount(0)
{
#if TRIANGULATOR_LOGGING
    static int gID = 0;
    fID = gID++;
    TESS_LOG("*** created Poly %d\n", fID);
#endif
}

Poly* GrTriangulator::Poly::addEdge(Edge* e, Side side, GrTriangulator* tri)
{
    TESS_LOG("addEdge (%g -> %g) to poly %d, %s side\n",
             e->fTop->fID,
             e->fBottom->fID,
             fID,
             side == Side::kLeft ? "left" : "right");
    Poly* partner = fPartner;
    Poly* poly = this;
    if (side == Side::kRight)
    {
        if (e->fUsedInRightPoly)
        {
            return this;
        }
    }
    else
    {
        if (e->fUsedInLeftPoly)
        {
            return this;
        }
    }
    if (partner)
    {
        fPartner = partner->fPartner = nullptr;
    }
    if (!fTail)
    {
        fHead = fTail = tri->allocateMonotonePoly(e, side, fWinding);
        fCount += 2;
    }
    else if (e->fBottom == fTail->fLastEdge->fBottom)
    {
        return poly;
    }
    else if (side == fTail->fSide)
    {
        fTail->addEdge(e);
        fCount++;
    }
    else
    {
        e = tri->allocateEdge(fTail->fLastEdge->fBottom,
                              e->fBottom,
                              1,
                              EdgeType::kInner);
        fTail->addEdge(e);
        fCount++;
        if (partner)
        {
            partner->addEdge(e, side, tri);
            poly = partner;
        }
        else
        {
            MonotonePoly* m = tri->allocateMonotonePoly(e, side, fWinding);
            m->fPrev = fTail;
            fTail->fNext = m;
            fTail = m;
        }
    }
    return poly;
}

template <typename Sink>
size_t GrTriangulator::emitPoly(const Poly* poly,
                                bool negateWinding,
                                gpu::WindingFaces windingFaces,
                                Sink* sink) const
{
    if (poly->fCount < 3)
    {
        return 0;
    }
    TESS_LOG("emit() %d, size %d\n", poly->fID, poly->fCount);
    size_t vertexCount = 0;
    for (MonotonePoly* m = poly->fHead; m != nullptr; m = m->fNext)
    {
        vertexCount += emitMonotonePoly(m, negateWinding, windingFaces, sink);
    }
    return vertexCount;
}

static bool coincident(const Vec2D& a, const Vec2D& b) { return a == b; }

Poly* GrTriangulator::makePoly(Poly** head, Vertex* v, int winding) const
{
    Poly* poly = fAlloc->make<Poly>(v, winding);
    poly->fNext = *head;
    *head = poly;
    return poly;
}

void GrTriangulator::appendPointToContour(const Vec2D& p,
                                          VertexList* contour) const
{
    Vertex* v = fAlloc->make<Vertex>(p, 255);
#if TRIANGULATOR_LOGGING
    static float gID = 0.0f;
    v->fID = gID++;
#endif
    contour->append(v);
}

#if 0
static float quad_error_at(const Vec2D pts[3], float t, float u)
{
    SkQuadCoeff quad(pts);
    Vec2D p0 = to_point(quad.eval(t - 0.5f * u));
    Vec2D mid = to_point(quad.eval(t));
    Vec2D p1 = to_point(quad.eval(t + 0.5f * u));
    if (!p0.isFinite() || !mid.isFinite() || !p1.isFinite())
    {
        return 0;
    }
    return SkPointPriv::DistanceToLineSegmentBetweenSqd(mid, p0, p1);
}

void GrTriangulator::appendQuadraticToContour(const Vec2D pts[3],
                                              float toleranceSqd,
                                              VertexList* contour) const
{
    SkQuadCoeff quad(pts);
    skvx::float2 aa = quad.fA * quad.fA;
    float denom = 2.0f * (aa[0] + aa[1]);
    skvx::float2 ab = quad.fA * quad.fB;
    float t = denom ? (-ab[0] - ab[1]) / denom : 0.0f;
    int nPoints = 1;
    float u = 1.0f;
    // Test possible subdivision values only at the point of maximum curvature.
    // If it passes the flatness metric there, it'll pass everywhere.
    while (nPoints < GrPathUtils::kMaxPointsPerCurve)
    {
        u = 1.0f / nPoints;
        if (quad_error_at(pts, t, u) < toleranceSqd)
        {
            break;
        }
        nPoints++;
    }
    for (int j = 1; j <= nPoints; j++)
    {
        this->appendPointToContour(to_point(quad.eval(j * u)), contour);
    }
}

void GrTriangulator::generateCubicPoints(const Vec2D& p0,
                                         const Vec2D& p1,
                                         const Vec2D& p2,
                                         const Vec2D& p3,
                                         float tolSqd,
                                         VertexList* contour,
                                         int pointsLeft) const
{
    float d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3);
    float d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3);
    if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || !SkIsFinite(d1, d2))
    {
        this->appendPointToContour(p3, contour);
        return;
    }
    const Vec2D q[] = {{SkScalarAve(p0.x, p1.x), SkScalarAve(p0.y, p1.y)},
                       {SkScalarAve(p1.x, p2.x), SkScalarAve(p1.y, p2.y)},
                       {SkScalarAve(p2.x, p3.x), SkScalarAve(p2.y, p3.y)}};
    const Vec2D r[] = {{SkScalarAve(q[0].x, q[1].x), SkScalarAve(q[0].y, q[1].y)},
                       {SkScalarAve(q[1].x, q[2].x), SkScalarAve(q[1].y, q[2].y)}};
    const Vec2D s = {SkScalarAve(r[0].x, r[1].x), SkScalarAve(r[0].y, r[1].y)};
    pointsLeft >>= 1;
    this->generateCubicPoints(p0, q[0], r[0], s, tolSqd, contour, pointsLeft);
    this->generateCubicPoints(s, r[1], q[2], p3, tolSqd, contour, pointsLeft);
}
#endif

// Stage 1: convert the input path to a set of linear contours (linked list of
// Vertices).

void GrTriangulator::pathToContours(const RawPath& path,
                                    float tolerance,
                                    const AABB& clipBounds,
                                    VertexList* contours,
                                    bool* isLinear) const
{
#if 0
    float toleranceSqd = tolerance * tolerance;
    Vec2D pts[4];
#endif
    *isLinear = true;
    VertexList* contour = contours;
#if 0
    RawPath::Iter iter(fPath, false);
    if (path.isInverseFillType())
    {
        Vec2D quad[4];
        clipBounds.toQuad(quad);
        for (int i = 3; i >= 0; i--)
        {
            this->appendPointToContour(quad[i], contours);
        }
        contour++;
    }
    SkAutoConicToQuads converter;
#endif
    for (const auto [verb, pts] : path)
    {
        switch (verb)
        {
#if 0
            case SkPath::kConic_Verb:
            {
                *isLinear = false;
                if (toleranceSqd == 0)
                {
                    this->appendPointToContour(pts[2], contour);
                    break;
                }
                float weight = iter.conicWeight();
                const Vec2D* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
                for (int i = 0; i < converter.countQuads(); ++i)
                {
                    this->appendQuadraticToContour(quadPts, toleranceSqd, contour);
                    quadPts += 2;
                }
                break;
            }
#endif
            case PathVerb::move:
                if (contour->fHead)
                {
                    contour++;
                }
                if (is_finite(pts[0]))
                {
                    this->appendPointToContour(pts[0], contour);
                }
                break;
            case PathVerb::line:
            {
                if (is_finite(pts[1]))
                {
                    this->appendPointToContour(pts[1], contour);
                }
                break;
            }
            case PathVerb::quad:
            {
#if 0
                *isLinear = false;
                if (toleranceSqd == 0)
                {
                    this->appendPointToContour(pts[2], contour);
                    break;
                }
                this->appendQuadraticToContour(pts, toleranceSqd, contour);
#else
                // RIVE edit: We only triangulate the interior polygon, so just
                // draw a flat line from the beginning to the end of the
                // quadratic.
                if (is_finite(pts[2]))
                {
                    this->appendPointToContour(pts[2], contour);
                }
#endif
                break;
            }
            case PathVerb::cubic:
            {
#if 0
                *isLinear = false;
                if (toleranceSqd == 0)
                {
                    this->appendPointToContour(pts[3], contour);
                    break;
                }
                int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance);
                this->generateCubicPoints(pts[0],
                                          pts[1],
                                          pts[2],
                                          pts[3],
                                          toleranceSqd,
                                          contour,
                                          pointsLeft);
#else
                // RIVE edit: We only triangulate the interior polygon, so just
                // draw a flat line from the beginning to the end of the cubic.
                if (is_finite(pts[3]))
                {
                    this->appendPointToContour(pts[3], contour);
                }
#endif
                break;
            }
            case PathVerb::close:
                break;
        }
    }
}

static inline bool apply_fill_type(FillRule fillRule, int winding)
{
    switch (fillRule)
    {
        // Clockwise triangulates the same as nonZero because clockwise still
        // uses the backward ones for borrowed coverage.
        case FillRule::nonZero:
        case FillRule::clockwise:
            return winding != 0;
        case FillRule::evenOdd:
            return (winding & 1) != 0;
    }
    RIVE_UNREACHABLE();
}

static inline bool apply_fill_type(FillRule fillType, const Poly* poly)
{
    return poly && apply_fill_type(fillType, poly->fWinding);
}

MonotonePoly* GrTriangulator::allocateMonotonePoly(Edge* edge,
                                                   Side side,
                                                   int winding)
{
    ++fNumMonotonePolys;
    return fAlloc->make<MonotonePoly>(edge, side, winding);
}

Edge* GrTriangulator::allocateEdge(Vertex* top,
                                   Vertex* bottom,
                                   int winding,
                                   EdgeType type)
{
    ++fNumEdges;
    return fAlloc->make<Edge>(top, bottom, winding, type);
}

Edge* GrTriangulator::makeEdge(Vertex* prev,
                               Vertex* next,
                               EdgeType type,
                               const Comparator& c)
{
    assert(prev->fPoint != next->fPoint);
    int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
    Vertex* top = winding < 0 ? next : prev;
    Vertex* bottom = winding < 0 ? prev : next;
    return this->allocateEdge(top, bottom, winding, type);
}

bool EdgeList::insert(Edge* edge, Edge* prev)
{
    TESS_LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
    // assert(!this->contains(edge));  // Leave this here for debugging.
    if (this->contains(edge))
    {
        return false;
    }
    Edge* next = prev ? prev->fRight : fHead;
    this->insert(edge, prev, next);
    return true;
}

void GrTriangulator::FindEnclosingEdges(const Vertex& v,
                                        const EdgeList& edges,
                                        Edge** left,
                                        Edge** right)
{
    if (v.fFirstEdgeAbove && v.fLastEdgeAbove)
    {
        *left = v.fFirstEdgeAbove->fLeft;
        *right = v.fLastEdgeAbove->fRight;
        return;
    }
    Edge* next = nullptr;
    Edge* prev;
    for (prev = edges.fTail; prev != nullptr; prev = prev->fLeft)
    {
        if (prev->isLeftOf(v))
        {
            break;
        }
        next = prev;
    }
    *left = prev;
    *right = next;
}

void GrTriangulator::Edge::insertAbove(Vertex* v, const Comparator& c)
{
    if (fTop->fPoint == fBottom->fPoint ||
        c.sweep_lt(fBottom->fPoint, fTop->fPoint))
    {
        return;
    }
    TESS_LOG("insert edge (%g -> %g) above vertex %g\n",
             fTop->fID,
             fBottom->fID,
             v->fID);
    Edge* prev = nullptr;
    Edge* next;
    for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove)
    {
        if (next->isRightOf(*fTop))
        {
            break;
        }
        prev = next;
    }
    list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
        this,
        prev,
        next,
        &v->fFirstEdgeAbove,
        &v->fLastEdgeAbove);
}

void GrTriangulator::Edge::insertBelow(Vertex* v, const Comparator& c)
{
    if (fTop->fPoint == fBottom->fPoint ||
        c.sweep_lt(fBottom->fPoint, fTop->fPoint))
    {
        return;
    }
    TESS_LOG("insert edge (%g -> %g) below vertex %g\n",
             fTop->fID,
             fBottom->fID,
             v->fID);
    Edge* prev = nullptr;
    Edge* next;
    for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow)
    {
        if (next->isRightOf(*fBottom))
        {
            break;
        }
        prev = next;
    }
    list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
        this,
        prev,
        next,
        &v->fFirstEdgeBelow,
        &v->fLastEdgeBelow);
}

static void remove_edge_above(Edge* edge)
{
    assert(edge->fTop && edge->fBottom);
    TESS_LOG("removing edge (%g -> %g) above vertex %g\n",
             edge->fTop->fID,
             edge->fBottom->fID,
             edge->fBottom->fID);
    list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
        edge,
        &edge->fBottom->fFirstEdgeAbove,
        &edge->fBottom->fLastEdgeAbove);
}

static void remove_edge_below(Edge* edge)
{
    assert(edge->fTop && edge->fBottom);
    TESS_LOG("removing edge (%g -> %g) below vertex %g\n",
             edge->fTop->fID,
             edge->fBottom->fID,
             edge->fTop->fID);
    list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
        edge,
        &edge->fTop->fFirstEdgeBelow,
        &edge->fTop->fLastEdgeBelow);
}

void GrTriangulator::Edge::disconnect()
{
    remove_edge_above(this);
    remove_edge_below(this);
}

static bool rewind(EdgeList* activeEdges,
                   Vertex** current,
                   Vertex* dst,
                   const Comparator& c)
{
    if (!current || *current == dst ||
        c.sweep_lt((*current)->fPoint, dst->fPoint))
    {
        return true;
    }
    Vertex* v = *current;
    TESS_LOG("rewinding active edges from vertex %g to vertex %g\n",
             v->fID,
             dst->fID);
    while (v != dst)
    {
        v = v->fPrev;
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow)
        {
            if (!activeEdges->remove(e))
            {
                return false;
            }
        }
        Edge* leftEdge = v->fLeftEnclosingEdge;
        for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove)
        {
            if (!e)
            {
                return false;
            }
            if (!activeEdges->insert(e, leftEdge))
            {
                return false;
            }
            leftEdge = e;
            Vertex* top = e->fTop;
            if (!top ||
                (top->fLeftEnclosingEdge &&
                 !top->fLeftEnclosingEdge->hasTopAndBottom()) ||
                (top->fRightEnclosingEdge &&
                 !top->fRightEnclosingEdge->hasTopAndBottom()))
            {
                return false;
            }
            if (c.sweep_lt(top->fPoint, dst->fPoint) &&
                ((top->fLeftEnclosingEdge &&
                  !top->fLeftEnclosingEdge->isLeftOf(*top)) ||
                 (top->fRightEnclosingEdge &&
                  !top->fRightEnclosingEdge->isRightOf(*top))))
            {
                dst = top;
            }
        }
    }
    *current = v;
    return true;
}

static bool rewind_if_necessary(Edge* edge,
                                EdgeList* activeEdges,
                                Vertex** current,
                                const Comparator& c)
{
    if (!activeEdges || !current)
    {
        return true;
    }
    if (!edge)
    {
        return false;
    }
    Vertex* top = edge->fTop;
    Vertex* bottom = edge->fBottom;
    if (edge->fLeft)
    {
        Vertex* leftTop = edge->fLeft->fTop;
        Vertex* leftBottom = edge->fLeft->fBottom;
        if (leftTop && leftBottom)
        {
            if (c.sweep_lt(leftTop->fPoint, top->fPoint) &&
                !edge->fLeft->isLeftOf(*top))
            {
                if (!rewind(activeEdges, current, leftTop, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(top->fPoint, leftTop->fPoint) &&
                     !edge->isRightOf(*leftTop))
            {
                if (!rewind(activeEdges, current, top, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
                     !edge->fLeft->isLeftOf(*bottom))
            {
                if (!rewind(activeEdges, current, leftTop, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) &&
                     !edge->isRightOf(*leftBottom))
            {
                if (!rewind(activeEdges, current, top, c))
                {
                    return false;
                }
            }
        }
    }
    if (edge->fRight)
    {
        Vertex* rightTop = edge->fRight->fTop;
        Vertex* rightBottom = edge->fRight->fBottom;
        if (rightTop && rightBottom)
        {
            if (c.sweep_lt(rightTop->fPoint, top->fPoint) &&
                !edge->fRight->isRightOf(*top))
            {
                if (!rewind(activeEdges, current, rightTop, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(top->fPoint, rightTop->fPoint) &&
                     !edge->isLeftOf(*rightTop))
            {
                if (!rewind(activeEdges, current, top, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
                     !edge->fRight->isRightOf(*bottom))
            {
                if (!rewind(activeEdges, current, rightTop, c))
                {
                    return false;
                }
            }
            else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
                     !edge->isLeftOf(*rightBottom))
            {
                if (!rewind(activeEdges, current, top, c))
                {
                    return false;
                }
            }
        }
    }
    return true;
}

bool GrTriangulator::setTop(Edge* edge,
                            Vertex* v,
                            EdgeList* activeEdges,
                            Vertex** current,
                            const Comparator& c) const
{
    remove_edge_below(edge);
    if (fCollectBreadcrumbTriangles)
    {
        fBreadcrumbList.append(fAlloc,
                               edge->fTop->fPoint,
                               edge->fBottom->fPoint,
                               v->fPoint,
                               edge->fWinding);
    }
    edge->fTop = v;
    edge->recompute();
    edge->insertBelow(v, c);
    if (!rewind_if_necessary(edge, activeEdges, current, c))
    {
        return false;
    }
    return this->mergeCollinearEdges(edge, activeEdges, current, c);
}

bool GrTriangulator::setBottom(Edge* edge,
                               Vertex* v,
                               EdgeList* activeEdges,
                               Vertex** current,
                               const Comparator& c) const
{
    remove_edge_above(edge);
    if (fCollectBreadcrumbTriangles)
    {
        fBreadcrumbList.append(fAlloc,
                               edge->fTop->fPoint,
                               edge->fBottom->fPoint,
                               v->fPoint,
                               edge->fWinding);
    }
    edge->fBottom = v;
    edge->recompute();
    edge->insertAbove(v, c);
    if (!rewind_if_necessary(edge, activeEdges, current, c))
    {
        return false;
    }
    return this->mergeCollinearEdges(edge, activeEdges, current, c);
}

/*
 * NOTE: Also used in mergeEdgesBelow().
 * Merges two adjacent, collinear edges. Two main cases:
 *
 * 1. Coincident endpoints: if the edges share the exact same top/bottom vertex,
 *    one edge's winding is absorbed into the other. The now-unused "zombie"
 * edge is fully disconnected and also explicitly removed from activeEdges, to
 *    prevent state corruption that can lead to null-pointer dereferences
 *    (b/419397557, b/421959607).
 *
 * 2. Non-coincident (overlapping) endpoints: one edge is shortened in place to
 *    meet the other's endpoint. This is fragile -- it relies on the stability
 * of the floating-point geometric comparisons (isLeftOf, etc.) to succeed on
 *    pathological coordinates.
 */
bool GrTriangulator::mergeEdgesAbove(Edge* edge,
                                     Edge* other,
                                     EdgeList* activeEdges,
                                     Vertex** current,
                                     const Comparator& c) const
{
    if (!edge || !other)
    {
        return false;
    }
    if (coincident(edge->fTop->fPoint, other->fTop->fPoint))
    {
        TESS_LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
                 edge->fTop->fPoint.x,
                 edge->fTop->fPoint.y,
                 edge->fBottom->fPoint.x,
                 edge->fBottom->fPoint.y);
        if (!rewind(activeEdges, current, edge->fTop, c))
        {
            return false;
        }
        other->fWinding += edge->fWinding;
        edge->disconnect();
        if (activeEdges)
        {
            activeEdges->remove(edge);
        }
        edge->fTop = edge->fBottom = nullptr;
    }
    else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint))
    {
        if (!rewind(activeEdges, current, edge->fTop, c))
        {
            return false;
        }
        other->fWinding += edge->fWinding;
        if (!this->setBottom(edge, other->fTop, activeEdges, current, c))
        {
            return false;
        }
    }
    else
    {
        if (!rewind(activeEdges, current, other->fTop, c))
        {
            return false;
        }
        edge->fWinding += other->fWinding;
        if (!this->setBottom(other, edge->fTop, activeEdges, current, c))
        {
            return false;
        }
    }
    return true;
}

// NOTE: See mergeEdgesAbove() comment.
bool GrTriangulator::mergeEdgesBelow(Edge* edge,
                                     Edge* other,
                                     EdgeList* activeEdges,
                                     Vertex** current,
                                     const Comparator& c) const
{
    if (!edge || !other)
    {
        return false;
    }
    if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint))
    {
        TESS_LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
                 edge->fTop->fPoint.x,
                 edge->fTop->fPoint.y,
                 edge->fBottom->fPoint.x,
                 edge->fBottom->fPoint.y);
        if (!rewind(activeEdges, current, edge->fTop, c))
        {
            return false;
        }
        other->fWinding += edge->fWinding;
        edge->disconnect();
        if (activeEdges)
        {
            activeEdges->remove(edge);
        }
        edge->fTop = edge->fBottom = nullptr;
    }
    else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint))
    {
        if (!rewind(activeEdges, current, other->fTop, c))
        {
            return false;
        }
        edge->fWinding += other->fWinding;
        if (!this->setTop(other, edge->fBottom, activeEdges, current, c))
        {
            return false;
        }
    }
    else
    {
        if (!rewind(activeEdges, current, edge->fTop, c))
        {
            return false;
        }
        other->fWinding += edge->fWinding;
        if (!this->setTop(edge, other->fBottom, activeEdges, current, c))
        {
            return false;
        }
    }
    return true;
}

static bool top_collinear(Edge* left, Edge* right)
{
    if (!left || !right)
    {
        return false;
    }
    return left->fTop->fPoint == right->fTop->fPoint ||
           !left->isLeftOf(*right->fTop) || !right->isRightOf(*left->fTop);
}

static bool bottom_collinear(Edge* left, Edge* right)
{
    if (!left || !right)
    {
        return false;
    }
    return left->fBottom->fPoint == right->fBottom->fPoint ||
           !left->isLeftOf(*right->fBottom) ||
           !right->isRightOf(*left->fBottom);
}

// How deep of a stack of mergeCollinearEdges() we'll accept.
static constexpr int kMaxMergeCollinearCalls = 64;

bool GrTriangulator::mergeCollinearEdges(Edge* edge,
                                         EdgeList* activeEdges,
                                         Vertex** current,
                                         const Comparator& c) const
{
    // Stack is unreasonably deep.
    if (++fMergeCollinearStackCount > kMaxMergeCollinearCalls)
    {
        return false;
    }
    for (;;)
    {
        if (top_collinear(edge->fPrevEdgeAbove, edge))
        {
            if (!this->mergeEdgesAbove(edge->fPrevEdgeAbove,
                                       edge,
                                       activeEdges,
                                       current,
                                       c))
            {
                return false;
            }
        }
        else if (top_collinear(edge, edge->fNextEdgeAbove))
        {
            if (!this->mergeEdgesAbove(edge->fNextEdgeAbove,
                                       edge,
                                       activeEdges,
                                       current,
                                       c))
            {
                return false;
            }
        }
        else if (bottom_collinear(edge->fPrevEdgeBelow, edge))
        {
            if (!this->mergeEdgesBelow(edge->fPrevEdgeBelow,
                                       edge,
                                       activeEdges,
                                       current,
                                       c))
            {
                return false;
            }
        }
        else if (bottom_collinear(edge, edge->fNextEdgeBelow))
        {
            if (!this->mergeEdgesBelow(edge->fNextEdgeBelow,
                                       edge,
                                       activeEdges,
                                       current,
                                       c))
            {
                return false;
            }
        }
        else
        {
            break;
        }
    }
    assert(!top_collinear(edge->fPrevEdgeAbove, edge));
    assert(!top_collinear(edge, edge->fNextEdgeAbove));
    assert(!bottom_collinear(edge->fPrevEdgeBelow, edge));
    assert(!bottom_collinear(edge, edge->fNextEdgeBelow));
    return true;
}

GrTriangulator::BoolFail GrTriangulator::splitEdge(Edge* edge,
                                                   Vertex* v,
                                                   EdgeList* activeEdges,
                                                   Vertex** current,
                                                   const Comparator& c)
{
    if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom)
    {
        return BoolFail::kFalse;
    }
    TESS_LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
             edge->fTop->fID,
             edge->fBottom->fID,
             v->fID,
             v->fPoint.x,
             v->fPoint.y);
    Vertex* top;
    Vertex* bottom;
    int winding = edge->fWinding;
    // Theoretically, and ideally, the edge betwee p0 and p1 is being split by
    // v, and v is "between" the segment end points according to c. This is
    // equivalent to p0 < v < p1.  Unfortunately, if v was clamped/rounded this
    // relation doesn't always hold.
    if (c.sweep_lt(v->fPoint, edge->fTop->fPoint))
    {
        // Actually "v < p0 < p1": update 'edge' to be v->p1 and add v->p0. We
        // flip the winding on the new edge so that it winds as if it were
        // p0->v.
        top = v;
        bottom = edge->fTop;
        winding *= -1;
        if (!this->setTop(edge, v, activeEdges, current, c))
        {
            return BoolFail::kFail;
        }
    }
    else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint))
    {
        // Actually "p0 < p1 < v": update 'edge' to be p0->v and add p1->v. We
        // flip the winding on the new edge so that it winds as if it were
        // v->p1.
        top = edge->fBottom;
        bottom = v;
        winding *= -1;
        if (!this->setBottom(edge, v, activeEdges, current, c))
        {
            return BoolFail::kFail;
        }
    }
    else
    {
        // The ideal case, "p0 < v < p1": update 'edge' to be p0->v and add
        // v->p1. Original winding is valid for both edges.
        top = v;
        bottom = edge->fBottom;
        if (!this->setBottom(edge, v, activeEdges, current, c))
        {
            return BoolFail::kFail;
        }
    }
    Edge* newEdge = this->allocateEdge(top, bottom, winding, edge->fType);
    newEdge->insertBelow(top, c);
    newEdge->insertAbove(bottom, c);
    fMergeCollinearStackCount = 0;
    if (!this->mergeCollinearEdges(newEdge, activeEdges, current, c))
    {
        return BoolFail::kFail;
    }
    return BoolFail::kTrue;
}

GrTriangulator::BoolFail GrTriangulator::intersectEdgePair(
    Edge* left,
    Edge* right,
    EdgeList* activeEdges,
    Vertex** current,
    const Comparator& c)
{
    if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom)
    {
        return BoolFail::kFalse;
    }
    if (left->fTop == right->fTop || left->fBottom == right->fBottom)
    {
        return BoolFail::kFalse;
    }

    // Check if the lines intersect as determined by isLeftOf and isRightOf,
    // since that is the source of ground truth. It may suggest an intersection
    // even if Edge::intersect() did not have the precision to check it. In this
    // case we are explicitly correcting the edge topology to match the
    // sided-ness checks.
    Edge* split = nullptr;
    Vertex* splitAt = nullptr;
    if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint))
    {
        if (!left->isLeftOf(*right->fTop))
        {
            split = left;
            splitAt = right->fTop;
        }
    }
    else
    {
        if (!right->isRightOf(*left->fTop))
        {
            split = right;
            splitAt = left->fTop;
        }
    }
    if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint))
    {
        if (!left->isLeftOf(*right->fBottom))
        {
            split = left;
            splitAt = right->fBottom;
        }
    }
    else
    {
        if (!right->isRightOf(*left->fBottom))
        {
            split = right;
            splitAt = left->fBottom;
        }
    }

    if (!split)
    {
        return BoolFail::kFalse;
    }

    // Rewind to the top of the edge that is "moving" since this topology
    // correction can change the geometry of the split edge.
    if (!rewind(activeEdges, current, split->fTop, c))
    {
        return BoolFail::kFail;
    }
    return this->splitEdge(split, splitAt, activeEdges, current, c);
}

Edge* GrTriangulator::makeConnectingEdge(Vertex* prev,
                                         Vertex* next,
                                         EdgeType type,
                                         const Comparator& c,
                                         int windingScale)
{
    if (!prev || !next || prev->fPoint == next->fPoint)
    {
        return nullptr;
    }
    Edge* edge = this->makeEdge(prev, next, type, c);
    edge->insertBelow(edge->fTop, c);
    edge->insertAbove(edge->fBottom, c);
    edge->fWinding *= windingScale;
    fMergeCollinearStackCount = 0;
    this->mergeCollinearEdges(edge, nullptr, nullptr, c);
    return edge;
}

void GrTriangulator::mergeVertices(Vertex* src,
                                   Vertex* dst,
                                   VertexList* mesh,
                                   const Comparator& c) const
{
    TESS_LOG("found coincident verts at %g, %g; merging %g into %g\n",
             src->fPoint.x,
             src->fPoint.y,
             src->fID,
             dst->fID);
    dst->fAlpha = std::max(src->fAlpha, dst->fAlpha);
    if (src->fPartner)
    {
        src->fPartner->fPartner = dst;
    }
    // setBottom()/setTop() call mergeCollinearEdges(), which can recurse, so
    // clear the stack count before each.
    while (Edge* edge = src->fFirstEdgeAbove)
    {
        fMergeCollinearStackCount = 0;
        std::ignore = this->setBottom(edge, dst, nullptr, nullptr, c);
    }
    while (Edge* edge = src->fFirstEdgeBelow)
    {
        fMergeCollinearStackCount = 0;
        std::ignore = this->setTop(edge, dst, nullptr, nullptr, c);
    }
    mesh->remove(src);
    dst->fSynthetic = true;
}

Vertex* GrTriangulator::makeSortedVertex(const Vec2D& p,
                                         uint8_t alpha,
                                         VertexList* mesh,
                                         Vertex* reference,
                                         const Comparator& c) const
{
    Vertex* prevV = reference;
    while (prevV && c.sweep_lt(p, prevV->fPoint))
    {
        prevV = prevV->fPrev;
    }
    Vertex* nextV = prevV ? prevV->fNext : mesh->fHead;
    while (nextV && c.sweep_lt(nextV->fPoint, p))
    {
        prevV = nextV;
        nextV = nextV->fNext;
    }
    Vertex* v;
    if (prevV && coincident(prevV->fPoint, p))
    {
        v = prevV;
    }
    else if (nextV && coincident(nextV->fPoint, p))
    {
        v = nextV;
    }
    else
    {
        v = fAlloc->make<Vertex>(p, alpha);
#if TRIANGULATOR_LOGGING
        if (!prevV)
        {
            v->fID = mesh->fHead->fID - 1.0f;
        }
        else if (!nextV)
        {
            v->fID = mesh->fTail->fID + 1.0f;
        }
        else
        {
            v->fID = (prevV->fID + nextV->fID) * 0.5f;
        }
#endif
        mesh->insert(v, prevV, nextV);
    }
    return v;
}

// Clamps x and y coordinates independently, so the returned point will lie
// within the bounding box formed by the corners of 'min' and 'max' (although
// min/max here refer to the ordering imposed by 'c').
static Vec2D clamp(Vec2D p, Vec2D min, Vec2D max, const Comparator& c)
{
    if (c.fDirection == Comparator::Direction::kHorizontal)
    {
        // With horizontal sorting, we know min.x <= max.x, but there's no
        // relation between Y components unless min.x == max.x.
        return {std::clamp(p.x, min.x, max.x),
                min.y < max.y ? std::clamp(p.y, min.y, max.y)
                              : std::clamp(p.y, max.y, min.y)};
    }
    else
    {
        // And with vertical sorting, we know Y's relation but not necessarily
        // X's.
        return {min.x < max.x ? std::clamp(p.x, min.x, max.x)
                              : std::clamp(p.x, max.x, min.x),
                std::clamp(p.y, min.y, max.y)};
    }
}

#if 0
void GrTriangulator::computeBisector(Edge* edge1, Edge* edge2, Vertex* v) const
{
    assert(fEmitCoverage); // Edge-AA only!
    Line line1 = edge1->fLine;
    Line line2 = edge2->fLine;
    line1.normalize();
    line2.normalize();
    double cosAngle = line1.fA * line2.fA + line1.fB * line2.fB;
    if (cosAngle > 0.999)
    {
        return;
    }
    line1.fC += edge1->fWinding > 0 ? -1 : 1;
    line2.fC += edge2->fWinding > 0 ? -1 : 1;
    Vec2D p;
    if (line1.intersect(line2, &p))
    {
        uint8_t alpha = edge1->fType == EdgeType::kOuter ? 255 : 0;
        v->fPartner = fAlloc->make<Vertex>(p, alpha);
        TESS_LOG("computed bisector (%g,%g) alpha %d for vertex %g\n", p.x, p.y, alpha, v->fID);
    }
}
#endif

GrTriangulator::BoolFail GrTriangulator::checkForIntersection(
    Edge* left,
    Edge* right,
    EdgeList* activeEdges,
    Vertex** current,
    VertexList* mesh,
    const Comparator& c)
{
    if (!left || !right)
    {
        return BoolFail::kFalse;
    }
    Vec2D p;
    uint8_t alpha;
    // If we are going to call intersect, then there must be tops and bottoms.
    if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom)
    {
        return BoolFail::kFail;
    }
    if (left->intersect(*right, &p, &alpha) && is_finite(p))
    {
        Vertex* v;
        TESS_LOG("found intersection, pt is %g, %g\n", p.x, p.y);
        Vertex* top = *current;
        // If the intersection point is above the current vertex, rewind to the
        // vertex above the intersection.
        while (top && c.sweep_lt(p, top->fPoint))
        {
            top = top->fPrev;
        }

        // Always clamp the intersection to lie between the vertices of each
        // segment, since in theory that's where the intersection is, but in
        // reality, floating point error may have computed an intersection
        // beyond a vertex's component(s).
        p = clamp(p, left->fTop->fPoint, left->fBottom->fPoint, c);
        p = clamp(p, right->fTop->fPoint, right->fBottom->fPoint, c);

        if (coincident(p, left->fTop->fPoint))
        {
            v = left->fTop;
        }
        else if (coincident(p, left->fBottom->fPoint))
        {
            v = left->fBottom;
        }
        else if (coincident(p, right->fTop->fPoint))
        {
            v = right->fTop;
        }
        else if (coincident(p, right->fBottom->fPoint))
        {
            v = right->fBottom;
        }
        else
        {
            v = this->makeSortedVertex(p, alpha, mesh, top, c);
#if 0
            if (left->fTop->fPartner)
            {
                assert(fEmitCoverage); // Edge-AA only!
                v->fSynthetic = true;
                this->computeBisector(left, right, v);
            }
#endif
        }
        if (!rewind(activeEdges, current, top ? top : v, c))
        {
            return BoolFail::kFail;
        }
        if (this->splitEdge(left, v, activeEdges, current, c) ==
            BoolFail::kFail)
        {
            return BoolFail::kFail;
        }
        if (this->splitEdge(right, v, activeEdges, current, c) ==
            BoolFail::kFail)
        {
            return BoolFail::kFail;
        }
        v->fAlpha = std::max(v->fAlpha, alpha);
        return BoolFail::kTrue;
    }
    return this->intersectEdgePair(left, right, activeEdges, current, c);
}

void GrTriangulator::sanitizeContours(VertexList* contours,
                                      int contourCnt) const
{
    for (VertexList* contour = contours; contourCnt > 0;
         --contourCnt, ++contour)
    {
        if (contour->fHead == nullptr)
        {
            continue; // empty
        }

        Vertex* prev = contour->fTail;
        prev->fPoint.x = double_to_clamped_scalar((double)prev->fPoint.x);
        prev->fPoint.y = double_to_clamped_scalar((double)prev->fPoint.y);
#if 0
        if (fRoundVerticesToQuarterPixel)
        {
            round(&prev->fPoint);
        }
#endif
        for (Vertex* v = contour->fHead; v;)
        {
            v->fPoint.x = double_to_clamped_scalar((double)v->fPoint.x);
            v->fPoint.y = double_to_clamped_scalar((double)v->fPoint.y);
#if 0
            if (fRoundVerticesToQuarterPixel)
            {
                round(&v->fPoint);
            }
#endif
            Vertex* next = v->fNext;
            Vertex* nextWrap = next ? next : contour->fHead;
            if (coincident(prev->fPoint, v->fPoint))
            {
                TESS_LOG("vertex %g,%g coincident; removing\n",
                         v->fPoint.x,
                         v->fPoint.y);
                contour->remove(v);
            }
            else if (!is_finite(v->fPoint))
            {
                TESS_LOG("vertex %g,%g non-finite; removing\n",
                         v->fPoint.x,
                         v->fPoint.y);
                contour->remove(v);
            }
            else if (!fPreserveCollinearVertices &&
                     Line(prev->fPoint, nextWrap->fPoint).dist(v->fPoint) ==
                         0.0)
            {
                TESS_LOG("vertex %g,%g collinear; removing\n",
                         v->fPoint.x,
                         v->fPoint.y);
                contour->remove(v);
            }
            else
            {
                prev = v;
            }
            v = next;
        }
    }
}

bool GrTriangulator::mergeCoincidentVertices(VertexList* mesh,
                                             const Comparator& c) const
{
    if (!mesh->fHead)
    {
        return false;
    }
    bool merged = false;
    for (Vertex* v = mesh->fHead->fNext; v;)
    {
        Vertex* next = v->fNext;
        if (c.sweep_lt(v->fPoint, v->fPrev->fPoint))
        {
            v->fPoint = v->fPrev->fPoint;
        }
        if (coincident(v->fPrev->fPoint, v->fPoint))
        {
            this->mergeVertices(v, v->fPrev, mesh, c);
            merged = true;
        }
        v = next;
    }
    return merged;
}

// Stage 2: convert the contours to a mesh of edges connecting the vertices.

void GrTriangulator::buildEdges(VertexList* contours,
                                int contourCnt,
                                VertexList* mesh,
                                const Comparator& c)
{
    for (VertexList* contour = contours; contourCnt > 0;
         --contourCnt, ++contour)
    {
        Vertex* prev = contour->fTail;
        for (Vertex* v = contour->fHead; v;)
        {
            Vertex* next = v->fNext;
            this->makeConnectingEdge(prev, v, EdgeType::kInner, c);
            mesh->append(v);
            prev = v;
            v = next;
        }
    }
}

template <CompareFunc sweep_lt>
static void sorted_merge(VertexList* front,
                         VertexList* back,
                         VertexList* result)
{
    Vertex* a = front->fHead;
    Vertex* b = back->fHead;
    while (a && b)
    {
        if (sweep_lt(a->fPoint, b->fPoint))
        {
            front->remove(a);
            result->append(a);
            a = front->fHead;
        }
        else
        {
            back->remove(b);
            result->append(b);
            b = back->fHead;
        }
    }
    result->append(*front);
    result->append(*back);
}

void GrTriangulator::SortedMerge(VertexList* front,
                                 VertexList* back,
                                 VertexList* result,
                                 const Comparator& c)
{
    if (c.fDirection == Comparator::Direction::kHorizontal)
    {
        sorted_merge<sweep_lt_horiz>(front, back, result);
    }
    else
    {
        sorted_merge<sweep_lt_vert>(front, back, result);
    }
#if TRIANGULATOR_LOGGING
    float id = 0.0f;
    for (Vertex* v = result->fHead; v; v = v->fNext)
    {
        v->fID = id++;
    }
#endif
}

// Stage 3: sort the vertices by increasing sweep direction.

template <CompareFunc sweep_lt> static void merge_sort(VertexList* vertices)
{
    Vertex* slow = vertices->fHead;
    if (!slow)
    {
        return;
    }
    Vertex* fast = slow->fNext;
    if (!fast)
    {
        return;
    }
    do
    {
        fast = fast->fNext;
        if (fast)
        {
            fast = fast->fNext;
            slow = slow->fNext;
        }
    } while (fast);
    VertexList front(vertices->fHead, slow);
    VertexList back(slow->fNext, vertices->fTail);
    front.fTail->fNext = back.fHead->fPrev = nullptr;

    merge_sort<sweep_lt>(&front);
    merge_sort<sweep_lt>(&back);

    vertices->fHead = vertices->fTail = nullptr;
    sorted_merge<sweep_lt>(&front, &back, vertices);
}

#if TRIANGULATOR_LOGGING
void VertexList::dump() const
{
    for (Vertex* v = fHead; v; v = v->fNext)
    {
        TESS_LOG("vertex %g (%g, %g) alpha %d",
                 v->fID,
                 v->fPoint.x,
                 v->fPoint.y,
                 v->fAlpha);
        if (Vertex* p = v->fPartner)
        {
            TESS_LOG(", partner %g (%g, %g) alpha %d\n",
                     p->fID,
                     p->fPoint.x,
                     p->fPoint.y,
                     p->fAlpha);
        }
        else
        {
            TESS_LOG(", null partner\n");
        }
        for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove)
        {
            TESS_LOG("  edge %g -> %g, winding %d\n",
                     e->fTop->fID,
                     e->fBottom->fID,
                     e->fWinding);
        }
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow)
        {
            TESS_LOG("  edge %g -> %g, winding %d\n",
                     e->fTop->fID,
                     e->fBottom->fID,
                     e->fWinding);
        }
    }
}
#endif

#ifdef SK_DEBUG
static void validate_edge_pair(Edge* left, Edge* right, const Comparator& c)
{
    if (!left || !right)
    {
        return;
    }
    if (left->fTop == right->fTop)
    {
        assert(left->isLeftOf(*right->fBottom));
        assert(right->isRightOf(*left->fBottom));
    }
    else if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint))
    {
        assert(left->isLeftOf(*right->fTop));
    }
    else
    {
        assert(right->isRightOf(*left->fTop));
    }
    if (left->fBottom == right->fBottom)
    {
        assert(left->isLeftOf(*right->fTop));
        assert(right->isRightOf(*left->fTop));
    }
    else if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint))
    {
        assert(left->isLeftOf(*right->fBottom));
    }
    else
    {
        assert(right->isRightOf(*left->fBottom));
    }
}

static void validate_edge_list(EdgeList* edges, const Comparator& c)
{
    Edge* left = edges->fHead;
    if (!left)
    {
        return;
    }
    for (Edge* right = left->fRight; right; right = right->fRight)
    {
        validate_edge_pair(left, right, c);
        left = right;
    }
}
#endif

// Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.

GrTriangulator::SimplifyResult GrTriangulator::simplify(VertexList* mesh,
                                                        const Comparator& c)
{
    TESS_LOG("simplifying complex polygons\n");

    int initialNumEdges = fNumEdges;
    int initialNumVertices = 0;
    for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext)
    {
        ++initialNumVertices;
    }
    int numSelfIntersections = 0;

    EdgeList activeEdges;
    auto result = SimplifyResult::kAlreadySimple;
    int numVisitedVertices = 0;
    for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext)
    {
        ++numVisitedVertices;
        if (!v->isConnected())
        {
            continue;
        }

        // The max increase across all skps, svgs and gms with only the
        // triangulating and SW path renderers enabled and with the
        // triangulator's maxVerbCount set to the Chrome value is 17x.
        if (fNumEdges > 170 * initialNumEdges)
        {
            return SimplifyResult::kFailed;
        }

        if (numVisitedVertices > 170 * initialNumVertices)
        {
            return SimplifyResult::kFailed;
        }

        Edge* leftEnclosingEdge;
        Edge* rightEnclosingEdge;
        bool restartChecks;
        do
        {
            TESS_LOG("\nvertex %g: (%g,%g), alpha %d\n",
                     v->fID,
                     v->fPoint.x,
                     v->fPoint.y,
                     v->fAlpha);
            restartChecks = false;
            FindEnclosingEdges(*v,
                               activeEdges,
                               &leftEnclosingEdge,
                               &rightEnclosingEdge);
            v->fLeftEnclosingEdge = leftEnclosingEdge;
            v->fRightEnclosingEdge = rightEnclosingEdge;
            if (v->fFirstEdgeBelow)
            {
                for (Edge* edge = v->fFirstEdgeBelow; edge;
                     edge = edge->fNextEdgeBelow)
                {
                    BoolFail l = this->checkForIntersection(leftEnclosingEdge,
                                                            edge,
                                                            &activeEdges,
                                                            &v,
                                                            mesh,
                                                            c);
                    if (l == BoolFail::kFail)
                    {
                        return SimplifyResult::kFailed;
                    }
                    if (l == BoolFail::kFalse)
                    {
                        BoolFail r =
                            this->checkForIntersection(edge,
                                                       rightEnclosingEdge,
                                                       &activeEdges,
                                                       &v,
                                                       mesh,
                                                       c);
                        if (r == BoolFail::kFail)
                        {
                            return SimplifyResult::kFailed;
                        }
                        if (r == BoolFail::kFalse)
                        {
                            // Neither l and r are both false.
                            continue;
                        }
                    }

                    // Either l or r are true.
                    result = SimplifyResult::kFoundSelfIntersection;
                    restartChecks = true;
                    ++numSelfIntersections;
                    break;
                } // for
            }
            else
            {
                BoolFail bf = this->checkForIntersection(leftEnclosingEdge,
                                                         rightEnclosingEdge,
                                                         &activeEdges,
                                                         &v,
                                                         mesh,
                                                         c);
                if (bf == BoolFail::kFail)
                {
                    return SimplifyResult::kFailed;
                }
                if (bf == BoolFail::kTrue)
                {
                    result = SimplifyResult::kFoundSelfIntersection;
                    restartChecks = true;
                    ++numSelfIntersections;
                }
            }

            // In pathological cases, a path can intersect itself millions of
            // times. After 500,000 self-intersections are found, reject the
            // path.
            if (numSelfIntersections > 500000)
            {
                return SimplifyResult::kFailed;
            }
        } while (restartChecks);
#ifdef SK_DEBUG
        validate_edge_list(&activeEdges, c);
#endif
        for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove)
        {
            if (!activeEdges.remove(e))
            {
                return SimplifyResult::kFailed;
            }
        }
        Edge* leftEdge = leftEnclosingEdge;
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow)
        {
            activeEdges.insert(e, leftEdge);
            leftEdge = e;
        }
    }
    assert(!activeEdges.fHead && !activeEdges.fTail);
    return result;
}

// Stage 5: Tessellate the simplified mesh into monotone polygons.

std::tuple<Poly*, bool> GrTriangulator::tessellate(const VertexList& vertices,
                                                   const Comparator&)
{
    TESS_LOG("\ntessellating simple polygons\n");
    EdgeList activeEdges;
    Poly* polys = nullptr;
    for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext)
    {
        if (!v->isConnected())
        {
            continue;
        }
#if TRIANGULATOR_LOGGING
        TESS_LOG("\nvertex %g: (%g,%g), alpha %d\n",
                 v->fID,
                 v->fPoint.x,
                 v->fPoint.y,
                 v->fAlpha);
#endif
        Edge* leftEnclosingEdge;
        Edge* rightEnclosingEdge;
        FindEnclosingEdges(*v,
                           activeEdges,
                           &leftEnclosingEdge,
                           &rightEnclosingEdge);
        Poly* leftPoly;
        Poly* rightPoly;
        if (v->fFirstEdgeAbove)
        {
            leftPoly = v->fFirstEdgeAbove->fLeftPoly;
            rightPoly = v->fLastEdgeAbove->fRightPoly;
        }
        else
        {
            leftPoly =
                leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr;
            rightPoly =
                rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr;
        }
#if TRIANGULATOR_LOGGING
        TESS_LOG("edges above:\n");
        for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove)
        {
            TESS_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);
        }
        TESS_LOG("edges below:\n");
        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow)
        {
            TESS_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
        if (v->fFirstEdgeAbove)
        {
            if (leftPoly)
            {
                leftPoly =
                    leftPoly->addEdge(v->fFirstEdgeAbove, Side::kRight, this);
            }
            if (rightPoly)
            {
                rightPoly =
                    rightPoly->addEdge(v->fLastEdgeAbove, Side::kLeft, this);
            }
            for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove;
                 e = e->fNextEdgeAbove)
            {
                Edge* rightEdge = e->fNextEdgeAbove;
                activeEdges.remove(e);
                if (e->fRightPoly)
                {
                    e->fRightPoly->addEdge(e, Side::kLeft, this);
                }
                if (rightEdge->fLeftPoly &&
                    rightEdge->fLeftPoly != e->fRightPoly)
                {
                    rightEdge->fLeftPoly->addEdge(e, Side::kRight, this);
                }
            }
            activeEdges.remove(v->fLastEdgeAbove);
            if (!v->fFirstEdgeBelow)
            {
                if (leftPoly && rightPoly && leftPoly != rightPoly)
                {
                    assert(leftPoly->fPartner == nullptr &&
                           rightPoly->fPartner == nullptr);
                    rightPoly->fPartner = leftPoly;
                    leftPoly->fPartner = rightPoly;
                }
            }
        }
        if (v->fFirstEdgeBelow)
        {
            if (!v->fFirstEdgeAbove)
            {
                if (leftPoly && rightPoly)
                {
                    if (leftPoly == rightPoly)
                    {
                        if (leftPoly->fTail &&
                            leftPoly->fTail->fSide == Side::kLeft)
                        {
                            leftPoly = this->makePoly(&polys,
                                                      leftPoly->lastVertex(),
                                                      leftPoly->fWinding);
                            leftEnclosingEdge->fRightPoly = leftPoly;
                        }
                        else
                        {
                            rightPoly = this->makePoly(&polys,
                                                       rightPoly->lastVertex(),
                                                       rightPoly->fWinding);
                            rightEnclosingEdge->fLeftPoly = rightPoly;
                        }
                    }
                    Edge* join = this->allocateEdge(leftPoly->lastVertex(),
                                                    v,
                                                    1,
                                                    EdgeType::kInner);
                    leftPoly = leftPoly->addEdge(join, Side::kRight, this);
                    rightPoly = rightPoly->addEdge(join, Side::kLeft, this);
                }
            }
            Edge* leftEdge = v->fFirstEdgeBelow;
            leftEdge->fLeftPoly = leftPoly;
            activeEdges.insert(leftEdge, leftEnclosingEdge);
            for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
                 rightEdge = rightEdge->fNextEdgeBelow)
            {
                activeEdges.insert(rightEdge, leftEdge);
                int winding =
                    leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0;
                winding += leftEdge->fWinding;
                if (winding != 0)
                {
                    Poly* poly = this->makePoly(&polys, v, winding);
                    leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
                }
                leftEdge = rightEdge;
            }
            v->fLastEdgeBelow->fRightPoly = rightPoly;
        }
#if TRIANGULATOR_LOGGING
        TESS_LOG("\nactive edges:\n");
        for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight)
        {
            TESS_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, true};
}

// This is a driver function that calls stages 2-5 in turn.

void GrTriangulator::contoursToMesh(VertexList* contours,
                                    int contourCnt,
                                    VertexList* mesh,
                                    const Comparator& c)
{
#if TRIANGULATOR_LOGGING
    for (int i = 0; i < contourCnt; ++i)
    {
        Vertex* v = contours[i].fHead;
        assert(v);
        TESS_LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.x, v->fPoint.y);
        for (v = v->fNext; v; v = v->fNext)
        {
            TESS_LOG("path.lineTo(%20.20g, %20.20g);\n",
                     v->fPoint.x,
                     v->fPoint.y);
        }
    }
#endif
    this->sanitizeContours(contours, contourCnt);
    this->buildEdges(contours, contourCnt, mesh, c);
}

void GrTriangulator::SortMesh(VertexList* vertices, const Comparator& c)
{
    if (!vertices || !vertices->fHead)
    {
        return;
    }

    // Sort vertices in Y (secondarily in X).
    if (c.fDirection == Comparator::Direction::kHorizontal)
    {
        merge_sort<sweep_lt_horiz>(vertices);
    }
    else
    {
        merge_sort<sweep_lt_vert>(vertices);
    }
#if TRIANGULATOR_LOGGING
    for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext)
    {
        static float gID = 0.0f;
        v->fID = gID++;
    }
#endif
}

std::tuple<Poly*, bool> GrTriangulator::contoursToPolys(VertexList* contours,
                                                        int contourCnt)
{
    Comparator c(fDirection);
    VertexList mesh;
    this->contoursToMesh(contours, contourCnt, &mesh, c);
    TESS_LOG("\ninitial mesh:\n");
    DUMP_MESH(mesh);
    SortMesh(&mesh, c);
    TESS_LOG("\nsorted mesh:\n");
    DUMP_MESH(mesh);
    this->mergeCoincidentVertices(&mesh, c);
    TESS_LOG("\nsorted+merged mesh:\n");
    DUMP_MESH(mesh);
    auto result = this->simplify(&mesh, c);
    if (result == SimplifyResult::kFailed)
    {
        return {nullptr, false};
    }
    TESS_LOG("\nsimplified mesh:\n");
    DUMP_MESH(mesh);
    return this->tessellate(mesh, c);
}

// Stage 6: Triangulate the monotone polygons into a vertex buffer.
template <typename Sink>
size_t GrTriangulator::polysToTriangles(Poly* polys,
                                        FillRule overrideFillType,
                                        bool negateWinding,
                                        gpu::WindingFaces windingFaces,
                                        Sink* sink) const
{
    size_t vertexCount = 0;
    for (Poly* poly = polys; poly; poly = poly->fNext)
    {
        if (apply_fill_type(overrideFillType, poly))
        {
            vertexCount += emitPoly(poly, negateWinding, windingFaces, sink);
        }
    }
    return vertexCount;
}

static int get_contour_count(const RawPath& path, float tolerance)
{
    // We could theoretically be more aggressive about not counting empty
    // contours, but we need to actually match the exact number of contour
    // linked lists the tessellator will create later on.
    int contourCnt = 1;
    bool hasPoints = false;

    bool first = true;
    for (auto [verb, pts] : path)
    {
        switch (verb)
        {
            case PathVerb::move:
                if (!first)
                {
                    ++contourCnt;
                }
                [[fallthrough]];
            case PathVerb::line:
            case PathVerb::quad:
            case PathVerb::cubic:
                hasPoints = true;
                break;
            default:
                break;
        }
        first = false;
    }
    if (!hasPoints)
    {
        return 0;
    }
    return contourCnt;
}

std::tuple<Poly*, bool> GrTriangulator::pathToPolys(const RawPath& path,
                                                    float tolerance,
                                                    const AABB& clipBounds,
                                                    bool* isLinear)
{
    int contourCnt = get_contour_count(path, tolerance);
    if (contourCnt <= 0)
    {
        *isLinear = true;
        return {nullptr, true};
    }

#if 0
    if (SkPathFillType_IsInverse(fPath.getFillType()))
    {
        contourCnt++;
    }
#endif
    std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]);

    this->pathToContours(path, tolerance, clipBounds, contours.get(), isLinear);
    return this->contoursToPolys(contours.get(), contourCnt);
}

int64_t GrTriangulator::CountPoints(Poly* polys, FillRule overrideFillType)
{
    int64_t count = 0;
    for (Poly* poly = polys; poly; poly = poly->fNext)
    {
        if (apply_fill_type(overrideFillType, poly) && poly->fCount >= 3)
        {
            count += (poly->fCount - 2) * (TRIANGULATOR_WIREFRAME ? 6 : 3);
        }
    }
    return count;
}

// Stage 6: Triangulate the monotone polygons into a vertex buffer.

size_t GrTriangulator::countMaxTriangleVertices(Poly* polys,
                                                FillRule fillRule) const
{
    return math::lossless_numeric_cast<size_t>(CountPoints(polys, fillRule));
}

size_t GrTriangulator::polysToTriangles(
    Poly* polys,
    uint64_t maxVertexCount,
    FillRule fillRule,
    uint16_t pathID,
    bool reverseTriangles,
    bool negateWinding,
    gpu::WindingFaces windingFaces,
    gpu::WriteOnlyMappedMemory<gpu::TriangleVertex>* mappedMemory) const
{
    if (0 == maxVertexCount ||
        maxVertexCount > std::numeric_limits<int32_t>::max())
    {
        return 0;
    }

    // Emits triangulations into Rive's mapped triangle vertex buffer.
    class TriangleVertexBufferSink
    {
    public:
        TriangleVertexBufferSink(
            uint16_t pathID,
            bool reverseTriangles,
            gpu::WriteOnlyMappedMemory<gpu::TriangleVertex>* mappedMemory) :
            m_pathID(pathID),
            m_reverseTriangles(reverseTriangles),
            m_mappedMemory(mappedMemory)
        {}

        void emitTriangle(Vec2D a, Vec2D b, Vec2D c, int16_t riveWeight)
        {
            if (m_reverseTriangles)
            {
                std::swap(a, c);
            }
            m_mappedMemory->emplace_back(a, riveWeight, m_pathID);
            m_mappedMemory->emplace_back(b, riveWeight, m_pathID);
            m_mappedMemory->emplace_back(c, riveWeight, m_pathID);
        }

    private:
        const uint16_t m_pathID;
        const bool m_reverseTriangles;
        gpu::WriteOnlyMappedMemory<gpu::TriangleVertex>* const m_mappedMemory;
    };

    TriangleVertexBufferSink sink(pathID, reverseTriangles, mappedMemory);
    size_t actualCount =
        polysToTriangles(polys, fillRule, negateWinding, windingFaces, &sink);
    assert(actualCount <= maxVertexCount);
    return actualCount;
}

size_t GrTriangulator::polysToRetrofitCubicPatches(
    Poly* polys,
    FillRule fillRule,
    gpu::WindingFaces windingFaces,
    const RetrofitCubicPatchEmitter& emitPatch) const
{
    // Accumulates edge-adjacent, equally-wound triangles into 3-triangle strips
    // that we emit in patches instead of 1 at a time, roughly halving the patch
    // count.
    class BufferedTriStripSink
    {
    public:
        BufferedTriStripSink(const RetrofitCubicPatchEmitter& emitPatch) :
            m_emitPatch(emitPatch)
        {}

        void emitTriangle(Vec2D a, Vec2D b, Vec2D c, int16_t riveWeight)
        {
            if (a == b || a == c || b == c || riveWeight == 0)
            {
                return;
            }
            if (!tryMerge(a, b, c, riveWeight))
            {
                flush();
                reset(a, b, c, riveWeight);
            }
        }

        // Emits the buffered polygon (if any) as abs(weight) properly-wound
        // patches.
        void flush()
        {
            if (m_corners.size() != 0)
            {
                // The triangulator is designed to emit all triangles clockwise,
                // and rely on the "weight" attribute. Stencil relies on actual
                // triangle winding to know whether to increment or decrement,
                // so reverse negative-weight polygons.
                if (m_weight < 0)
                {
                    std::reverse(m_corners.begin(), m_corners.end());
                }

                // Convert the polygon vertices to strip ordering.
                // (Rotate the first 3 left by 1 position, yielding
                // {v1,v2,v0,v3,v4}).
                std::rotate(m_corners.begin(),
                            m_corners.begin() + 1,
                            m_corners.begin() + 3);

                // Stencil can't incr/decr by a variable amount, so emit
                // abs(m_weight) patches instead.
                size_t numPatches = std::abs(m_weight);
                for (size_t i = 0; i < numPatches; ++i)
                {
                    m_emitPatch(m_corners.data(), m_corners.size());
                }

                m_emittedPatchCount += numPatches;
                m_corners.clear();
            }
        }

        // Total patches emitted across all flushes.
        size_t emittedPatchCount() const { return m_emittedPatchCount; }

    private:
        // Start a fresh polygon from a single triangle.
        void reset(Vec2D a, Vec2D b, Vec2D c, int16_t weight)
        {
            m_corners.clear();
            m_corners.push_back(a);
            m_corners.push_back(b);
            m_corners.push_back(c);
            m_weight = weight;
        }

        // Merges a triangle if it fits in the patch, has the same winding, and
        // shares an edge with any side of the polygon.
        // Returns false if it can't, in which case the caller flushes and
        // starts a new polygon.
        bool tryMerge(Vec2D a, Vec2D b, Vec2D c, int16_t weight)
        {
            if (m_corners.size() == 0 || weight != m_weight ||
                m_corners.size() >= 5)
            {
                return false;
            }
            // Compare each triangle edge against each edge of the buffered
            // polygon, searching for a match.
            Vec2D tri[3] = {a, b, c};
            for (int e = 0; e < 3; ++e)
            {
                Vec2D e0 = tri[e], e1 = tri[(e + 1) % 3],
                      opp = tri[(e + 2) % 3];
                for (uint32_t i = 0; i < m_corners.size(); ++i)
                {
                    Vec2D c0 = m_corners[i];
                    Vec2D c1 = m_corners[i + 1 == m_corners.size() ? 0 : i + 1];
                    if (e0 == c1 && e1 == c0)
                    {
                        // Match! Insert opp between c0 and c1.
                        m_corners.insert(i + 1, opp);
                        return true;
                    }
                    else
                    {
                        // Not a match. Since the buffered triangles all wind in
                        // the same direction, and since the triangulator
                        // guarantees no overlap, a matching edge will always be
                        // (e0,e1)<->(c1,c0).
                        assert(e0 != c0 || e1 != c1);
                    }
                }
            }
            return false;
        }

        // Buffered polygon that we are attempting to emit as a strip of 3
        // triangles instead of a single one.
        StackVector<Vec2D, 5> m_corners;
        int16_t m_weight = 0;

        const RetrofitCubicPatchEmitter& m_emitPatch;
        size_t m_emittedPatchCount = 0;
    };

    BufferedTriStripSink sink(emitPatch);
    polysToTriangles(polys,
                     fillRule,
                     /*negateWinding=*/false,
                     windingFaces,
                     &sink);
    sink.flush(); // Flush the final buffered polygon (if any).
    return sink.emittedPatchCount();
}
} // namespace rive

#endif // SK_ENABLE_OPTIMIZE_SIZE