godot/thirdparty/manifold/src/sort.cpp

// Copyright 2021 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.

#include <atomic>
#include <set>

#include "./impl.h"
#include "./parallel.h"

namespace {
usingnamespacemanifold;

constexpr uint32_t kNoCode = …;

uint32_t MortonCode(vec3 position, Box bBox) { … }

struct Reindex { … };

struct MarkProp { … };

struct ReindexProps { … };

struct ReindexFace { … };

template <typename Precision, typename I>
bool MergeMeshGLP(MeshGLP<Precision, I>& mesh) { … }
}  // namespace

namespace manifold {

/**
 * Once halfedge_ has been filled in, this function can be called to create the
 * rest of the internal data structures. This function also removes the verts
 * and halfedges flagged for removal (NaN verts and -1 halfedges).
 */
void Manifold::Impl::Finish() { … }

/**
 * Sorts the vertices according to their Morton code.
 */
void Manifold::Impl::SortVerts() { … }

/**
 * Updates the halfedges to point to new vert indices based on a mapping,
 * vertNew2Old. This may be a subset, so the total number of original verts is
 * also given.
 */
void Manifold::Impl::ReindexVerts(const Vec<int>& vertNew2Old,
                                  size_t oldNumVert) { … }

/**
 * Removes unreferenced property verts and reindexes triProperties.
 */
void Manifold::Impl::CompactProps() { … }

/**
 * Fills the faceBox and faceMorton input with the bounding boxes and Morton
 * codes of the faces, respectively. The Morton code is based on the center of
 * the bounding box.
 */
void Manifold::Impl::GetFaceBoxMorton(Vec<Box>& faceBox,
                                      Vec<uint32_t>& faceMorton) const { … }

/**
 * Sorts the faces of this manifold according to their input Morton code. The
 * bounding box and Morton code arrays are also sorted accordingly.
 */
void Manifold::Impl::SortFaces(Vec<Box>& faceBox, Vec<uint32_t>& faceMorton) { … }

/**
 * Creates the halfedge_ vector for this manifold by copying a set of faces from
 * another manifold, given by oldHalfedge. Input faceNew2Old defines the old
 * faces to gather into this.
 */
void Manifold::Impl::GatherFaces(const Vec<int>& faceNew2Old) { … }

void Manifold::Impl::GatherFaces(const Impl& old, const Vec<int>& faceNew2Old) { … }

/**
 * Updates the mergeFromVert and mergeToVert vectors in order to create a
 * manifold solid. If the MeshGL is already manifold, no change will occur and
 * the function will return false. Otherwise, this will merge verts along open
 * edges within tolerance (the maximum of the MeshGL tolerance and the
 * baseline bounding-box tolerance), keeping any from the existing merge
 * vectors, and return true.
 *
 * There is no guarantee the result will be manifold - this is a best-effort
 * helper function designed primarily to aid in the case where a manifold
 * multi-material MeshGL was produced, but its merge vectors were lost due to
 * a round-trip through a file format. Constructing a Manifold from the result
 * will report an error status if it is not manifold.
 */
template <>
bool MeshGL::Merge() { … }

template <>
bool MeshGL64::Merge() { … }
}  // namespace manifold