Import GrTriangulator from Skia with tests We intentionally chose Skia's triangulator, as opposed to libtess et. al., because it gives us the "breadcrumb triangle" list, which we need in order to do coarse tessellations of just the inner fan. Diffs= c153c393a Import GrTriangulator from Skia with tests (#5417) Co-authored-by: Chris Dalton <99840794+csmartdalton@users.noreply.github.com>
diff --git a/.rive_head b/.rive_head index 9faf631..00fcc68 100644 --- a/.rive_head +++ b/.rive_head
@@ -1 +1 @@ -beab8bab0c8748c652dc07ca8f6e11d5ad22a9af +c153c393adbee427620f7c4f25ef3f0f53173b0e
diff --git a/include/rive/pls/trivial_block_allocator.hpp b/include/rive/pls/trivial_block_allocator.hpp new file mode 100644 index 0000000..b7302ae --- /dev/null +++ b/include/rive/pls/trivial_block_allocator.hpp
@@ -0,0 +1,61 @@ +/* + * Copyright 2023 Rive + */ + +#pragma once + +#include <cassert> +#include <memory> +#include <vector> + +namespace rive +{ +// Fast block allocator for trivially-destructible types. +class TrivialBlockAllocator +{ +public: + TrivialBlockAllocator(size_t initialBlockSize) + { + // Make it so the second allocation doubles initialBlockSize once it happens. + m_currentBlockSize = initialBlockSize; + pushBlock(initialBlockSize); + } + + void* alloc(size_t size) + { + // Align all allocations on 8-byte boundaries. + size = (size + 7) & ~size_t(7); + if (m_currentBlockUsage + size > m_currentBlockSize) + { + // Grow with a fibonacci function. + pushBlock(std::max(m_currentBlockSize + m_lastBlockSize, size)); + } + void* ret = &m_blocks.back()[m_currentBlockUsage]; + m_currentBlockUsage += size; + // Since we round up all allocation sizes, allocations should be 8-byte aligned. + assert((reinterpret_cast<uintptr_t>(ret) & 7) == 0); + return ret; + } + + template <typename T, typename... Args> T* make(Args&&... args) + { + // We don't call destructors on objects we allocate here. + static_assert(std::is_trivially_destructible<T>::value); + return new (alloc(sizeof(T))) T(std::forward<Args>(args)...); + } + +private: + void pushBlock(size_t size) + { + m_blocks.push_back(std::unique_ptr<uint8_t[]>(new uint8_t[size])); + m_lastBlockSize = m_currentBlockSize; + m_currentBlockSize = size; + m_currentBlockUsage = 0; + } + + std::vector<std::unique_ptr<uint8_t[]>> m_blocks; + size_t m_lastBlockSize; + size_t m_currentBlockSize; + size_t m_currentBlockUsage; +}; +} // namespace rive
diff --git a/renderer/gr_inner_fan_triangulator.hpp b/renderer/gr_inner_fan_triangulator.hpp new file mode 100644 index 0000000..c4eac3d --- /dev/null +++ b/renderer/gr_inner_fan_triangulator.hpp
@@ -0,0 +1,78 @@ +/* + * Copyright 2021 Google LLC + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef GrInnerFanTriangulator_DEFINED +#define GrInnerFanTriangulator_DEFINED + +#if !defined(SK_ENABLE_OPTIMIZE_SIZE) + +#include "gr_triangulator.hpp" + +namespace rive +{ +// Triangulates the inner polygon(s) of a path (i.e., the triangle fan for a Redbook rendering +// method). When combined with the outer curves and breadcrumb triangles, these produce a complete +// path. If a breadcrumbCollector is not provided, pathToPolys fails upon self intersection. +class GrInnerFanTriangulator : private GrTriangulator +{ +public: + using GrTriangulator::BreadcrumbTriangleList; + + GrInnerFanTriangulator(const RawPath& path, + FillRule fillRule, + const AABB& pathBounds, + TrivialBlockAllocator* alloc) : + GrTriangulator(path, fillRule, pathBounds, alloc) + { + fPreserveCollinearVertices = true; + fCollectBreadcrumbTriangles = true; + } + + int pathToTriangles(GrEagerVertexAllocator* vertexAlloc, + BreadcrumbTriangleList* breadcrumbList, + bool* isLinear) + { + Poly* polys = this->pathToPolys(breadcrumbList, isLinear); + return this->polysToTriangles(polys, vertexAlloc, breadcrumbList); + } + + Poly* pathToPolys(BreadcrumbTriangleList* breadcrumbList, bool* isLinear) + { + auto [polys, success] = this->GrTriangulator::pathToPolys(0, AABB{}, isLinear); + if (!success) + { + return nullptr; + } + breadcrumbList->concat(std::move(fBreadcrumbList)); + return polys; + } + + int polysToTriangles(Poly* polys, + GrEagerVertexAllocator* vertexAlloc, + BreadcrumbTriangleList* breadcrumbList) const + { + int vertexCount = this->GrTriangulator::polysToTriangles(polys, vertexAlloc); + breadcrumbList->concat(std::move(fBreadcrumbList)); + return vertexCount; + } +}; +} // namespace rive + +#else + +// Stub out GrInnerFanTriangulator::BreadcrumbTriangleList for function declarations. +namespace GrInnerFanTriangulator +{ +struct BreadcrumbTriangleList +{ + BreadcrumbTriangleList() = delete; +}; +}; // namespace GrInnerFanTriangulator + +#endif // SK_ENABLE_OPTIMIZE_SIZE + +#endif // GrInnerFanTriangulator_DEFINED
diff --git a/renderer/gr_triangulator.cpp b/renderer/gr_triangulator.cpp new file mode 100644 index 0000000..5cba84e --- /dev/null +++ b/renderer/gr_triangulator.cpp
@@ -0,0 +1,2204 @@ +/* + * 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:src/gpu/ganesh/geometry/GrTriangulator.cpp + * + * Copyright 2023 Rive + */ + +#include "gr_triangulator.hpp" +#include "path_utils.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); +} + +static inline skgpu::VertexWriter emit_vertex(Vertex* v, + // bool emitCoverage, + skgpu::VertexWriter data) +{ + data << v->fPoint; + +#if 0 + if (emitCoverage) + { + data << GrNormalizeByteToFloat(v->fAlpha); + } +#endif + + return data; +} + +static skgpu::VertexWriter emit_triangle(Vertex* v0, + Vertex* v1, + Vertex* v2, + // bool emitCoverage, + skgpu::VertexWriter data) +{ + 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); +#if TESSELLATOR_WIREFRAME + data = emit_vertex(v0 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v1 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v1 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v2 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v2 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v0 /*, emitCoverage*/, std::move(data)); +#else + data = emit_vertex(v0 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v1 /*, emitCoverage*/, std::move(data)); + data = emit_vertex(v2 /*, emitCoverage*/, std::move(data)); +#endif + return data; +} + +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 * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); + p->y = SkScalarRoundToScalar(p->y * SkFloatToScalar(4.0f)) * SkFloatToScalar(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); +} + +void GrTriangulator::EdgeList::remove(Edge* edge) +{ + TESS_LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); + assert(this->contains(edge)); + list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail); +} + +void GrTriangulator::MonotonePoly::addEdge(Edge* edge) +{ + if (fSide == kRight_Side) + { + 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; + } +} + +skgpu::VertexWriter GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly, + skgpu::VertexWriter data) const +{ + assert(monotonePoly->fWinding != 0); + Edge* e = monotonePoly->fFirstEdge; + VertexList vertices; + vertices.append(e->fTop); + int count = 1; + while (e != nullptr) + { + if (kRight_Side == 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; + while (v != vertices.fTail) + { + assert(v && v->fPrev && v->fNext); + Vertex* prev = v->fPrev; + Vertex* curr = v; + Vertex* next = v->fNext; + if (count == 3) + { + return this->emitTriangle(prev, curr, next, monotonePoly->fWinding, std::move(data)); + } + 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) + { + data = this->emitTriangle(prev, curr, next, monotonePoly->fWinding, std::move(data)); + 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 data; +} + +skgpu::VertexWriter GrTriangulator::emitTriangle(Vertex* prev, + Vertex* curr, + Vertex* next, + int winding, + skgpu::VertexWriter data) const +{ + if (winding > 0) + { + // Ensure our triangles always wind in the same direction as if the path had been + // triangulated as a simple fan (a la red book). + std::swap(prev, next); + } + if (fCollectBreadcrumbTriangles && abs(winding) > 1 && fFillRule == FillRule::nonZero) + { + // The first winding count will come from the actual triangle we emit. The remaining counts + // come from the breadcrumb triangle. + fBreadcrumbList.append(fAlloc, prev->fPoint, curr->fPoint, next->fPoint, abs(winding) - 1); + } + return emit_triangle(prev, curr, next /*, fEmitCoverage*/, std::move(data)); +} + +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 == kLeft_Side ? "left" : "right"); + Poly* partner = fPartner; + Poly* poly = this; + if (side == kRight_Side) + { + 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; +} +skgpu::VertexWriter GrTriangulator::emitPoly(const Poly* poly, skgpu::VertexWriter data) const +{ + if (poly->fCount < 3) + { + return data; + } + TESS_LOG("emit() %d, size %d\n", poly->fID, poly->fCount); + for (MonotonePoly* m = poly->fHead; m != nullptr; m = m->fNext) + { + data = this->emitMonotonePoly(m, std::move(data)); + } + return data; +} + +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) || !SkScalarIsFinite(d1) || + !SkScalarIsFinite(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(float tolerance, + const AABB& clipBounds, + VertexList* contours, + bool* isLinear) const +{ +#if 0 + float toleranceSqd = tolerance * tolerance; +#endif + *isLinear = true; + VertexList* contour = contours; +#if 0 + RawPath::Iter iter(fPath, false); + if (fPath.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] : fPath) + { + switch (verb) + { +#if 0 + case PathVerb::conic + { + *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++; + } + this->appendPointToContour(pts[0], contour); + break; + case PathVerb::line: + { + 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); + break; +#else + RIVE_UNREACHABLE(); +#endif + } + 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); + break; +#else + RIVE_UNREACHABLE(); +#endif + } + case PathVerb::close: + break; + } + } +} + +static inline bool apply_fill_type(FillRule fillRule, int winding) +{ + switch (fillRule) + { + case FillRule::nonZero: + return winding != 0; + case FillRule::evenOdd: + return (winding & 1) != 0; + default: + RIVE_UNREACHABLE(); + } +} + +bool GrTriangulator::applyFillType(int winding) const +{ + return apply_fill_type(fFillRule, winding); +} + +static inline bool apply_fill_type(FillRule fillType, 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); +} + +void EdgeList::insert(Edge* edge, Edge* prev) +{ + TESS_LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); + assert(!this->contains(edge)); + Edge* next = prev ? prev->fRight : fHead; + this->insert(edge, prev, next); +} + +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 void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, const Comparator& c) +{ + if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) + { + return; + } + 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) + { + activeEdges->remove(e); + } + Edge* leftEdge = v->fLeftEnclosingEdge; + for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) + { + activeEdges->insert(e, leftEdge); + leftEdge = e; + Vertex* top = e->fTop; + if (c.sweep_lt(top->fPoint, dst->fPoint) && + ((top->fLeftEnclosingEdge && !top->fLeftEnclosingEdge->isLeftOf(*e->fTop)) || + (top->fRightEnclosingEdge && !top->fRightEnclosingEdge->isRightOf(*e->fTop)))) + { + dst = top; + } + } + } + *current = v; +} + +static void rewind_if_necessary(Edge* edge, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) +{ + if (!activeEdges || !current) + { + return; + } + Vertex* top = edge->fTop; + Vertex* bottom = edge->fBottom; + if (edge->fLeft) + { + Vertex* leftTop = edge->fLeft->fTop; + Vertex* leftBottom = edge->fLeft->fBottom; + if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(*top)) + { + rewind(activeEdges, current, leftTop, c); + } + else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(*leftTop)) + { + rewind(activeEdges, current, top, c); + } + else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && !edge->fLeft->isLeftOf(*bottom)) + { + rewind(activeEdges, current, leftTop, c); + } + else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(*leftBottom)) + { + rewind(activeEdges, current, top, c); + } + } + if (edge->fRight) + { + Vertex* rightTop = edge->fRight->fTop; + Vertex* rightBottom = edge->fRight->fBottom; + if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(*top)) + { + rewind(activeEdges, current, rightTop, c); + } + else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(*rightTop)) + { + rewind(activeEdges, current, top, c); + } + else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && + !edge->fRight->isRightOf(*bottom)) + { + rewind(activeEdges, current, rightTop, c); + } + else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && !edge->isLeftOf(*rightBottom)) + { + rewind(activeEdges, current, top, c); + } + } +} + +void 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); + rewind_if_necessary(edge, activeEdges, current, c); + this->mergeCollinearEdges(edge, activeEdges, current, c); +} + +void 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); + rewind_if_necessary(edge, activeEdges, current, c); + this->mergeCollinearEdges(edge, activeEdges, current, c); +} + +void GrTriangulator::mergeEdgesAbove(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) const +{ + 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); + rewind(activeEdges, current, edge->fTop, c); + other->fWinding += edge->fWinding; + edge->disconnect(); + edge->fTop = edge->fBottom = nullptr; + } + else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) + { + rewind(activeEdges, current, edge->fTop, c); + other->fWinding += edge->fWinding; + this->setBottom(edge, other->fTop, activeEdges, current, c); + } + else + { + rewind(activeEdges, current, other->fTop, c); + edge->fWinding += other->fWinding; + this->setBottom(other, edge->fTop, activeEdges, current, c); + } +} + +void GrTriangulator::mergeEdgesBelow(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) const +{ + 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); + rewind(activeEdges, current, edge->fTop, c); + other->fWinding += edge->fWinding; + edge->disconnect(); + edge->fTop = edge->fBottom = nullptr; + } + else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) + { + rewind(activeEdges, current, other->fTop, c); + edge->fWinding += other->fWinding; + this->setTop(other, edge->fBottom, activeEdges, current, c); + } + else + { + rewind(activeEdges, current, edge->fTop, c); + other->fWinding += edge->fWinding; + this->setTop(edge, other->fBottom, activeEdges, current, c); + } +} + +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); +} + +void GrTriangulator::mergeCollinearEdges(Edge* edge, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) const +{ + for (;;) + { + if (top_collinear(edge->fPrevEdgeAbove, edge)) + { + this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c); + } + else if (top_collinear(edge, edge->fNextEdgeAbove)) + { + this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c); + } + else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) + { + this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c); + } + else if (bottom_collinear(edge, edge->fNextEdgeBelow)) + { + this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c); + } + 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)); +} + +bool 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 false; + } + 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; + this->setTop(edge, v, activeEdges, current, c); + } + 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; + this->setBottom(edge, v, activeEdges, current, c); + } + 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; + this->setBottom(edge, v, activeEdges, current, c); + } + Edge* newEdge = this->allocateEdge(top, bottom, winding, edge->fType); + newEdge->insertBelow(top, c); + newEdge->insertAbove(bottom, c); + this->mergeCollinearEdges(newEdge, activeEdges, current, c); + return true; +} + +bool GrTriangulator::intersectEdgePair(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) +{ + if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) + { + return false; + } + if (left->fTop == right->fTop || left->fBottom == right->fBottom) + { + return false; + } + + // 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 false; + } + + // Rewind to the top of the edge that is "moving" since this topology correction can change the + // geometry of the split edge. + rewind(activeEdges, current, split->fTop, c); + 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; + 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; + } + while (Edge* edge = src->fFirstEdgeAbove) + { + this->setBottom(edge, dst, nullptr, nullptr, c); + } + while (Edge* edge = src->fFirstEdgeBelow) + { + 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 + +bool GrTriangulator::checkForIntersection(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + VertexList* mesh, + const Comparator& c) +{ + if (!left || !right) + { + return false; + } + Vec2D p; + uint8_t alpha; + 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 + } + rewind(activeEdges, current, top ? top : v, c); + this->splitEdge(left, v, activeEdges, current, c); + this->splitEdge(right, v, activeEdges, current, c); + v->fAlpha = std::max(v->fAlpha, alpha); + return true; + } + return this->intersectEdgePair(left, right, activeEdges, current, c); +} + +void GrTriangulator::sanitizeContours(VertexList* contours, int contourCnt) const +{ + for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) + { + assert(contour->fHead); + 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; + + EdgeList activeEdges; + auto result = SimplifyResult::kAlreadySimple; + for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) + { + 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; + } + + 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) + { + if (this->checkForIntersection(leftEnclosingEdge, + edge, + &activeEdges, + &v, + mesh, + c) || + this->checkForIntersection(edge, + rightEnclosingEdge, + &activeEdges, + &v, + mesh, + c)) + { + result = SimplifyResult::kFoundSelfIntersection; + restartChecks = true; + break; + } + } + } + else + { + if (this->checkForIntersection(leftEnclosingEdge, + rightEnclosingEdge, + &activeEdges, + &v, + mesh, + c)) + { + result = SimplifyResult::kFoundSelfIntersection; + restartChecks = true; + } + } + } while (restartChecks); +#ifdef SK_DEBUG + validate_edge_list(&activeEdges, c); +#endif + for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) + { + activeEdges.remove(e); + } + 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, kRight_Side, this); + } + if (rightPoly) + { + rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, kLeft_Side, 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, kLeft_Side, this); + } + if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) + { + rightEdge->fLeftPoly->addEdge(e, kRight_Side, 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 == kLeft_Side) + { + 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, kRight_Side, this); + rightPoly = rightPoly->addEdge(join, kLeft_Side, 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(fPathBounds.width() > fPathBounds.height() ? Comparator::Direction::kHorizontal + : Comparator::Direction::kVertical); + 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. +skgpu::VertexWriter GrTriangulator::polysToTriangles(Poly* polys, + FillRule overrideFillType, + skgpu::VertexWriter data) const +{ + for (Poly* poly = polys; poly; poly = poly->fNext) + { + if (apply_fill_type(overrideFillType, poly)) + { + data = this->emitPoly(poly, std::move(data)); + } + } + return data; +} + +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(float tolerance, + const AABB& clipBounds, + bool* isLinear) +{ + int contourCnt = get_contour_count(fPath, 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(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. + +int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) const +{ + int64_t count64 = CountPoints(polys, fFillRule); + if (0 == count64 || count64 > std::numeric_limits<int32_t>::max()) + { + return 0; + } + int count = count64; + + size_t vertexStride = sizeof(Vec2D); +#if 0 + if (fEmitCoverage) + { + vertexStride += sizeof(float); + } +#endif + skgpu::VertexWriter verts = vertexAllocator->lockWriter(count64); + if (!verts) + { + fprintf(stderr, "Could not allocate vertices\n"); + return 0; + } + + TESS_LOG("emitting %d verts\n", count); + + skgpu::VertexWriter::Mark start = verts.mark(); + verts = this->polysToTriangles(polys, fFillRule, std::move(verts)); + + int actualCount = static_cast<int>((verts.mark() - start) / vertexStride); + assert(actualCount <= count); + vertexAllocator->unlock(actualCount); + return actualCount; +} +} // namespace rive + +#endif // SK_ENABLE_OPTIMIZE_SIZE
diff --git a/renderer/gr_triangulator.hpp b/renderer/gr_triangulator.hpp new file mode 100644 index 0000000..d968bf1 --- /dev/null +++ b/renderer/gr_triangulator.hpp
@@ -0,0 +1,685 @@ +/* + * 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:src/gpu/ganesh/geometry/GrTriangulator.h + * + * Copyright 2023 Rive + */ + +#ifndef GrTriangulator_DEFINED +#define GrTriangulator_DEFINED + +#if !defined(SK_ENABLE_OPTIMIZE_SIZE) + +#include "rive/math/raw_path.hpp" +#include "rive/math/vec2d.hpp" +#include "rive/math/aabb.hpp" +#include "rive/pls/trivial_block_allocator.hpp" + +namespace skgpu +{ +class VertexWriter +{ +public: + VertexWriter() = default; + VertexWriter(rive::Vec2D* buff, size_t buffCount) : m_buff(buff) {} + VertexWriter& operator<<(rive::Vec2D pt) + { + *m_buff++ = pt; + return *this; + } + + operator bool() { return m_buff; } + + using Mark = uintptr_t; + Mark mark() const { return reinterpret_cast<uintptr_t>(m_buff); } + +private: + rive::Vec2D* m_buff = nullptr; +}; +} // namespace skgpu + +// This interface is used to allocate and map GPU vertex data before the exact number of required +// vertices is known. Usage pattern: +// +// 1. Call lock(eagerCount) with an upper bound on the number of required vertices. +// 2. Compute and write vertex data to the returned pointer (if not null). +// 3. Call unlock(actualCount) and provide the actual number of vertices written during step #2. +// +// On step #3, the implementation will attempt to shrink the underlying GPU memory slot to fit the +// actual vertex count. +class GrEagerVertexAllocator +{ +public: + virtual rive::Vec2D* lock(int eagerCount) = 0; + + virtual void unlock(int actualCount) = 0; + + virtual ~GrEagerVertexAllocator() {} + + skgpu::VertexWriter lockWriter(size_t eagerCount) + { + rive::Vec2D* p = this->lock(eagerCount); + return p ? skgpu::VertexWriter{p, eagerCount} : skgpu::VertexWriter{}; + } +}; + +namespace rive +{ +#define TRIANGULATOR_LOGGING 0 +#define TRIANGULATOR_WIREFRAME 0 + +/** + * Provides utility functions for converting paths to a collection of triangles. + */ +class GrTriangulator +{ +public: + constexpr static int kArenaDefaultChunkSize = 16 * 1024; + + static int PathToTriangles(const RawPath& path, + FillRule fillRule, + const AABB& pathBounds, + float tolerance, + const AABB& clipBounds, + GrEagerVertexAllocator* vertexAllocator, + bool* isLinear) + { + // if (!path.isFinite()) + // { + // return 0; + // } + TrivialBlockAllocator alloc(kArenaDefaultChunkSize); + GrTriangulator triangulator(path, fillRule, pathBounds, &alloc); + auto [polys, success] = triangulator.pathToPolys(tolerance, clipBounds, isLinear); + if (!success) + { + return 0; + } + int count = triangulator.polysToTriangles(polys, vertexAllocator); + return count; + } + + // Enums used by GrTriangulator internals. + typedef enum + { + kLeft_Side, + kRight_Side + } Side; + enum class EdgeType + { + kInner, + kOuter, + kConnector + }; + + // Structs used by GrTriangulator internals. + struct Vertex; + struct VertexList; + struct Line; + struct Edge; + struct EdgeList; + struct MonotonePoly; + struct Poly; + struct Comparator; + +protected: + GrTriangulator(const RawPath& path, + FillRule fillRule, + const AABB& pathBounds, + TrivialBlockAllocator* alloc) : + fPath(path), fFillRule(fillRule), fPathBounds(pathBounds), fAlloc(alloc) + {} + virtual ~GrTriangulator() {} + + // There are six stages to the basic algorithm: + // + // 1) Linearize the path contours into piecewise linear segments: + void pathToContours(float tolerance, + const AABB& clipBounds, + VertexList* contours, + bool* isLinear) const; + + // 2) Build a mesh of edges connecting the vertices: + void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&); + + // 3) Sort the vertices in Y (and secondarily in X): + static void SortedMerge(VertexList* front, + VertexList* back, + VertexList* result, + const Comparator&); + static void SortMesh(VertexList* vertices, const Comparator&); + + // 4) Simplify the mesh by inserting new vertices at intersecting edges: + enum class SimplifyResult + { + kFailed, + kAlreadySimple, + kFoundSelfIntersection + }; + + [[nodiscard]] SimplifyResult simplify(VertexList* mesh, const Comparator&); + + // 5) Tessellate the simplified mesh into monotone polygons: + virtual std::tuple<Poly*, bool> tessellate(const VertexList& vertices, const Comparator&); + + // 6) Triangulate the monotone polygons directly into a vertex buffer: + skgpu::VertexWriter polysToTriangles(Poly* polys, + FillRule overrideFillRule, + skgpu::VertexWriter data) const; + + // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list + // of vertices (and the necessity of inserting new vertices on intersection). + // + // Stages (4) and (5) use an active edge list -- a list of all edges for which the + // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted + // left-to-right based on the point where both edges are active (when both top vertices + // have been seen, so the "lower" top vertex of the two). If the top vertices are equal + // (shared), it's sorted based on the last point where both edges are active, so the + // "upper" bottom vertex. + // + // The most complex step is the simplification (4). It's based on the Bentley-Ottman + // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are + // not exact and may violate the mesh topology or active edge list ordering. We + // accommodate this by adjusting the topology of the mesh and AEL to match the intersection + // points. This occurs in two ways: + // + // A) Intersections may cause a shortened edge to no longer be ordered with respect to its + // neighbouring edges at the top or bottom vertex. This is handled by merging the + // edges (mergeCollinearVertices()). + // B) Intersections may cause an edge to violate the left-to-right ordering of the + // active edge list. This is handled by detecting potential violations and rewinding + // the active edge list to the vertex before they occur (rewind() during merging, + // rewind_if_necessary() during splitting). + // + // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and + // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it + // currently uses a linked list for the active edge list, rather than a 2-3 tree as the + // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also + // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N) + // insertions and removals was greater than the cost of infrequent O(N) lookups with the + // linked list implementation. With the latter, all removals are O(1), and most insertions + // are O(1), since we know the adjacent edge in the active edge list based on the topology. + // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less + // frequent. There may be other data structures worth investigating, however. + // + // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of + // the path bounds. When the path is taller than it is wide, we sort vertices based on + // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider + // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y + // coordinate. This is so that the "left" and "right" orientation in the code remains correct + // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the + // setting rotates 90 degrees counterclockwise, rather that transposing. + + // Additional helpers and driver functions. + skgpu::VertexWriter emitMonotonePoly(const MonotonePoly*, skgpu::VertexWriter data) const; + skgpu::VertexWriter emitTriangle(Vertex* prev, + Vertex* curr, + Vertex* next, + int winding, + skgpu::VertexWriter data) const; + skgpu::VertexWriter emitPoly(const Poly*, skgpu::VertexWriter data) const; + + Poly* makePoly(Poly** head, Vertex* v, int winding) const; + void appendPointToContour(const Vec2D& p, VertexList* contour) const; + void appendQuadraticToContour(const Vec2D[3], float toleranceSqd, VertexList* contour) const; + void generateCubicPoints(const Vec2D&, + const Vec2D&, + const Vec2D&, + const Vec2D&, + float tolSqd, + VertexList* contour, + int pointsLeft) const; + bool applyFillType(int winding) const; + MonotonePoly* allocateMonotonePoly(Edge* edge, Side side, int winding); + Edge* allocateEdge(Vertex* top, Vertex* bottom, int winding, EdgeType type); + Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&); + void setTop(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + void setBottom(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + void mergeEdgesAbove(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + void mergeEdgesBelow(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + Edge* makeConnectingEdge(Vertex* prev, + Vertex* next, + EdgeType, + const Comparator&, + int windingScale = 1); + void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&) const; + static void FindEnclosingEdges(const Vertex& v, + const EdgeList& edges, + Edge** left, + Edge** right); + void mergeCollinearEdges(Edge* edge, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + bool splitEdge(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&); + bool intersectEdgePair(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + const Comparator&); + Vertex* makeSortedVertex(const Vec2D&, + uint8_t alpha, + VertexList* mesh, + Vertex* reference, + const Comparator&) const; +#if 0 + void computeBisector(Edge* edge1, Edge* edge2, Vertex*) const; +#endif + bool checkForIntersection(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + VertexList* mesh, + const Comparator&); + void sanitizeContours(VertexList* contours, int contourCnt) const; + bool mergeCoincidentVertices(VertexList* mesh, const Comparator&) const; + void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&); + std::tuple<Poly*, bool> contoursToPolys(VertexList* contours, int contourCnt); + std::tuple<Poly*, bool> pathToPolys(float tolerance, const AABB& clipBounds, bool* isLinear); + static int64_t CountPoints(Poly* polys, FillRule overrideFillRule); + int polysToTriangles(Poly*, GrEagerVertexAllocator*) const; + + // FIXME: fPath should be plumbed through function parameters instead. + const RawPath fPath; + FillRule fFillRule; + AABB fPathBounds; + TrivialBlockAllocator* const fAlloc; + int fNumMonotonePolys = 0; + int fNumEdges = 0; + + // Internal control knobs. +#if 0 + bool fRoundVerticesToQuarterPixel = false; + bool fEmitCoverage = false; +#endif + bool fPreserveCollinearVertices = false; + bool fCollectBreadcrumbTriangles = false; + + // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer + // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb + // triangles, and inner polygon triangulation all together into the stencil buffer has the same + // identical rasterized effect as stenciling a classic Redbook fan. + // + // The breadcrumb triangles track all the edge splits that led from the original inner polygon + // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb + // triangle consisting of the edge's original endpoints and the split point. (We also add + // supplemental breadcrumb triangles to areas where abs(winding) > 1.) + // + // a + // / + // / + // / + // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x]. + // / + // / + // b + // + // The opposite-direction shared edges between the triangulation and breadcrumb triangles should + // all cancel out, leaving just the set of edges from the original polygon. + class BreadcrumbTriangleList + { + public: + struct Node + { + Node(Vec2D a, Vec2D b, Vec2D c) : fPts{a, b, c} {} + Vec2D fPts[3]; + Node* fNext = nullptr; + }; + const Node* head() const { return fHead; } + int count() const { return fCount; } + + void append(TrivialBlockAllocator* alloc, Vec2D a, Vec2D b, Vec2D c, int winding) + { + if (a == b || a == c || b == c || winding == 0) + { + return; + } + if (winding < 0) + { + std::swap(a, b); + winding = -winding; + } + for (int i = 0; i < winding; ++i) + { + assert(fTail && !(*fTail)); + *fTail = alloc->make<Node>(a, b, c); + fTail = &(*fTail)->fNext; + } + fCount += winding; + } + + void concat(BreadcrumbTriangleList&& list) + { + assert(fTail && !(*fTail)); + if (list.fHead) + { + *fTail = list.fHead; + fTail = list.fTail; + fCount += list.fCount; + list.fHead = nullptr; + list.fTail = &list.fHead; + list.fCount = 0; + } + } + + private: + Node* fHead = nullptr; + Node** fTail = &fHead; + int fCount = 0; + }; + + mutable BreadcrumbTriangleList fBreadcrumbList; +}; + +/** + * Vertices are used in three ways: first, the path contours are converted into a + * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices + * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing + * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid + * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of + * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since + * an individual Vertex from the path mesh may belong to multiple + * MonotonePolys, so the original Vertices cannot be re-used. + */ + +struct GrTriangulator::Vertex +{ + Vertex(const Vec2D& point, uint8_t alpha) : + fPoint(point), + fPrev(nullptr), + fNext(nullptr), + fFirstEdgeAbove(nullptr), + fLastEdgeAbove(nullptr), + fFirstEdgeBelow(nullptr), + fLastEdgeBelow(nullptr), + fLeftEnclosingEdge(nullptr), + fRightEnclosingEdge(nullptr), + fPartner(nullptr), + fAlpha(alpha), + fSynthetic(false) +#if TRIANGULATOR_LOGGING + , + fID(-1.0f) +#endif + {} + Vec2D fPoint; // Vertex position + Vertex* fPrev; // Linked list of contours, then Y-sorted vertices. + Vertex* fNext; // " + Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. + Edge* fLastEdgeAbove; // " + Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. + Edge* fLastEdgeBelow; // " + Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex. + Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex. + Vertex* fPartner; // Corresponding inner or outer vertex (for AA). + uint8_t fAlpha; + bool fSynthetic; // Is this a synthetic vertex? +#if TRIANGULATOR_LOGGING + float fID; // Identifier used for logging. +#endif + bool isConnected() const { return this->fFirstEdgeAbove || this->fFirstEdgeBelow; } +}; + +struct GrTriangulator::VertexList +{ + VertexList() : fHead(nullptr), fTail(nullptr) {} + VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {} + Vertex* fHead; + Vertex* fTail; + void insert(Vertex* v, Vertex* prev, Vertex* next); + void append(Vertex* v) { insert(v, fTail, nullptr); } + void append(const VertexList& list) + { + if (!list.fHead) + { + return; + } + if (fTail) + { + fTail->fNext = list.fHead; + list.fHead->fPrev = fTail; + } + else + { + fHead = list.fHead; + } + fTail = list.fTail; + } + void prepend(Vertex* v) { insert(v, nullptr, fHead); } + void remove(Vertex* v); + void close() + { + if (fHead && fTail) + { + fTail->fNext = fHead; + fHead->fPrev = fTail; + } + } +#if TRIANGULATOR_LOGGING + void dump() const; +#endif +}; + +// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line. +struct GrTriangulator::Line +{ + Line(double a, double b, double c) : fA(a), fB(b), fC(c) {} + Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {} + Line(const Vec2D& p, const Vec2D& q) : + fA(static_cast<double>(q.y) - p.y) // a = dY + , + fB(static_cast<double>(p.x) - q.x) // b = -dX + , + fC(static_cast<double>(p.y) * q.x - // c = cross(q, p) + static_cast<double>(p.x) * q.y) + {} + double dist(const Vec2D& p) const { return fA * p.x + fB * p.y + fC; } + Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); } + double magSq() const { return fA * fA + fB * fB; } + void normalize() + { + double len = sqrt(this->magSq()); + if (len == 0.0) + { + return; + } + double scale = 1.0f / len; + fA *= scale; + fB *= scale; + fC *= scale; + } + bool nearParallel(const Line& o) const + { + return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001; + } + +#if 0 + // Compute the intersection of two (infinite) Lines. + bool intersect(const Line& other, Vec2D* point) const; +#endif + double fA, fB, fC; +}; + +/** + * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and + * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf(). + * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating + * point). For speed, that case is only tested by the callers that require it (e.g., + * rewind_if_necessary()). Edges also handle checking for intersection with other edges. + * Currently, this converts the edges to the parametric form, in order to avoid doing a division + * until an intersection has been confirmed. This is slightly slower in the "found" case, but + * a lot faster in the "not found" case. + * + * The coefficients of the line equation stored in double precision to avoid catastrophic + * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is + * correct in float, since it's a polynomial of degree 2. The intersect() function, being + * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its + * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of + * this file). + */ + +struct GrTriangulator::Edge +{ + Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type) : + fWinding(winding), + fTop(top), + fBottom(bottom), + fType(type), + fLeft(nullptr), + fRight(nullptr), + fPrevEdgeAbove(nullptr), + fNextEdgeAbove(nullptr), + fPrevEdgeBelow(nullptr), + fNextEdgeBelow(nullptr), + fLeftPoly(nullptr), + fRightPoly(nullptr), + fLeftPolyPrev(nullptr), + fLeftPolyNext(nullptr), + fRightPolyPrev(nullptr), + fRightPolyNext(nullptr), + fUsedInLeftPoly(false), + fUsedInRightPoly(false), + fLine(top, bottom) + {} + int fWinding; // 1 == edge goes downward; -1 = edge goes upward. + Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt). + Vertex* fBottom; // The bottom vertex in vertex-sort-order. + EdgeType fType; + Edge* fLeft; // The linked list of edges in the active edge list. + Edge* fRight; // " + Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above". + Edge* fNextEdgeAbove; // " + Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". + Edge* fNextEdgeBelow; // " + Poly* fLeftPoly; // The Poly to the left of this edge, if any. + Poly* fRightPoly; // The Poly to the right of this edge, if any. + Edge* fLeftPolyPrev; + Edge* fLeftPolyNext; + Edge* fRightPolyPrev; + Edge* fRightPolyNext; + bool fUsedInLeftPoly; + bool fUsedInRightPoly; + Line fLine; + + double dist(const Vec2D& p) const + { + // Coerce points coincident with the vertices to have dist = 0, since converting from + // a double intersection point back to float storage might construct a point that's no + // longer on the ideal line. + return (p == fTop->fPoint || p == fBottom->fPoint) ? 0.0 : fLine.dist(p); + } + bool isRightOf(const Vertex& v) const { return this->dist(v.fPoint) < 0.0; } + bool isLeftOf(const Vertex& v) const { return this->dist(v.fPoint) > 0.0; } + void recompute() { fLine = Line(fTop, fBottom); } + void insertAbove(Vertex*, const Comparator&); + void insertBelow(Vertex*, const Comparator&); + void disconnect(); + bool intersect(const Edge& other, Vec2D* p, uint8_t* alpha = nullptr) const; +}; + +struct GrTriangulator::EdgeList +{ + EdgeList() : fHead(nullptr), fTail(nullptr) {} + Edge* fHead; + Edge* fTail; + void insert(Edge* edge, Edge* prev, Edge* next); + void insert(Edge* edge, Edge* prev); + void append(Edge* e) { insert(e, fTail, nullptr); } + void remove(Edge* edge); + void removeAll() + { + while (fHead) + { + this->remove(fHead); + } + } + void close() + { + if (fHead && fTail) + { + fTail->fRight = fHead; + fHead->fLeft = fTail; + } + } + bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; } +}; + +struct GrTriangulator::MonotonePoly +{ + MonotonePoly(Edge* edge, Side side, int winding) : + fSide(side), + fFirstEdge(nullptr), + fLastEdge(nullptr), + fPrev(nullptr), + fNext(nullptr), + fWinding(winding) + { + this->addEdge(edge); + } + Side fSide; + Edge* fFirstEdge; + Edge* fLastEdge; + MonotonePoly* fPrev; + MonotonePoly* fNext; + int fWinding; + void addEdge(Edge*); +}; + +struct GrTriangulator::Poly +{ + Poly(Vertex* v, int winding); + + Poly* addEdge(Edge* e, Side side, GrTriangulator*); + Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; } + Vertex* fFirstVertex; + int fWinding; + MonotonePoly* fHead; + MonotonePoly* fTail; + Poly* fNext; + Poly* fPartner; + int fCount; +#if TRIANGULATOR_LOGGING + int fID; +#endif +}; + +struct GrTriangulator::Comparator +{ + enum class Direction + { + kVertical, + kHorizontal + }; + Comparator(Direction direction) : fDirection(direction) {} + bool sweep_lt(const Vec2D& a, const Vec2D& b) const; + Direction fDirection; +}; +} // namespace rive + +#endif // SK_ENABLE_OPTIMIZE_SIZE + +#endif // GrTriangulator_DEFINED