#include "src/gpu/ganesh/geometry/GrTriangulator.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkRect.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkTPin.h"
#include "src/base/SkVx.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkPointPriv.h"
#include "src/gpu/BufferWriter.h"
#include "src/gpu/ganesh/GrColor.h"
#include "src/gpu/ganesh/GrEagerVertexAllocator.h"
#include "src/gpu/ganesh/geometry/GrPathUtils.h"
#include <algorithm>
#include <cstddef>
#include <limits>
#include <memory>
#include <tuple>
#include <utility>
#if !defined(SK_ENABLE_OPTIMIZE_SIZE)
#if TRIANGULATOR_LOGGING
#define TESS_LOG …
#define DUMP_MESH …
#else
#define TESS_LOG(...) …
#define DUMP_MESH(M) …
#endif
EdgeType;
Vertex;
VertexList;
Line;
Edge;
EdgeList;
Poly;
MonotonePoly;
Comparator;
template <class T, T* T::*Prev, T* T::*Next>
static void list_insert(T* t, T* prev, T* next, T** head, T** tail) { … }
template <class T, T* T::*Prev, T* T::*Next>
static void list_remove(T* t, T** head, T** tail) { … }
CompareFunc;
static bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { … }
static bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { … }
bool GrTriangulator::Comparator::sweep_lt(const SkPoint& a, const SkPoint& b) const { … }
static inline skgpu::VertexWriter emit_vertex(Vertex* v,
bool emitCoverage,
skgpu::VertexWriter data) { … }
static skgpu::VertexWriter emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2,
bool emitCoverage, skgpu::VertexWriter data) { … }
void GrTriangulator::VertexList::insert(Vertex* v, Vertex* prev, Vertex* next) { … }
void GrTriangulator::VertexList::remove(Vertex* v) { … }
static inline void round(SkPoint* p) { … }
static inline SkScalar double_to_clamped_scalar(double d) { … }
bool GrTriangulator::Line::intersect(const Line& other, SkPoint* point) const { … }
static bool edge_line_needs_recursion(const SkPoint& p0, const SkPoint& p1) { … }
static bool recursive_edge_intersect(const Line& u, SkPoint u0, SkPoint u1,
const Line& v, SkPoint v0, SkPoint v1,
SkPoint* p, double* s, double* t) { … }
bool GrTriangulator::Edge::intersect(const Edge& other, SkPoint* p, uint8_t* alpha) const { … }
void GrTriangulator::EdgeList::insert(Edge* edge, Edge* prev, Edge* next) { … }
bool GrTriangulator::EdgeList::remove(Edge* edge) { … }
void GrTriangulator::MonotonePoly::addEdge(Edge* edge) { … }
skgpu::VertexWriter GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly,
skgpu::VertexWriter data) const { … }
skgpu::VertexWriter GrTriangulator::emitTriangle(
Vertex* prev, Vertex* curr, Vertex* next, int winding, skgpu::VertexWriter data) const { … }
GrTriangulator::Poly::Poly(Vertex* v, int winding)
: … { … }
Poly* GrTriangulator::Poly::addEdge(Edge* e, Side side, GrTriangulator* tri) { … }
skgpu::VertexWriter GrTriangulator::emitPoly(const Poly* poly, skgpu::VertexWriter data) const { … }
static bool coincident(const SkPoint& a, const SkPoint& b) { … }
Poly* GrTriangulator::makePoly(Poly** head, Vertex* v, int winding) const { … }
void GrTriangulator::appendPointToContour(const SkPoint& p, VertexList* contour) const { … }
static SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u) { … }
void GrTriangulator::appendQuadraticToContour(const SkPoint pts[3], SkScalar toleranceSqd,
VertexList* contour) const { … }
void GrTriangulator::generateCubicPoints(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
const SkPoint& p3, SkScalar tolSqd, VertexList* contour,
int pointsLeft) const { … }
void GrTriangulator::pathToContours(float tolerance, const SkRect& clipBounds,
VertexList* contours, bool* isLinear) const { … }
static inline bool apply_fill_type(SkPathFillType fillType, int winding) { … }
bool GrTriangulator::applyFillType(int winding) const { … }
static inline bool apply_fill_type(SkPathFillType fillType, Poly* poly) { … }
MonotonePoly* GrTriangulator::allocateMonotonePoly(Edge* edge, Side side, int winding) { … }
Edge* GrTriangulator::allocateEdge(Vertex* top, Vertex* bottom, int winding, EdgeType type) { … }
Edge* GrTriangulator::makeEdge(Vertex* prev, Vertex* next, EdgeType type,
const Comparator& c) { … }
bool EdgeList::insert(Edge* edge, Edge* prev) { … }
void GrTriangulator::FindEnclosingEdges(const Vertex& v,
const EdgeList& edges,
Edge** left, Edge**right) { … }
void GrTriangulator::Edge::insertAbove(Vertex* v, const Comparator& c) { … }
void GrTriangulator::Edge::insertBelow(Vertex* v, const Comparator& c) { … }
static void remove_edge_above(Edge* edge) { … }
static void remove_edge_below(Edge* edge) { … }
void GrTriangulator::Edge::disconnect() { … }
static bool rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, const Comparator& c) { … }
static bool rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current,
const Comparator& c) { … }
bool GrTriangulator::setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
const Comparator& c) const { … }
bool GrTriangulator::setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
const Comparator& c) const { … }
bool GrTriangulator::mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges,
Vertex** current, const Comparator& c) const { … }
bool GrTriangulator::mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges,
Vertex** current, const Comparator& c) const { … }
static bool top_collinear(Edge* left, Edge* right) { … }
static bool bottom_collinear(Edge* left, Edge* right) { … }
bool GrTriangulator::mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
const Comparator& c) const { … }
GrTriangulator::BoolFail GrTriangulator::splitEdge(
Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator& c) { … }
GrTriangulator::BoolFail GrTriangulator::intersectEdgePair(
Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, const Comparator& c) { … }
Edge* GrTriangulator::makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType type,
const Comparator& c, int windingScale) { … }
void GrTriangulator::mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh,
const Comparator& c) const { … }
Vertex* GrTriangulator::makeSortedVertex(const SkPoint& p, uint8_t alpha, VertexList* mesh,
Vertex* reference, const Comparator& c) const { … }
static SkPoint clamp(SkPoint p, SkPoint min, SkPoint max, const Comparator& c) { … }
void GrTriangulator::computeBisector(Edge* edge1, Edge* edge2, Vertex* v) const { … }
GrTriangulator::BoolFail GrTriangulator::checkForIntersection(
Edge* left, Edge* right, EdgeList* activeEdges,
Vertex** current, VertexList* mesh,
const Comparator& c) { … }
void GrTriangulator::sanitizeContours(VertexList* contours, int contourCnt) const { … }
bool GrTriangulator::mergeCoincidentVertices(VertexList* mesh, const Comparator& c) const { … }
void GrTriangulator::buildEdges(VertexList* contours, int contourCnt, VertexList* mesh,
const Comparator& c) { … }
template <CompareFunc sweep_lt>
static void sorted_merge(VertexList* front, VertexList* back, VertexList* result) { … }
void GrTriangulator::SortedMerge(VertexList* front, VertexList* back, VertexList* result,
const Comparator& c) { … }
template <CompareFunc sweep_lt>
static void merge_sort(VertexList* 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.fX, v->fPoint.fY, v->fAlpha);
if (Vertex* p = v->fPartner) {
TESS_LOG(", partner %g (%g, %g) alpha %d\n",
p->fID, p->fPoint.fX, p->fPoint.fY, 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) { … }
static void validate_edge_list(EdgeList* edges, const Comparator& c) { … }
#endif
GrTriangulator::SimplifyResult GrTriangulator::simplify(VertexList* mesh,
const Comparator& c) { … }
std::tuple<Poly*, bool> GrTriangulator::tessellate(const VertexList& vertices, const Comparator&) { … }
void GrTriangulator::contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh,
const Comparator& c) { … }
void GrTriangulator::SortMesh(VertexList* vertices, const Comparator& c) { … }
std::tuple<Poly*, bool> GrTriangulator::contoursToPolys(VertexList* contours, int contourCnt) { … }
skgpu::VertexWriter GrTriangulator::polysToTriangles(Poly* polys,
SkPathFillType overrideFillType,
skgpu::VertexWriter data) const { … }
static int get_contour_count(const SkPath& path, SkScalar tolerance) { … }
std::tuple<Poly*, bool> GrTriangulator::pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear) { … }
int64_t GrTriangulator::CountPoints(Poly* polys, SkPathFillType overrideFillType) { … }
int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) const { … }
#endif