godot/thirdparty/manifold/src/quickhull.cpp

// Copyright 2024 The Manifold Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Derived from the public domain work of Antti Kuukka at
// https://github.com/akuukka/quickhull

#include "quickhull.h"

#include <algorithm>
#include <limits>

#include "./impl.h"

namespace manifold {

double defaultEps() { … }

inline double getSquaredDistanceBetweenPointAndRay(const vec3& p,
                                                   const Ray& r) { … }

inline double getSquaredDistance(const vec3& p1, const vec3& p2) { … }
// Note that the unit of distance returned is relative to plane's normal's
// length (divide by N.getNormalized() if needed to get the "real" distance).
inline double getSignedDistanceToPlane(const vec3& v, const Plane& p) { … }

inline vec3 getTriangleNormal(const vec3& a, const vec3& b, const vec3& c) { … }

size_t MeshBuilder::addFace() { … }

size_t MeshBuilder::addHalfedge() { … }

void MeshBuilder::setup(int a, int b, int c, int d) { … }

std::array<int, 3> MeshBuilder::getVertexIndicesOfFace(const Face& f) const { … }

HalfEdgeMesh::HalfEdgeMesh(const MeshBuilder& builderObject,
                           const VecView<vec3>& vertexData) { … }

/*
 * Implementation of the algorithm
 */
std::pair<Vec<Halfedge>, Vec<vec3>> QuickHull::buildMesh(double epsilon) { … }

void QuickHull::createConvexHalfedgeMesh() { … }

/*
 * Private helper functions
 */

std::array<size_t, 6> QuickHull::getExtremeValues() { … }

bool QuickHull::reorderHorizonEdges(VecView<size_t>& horizonEdges) { … }

double QuickHull::getScale(const std::array<size_t, 6>& extremeValuesInput) { … }

void QuickHull::setupInitialTetrahedron() { … }

std::unique_ptr<Vec<size_t>> QuickHull::getIndexVectorFromPool() { … }

void QuickHull::reclaimToIndexVectorPool(std::unique_ptr<Vec<size_t>>& ptr) { … }

bool QuickHull::addPointToFace(typename MeshBuilder::Face& f,
                               size_t pointIndex) { … }

// Wrapper to call the QuickHull algorithm with the given vertex data to build
// the Impl
void Manifold::Impl::Hull(VecView<vec3> vertPos) { … }

}  // namespace manifold