diff options
Diffstat (limited to 'extern/draco/draco/src/draco/mesh')
8 files changed, 231 insertions, 145 deletions
diff --git a/extern/draco/draco/src/draco/mesh/corner_table.cc b/extern/draco/draco/src/draco/mesh/corner_table.cc index 6066e58bd8b..3f92f651ab6 100644 --- a/extern/draco/draco/src/draco/mesh/corner_table.cc +++ b/extern/draco/draco/src/draco/mesh/corner_table.cc @@ -66,12 +66,13 @@ 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) > + const unsigned int num_faces_unsigned = num_faces; + if (num_faces_unsigned > 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); + corner_to_vertex_map_.assign(num_faces_unsigned * 3, kInvalidVertexIndex); + opposite_corners_.assign(num_faces_unsigned * 3, kInvalidCornerIndex); vertex_corners_.reserve(num_vertices); valence_cache_.ClearValenceCache(); valence_cache_.ClearValenceCacheInaccurate(); diff --git a/extern/draco/draco/src/draco/mesh/mesh.h b/extern/draco/draco/src/draco/mesh/mesh.h index f4506da81c9..b1577c03986 100644 --- a/extern/draco/draco/src/draco/mesh/mesh.h +++ b/extern/draco/draco/src/draco/mesh/mesh.h @@ -119,6 +119,10 @@ class Mesh : public PointCloud { const std::vector<PointIndex> &unique_point_ids) override; #endif + // Exposes |faces_|. Use |faces_| at your own risk. DO NOT store the + // reference: the |faces_| object is destroyed with the mesh. + IndexTypeVector<FaceIndex, Face> &faces() { return faces_; } + private: // Mesh specific per-attribute data. std::vector<AttributeData> attribute_data_; diff --git a/extern/draco/draco/src/draco/mesh/mesh_attribute_corner_table.h b/extern/draco/draco/src/draco/mesh/mesh_attribute_corner_table.h index 7dad25cf1d2..6f02453d2d4 100644 --- a/extern/draco/draco/src/draco/mesh/mesh_attribute_corner_table.h +++ b/extern/draco/draco/src/draco/mesh/mesh_attribute_corner_table.h @@ -130,6 +130,12 @@ class MeshAttributeCornerTable { return false; } + bool IsDegenerated(FaceIndex face) const { + // Introducing seams can't change the degeneracy of the individual faces, + // therefore we can delegate the check to the original |corner_table_|. + return corner_table_->IsDegenerated(face); + } + bool no_interior_seams() const { return no_interior_seams_; } const CornerTable *corner_table() const { return corner_table_; } diff --git a/extern/draco/draco/src/draco/mesh/mesh_cleanup.cc b/extern/draco/draco/src/draco/mesh/mesh_cleanup.cc index 773c1e18fe6..bc44c831c4e 100644 --- a/extern/draco/draco/src/draco/mesh/mesh_cleanup.cc +++ b/extern/draco/draco/src/draco/mesh/mesh_cleanup.cc @@ -14,25 +14,42 @@ // #include "draco/mesh/mesh_cleanup.h" +#include <unordered_set> + +#include "draco/core/hash_utils.h" + namespace draco { -bool MeshCleanup::operator()(Mesh *mesh, const MeshCleanupOptions &options) { - if (!options.remove_degenerated_faces && !options.remove_unused_attributes) { - return true; // Nothing to cleanup. +Status MeshCleanup::Cleanup(Mesh *mesh, const MeshCleanupOptions &options) { + if (!options.remove_degenerated_faces && !options.remove_unused_attributes && + !options.remove_duplicate_faces && !options.make_geometry_manifold) { + return OkStatus(); // Nothing to cleanup. } const PointAttribute *const pos_att = mesh->GetNamedAttribute(GeometryAttribute::POSITION); if (pos_att == nullptr) { - return false; + return Status(Status::DRACO_ERROR, "Missing position attribute."); } - // Array that is going to store whether a corresponding point is used. - std::vector<bool> is_point_used; + + if (options.remove_degenerated_faces) { + RemoveDegeneratedFaces(mesh); + } + + if (options.remove_duplicate_faces) { + RemoveDuplicateFaces(mesh); + } + if (options.remove_unused_attributes) { - is_point_used.resize(mesh->num_points(), false); + RemoveUnusedAttributes(mesh); } + return OkStatus(); +} + +void MeshCleanup::RemoveDegeneratedFaces(Mesh *mesh) { + const PointAttribute *const pos_att = + mesh->GetNamedAttribute(GeometryAttribute::POSITION); FaceIndex::ValueType num_degenerated_faces = 0; - PointIndex::ValueType num_new_points = 0; // Array for storing position indices on a face. std::array<AttributeValueIndex, 3> pos_indices; for (FaceIndex f(0); f < mesh->num_faces(); ++f) { @@ -40,149 +57,195 @@ bool MeshCleanup::operator()(Mesh *mesh, const MeshCleanupOptions &options) { for (int p = 0; p < 3; ++p) { pos_indices[p] = pos_att->mapped_index(face[p]); } - bool is_face_valid = true; - if (options.remove_degenerated_faces) { - if (pos_indices[0] == pos_indices[1] || - pos_indices[0] == pos_indices[2] || - pos_indices[1] == pos_indices[2]) { - ++num_degenerated_faces; - is_face_valid = false; - } else if (num_degenerated_faces > 0) { - // Copy the face to its new location. - mesh->SetFace(f - num_degenerated_faces, face); - } - } - if (options.remove_unused_attributes && is_face_valid) { - for (int p = 0; p < 3; ++p) { - if (!is_point_used[face[p].value()]) { - is_point_used[face[p].value()] = true; - ++num_new_points; - } - } + if (pos_indices[0] == pos_indices[1] || pos_indices[0] == pos_indices[2] || + pos_indices[1] == pos_indices[2]) { + ++num_degenerated_faces; + } else if (num_degenerated_faces > 0) { + // Copy the face to its new location. + mesh->SetFace(f - num_degenerated_faces, face); } } if (num_degenerated_faces > 0) { mesh->SetNumFaces(mesh->num_faces() - num_degenerated_faces); } - if (options.remove_unused_attributes) { - bool points_changed = false; - const PointIndex::ValueType num_original_points = mesh->num_points(); - // Map from old points to the new ones. - IndexTypeVector<PointIndex, PointIndex> point_map(num_original_points); - if (num_new_points < static_cast<int>(mesh->num_points())) { - // Some of the points were removed. We need to remap the old points to the - // new ones. - num_new_points = 0; - for (PointIndex i(0); i < num_original_points; ++i) { - if (is_point_used[i.value()]) { - point_map[i] = num_new_points++; - } else { - point_map[i] = kInvalidPointIndex; - } +} + +void MeshCleanup::RemoveDuplicateFaces(Mesh *mesh) { + const PointAttribute *const pos_att = + mesh->GetNamedAttribute(GeometryAttribute::POSITION); + + typedef std::array<AttributeValueIndex::ValueType, 3> PosTriplet; + PosTriplet pos_indices; + std::unordered_set<PosTriplet, HashArray<PosTriplet>> is_face_used; + + uint32_t num_duplicate_faces = 0; + for (FaceIndex fi(0); fi < mesh->num_faces(); ++fi) { + const auto f = mesh->face(fi); + for (int c = 0; c < 3; ++c) { + pos_indices[c] = pos_att->mapped_index(f[c]).value(); + } + // Shift the position indices until the smallest index is the first one. + while (pos_indices[0] > pos_indices[1] || pos_indices[0] > pos_indices[2]) { + // Shift to the left. + std::swap(pos_indices[0], pos_indices[1]); + std::swap(pos_indices[1], pos_indices[2]); + } + // Check if have encountered the same position triplet on a different face. + if (is_face_used.find(pos_indices) != is_face_used.end()) { + // Duplicate face. Ignore it. + num_duplicate_faces++; + } else { + // Insert new face to the set. + is_face_used.insert(pos_indices); + if (num_duplicate_faces > 0) { + // Copy the face to its new location. + mesh->SetFace(fi - num_duplicate_faces, f); } - // Go over faces and update their points. - for (FaceIndex f(0); f < mesh->num_faces(); ++f) { - Mesh::Face face = mesh->face(f); - for (int p = 0; p < 3; ++p) { - face[p] = point_map[face[p]]; - } - mesh->SetFace(f, face); + } + } + if (num_duplicate_faces > 0) { + mesh->SetNumFaces(mesh->num_faces() - num_duplicate_faces); + } +} + +void MeshCleanup::RemoveUnusedAttributes(Mesh *mesh) { + // Array that is going to store whether a corresponding point is used. + std::vector<bool> is_point_used; + PointIndex::ValueType num_new_points = 0; + is_point_used.resize(mesh->num_points(), false); + for (FaceIndex f(0); f < mesh->num_faces(); ++f) { + const Mesh::Face &face = mesh->face(f); + for (int p = 0; p < 3; ++p) { + if (!is_point_used[face[p].value()]) { + is_point_used[face[p].value()] = true; + ++num_new_points; } - // Set the new number of points. - mesh->set_num_points(num_new_points); - points_changed = true; - } else { - // No points were removed. Initialize identity map between the old and new - // points. - for (PointIndex i(0); i < num_original_points; ++i) { - point_map[i] = i; + } + } + + bool points_changed = false; + const PointIndex::ValueType num_original_points = mesh->num_points(); + // Map from old points to the new ones. + IndexTypeVector<PointIndex, PointIndex> point_map(num_original_points); + if (num_new_points < static_cast<int>(mesh->num_points())) { + // Some of the points were removed. We need to remap the old points to the + // new ones. + num_new_points = 0; + for (PointIndex i(0); i < num_original_points; ++i) { + if (is_point_used[i.value()]) { + point_map[i] = num_new_points++; + } else { + point_map[i] = kInvalidPointIndex; + } + } + // Go over faces and update their points. + for (FaceIndex f(0); f < mesh->num_faces(); ++f) { + Mesh::Face face = mesh->face(f); + for (int p = 0; p < 3; ++p) { + face[p] = point_map[face[p]]; } + mesh->SetFace(f, face); } + // Set the new number of points. + mesh->set_num_points(num_new_points); + points_changed = true; + } else { + // No points were removed. Initialize identity map between the old and new + // points. + for (PointIndex i(0); i < num_original_points; ++i) { + point_map[i] = i; + } + } - // Update index mapping for attributes. - IndexTypeVector<AttributeValueIndex, uint8_t> is_att_index_used; - IndexTypeVector<AttributeValueIndex, AttributeValueIndex> att_index_map; - for (int a = 0; a < mesh->num_attributes(); ++a) { - PointAttribute *const att = mesh->attribute(a); - // First detect which attribute entries are used (included in a point). - is_att_index_used.assign(att->size(), 0); - att_index_map.clear(); - AttributeValueIndex::ValueType num_used_entries = 0; - for (PointIndex i(0); i < num_original_points; ++i) { - if (point_map[i] != kInvalidPointIndex) { - const AttributeValueIndex entry_id = att->mapped_index(i); - if (!is_att_index_used[entry_id]) { - is_att_index_used[entry_id] = 1; - ++num_used_entries; - } + // Update index mapping for attributes. + IndexTypeVector<AttributeValueIndex, uint8_t> is_att_index_used; + IndexTypeVector<AttributeValueIndex, AttributeValueIndex> att_index_map; + for (int a = 0; a < mesh->num_attributes(); ++a) { + PointAttribute *const att = mesh->attribute(a); + // First detect which attribute entries are used (included in a point). + is_att_index_used.assign(att->size(), 0); + att_index_map.clear(); + AttributeValueIndex::ValueType num_used_entries = 0; + for (PointIndex i(0); i < num_original_points; ++i) { + if (point_map[i] != kInvalidPointIndex) { + const AttributeValueIndex entry_id = att->mapped_index(i); + if (!is_att_index_used[entry_id]) { + is_att_index_used[entry_id] = 1; + ++num_used_entries; } } - bool att_indices_changed = false; - // If there are some unused attribute entries, remap the attribute values - // in the attribute buffer. - if (num_used_entries < static_cast<int>(att->size())) { - att_index_map.resize(att->size()); - num_used_entries = 0; - for (AttributeValueIndex i(0); i < static_cast<uint32_t>(att->size()); - ++i) { - if (is_att_index_used[i]) { - att_index_map[i] = num_used_entries; - if (i > num_used_entries) { - const uint8_t *const src_add = att->GetAddress(i); - att->buffer()->Write( - att->GetBytePos(AttributeValueIndex(num_used_entries)), - src_add, att->byte_stride()); - } - ++num_used_entries; + } + bool att_indices_changed = false; + // If there are some unused attribute entries, remap the attribute values + // in the attribute buffer. + if (num_used_entries < static_cast<int>(att->size())) { + att_index_map.resize(att->size()); + num_used_entries = 0; + for (AttributeValueIndex i(0); i < static_cast<uint32_t>(att->size()); + ++i) { + if (is_att_index_used[i]) { + att_index_map[i] = num_used_entries; + if (i > num_used_entries) { + const uint8_t *const src_add = att->GetAddress(i); + att->buffer()->Write( + att->GetBytePos(AttributeValueIndex(num_used_entries)), src_add, + att->byte_stride()); } + ++num_used_entries; } - // Update the number of unique entries in the vertex buffer. - att->Resize(num_used_entries); - att_indices_changed = true; } - // If either the points or attribute indices have changed, we need to - // update the attribute index mapping. - if (points_changed || att_indices_changed) { - if (att->is_mapping_identity()) { - // The mapping was identity. It'll remain identity only if the - // number of point and attribute indices is still the same. - if (num_used_entries != static_cast<int>(mesh->num_points())) { - // We need to create an explicit mapping. - // First we need to initialize the explicit map to the original - // number of points to recreate the original identity map. - att->SetExplicitMapping(num_original_points); - // Set the entries of the explicit map to identity. - for (PointIndex::ValueType i = 0; i < num_original_points; ++i) { - att->SetPointMapEntry(PointIndex(i), AttributeValueIndex(i)); - } + // Update the number of unique entries in the vertex buffer. + att->Resize(num_used_entries); + att_indices_changed = true; + } + // If either the points or attribute indices have changed, we need to + // update the attribute index mapping. + if (points_changed || att_indices_changed) { + if (att->is_mapping_identity()) { + // The mapping was identity. It'll remain identity only if the + // number of point and attribute indices is still the same. + if (num_used_entries != static_cast<int>(mesh->num_points())) { + // We need to create an explicit mapping. + // First we need to initialize the explicit map to the original + // number of points to recreate the original identity map. + att->SetExplicitMapping(num_original_points); + // Set the entries of the explicit map to identity. + for (PointIndex::ValueType i = 0; i < num_original_points; ++i) { + att->SetPointMapEntry(PointIndex(i), AttributeValueIndex(i)); } } - if (!att->is_mapping_identity()) { - // Explicit mapping between points and local attribute indices. - for (PointIndex i(0); i < num_original_points; ++i) { - // The new point id that maps to the currently processed attribute - // entry. - const PointIndex new_point_id = point_map[i]; - if (new_point_id == kInvalidPointIndex) { - continue; - } - // Index of the currently processed attribute entry in the original - // mesh. - const AttributeValueIndex original_entry_index = - att->mapped_index(i); - // New index of the same entry after unused entries were removed. - const AttributeValueIndex new_entry_index = - att_index_map[original_entry_index]; - att->SetPointMapEntry(new_point_id, new_entry_index); + } + if (!att->is_mapping_identity()) { + // Explicit mapping between points and local attribute indices. + for (PointIndex i(0); i < num_original_points; ++i) { + // The new point id that maps to the currently processed attribute + // entry. + const PointIndex new_point_id = point_map[i]; + if (new_point_id == kInvalidPointIndex) { + continue; } - // If the number of points changed, we need to set a new explicit map - // size. - att->SetExplicitMapping(mesh->num_points()); + // Index of the currently processed attribute entry in the original + // mesh. + const AttributeValueIndex original_entry_index = att->mapped_index(i); + // New index of the same entry after unused entries were removed. + const AttributeValueIndex new_entry_index = + att_indices_changed ? att_index_map[original_entry_index] + : original_entry_index; + + // Update the mapping. Note that the new point index is always smaller + // than the processed index |i|, making this operation safe. + att->SetPointMapEntry(new_point_id, new_entry_index); } + // If the number of points changed, we need to set a new explicit map + // size. + att->SetExplicitMapping(mesh->num_points()); } } } - return true; +} + +Status MeshCleanup::MakeGeometryManifold(Mesh *mesh) { + return Status(Status::DRACO_ERROR, "Unsupported function."); } } // namespace draco diff --git a/extern/draco/draco/src/draco/mesh/mesh_cleanup.h b/extern/draco/draco/src/draco/mesh/mesh_cleanup.h index b56129dce58..0acdc2ae5b8 100644 --- a/extern/draco/draco/src/draco/mesh/mesh_cleanup.h +++ b/extern/draco/draco/src/draco/mesh/mesh_cleanup.h @@ -15,27 +15,44 @@ #ifndef DRACO_MESH_MESH_CLEANUP_H_ #define DRACO_MESH_MESH_CLEANUP_H_ +#include "draco/core/status.h" #include "draco/mesh/mesh.h" namespace draco { // Options used by the MeshCleanup class. struct MeshCleanupOptions { - MeshCleanupOptions() - : remove_degenerated_faces(true), remove_unused_attributes(true) {} // If true, the cleanup tool removes any face where two or more vertices // share the same position index. - bool remove_degenerated_faces; + bool remove_degenerated_faces = true; + + // If true, the cleanup tool removes all duplicate faces. A pair of faces is + // duplicate if both faces share the same position indices on all vertices + // (that is, position values have to be duduplicated). Note that all + // non-position properties are currently ignored. + bool remove_duplicate_faces = true; + // If true, the cleanup tool removes any unused attribute value or unused // point id. For example, it can be used to remove isolated vertices. - bool remove_unused_attributes; + bool remove_unused_attributes = true; + + // If true, the cleanup tool splits vertices along non-manifold edges and + // vertices. This ensures that the connectivity defined by position indices + // is manifold. + bool make_geometry_manifold = false; }; // Tool that can be used for removing bad or unused data from draco::Meshes. class MeshCleanup { public: // Performs in-place cleanup of the input mesh according to the input options. - bool operator()(Mesh *mesh, const MeshCleanupOptions &options); + static Status Cleanup(Mesh *mesh, const MeshCleanupOptions &options); + + private: + static void RemoveDegeneratedFaces(Mesh *mesh); + static void RemoveDuplicateFaces(Mesh *mesh); + static void RemoveUnusedAttributes(Mesh *mesh); + static Status MakeGeometryManifold(Mesh *mesh); }; } // namespace draco diff --git a/extern/draco/draco/src/draco/mesh/mesh_misc_functions.h b/extern/draco/draco/src/draco/mesh/mesh_misc_functions.h index b450bc80cd8..0a3bcf49782 100644 --- a/extern/draco/draco/src/draco/mesh/mesh_misc_functions.h +++ b/extern/draco/draco/src/draco/mesh/mesh_misc_functions.h @@ -67,7 +67,6 @@ inline bool IsCornerOppositeToAttributeSeam(CornerIndex ci, // Interpolates an attribute value on a face using given barycentric // coordinates. InterpolatedVectorT should be a VectorD that corresponds to the // values stored in the attribute. -// TODO(ostava): Find a better place for this. template <typename InterpolatedVectorT> InterpolatedVectorT ComputeInterpolatedAttributeValueOnMeshFace( const Mesh &mesh, const PointAttribute &attribute, FaceIndex fi, diff --git a/extern/draco/draco/src/draco/mesh/mesh_stripifier.h b/extern/draco/draco/src/draco/mesh/mesh_stripifier.h index 0c298f48e86..8e8d8d9f21f 100644 --- a/extern/draco/draco/src/draco/mesh/mesh_stripifier.h +++ b/extern/draco/draco/src/draco/mesh/mesh_stripifier.h @@ -12,8 +12,8 @@ // See the License for the specific language governing permissions and // limitations under the License. // -#ifndef DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_ -#define DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_ +#ifndef DRACO_MESH_MESH_STRIPIFIER_H_ +#define DRACO_MESH_MESH_STRIPIFIER_H_ #include "draco/mesh/mesh_misc_functions.h" @@ -71,8 +71,6 @@ class MeshStripifier { 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; @@ -257,4 +255,4 @@ bool MeshStripifier::GenerateTriangleStripsWithDegenerateTriangles( } // namespace draco -#endif // DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_ +#endif // DRACO_MESH_MESH_STRIPIFIER_H_ diff --git a/extern/draco/draco/src/draco/mesh/triangle_soup_mesh_builder.cc b/extern/draco/draco/src/draco/mesh/triangle_soup_mesh_builder.cc index 60b0c50b8d5..cb767f871a9 100644 --- a/extern/draco/draco/src/draco/mesh/triangle_soup_mesh_builder.cc +++ b/extern/draco/draco/src/draco/mesh/triangle_soup_mesh_builder.cc @@ -41,8 +41,6 @@ void TriangleSoupMeshBuilder::SetAttributeValuesForFace( att->SetAttributeValue(AttributeValueIndex(start_index), corner_value_0); att->SetAttributeValue(AttributeValueIndex(start_index + 1), corner_value_1); att->SetAttributeValue(AttributeValueIndex(start_index + 2), corner_value_2); - // TODO(ostava): The below code should be called only for one attribute. - // It will work OK even for multiple attributes, but it's redundant. mesh_->SetFace(face_id, {{PointIndex(start_index), PointIndex(start_index + 1), PointIndex(start_index + 2)}}); |