Changeset View
Changeset View
Standalone View
Standalone View
extern/draco/draco/src/draco/mesh/corner_table.cc
- This file was moved from extern/draco/dracoenc/src/draco/mesh/corner_table.cc.
| Show All 24 Lines | CornerTable::CornerTable() | ||||
| : num_original_vertices_(0), | : num_original_vertices_(0), | ||||
| num_degenerated_faces_(0), | num_degenerated_faces_(0), | ||||
| num_isolated_vertices_(0), | num_isolated_vertices_(0), | ||||
| valence_cache_(*this) {} | valence_cache_(*this) {} | ||||
| std::unique_ptr<CornerTable> CornerTable::Create( | std::unique_ptr<CornerTable> CornerTable::Create( | ||||
| const IndexTypeVector<FaceIndex, FaceType> &faces) { | const IndexTypeVector<FaceIndex, FaceType> &faces) { | ||||
| std::unique_ptr<CornerTable> ct(new CornerTable()); | std::unique_ptr<CornerTable> ct(new CornerTable()); | ||||
| if (!ct->Init(faces)) | if (!ct->Init(faces)) { | ||||
| return nullptr; | return nullptr; | ||||
| } | |||||
| return ct; | return ct; | ||||
| } | } | ||||
| bool CornerTable::Init(const IndexTypeVector<FaceIndex, FaceType> &faces) { | bool CornerTable::Init(const IndexTypeVector<FaceIndex, FaceType> &faces) { | ||||
| valence_cache_.ClearValenceCache(); | valence_cache_.ClearValenceCache(); | ||||
| valence_cache_.ClearValenceCacheInaccurate(); | valence_cache_.ClearValenceCacheInaccurate(); | ||||
| corner_to_vertex_map_.resize(faces.size() * 3); | corner_to_vertex_map_.resize(faces.size() * 3); | ||||
| for (FaceIndex fi(0); fi < static_cast<uint32_t>(faces.size()); ++fi) { | for (FaceIndex fi(0); fi < static_cast<uint32_t>(faces.size()); ++fi) { | ||||
| for (int i = 0; i < 3; ++i) { | for (int i = 0; i < 3; ++i) { | ||||
| corner_to_vertex_map_[FirstCorner(fi) + i] = faces[fi][i]; | corner_to_vertex_map_[FirstCorner(fi) + i] = faces[fi][i]; | ||||
| } | } | ||||
| } | } | ||||
| int num_vertices = -1; | int num_vertices = -1; | ||||
| if (!ComputeOppositeCorners(&num_vertices)) | if (!ComputeOppositeCorners(&num_vertices)) { | ||||
| return false; | return false; | ||||
| if (!BreakNonManifoldEdges()) | } | ||||
| if (!BreakNonManifoldEdges()) { | |||||
| return false; | return false; | ||||
| if (!ComputeVertexCorners(num_vertices)) | } | ||||
| if (!ComputeVertexCorners(num_vertices)) { | |||||
| return false; | return false; | ||||
| } | |||||
| return true; | return true; | ||||
| } | } | ||||
| bool CornerTable::Reset(int num_faces) { | bool CornerTable::Reset(int num_faces) { | ||||
| return Reset(num_faces, num_faces * 3); | return Reset(num_faces, num_faces * 3); | ||||
| } | } | ||||
| bool CornerTable::Reset(int num_faces, int num_vertices) { | bool CornerTable::Reset(int num_faces, int num_vertices) { | ||||
| if (num_faces < 0 || num_vertices < 0) | if (num_faces < 0 || num_vertices < 0) { | ||||
| return false; | return false; | ||||
| } | |||||
| if (static_cast<unsigned int>(num_faces) > | if (static_cast<unsigned int>(num_faces) > | ||||
| std::numeric_limits<CornerIndex::ValueType>::max() / 3) | std::numeric_limits<CornerIndex::ValueType>::max() / 3) { | ||||
| return false; | return false; | ||||
| } | |||||
| corner_to_vertex_map_.assign(num_faces * 3, kInvalidVertexIndex); | corner_to_vertex_map_.assign(num_faces * 3, kInvalidVertexIndex); | ||||
| opposite_corners_.assign(num_faces * 3, kInvalidCornerIndex); | opposite_corners_.assign(num_faces * 3, kInvalidCornerIndex); | ||||
| vertex_corners_.reserve(num_vertices); | vertex_corners_.reserve(num_vertices); | ||||
| valence_cache_.ClearValenceCache(); | valence_cache_.ClearValenceCache(); | ||||
| valence_cache_.ClearValenceCacheInaccurate(); | valence_cache_.ClearValenceCacheInaccurate(); | ||||
| return true; | return true; | ||||
| } | } | ||||
| bool CornerTable::ComputeOppositeCorners(int *num_vertices) { | bool CornerTable::ComputeOppositeCorners(int *num_vertices) { | ||||
| DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); | DRACO_DCHECK(GetValenceCache().IsCacheEmpty()); | ||||
| if (num_vertices == nullptr) | if (num_vertices == nullptr) { | ||||
| return false; | return false; | ||||
| } | |||||
| opposite_corners_.resize(num_corners(), kInvalidCornerIndex); | opposite_corners_.resize(num_corners(), kInvalidCornerIndex); | ||||
| // Out implementation for finding opposite corners is based on keeping track | // 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 | // 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 | // their opposite corners) are processed one by one and whenever a new | ||||
| // half-edge (corner) is processed, we check whether the sink vertex of | // 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 | // 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 | // remove the sibling half-edge from the sink vertex, otherwise we add the new | ||||
| // half-edge to its source vertex. | // half-edge to its source vertex. | ||||
| // First compute the number of outgoing half-edges (corners) attached to each | // First compute the number of outgoing half-edges (corners) attached to each | ||||
| // vertex. | // vertex. | ||||
| std::vector<int> num_corners_on_vertices; | std::vector<int> num_corners_on_vertices; | ||||
| num_corners_on_vertices.reserve(num_corners()); | num_corners_on_vertices.reserve(num_corners()); | ||||
| for (CornerIndex c(0); c < num_corners(); ++c) { | for (CornerIndex c(0); c < num_corners(); ++c) { | ||||
| const VertexIndex v1 = Vertex(c); | const VertexIndex v1 = Vertex(c); | ||||
| if (v1.value() >= static_cast<int>(num_corners_on_vertices.size())) | if (v1.value() >= static_cast<int>(num_corners_on_vertices.size())) { | ||||
| num_corners_on_vertices.resize(v1.value() + 1, 0); | num_corners_on_vertices.resize(v1.value() + 1, 0); | ||||
| } | |||||
| // For each corner there is always exactly one outgoing half-edge attached | // For each corner there is always exactly one outgoing half-edge attached | ||||
| // to its vertex. | // to its vertex. | ||||
| num_corners_on_vertices[v1.value()]++; | num_corners_on_vertices[v1.value()]++; | ||||
| } | } | ||||
| // Create a storage for half-edges on each vertex. We store all half-edges in | // 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 | // 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). | // and the associated half-edge corner id (corner opposite to the half-edge). | ||||
| Show All 40 Lines | for (CornerIndex c(0); c < num_corners(); ++c) { | ||||
| CornerIndex opposite_c(kInvalidCornerIndex); | CornerIndex opposite_c(kInvalidCornerIndex); | ||||
| // The maximum number of half-edges attached to the sink vertex. | // The maximum number of half-edges attached to the sink vertex. | ||||
| const int num_corners_on_vert = num_corners_on_vertices[sink_v.value()]; | 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. | // Where to look for the first half-edge on the sink vertex. | ||||
| offset = vertex_offset[sink_v.value()]; | offset = vertex_offset[sink_v.value()]; | ||||
| for (int i = 0; i < num_corners_on_vert; ++i, ++offset) { | for (int i = 0; i < num_corners_on_vert; ++i, ++offset) { | ||||
| const VertexIndex other_v = vertex_edges[offset].sink_vert; | const VertexIndex other_v = vertex_edges[offset].sink_vert; | ||||
| if (other_v == kInvalidVertexIndex) | if (other_v == kInvalidVertexIndex) { | ||||
| break; // No matching half-edge found on the sink vertex. | break; // No matching half-edge found on the sink vertex. | ||||
| } | |||||
| if (other_v == source_v) { | if (other_v == source_v) { | ||||
| if (tip_v == Vertex(vertex_edges[offset].edge_corner)) | if (tip_v == Vertex(vertex_edges[offset].edge_corner)) { | ||||
| continue; // Don't connect mirrored faces. | continue; // Don't connect mirrored faces. | ||||
| } | |||||
| // A matching half-edge was found on the sink vertex. Mark the | // A matching half-edge was found on the sink vertex. Mark the | ||||
| // half-edge's opposite corner. | // half-edge's opposite corner. | ||||
| opposite_c = vertex_edges[offset].edge_corner; | opposite_c = vertex_edges[offset].edge_corner; | ||||
| // Remove the half-edge from the sink vertex. We remap all subsequent | // Remove the half-edge from the sink vertex. We remap all subsequent | ||||
| // half-edges one slot down. | // half-edges one slot down. | ||||
| // TODO(ostava): This can be optimized a little bit, by remapping only | // 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 | // the half-edge on the last valid slot into the deleted half-edge's | ||||
| // slot. | // slot. | ||||
| for (int j = i + 1; j < num_corners_on_vert; ++j, ++offset) { | for (int j = i + 1; j < num_corners_on_vert; ++j, ++offset) { | ||||
| vertex_edges[offset] = vertex_edges[offset + 1]; | vertex_edges[offset] = vertex_edges[offset + 1]; | ||||
| if (vertex_edges[offset].sink_vert == kInvalidVertexIndex) | if (vertex_edges[offset].sink_vert == kInvalidVertexIndex) { | ||||
| break; // Unused half-edge reached. | break; // Unused half-edge reached. | ||||
| } | } | ||||
| } | |||||
| // Mark the last entry as unused. | // Mark the last entry as unused. | ||||
| vertex_edges[offset].sink_vert = kInvalidVertexIndex; | vertex_edges[offset].sink_vert = kInvalidVertexIndex; | ||||
| break; | break; | ||||
| } | } | ||||
| } | } | ||||
| if (opposite_c == kInvalidCornerIndex) { | if (opposite_c == kInvalidCornerIndex) { | ||||
| // No opposite corner found. Insert the new edge | // No opposite corner found. Insert the new edge | ||||
| const int num_corners_on_source_vert = | const int num_corners_on_source_vert = | ||||
| Show All 33 Lines | bool CornerTable::BreakNonManifoldEdges() { | ||||
| // on disjoint 1-ring surface patches. | // on disjoint 1-ring surface patches. | ||||
| std::vector<bool> visited_corners(num_corners(), false); | std::vector<bool> visited_corners(num_corners(), false); | ||||
| std::vector<std::pair<VertexIndex, CornerIndex>> sink_vertices; | std::vector<std::pair<VertexIndex, CornerIndex>> sink_vertices; | ||||
| bool mesh_connectivity_updated = false; | bool mesh_connectivity_updated = false; | ||||
| do { | do { | ||||
| mesh_connectivity_updated = false; | mesh_connectivity_updated = false; | ||||
| for (CornerIndex c(0); c < num_corners(); ++c) { | for (CornerIndex c(0); c < num_corners(); ++c) { | ||||
| if (visited_corners[c.value()]) | if (visited_corners[c.value()]) { | ||||
| continue; | continue; | ||||
| } | |||||
| sink_vertices.clear(); | sink_vertices.clear(); | ||||
| // First swing all the way to find the left-most corner connected to the | // First swing all the way to find the left-most corner connected to the | ||||
| // corner's vertex. | // corner's vertex. | ||||
| CornerIndex first_c = c; | CornerIndex first_c = c; | ||||
| CornerIndex current_c = c; | CornerIndex current_c = c; | ||||
| CornerIndex next_c; | CornerIndex next_c; | ||||
| while (next_c = SwingLeft(current_c), | while (next_c = SwingLeft(current_c), | ||||
| Show All 32 Lines | for (CornerIndex c(0); c < num_corners(); ++c) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| // Break the connectivity on the non-manifold edge. | // Break the connectivity on the non-manifold edge. | ||||
| // TODO(ostava): It may be possible to reconnect the faces in a way | // TODO(ostava): It may be possible to reconnect the faces in a way | ||||
| // that the final surface would be manifold. | // that the final surface would be manifold. | ||||
| const CornerIndex opp_other_edge_corner = | const CornerIndex opp_other_edge_corner = | ||||
| Opposite(other_edge_corner); | Opposite(other_edge_corner); | ||||
| if (opp_edge_corner != kInvalidCornerIndex) | if (opp_edge_corner != kInvalidCornerIndex) { | ||||
| SetOppositeCorner(opp_edge_corner, kInvalidCornerIndex); | SetOppositeCorner(opp_edge_corner, kInvalidCornerIndex); | ||||
| if (opp_other_edge_corner != kInvalidCornerIndex) | } | ||||
| if (opp_other_edge_corner != kInvalidCornerIndex) { | |||||
| SetOppositeCorner(opp_other_edge_corner, kInvalidCornerIndex); | SetOppositeCorner(opp_other_edge_corner, kInvalidCornerIndex); | ||||
| } | |||||
| SetOppositeCorner(edge_corner, kInvalidCornerIndex); | SetOppositeCorner(edge_corner, kInvalidCornerIndex); | ||||
| SetOppositeCorner(other_edge_corner, kInvalidCornerIndex); | SetOppositeCorner(other_edge_corner, kInvalidCornerIndex); | ||||
| vertex_connectivity_updated = true; | vertex_connectivity_updated = true; | ||||
| break; | break; | ||||
| } | } | ||||
| } | } | ||||
| Show All 25 Lines | bool CornerTable::ComputeVertexCorners(int num_vertices) { | ||||
| // Arrays for marking visited vertices and corners that allow us to detect | // Arrays for marking visited vertices and corners that allow us to detect | ||||
| // non-manifold vertices. | // non-manifold vertices. | ||||
| std::vector<bool> visited_vertices(num_vertices, false); | std::vector<bool> visited_vertices(num_vertices, false); | ||||
| std::vector<bool> visited_corners(num_corners(), false); | std::vector<bool> visited_corners(num_corners(), false); | ||||
| for (FaceIndex f(0); f < num_faces(); ++f) { | for (FaceIndex f(0); f < num_faces(); ++f) { | ||||
| const CornerIndex first_face_corner = FirstCorner(f); | const CornerIndex first_face_corner = FirstCorner(f); | ||||
| // Check whether the face is degenerated. If so ignore it. | // Check whether the face is degenerated. If so ignore it. | ||||
| if (IsDegenerated(f)) | if (IsDegenerated(f)) { | ||||
| continue; | continue; | ||||
| } | |||||
| for (int k = 0; k < 3; ++k) { | for (int k = 0; k < 3; ++k) { | ||||
| const CornerIndex c = first_face_corner + k; | const CornerIndex c = first_face_corner + k; | ||||
| if (visited_corners[c.value()]) | if (visited_corners[c.value()]) { | ||||
| continue; | continue; | ||||
| } | |||||
| VertexIndex v = corner_to_vertex_map_[c]; | VertexIndex v = corner_to_vertex_map_[c]; | ||||
| // Note that one vertex maps to many corners, but we just keep track | // 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 | // 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 | // the boundary. This means that all the related corners can be accessed | ||||
| // by iterating over the SwingRight() operator. | // by iterating over the SwingRight() operator. | ||||
| // In case of a vertex inside the mesh, the choice is arbitrary. | // In case of a vertex inside the mesh, the choice is arbitrary. | ||||
| bool is_non_manifold_vertex = false; | bool is_non_manifold_vertex = false; | ||||
| if (visited_vertices[v.value()]) { | if (visited_vertices[v.value()]) { | ||||
| Show All 15 Lines | for (int k = 0; k < 3; ++k) { | ||||
| visited_corners[act_c.value()] = true; | visited_corners[act_c.value()] = true; | ||||
| // Vertex will eventually point to the left most corner. | // Vertex will eventually point to the left most corner. | ||||
| vertex_corners_[v] = act_c; | vertex_corners_[v] = act_c; | ||||
| if (is_non_manifold_vertex) { | if (is_non_manifold_vertex) { | ||||
| // Update vertex index in the corresponding face. | // Update vertex index in the corresponding face. | ||||
| corner_to_vertex_map_[act_c] = v; | corner_to_vertex_map_[act_c] = v; | ||||
| } | } | ||||
| act_c = SwingLeft(act_c); | act_c = SwingLeft(act_c); | ||||
| if (act_c == c) | if (act_c == c) { | ||||
| break; // Full circle reached. | break; // Full circle reached. | ||||
| } | } | ||||
| } | |||||
| if (act_c == kInvalidCornerIndex) { | if (act_c == kInvalidCornerIndex) { | ||||
| // If we have reached an open boundary we need to swing right from the | // If we have reached an open boundary we need to swing right from the | ||||
| // initial corner to mark all corners in the opposite direction. | // initial corner to mark all corners in the opposite direction. | ||||
| act_c = SwingRight(c); | act_c = SwingRight(c); | ||||
| while (act_c != kInvalidCornerIndex) { | while (act_c != kInvalidCornerIndex) { | ||||
| visited_corners[act_c.value()] = true; | visited_corners[act_c.value()] = true; | ||||
| if (is_non_manifold_vertex) { | if (is_non_manifold_vertex) { | ||||
| // Update vertex index in the corresponding face. | // Update vertex index in the corresponding face. | ||||
| corner_to_vertex_map_[act_c] = v; | corner_to_vertex_map_[act_c] = v; | ||||
| } | } | ||||
| act_c = SwingRight(act_c); | act_c = SwingRight(act_c); | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| // Count the number of isolated (unprocessed) vertices. | // Count the number of isolated (unprocessed) vertices. | ||||
| num_isolated_vertices_ = 0; | num_isolated_vertices_ = 0; | ||||
| for (bool visited : visited_vertices) { | for (bool visited : visited_vertices) { | ||||
| if (!visited) | if (!visited) { | ||||
| ++num_isolated_vertices_; | ++num_isolated_vertices_; | ||||
| } | } | ||||
| } | |||||
| return true; | return true; | ||||
| } | } | ||||
| bool CornerTable::IsDegenerated(FaceIndex face) const { | bool CornerTable::IsDegenerated(FaceIndex face) const { | ||||
| if (face == kInvalidFaceIndex) | if (face == kInvalidFaceIndex) { | ||||
| return true; | return true; | ||||
| } | |||||
| const CornerIndex first_face_corner = FirstCorner(face); | const CornerIndex first_face_corner = FirstCorner(face); | ||||
| const VertexIndex v0 = Vertex(first_face_corner); | const VertexIndex v0 = Vertex(first_face_corner); | ||||
| const VertexIndex v1 = Vertex(Next(first_face_corner)); | const VertexIndex v1 = Vertex(Next(first_face_corner)); | ||||
| const VertexIndex v2 = Vertex(Previous(first_face_corner)); | const VertexIndex v2 = Vertex(Previous(first_face_corner)); | ||||
| if (v0 == v1 || v0 == v2 || v1 == v2) | if (v0 == v1 || v0 == v2 || v1 == v2) { | ||||
| return true; | return true; | ||||
| } | |||||
| return false; | return false; | ||||
| } | } | ||||
| int CornerTable::Valence(VertexIndex v) const { | int CornerTable::Valence(VertexIndex v) const { | ||||
| if (v == kInvalidVertexIndex) | if (v == kInvalidVertexIndex) { | ||||
| return -1; | return -1; | ||||
| } | |||||
| return ConfidentValence(v); | return ConfidentValence(v); | ||||
| } | } | ||||
| int CornerTable::ConfidentValence(VertexIndex v) const { | int CornerTable::ConfidentValence(VertexIndex v) const { | ||||
| DRACO_DCHECK_GE(v.value(), 0); | DRACO_DCHECK_GE(v.value(), 0); | ||||
| DRACO_DCHECK_LT(v.value(), num_vertices()); | DRACO_DCHECK_LT(v.value(), num_vertices()); | ||||
| VertexRingIterator<CornerTable> vi(this, v); | VertexRingIterator<CornerTable> vi(this, v); | ||||
| int valence = 0; | int valence = 0; | ||||
| Show All 16 Lines | |||||