diff options
Diffstat (limited to 'extern/draco/dracoenc/src/draco/mesh/corner_table.cc')
| -rw-r--r-- | extern/draco/dracoenc/src/draco/mesh/corner_table.cc | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/extern/draco/dracoenc/src/draco/mesh/corner_table.cc b/extern/draco/dracoenc/src/draco/mesh/corner_table.cc new file mode 100644 index 00000000000..e4608fe8f9d --- /dev/null +++ b/extern/draco/dracoenc/src/draco/mesh/corner_table.cc @@ -0,0 +1,312 @@ +// 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. +// +#include "draco/mesh/corner_table.h" + +#include <limits> + +#include "draco/mesh/corner_table_iterators.h" + +namespace draco { + +CornerTable::CornerTable() + : num_original_vertices_(0), + num_degenerated_faces_(0), + num_isolated_vertices_(0), + valence_cache_(*this) {} + +std::unique_ptr<CornerTable> CornerTable::Create( + const IndexTypeVector<FaceIndex, FaceType> &faces) { + std::unique_ptr<CornerTable> ct(new CornerTable()); + if (!ct->Init(faces)) + return nullptr; + return ct; +} + +bool CornerTable::Init(const IndexTypeVector<FaceIndex, FaceType> &faces) { + valence_cache_.ClearValenceCache(); + valence_cache_.ClearValenceCacheInaccurate(); + corner_to_vertex_map_.resize(faces.size() * 3); + for (FaceIndex fi(0); fi < static_cast<uint32_t>(faces.size()); ++fi) { + for (int i = 0; i < 3; ++i) { + corner_to_vertex_map_[FirstCorner(fi) + i] = faces[fi][i]; + } + } + int num_vertices = -1; + if (!ComputeOppositeCorners(&num_vertices)) + return false; + if (!ComputeVertexCorners(num_vertices)) + return false; + return true; +} + +bool CornerTable::Reset(int num_faces) { + return Reset(num_faces, num_faces * 3); +} + +bool CornerTable::Reset(int num_faces, int num_vertices) { + if (num_faces < 0 || num_vertices < 0) + return false; + if (static_cast<unsigned int>(num_faces) > + std::numeric_limits<CornerIndex::ValueType>::max() / 3) + return false; + corner_to_vertex_map_.assign(num_faces * 3, kInvalidVertexIndex); + opposite_corners_.assign(num_faces * 3, kInvalidCornerIndex); + vertex_corners_.reserve(num_vertices); + valence_cache_.ClearValenceCache(); + valence_cache_.ClearValenceCacheInaccurate(); + return true; +} + +bool CornerTable::ComputeOppositeCorners(int *num_vertices) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + if (num_vertices == nullptr) + return false; + opposite_corners_.resize(num_corners(), kInvalidCornerIndex); + + // Out implementation for finding opposite corners is based on keeping track + // of outgoing half-edges for each vertex of the mesh. Half-edges (defined by + // their opposite corners) are processed one by one and whenever a new + // half-edge (corner) is processed, we check whether the sink vertex of + // this half-edge contains its sibling half-edge. If yes, we connect them and + // remove the sibling half-edge from the sink vertex, otherwise we add the new + // half-edge to its source vertex. + + // First compute the number of outgoing half-edges (corners) attached to each + // vertex. + std::vector<int> num_corners_on_vertices; + num_corners_on_vertices.reserve(num_corners()); + for (CornerIndex c(0); c < num_corners(); ++c) { + const VertexIndex v1 = Vertex(c); + if (v1.value() >= static_cast<int>(num_corners_on_vertices.size())) + num_corners_on_vertices.resize(v1.value() + 1, 0); + // For each corner there is always exactly one outgoing half-edge attached + // to its vertex. + num_corners_on_vertices[v1.value()]++; + } + + // Create a storage for half-edges on each vertex. We store all half-edges in + // one array, where each entry is identified by the half-edge's sink vertex id + // and the associated half-edge corner id (corner opposite to the half-edge). + // Each vertex will be assigned storage for up to + // |num_corners_on_vertices[vert_id]| half-edges. Unused half-edges are marked + // with |sink_vert| == kInvalidVertexIndex. + struct VertexEdgePair { + VertexEdgePair() + : sink_vert(kInvalidVertexIndex), edge_corner(kInvalidCornerIndex) {} + VertexIndex sink_vert; + CornerIndex edge_corner; + }; + std::vector<VertexEdgePair> vertex_edges(num_corners(), VertexEdgePair()); + + // For each vertex compute the offset (location where the first half-edge + // entry of a given vertex is going to be stored). This way each vertex is + // guaranteed to have a non-overlapping storage with respect to the other + // vertices. + std::vector<int> vertex_offset(num_corners_on_vertices.size()); + int offset = 0; + for (size_t i = 0; i < num_corners_on_vertices.size(); ++i) { + vertex_offset[i] = offset; + offset += num_corners_on_vertices[i]; + } + + // Now go over the all half-edges (using their opposite corners) and either + // insert them to the |vertex_edge| array or connect them with existing + // half-edges. + for (CornerIndex c(0); c < num_corners(); ++c) { + const VertexIndex tip_v = Vertex(c); + const VertexIndex source_v = Vertex(Next(c)); + const VertexIndex sink_v = Vertex(Previous(c)); + + const FaceIndex face_index = Face(c); + if (c == FirstCorner(face_index)) { + // Check whether the face is degenerated, if so ignore it. + const VertexIndex v0 = Vertex(c); + if (v0 == source_v || v0 == sink_v || source_v == sink_v) { + ++num_degenerated_faces_; + c += 2; // Ignore the next two corners of the same face. + continue; + } + } + + CornerIndex opposite_c(kInvalidCornerIndex); + // The maximum number of half-edges attached to the sink vertex. + const int num_corners_on_vert = num_corners_on_vertices[sink_v.value()]; + // Where to look for the first half-edge on the sink vertex. + offset = vertex_offset[sink_v.value()]; + for (int i = 0; i < num_corners_on_vert; ++i, ++offset) { + const VertexIndex other_v = vertex_edges[offset].sink_vert; + if (other_v == kInvalidVertexIndex) + break; // No matching half-edge found on the sink vertex. + if (other_v == source_v) { + if (tip_v == Vertex(vertex_edges[offset].edge_corner)) + continue; // Don't connect mirrored faces. + // A matching half-edge was found on the sink vertex. Mark the + // half-edge's opposite corner. + opposite_c = vertex_edges[offset].edge_corner; + // Remove the half-edge from the sink vertex. We remap all subsequent + // half-edges one slot down. + // TODO(ostava): This can be optimized a little bit, by remapping only + // the half-edge on the last valid slot into the deleted half-edge's + // slot. + for (int j = i + 1; j < num_corners_on_vert; ++j, ++offset) { + vertex_edges[offset] = vertex_edges[offset + 1]; + if (vertex_edges[offset].sink_vert == kInvalidVertexIndex) + break; // Unused half-edge reached. + } + // Mark the last entry as unused. + vertex_edges[offset].sink_vert = kInvalidVertexIndex; + break; + } + } + if (opposite_c == kInvalidCornerIndex) { + // No opposite corner found. Insert the new edge + const int num_corners_on_source_vert = + num_corners_on_vertices[source_v.value()]; + offset = vertex_offset[source_v.value()]; + for (int i = 0; i < num_corners_on_source_vert; ++i, ++offset) { + // Find the first unused half-edge slot on the source vertex. + if (vertex_edges[offset].sink_vert == kInvalidVertexIndex) { + vertex_edges[offset].sink_vert = sink_v; + vertex_edges[offset].edge_corner = c; + break; + } + } + } else { + // Opposite corner found. + opposite_corners_[c] = opposite_c; + opposite_corners_[opposite_c] = c; + } + } + *num_vertices = static_cast<int>(num_corners_on_vertices.size()); + return true; +} + +bool CornerTable::ComputeVertexCorners(int num_vertices) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + num_original_vertices_ = num_vertices; + vertex_corners_.resize(num_vertices, kInvalidCornerIndex); + // Arrays for marking visited vertices and corners that allow us to detect + // non-manifold vertices. + std::vector<bool> visited_vertices(num_vertices, false); + std::vector<bool> visited_corners(num_corners(), false); + + for (FaceIndex f(0); f < num_faces(); ++f) { + const CornerIndex first_face_corner = FirstCorner(f); + // Check whether the face is degenerated. If so ignore it. + if (IsDegenerated(f)) + continue; + + for (int k = 0; k < 3; ++k) { + const CornerIndex c = first_face_corner + k; + if (visited_corners[c.value()]) + continue; + VertexIndex v = corner_to_vertex_map_[c]; + // Note that one vertex maps to many corners, but we just keep track + // of the vertex which has a boundary on the left if the vertex lies on + // the boundary. This means that all the related corners can be accessed + // by iterating over the SwingRight() operator. + // In case of a vertex inside the mesh, the choice is arbitrary. + bool is_non_manifold_vertex = false; + if (visited_vertices[v.value()]) { + // A visited vertex of an unvisited corner found. Must be a non-manifold + // vertex. + // Create a new vertex for it. + vertex_corners_.push_back(kInvalidCornerIndex); + non_manifold_vertex_parents_.push_back(v); + visited_vertices.push_back(false); + v = VertexIndex(num_vertices++); + is_non_manifold_vertex = true; + } + // Mark the vertex as visited. + visited_vertices[v.value()] = true; + + // First swing all the way to the left and mark all corners on the way. + CornerIndex act_c(c); + while (act_c != kInvalidCornerIndex) { + visited_corners[act_c.value()] = true; + // Vertex will eventually point to the left most corner. + vertex_corners_[v] = act_c; + if (is_non_manifold_vertex) { + // Update vertex index in the corresponding face. + corner_to_vertex_map_[act_c] = v; + } + act_c = SwingLeft(act_c); + if (act_c == c) + break; // Full circle reached. + } + if (act_c == kInvalidCornerIndex) { + // If we have reached an open boundary we need to swing right from the + // initial corner to mark all corners in the opposite direction. + act_c = SwingRight(c); + while (act_c != kInvalidCornerIndex) { + visited_corners[act_c.value()] = true; + if (is_non_manifold_vertex) { + // Update vertex index in the corresponding face. + corner_to_vertex_map_[act_c] = v; + } + act_c = SwingRight(act_c); + } + } + } + } + + // Count the number of isolated (unprocessed) vertices. + num_isolated_vertices_ = 0; + for (bool visited : visited_vertices) { + if (!visited) + ++num_isolated_vertices_; + } + return true; +} + +bool CornerTable::IsDegenerated(FaceIndex face) const { + if (face == kInvalidFaceIndex) + return true; + const CornerIndex first_face_corner = FirstCorner(face); + const VertexIndex v0 = Vertex(first_face_corner); + const VertexIndex v1 = Vertex(Next(first_face_corner)); + const VertexIndex v2 = Vertex(Previous(first_face_corner)); + if (v0 == v1 || v0 == v2 || v1 == v2) + return true; + return false; +} + +int CornerTable::Valence(VertexIndex v) const { + if (v == kInvalidVertexIndex) + return -1; + return ConfidentValence(v); +} + +int CornerTable::ConfidentValence(VertexIndex v) const { + DRACO_DCHECK_GE(v.value(), 0); + DRACO_DCHECK_LT(v.value(), num_vertices()); + VertexRingIterator<CornerTable> vi(this, v); + int valence = 0; + for (; !vi.End(); vi.Next()) { + ++valence; + } + return valence; +} + +void CornerTable::UpdateFaceToVertexMap(const VertexIndex vertex) { + DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); + VertexCornersIterator<CornerTable> it(this, vertex); + for (; !it.End(); ++it) { + const CornerIndex corner = *it; + corner_to_vertex_map_[corner] = vertex; + } +} + +} // namespace draco |