diff options
Diffstat (limited to 'extern/draco/dracoenc/src/draco/mesh/corner_table.h')
| -rw-r--r-- | extern/draco/dracoenc/src/draco/mesh/corner_table.h | 364 |
1 files changed, 364 insertions, 0 deletions
diff --git a/extern/draco/dracoenc/src/draco/mesh/corner_table.h b/extern/draco/dracoenc/src/draco/mesh/corner_table.h new file mode 100644 index 00000000000..b916b995f66 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/mesh/corner_table.h @@ -0,0 +1,364 @@ +// Copyright 2016 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_CORNER_TABLE_H_ +#define DRACO_MESH_CORNER_TABLE_H_ + +#include <array> +#include <memory> + +#include "draco/attributes/geometry_indices.h" +#include "draco/core/draco_index_type_vector.h" +#include "draco/core/macros.h" +#include "draco/mesh/valence_cache.h" + +namespace draco { + +// CornerTable is used to represent connectivity of triangular meshes. +// For every corner of all faces, the corner table stores the index of the +// opposite corner in the neighboring face (if it exists) as illustrated in the +// figure below (see corner |c| and it's opposite corner |o|). +// +// * +// /c\ +// / \ +// /n p\ +// *-------* +// \ / +// \ / +// \o/ +// * +// +// All corners are defined by unique CornerIndex and each triplet of corners +// that define a single face id always ordered consecutively as: +// { 3 * FaceIndex, 3 * FaceIndex + 1, 3 * FaceIndex +2 }. +// This representation of corners allows CornerTable to easily retrieve Next and +// Previous corners on any face (see corners |n| and |p| in the figure above). +// Using the Next, Previous, and Opposite corners then enables traversal of any +// 2-manifold surface. +// If the CornerTable is constructed from a non-manifold surface, the input +// non-manifold edges and vertices are automatically split. +class CornerTable { + public: + // TODO(hemmer): rename to Face. + // Corner table face type. + typedef std::array<VertexIndex, 3> FaceType; + + CornerTable(); + static std::unique_ptr<CornerTable> Create( + const IndexTypeVector<FaceIndex, FaceType> &faces); + + // Initializes the CornerTable from provides set of indexed faces. + // The input faces can represent a non-manifold topology, in which case the + // non-manifold edges and vertices are going to be split. + bool Init(const IndexTypeVector<FaceIndex, FaceType> &faces); + + // Resets the corner table to the given number of invalid faces. + bool Reset(int num_faces); + + // Resets the corner table to the given number of invalid faces and vertices. + bool Reset(int num_faces, int num_vertices); + + inline int num_vertices() const { + return static_cast<int>(vertex_corners_.size()); + } + inline int num_corners() const { + return static_cast<int>(corner_to_vertex_map_.size()); + } + inline int num_faces() const { + return static_cast<int>(corner_to_vertex_map_.size() / 3); + } + + inline CornerIndex Opposite(CornerIndex corner) const { + if (corner == kInvalidCornerIndex) + return corner; + return opposite_corners_[corner]; + } + inline CornerIndex Next(CornerIndex corner) const { + if (corner == kInvalidCornerIndex) + return corner; + return LocalIndex(++corner) ? corner : corner - 3; + } + inline CornerIndex Previous(CornerIndex corner) const { + if (corner == kInvalidCornerIndex) + return corner; + return LocalIndex(corner) ? corner - 1 : corner + 2; + } + inline VertexIndex Vertex(CornerIndex corner) const { + if (corner == kInvalidCornerIndex) + return kInvalidVertexIndex; + return ConfidentVertex(corner); + } + inline VertexIndex ConfidentVertex(CornerIndex corner) const { + DRACO_DCHECK_GE(corner.value(), 0); + DRACO_DCHECK_LT(corner.value(), num_corners()); + return corner_to_vertex_map_[corner]; + } + inline FaceIndex Face(CornerIndex corner) const { + if (corner == kInvalidCornerIndex) + return kInvalidFaceIndex; + return FaceIndex(corner.value() / 3); + } + inline CornerIndex FirstCorner(FaceIndex face) const { + if (face == kInvalidFaceIndex) + return kInvalidCornerIndex; + return CornerIndex(face.value() * 3); + } + inline std::array<CornerIndex, 3> AllCorners(FaceIndex face) const { + const CornerIndex ci = CornerIndex(face.value() * 3); + return {{ci, ci + 1, ci + 2}}; + } + inline int LocalIndex(CornerIndex corner) const { return corner.value() % 3; } + + inline FaceType FaceData(FaceIndex face) const { + const CornerIndex first_corner = FirstCorner(face); + FaceType face_data; + for (int i = 0; i < 3; ++i) { + face_data[i] = corner_to_vertex_map_[first_corner + i]; + } + return face_data; + } + + void SetFaceData(FaceIndex face, FaceType data) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + const CornerIndex first_corner = FirstCorner(face); + for (int i = 0; i < 3; ++i) { + corner_to_vertex_map_[first_corner + i] = data[i]; + } + } + + // Returns the left-most corner of a single vertex 1-ring. If a vertex is not + // on a boundary (in which case it has a full 1-ring), this function returns + // any of the corners mapped to the given vertex. + inline CornerIndex LeftMostCorner(VertexIndex v) const { + return vertex_corners_[v]; + } + + // Returns the parent vertex index of a given corner table vertex. + VertexIndex VertexParent(VertexIndex vertex) const { + if (vertex.value() < static_cast<uint32_t>(num_original_vertices_)) + return vertex; + return non_manifold_vertex_parents_[vertex - num_original_vertices_]; + } + + // Returns true if the corner is valid. + inline bool IsValid(CornerIndex c) const { + return Vertex(c) != kInvalidVertexIndex; + } + + // Returns the valence (or degree) of a vertex. + // Returns -1 if the given vertex index is not valid. + int Valence(VertexIndex v) const; + // Same as above but does not check for validity and does not return -1 + int ConfidentValence(VertexIndex v) const; + // Returns the valence of the vertex at the given corner. + inline int Valence(CornerIndex c) const { + if (c == kInvalidCornerIndex) + return -1; + return ConfidentValence(c); + } + inline int ConfidentValence(CornerIndex c) const { + DRACO_DCHECK_LT(c.value(), num_corners()); + return ConfidentValence(ConfidentVertex(c)); + } + + // Returns true if the specified vertex is on a boundary. + inline bool IsOnBoundary(VertexIndex vert) const { + const CornerIndex corner = LeftMostCorner(vert); + if (SwingLeft(corner) == kInvalidCornerIndex) + return true; + return false; + } + + // *-------* + // / \ / \ + // / \ / \ + // / sl\c/sr \ + // *-------v-------* + // Returns the corner on the adjacent face on the right that maps to + // the same vertex as the given corner (sr in the above diagram). + inline CornerIndex SwingRight(CornerIndex corner) const { + return Previous(Opposite(Previous(corner))); + } + // Returns the corner on the left face that maps to the same vertex as the + // given corner (sl in the above diagram). + inline CornerIndex SwingLeft(CornerIndex corner) const { + return Next(Opposite(Next(corner))); + } + + // Get opposite corners on the left and right faces respectively (see image + // below, where L and R are the left and right corners of a corner X. + // + // *-------*-------* + // \L /X\ R/ + // \ / \ / + // \ / \ / + // *-------* + inline CornerIndex GetLeftCorner(CornerIndex corner_id) const { + if (corner_id == kInvalidCornerIndex) + return kInvalidCornerIndex; + return Opposite(Previous(corner_id)); + } + inline CornerIndex GetRightCorner(CornerIndex corner_id) const { + if (corner_id == kInvalidCornerIndex) + return kInvalidCornerIndex; + return Opposite(Next(corner_id)); + } + + // Returns the number of new vertices that were created as a result of + // splitting of non-manifold vertices of the input geometry. + int NumNewVertices() const { return num_vertices() - num_original_vertices_; } + int NumOriginalVertices() const { return num_original_vertices_; } + + // Returns the number of faces with duplicated vertex indices. + int NumDegeneratedFaces() const { return num_degenerated_faces_; } + + // Returns the number of isolated vertices (vertices that have + // vertex_corners_ mapping set to kInvalidCornerIndex. + int NumIsolatedVertices() const { return num_isolated_vertices_; } + + bool IsDegenerated(FaceIndex face) const; + + // Methods that modify an existing corner table. + // Sets the opposite corner mapping between two corners. Caller must ensure + // that the indices are valid. + inline void SetOppositeCorner(CornerIndex corner_id, + CornerIndex opp_corner_id) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + opposite_corners_[corner_id] = opp_corner_id; + } + + // Sets opposite corners for both input corners. + inline void SetOppositeCorners(CornerIndex corner_0, CornerIndex corner_1) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + if (corner_0 != kInvalidCornerIndex) + SetOppositeCorner(corner_0, corner_1); + if (corner_1 != kInvalidCornerIndex) + SetOppositeCorner(corner_1, corner_0); + } + + // Updates mapping between a corner and a vertex. + inline void MapCornerToVertex(CornerIndex corner_id, VertexIndex vert_id) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + corner_to_vertex_map_[corner_id] = vert_id; + } + + VertexIndex AddNewVertex() { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + // Add a new invalid vertex. + vertex_corners_.push_back(kInvalidCornerIndex); + return VertexIndex(static_cast<uint32_t>(vertex_corners_.size() - 1)); + } + + // Sets a new left most corner for a given vertex. + void SetLeftMostCorner(VertexIndex vert, CornerIndex corner) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + if (vert != kInvalidVertexIndex) + vertex_corners_[vert] = corner; + } + + // Updates the vertex to corner map on a specified vertex. This should be + // called in cases where the mapping may be invalid (e.g. when the corner + // table was constructed manually). + void UpdateVertexToCornerMap(VertexIndex vert) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + const CornerIndex first_c = vertex_corners_[vert]; + if (first_c == kInvalidCornerIndex) + return; // Isolated vertex. + CornerIndex act_c = SwingLeft(first_c); + CornerIndex c = first_c; + while (act_c != kInvalidCornerIndex && act_c != first_c) { + c = act_c; + act_c = SwingLeft(act_c); + } + if (act_c != first_c) { + vertex_corners_[vert] = c; + } + } + + // Sets the new number of vertices. It's a responsibility of the caller to + // ensure that no corner is mapped beyond the range of the new number of + // vertices. + inline void SetNumVertices(int num_vertices) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + vertex_corners_.resize(num_vertices, kInvalidCornerIndex); + } + + // Makes a vertex isolated (not attached to any corner). + void MakeVertexIsolated(VertexIndex vert) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + vertex_corners_[vert] = kInvalidCornerIndex; + } + + // Returns true if a vertex is not attached to any face. + inline bool IsVertexIsolated(VertexIndex v) const { + return LeftMostCorner(v) == kInvalidCornerIndex; + } + + // Makes a given face invalid (all corners are marked as invalid). + void MakeFaceInvalid(FaceIndex face) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + if (face != kInvalidFaceIndex) { + const CornerIndex first_corner = FirstCorner(face); + for (int i = 0; i < 3; ++i) { + corner_to_vertex_map_[first_corner + i] = kInvalidVertexIndex; + } + } + } + + // Updates mapping between faces and a vertex using the corners mapped to + // the provided vertex. + void UpdateFaceToVertexMap(const VertexIndex vertex); + + // Allows access to an internal object for caching valences. The object can + // be instructed to cache or uncache all valences and then its interfaces + // queried directly for valences with differing performance/confidence + // qualities. If the mesh or table is modified the cache should be discarded + // and not relied on as it does not automatically update or invalidate for + // performance reasons. + const draco::ValenceCache<CornerTable> &GetValenceCache() const { + return valence_cache_; + } + + private: + // Computes opposite corners mapping from the data stored in + // |corner_to_vertex_map_|. Any non-manifold edge will be split so the result + // is always a 2-manifold surface. + bool ComputeOppositeCorners(int *num_vertices); + + // Computes the lookup map for going from a vertex to a corner. This method + // can handle non-manifold vertices by splitting them into multiple manifold + // vertices. + bool ComputeVertexCorners(int num_vertices); + + // Each three consecutive corners represent one face. + IndexTypeVector<CornerIndex, VertexIndex> corner_to_vertex_map_; + IndexTypeVector<CornerIndex, CornerIndex> opposite_corners_; + IndexTypeVector<VertexIndex, CornerIndex> vertex_corners_; + + int num_original_vertices_; + int num_degenerated_faces_; + int num_isolated_vertices_; + IndexTypeVector<VertexIndex, VertexIndex> non_manifold_vertex_parents_; + + draco::ValenceCache<CornerTable> valence_cache_; +}; + +// A special case to denote an invalid corner table triangle. +static constexpr CornerTable::FaceType kInvalidFace( + {{kInvalidVertexIndex, kInvalidVertexIndex, kInvalidVertexIndex}}); + +} // namespace draco + +#endif // DRACO_MESH_CORNER_TABLE_H_ |