chromium/third_party/skia/src/gpu/ganesh/geometry/GrTriangulator.cpp

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

#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) {}

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

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 {}

// 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 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 {}

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

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 {}

// 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 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 {}

// 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) {}

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) {}

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

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

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

GrTriangulator::SimplifyResult GrTriangulator::simplify(VertexList* mesh,
                                                        const Comparator& c) {}

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

std::tuple<Poly*, bool> GrTriangulator::tessellate(const VertexList& vertices, const Comparator&) {}

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

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) {}

// Stage 6: Triangulate the monotone polygons into a vertex buffer.
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) {}

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

int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) const {}

#endif // SK_ENABLE_OPTIMIZE_SIZE