8#ifndef GrTriangulator_DEFINED
9#define GrTriangulator_DEFINED
11#if !defined(SK_ENABLE_OPTIMIZE_SIZE)
29#define TRIANGULATOR_LOGGING 0
30#define TRIANGULATOR_WIREFRAME 0
41 if (!path.isFinite()) {
46 auto [ polys, success ] = triangulator.
pathToPolys(tolerance, clipBounds, isLinear);
76 bool* isLinear)
const;
169 [[nodiscard]]
bool setTop(
178 int windingScale = 1);
244 int count()
const {
return fCount; }
247 if (
a ==
b ||
a == c ||
b == c || winding == 0) {
254 for (
int i = 0; i < winding; ++i) {
257 fTail = &(*fTail)->
fNext;
267 fCount += list.fCount;
268 list.fHead =
nullptr;
269 list.fTail = &list.fHead;
275 Node* fHead =
nullptr;
276 Node** fTail = &fHead;
319#if TRIANGULATOR_LOGGING
352#if TRIANGULATOR_LOGGING
362 :
fA(static_cast<double>(q.fY) - p.fY)
363 ,
fB(static_cast<double>(p.fX) - q.fX)
364 ,
fC(static_cast<double>(p.fY) * q.fX -
365 static_cast<double>(p.fX) * q.fY) {}
370 double len = sqrt(this->
magSq());
374 double scale = 1.0f / len;
380 return fabs(o.
fA -
fA) < 0.00001 && fabs(o.
fB -
fB) < 0.00001;
426 ,
fLine(top, bottom) {
516#if TRIANGULATOR_LOGGING
#define TRIANGULATOR_LOGGING
static float next(float f)
static float prev(float f)
static int side(double x)
static bool left(const SkPoint &p0, const SkPoint &p1)
static bool right(const SkPoint &p0, const SkPoint &p1)
static void dump(const float m[20], SkYUVColorSpace cs, bool rgb2yuv)
void concat(BreadcrumbTriangleList &&list)
void append(SkArenaAlloc *alloc, SkPoint a, SkPoint b, SkPoint c, int winding)
const Node * head() const
void contoursToMesh(VertexList *contours, int contourCnt, VertexList *mesh, const Comparator &)
GrTriangulator(const SkPath &path, SkArenaAlloc *alloc)
std::tuple< Poly *, bool > pathToPolys(float tolerance, const SkRect &clipBounds, bool *isLinear)
skgpu::VertexWriter emitMonotonePoly(const MonotonePoly *, skgpu::VertexWriter data) const
static int64_t CountPoints(Poly *polys, SkPathFillType overrideFillType)
static void SortMesh(VertexList *vertices, const Comparator &)
bool mergeCollinearEdges(Edge *edge, EdgeList *activeEdges, Vertex **current, const Comparator &) const
Edge * allocateEdge(Vertex *top, Vertex *bottom, int winding, EdgeType type)
bool setTop(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &) const
bool fPreserveCollinearVertices
Edge * makeEdge(Vertex *prev, Vertex *next, EdgeType type, const Comparator &)
SkArenaAlloc *const fAlloc
void buildEdges(VertexList *contours, int contourCnt, VertexList *mesh, const Comparator &)
bool fCollectBreadcrumbTriangles
BreadcrumbTriangleList fBreadcrumbList
bool applyFillType(int winding) const
MonotonePoly * allocateMonotonePoly(Edge *edge, Side side, int winding)
SimplifyResult simplify(VertexList *mesh, const Comparator &)
virtual std::tuple< Poly *, bool > tessellate(const VertexList &vertices, const Comparator &)
Poly * makePoly(Poly **head, Vertex *v, int winding) const
static int PathToTriangles(const SkPath &path, SkScalar tolerance, const SkRect &clipBounds, GrEagerVertexAllocator *vertexAllocator, bool *isLinear)
skgpu::VertexWriter polysToTriangles(Poly *polys, SkPathFillType overrideFillType, skgpu::VertexWriter data) const
static void SortedMerge(VertexList *front, VertexList *back, VertexList *result, const Comparator &)
bool setBottom(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &) const
bool fRoundVerticesToQuarterPixel
void pathToContours(float tolerance, const SkRect &clipBounds, VertexList *contours, bool *isLinear) const
Edge * makeConnectingEdge(Vertex *prev, Vertex *next, EdgeType, const Comparator &, int windingScale=1)
void mergeVertices(Vertex *src, Vertex *dst, VertexList *mesh, const Comparator &) const
Vertex * makeSortedVertex(const SkPoint &, uint8_t alpha, VertexList *mesh, Vertex *reference, const Comparator &) const
skgpu::VertexWriter emitPoly(const Poly *, skgpu::VertexWriter data) const
bool mergeEdgesAbove(Edge *edge, Edge *other, EdgeList *activeEdges, Vertex **current, const Comparator &) const
void generateCubicPoints(const SkPoint &, const SkPoint &, const SkPoint &, const SkPoint &, SkScalar tolSqd, VertexList *contour, int pointsLeft) const
virtual ~GrTriangulator()
static void FindEnclosingEdges(const Vertex &v, const EdgeList &edges, Edge **left, Edge **right)
std::tuple< Poly *, bool > contoursToPolys(VertexList *contours, int contourCnt)
skgpu::VertexWriter emitTriangle(Vertex *prev, Vertex *curr, Vertex *next, int winding, skgpu::VertexWriter data) const
bool mergeCoincidentVertices(VertexList *mesh, const Comparator &) const
bool mergeEdgesBelow(Edge *edge, Edge *other, EdgeList *activeEdges, Vertex **current, const Comparator &) const
void sanitizeContours(VertexList *contours, int contourCnt) const
void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList *contour) const
BoolFail intersectEdgePair(Edge *left, Edge *right, EdgeList *activeEdges, Vertex **current, const Comparator &)
BoolFail checkForIntersection(Edge *left, Edge *right, EdgeList *activeEdges, Vertex **current, VertexList *mesh, const Comparator &)
void appendPointToContour(const SkPoint &p, VertexList *contour) const
BoolFail splitEdge(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &)
void computeBisector(Edge *edge1, Edge *edge2, Vertex *) const
static constexpr int kArenaDefaultChunkSize
auto make(Ctor &&ctor) -> decltype(ctor(nullptr))
Node(SkPoint a, SkPoint b, SkPoint c)
bool sweep_lt(const SkPoint &a, const SkPoint &b) const
Comparator(Direction direction)
void insert(Edge *edge, Edge *prev, Edge *next)
bool contains(Edge *edge) const
void insertBelow(Vertex *, const Comparator &)
bool isLeftOf(const Vertex &v) const
void insertAbove(Vertex *, const Comparator &)
bool isRightOf(const Vertex &v) const
Edge(Vertex *top, Vertex *bottom, int winding, EdgeType type)
double dist(const SkPoint &p) const
bool intersect(const Edge &other, SkPoint *p, uint8_t *alpha=nullptr) const
bool nearParallel(const Line &o) const
double dist(const SkPoint &p) const
bool intersect(const Line &other, SkPoint *point) const
Line(Vertex *p, Vertex *q)
Line operator*(double v) const
Line(const SkPoint &p, const SkPoint &q)
Line(double a, double b, double c)
MonotonePoly(Edge *edge, Side side, int winding)
Vertex * lastVertex() const
Poly * addEdge(Edge *e, Side side, GrTriangulator *)
VertexList(Vertex *head, Vertex *tail)
void insert(Vertex *v, Vertex *prev, Vertex *next)
void append(const VertexList &list)
Edge * fLeftEnclosingEdge
Edge * fRightEnclosingEdge
Vertex(const SkPoint &point, uint8_t alpha)