diff options
Diffstat (limited to 'libs/assimp/contrib/draco/src/draco/mesh/mesh_stripifier.h')
| -rw-r--r-- | libs/assimp/contrib/draco/src/draco/mesh/mesh_stripifier.h | 260 |
1 files changed, 0 insertions, 260 deletions
diff --git a/libs/assimp/contrib/draco/src/draco/mesh/mesh_stripifier.h b/libs/assimp/contrib/draco/src/draco/mesh/mesh_stripifier.h deleted file mode 100644 index 262e3c7..0000000 --- a/libs/assimp/contrib/draco/src/draco/mesh/mesh_stripifier.h +++ /dev/null @@ -1,260 +0,0 @@ -// Copyright 2017 The Draco 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. -// -#ifndef DRACO_MESH_MESH_STRIPIFIER_H_ -#define DRACO_MESH_MESH_STRIPIFIER_H_ - -#include "draco/mesh/mesh_misc_functions.h" - -namespace draco { - -// Class that generates triangle strips from a provided draco::Mesh data -// structure. The strips represent a more memory efficient storage of triangle -// connectivity that can be used directly on the GPU (see -// https://en.wikipedia.org/wiki/Triangle_strip ). In general, a mesh needs to -// be represented by several triangle strips and it has been proven that finding -// the optimal set of triangle strips is an NP-complete problem. The algorithm -// implemented by this class finds this set of triangle strips based on a greedy -// heuristic that always selects the longest available strip that covers the -// next unprocessed face. The longest strip is found by analyzing all strips -// that can cover the given face (three strips corresponding to three -// directions). -class MeshStripifier { - public: - MeshStripifier() - : mesh_(nullptr), - num_strips_(0), - num_encoded_faces_(0), - last_encoded_point_(kInvalidPointIndex) {} - - // Generate triangle strips for a given mesh and output them to the output - // iterator |out_it|. In most cases |out_it| stores the values in a buffer - // that can be used directly on the GPU. Note that the algorithm can generate - // multiple strips to represent the whole mesh. In such cases multiple strips - // are separated using a so called primitive restart index that is specified - // by the |primitive_restart_index| (usually defined as the maximum allowed - // value for the given type). - // https://www.khronos.org/opengl/wiki/Vertex_Rendering#Primitive_Restart - template <typename OutputIteratorT, typename IndexTypeT> - bool GenerateTriangleStripsWithPrimitiveRestart( - const Mesh &mesh, IndexTypeT primitive_restart_index, - OutputIteratorT out_it); - - // The same as above but disjoint triangle strips are separated by degenerate - // triangles instead of the primitive restart index. Degenerate triangles are - // zero area triangles that are automatically discarded by the GPU. Using - // degenerate triangles usually results in a slightly longer output indices - // array compared to the similar triangle strips that use primitive restart - // index. The advantage of this method is that it is supported by all hardware - // and all relevant APIs (including WebGL 1.0). - template <typename OutputIteratorT> - bool GenerateTriangleStripsWithDegenerateTriangles(const Mesh &mesh, - OutputIteratorT out_it); - - // Returns the number of strips generated by the last call of the - // GenerateTriangleStrips() method. - int num_strips() const { return num_strips_; } - - private: - bool Prepare(const Mesh &mesh) { - mesh_ = &mesh; - num_strips_ = 0; - num_encoded_faces_ = 0; - // TODO(ostava): We may be able to avoid computing the corner table if we - // already have it stored somewhere. - corner_table_ = CreateCornerTableFromPositionAttribute(mesh_); - if (corner_table_ == nullptr) { - return false; - } - - // Mark all faces as unvisited. - is_face_visited_.assign(mesh.num_faces(), false); - return true; - } - - // Returns local id of the longest strip that can be created from the given - // face |fi|. - int FindLongestStripFromFace(FaceIndex fi) { - // There are three possible strip directions that can contain the provided - // input face. We try all of them and select the direction that result in - // the longest strip. - const CornerIndex first_ci = corner_table_->FirstCorner(fi); - int longest_strip_id = -1; - int longest_strip_length = 0; - for (int i = 0; i < 3; ++i) { - GenerateStripsFromCorner(i, first_ci + i); - if (strip_faces_[i].size() > longest_strip_length) { - longest_strip_length = static_cast<int>(strip_faces_[i].size()); - longest_strip_id = i; - } - } - return longest_strip_id; - } - - // Generates strip from the data stored in |strip_faces_| and - // |strip_start_start_corners_| and stores it to |out_it|. - template <typename OutputIteratorT> - void StoreStrip(int local_strip_id, OutputIteratorT out_it) { - ++num_strips_; - - const int num_strip_faces = strip_faces_[local_strip_id].size(); - CornerIndex ci = strip_start_corners_[local_strip_id]; - for (int i = 0; i < num_strip_faces; ++i) { - const FaceIndex fi = corner_table_->Face(ci); - is_face_visited_[fi] = true; - ++num_encoded_faces_; - - if (i == 0) { - // Add the start face (three indices). - *out_it++ = CornerToPointIndex(ci).value(); - *out_it++ = CornerToPointIndex(corner_table_->Next(ci)).value(); - last_encoded_point_ = CornerToPointIndex(corner_table_->Previous(ci)); - *out_it++ = last_encoded_point_.value(); - } else { - // Store the point on the newly reached corner. - last_encoded_point_ = CornerToPointIndex(ci); - *out_it++ = last_encoded_point_.value(); - - // Go to the correct source corner to proceed to the next face. - if (i & 1) { - ci = corner_table_->Previous(ci); - } else { - ci = corner_table_->Next(ci); - } - } - ci = corner_table_->Opposite(ci); - } - } - - PointIndex CornerToPointIndex(CornerIndex ci) const { - return mesh_->CornerToPointId(ci); - } - - // Returns the opposite corner in case the opposite triangle does not lie - // across an attribute seam. Otherwise return kInvalidCornerIndex. - CornerIndex GetOppositeCorner(CornerIndex ci) const { - const CornerIndex oci = corner_table_->Opposite(ci); - if (oci < 0) { - return kInvalidCornerIndex; - } - // Ensure the point ids are same on both sides of the shared edge between - // the triangles. - if (CornerToPointIndex(corner_table_->Next(ci)) != - CornerToPointIndex(corner_table_->Previous(oci))) { - return kInvalidCornerIndex; - } - if (CornerToPointIndex(corner_table_->Previous(ci)) != - CornerToPointIndex(corner_table_->Next(oci))) { - return kInvalidCornerIndex; - } - return oci; - } - - void GenerateStripsFromCorner(int local_strip_id, CornerIndex ci); - - const Mesh *mesh_; - std::unique_ptr<CornerTable> corner_table_; - - // Store strip faces for each of three possible directions from a given face. - std::vector<FaceIndex> strip_faces_[3]; - // Start corner for each direction of the strip containing the processed face. - CornerIndex strip_start_corners_[3]; - IndexTypeVector<FaceIndex, bool> is_face_visited_; - // The number of strips generated by this method. - int num_strips_; - // The number of encoded triangles. - int num_encoded_faces_; - // Last encoded point. - PointIndex last_encoded_point_; -}; - -template <typename OutputIteratorT, typename IndexTypeT> -bool MeshStripifier::GenerateTriangleStripsWithPrimitiveRestart( - const Mesh &mesh, IndexTypeT primitive_restart_index, - OutputIteratorT out_it) { - if (!Prepare(mesh)) { - return false; - } - - // Go over all faces and generate strips from the first unvisited one. - for (FaceIndex fi(0); fi < mesh.num_faces(); ++fi) { - if (is_face_visited_[fi]) { - continue; - } - - const int longest_strip_id = FindLongestStripFromFace(fi); - - // Separate triangle strips with the primitive restart index. - if (num_strips_ > 0) { - *out_it++ = primitive_restart_index; - } - - StoreStrip(longest_strip_id, out_it); - } - - return true; -} - -template <typename OutputIteratorT> -bool MeshStripifier::GenerateTriangleStripsWithDegenerateTriangles( - const Mesh &mesh, OutputIteratorT out_it) { - if (!Prepare(mesh)) { - return false; - } - - // Go over all faces and generate strips from the first unvisited one. - for (FaceIndex fi(0); fi < mesh.num_faces(); ++fi) { - if (is_face_visited_[fi]) { - continue; - } - - const int longest_strip_id = FindLongestStripFromFace(fi); - - // Separate triangle strips by degenerate triangles. There will be either - // three or four degenerate triangles inserted based on the number of - // triangles that are already encoded in the output strip (three degenerate - // triangles for even number of existing triangles, four degenerate - // triangles for odd number of triangles). - if (num_strips_ > 0) { - // Duplicate last encoded index (first degenerate face). - *out_it++ = last_encoded_point_.value(); - - // Connect it to the start point of the new triangle strip (second - // degenerate face). - const CornerIndex new_start_corner = - strip_start_corners_[longest_strip_id]; - const PointIndex new_start_point = CornerToPointIndex(new_start_corner); - *out_it++ = new_start_point.value(); - num_encoded_faces_ += 2; - // If we have previously encoded number of faces we need to duplicate the - // point one more time to preserve the correct orientation of the next - // strip. - if (num_encoded_faces_ & 1) { - *out_it++ = new_start_point.value(); - num_encoded_faces_ += 1; - } - // The last degenerate face will be added implicitly in the StoreStrip() - // function below as the first point index is going to be encoded there - // again. - } - - StoreStrip(longest_strip_id, out_it); - } - - return true; -} - -} // namespace draco - -#endif // DRACO_MESH_MESH_STRIPIFIER_H_ |