From 3ed3ee253b12fe4d481357386650a13de244caf9 Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Tue, 15 Feb 2022 09:29:22 -0600 Subject: Cleanup: Rename file used for calculating mesh edges This commit renames `mesh_validate.cc` to `mesh_calc_edges.cc`. I would like to move `mesh_validate.c` to C++, but it makes sense to keep this specific algorithm in a smaller file. --- source/blender/blenkernel/CMakeLists.txt | 2 +- .../blender/blenkernel/intern/mesh_calc_edges.cc | 248 ++++++++++++++++++++ source/blender/blenkernel/intern/mesh_validate.cc | 251 --------------------- 3 files changed, 249 insertions(+), 252 deletions(-) create mode 100644 source/blender/blenkernel/intern/mesh_calc_edges.cc delete mode 100644 source/blender/blenkernel/intern/mesh_validate.cc (limited to 'source') diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 2de18382b7f..bf720fa1341 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -183,6 +183,7 @@ set(SRC intern/mball_tessellate.c intern/mesh.cc intern/mesh_boolean_convert.cc + intern/mesh_calc_edges.cc intern/mesh_convert.cc intern/mesh_debug.cc intern/mesh_evaluate.cc @@ -199,7 +200,6 @@ set(SRC intern/mesh_tangent.c intern/mesh_tessellate.c intern/mesh_validate.c - intern/mesh_validate.cc intern/mesh_wrapper.c intern/modifier.c intern/movieclip.c diff --git a/source/blender/blenkernel/intern/mesh_calc_edges.cc b/source/blender/blenkernel/intern/mesh_calc_edges.cc new file mode 100644 index 00000000000..0524412e302 --- /dev/null +++ b/source/blender/blenkernel/intern/mesh_calc_edges.cc @@ -0,0 +1,248 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +/** \file + * \ingroup bke + */ + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" +#include "DNA_object_types.h" +#include "BLI_map.hh" +#include "BLI_task.hh" +#include "BLI_threads.h" +#include "BLI_timeit.hh" + +#include "BKE_customdata.h" +#include "BKE_mesh.h" + +namespace blender::bke::calc_edges { + +/** This is used to uniquely identify edges in a hash map. */ +struct OrderedEdge { + int v_low, v_high; + + OrderedEdge(const int v1, const int v2) + { + if (v1 < v2) { + v_low = v1; + v_high = v2; + } + else { + v_low = v2; + v_high = v1; + } + } + + OrderedEdge(const uint v1, const uint v2) + : OrderedEdge(static_cast(v1), static_cast(v2)) + { + } + + uint64_t hash() const + { + return (this->v_low << 8) ^ this->v_high; + } + + /** Return a hash value that is likely to be different in the low bits from the normal `hash()` + * function. This is necessary to avoid collisions in #BKE_mesh_calc_edges. */ + uint64_t hash2() const + { + return this->v_low; + } + + friend bool operator==(const OrderedEdge &e1, const OrderedEdge &e2) + { + BLI_assert(e1.v_low < e1.v_high); + BLI_assert(e2.v_low < e2.v_high); + return e1.v_low == e2.v_low && e1.v_high == e2.v_high; + } +}; + +/* The map first contains an edge pointer and later an index. */ +union OrigEdgeOrIndex { + const MEdge *original_edge; + int index; +}; +using EdgeMap = Map; + +static void reserve_hash_maps(const Mesh *mesh, + const bool keep_existing_edges, + MutableSpan edge_maps) +{ + const int totedge_guess = std::max(keep_existing_edges ? mesh->totedge : 0, mesh->totpoly * 2); + threading::parallel_for_each( + edge_maps, [&](EdgeMap &edge_map) { edge_map.reserve(totedge_guess / edge_maps.size()); }); +} + +static void add_existing_edges_to_hash_maps(Mesh *mesh, + MutableSpan edge_maps, + uint32_t parallel_mask) +{ + /* Assume existing edges are valid. */ + threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { + const int task_index = &edge_map - &edge_maps[0]; + for (const MEdge &edge : Span(mesh->medge, mesh->totedge)) { + OrderedEdge ordered_edge{edge.v1, edge.v2}; + /* Only add the edge when it belongs into this map. */ + if (task_index == (parallel_mask & ordered_edge.hash2())) { + edge_map.add_new(ordered_edge, {&edge}); + } + } + }); +} + +static void add_polygon_edges_to_hash_maps(Mesh *mesh, + MutableSpan edge_maps, + uint32_t parallel_mask) +{ + const Span loops{mesh->mloop, mesh->totloop}; + threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { + const int task_index = &edge_map - &edge_maps[0]; + for (const MPoly &poly : Span(mesh->mpoly, mesh->totpoly)) { + Span poly_loops = loops.slice(poly.loopstart, poly.totloop); + const MLoop *prev_loop = &poly_loops.last(); + for (const MLoop &next_loop : poly_loops) { + /* Can only be the same when the mesh data is invalid. */ + if (prev_loop->v != next_loop.v) { + OrderedEdge ordered_edge{prev_loop->v, next_loop.v}; + /* Only add the edge when it belongs into this map. */ + if (task_index == (parallel_mask & ordered_edge.hash2())) { + edge_map.lookup_or_add(ordered_edge, {nullptr}); + } + } + prev_loop = &next_loop; + } + } + }); +} + +static void serialize_and_initialize_deduplicated_edges(MutableSpan edge_maps, + MutableSpan new_edges, + short new_edge_flag) +{ + /* All edges are distributed in the hash tables now. They have to be serialized into a single + * array below. To be able to parallelize this, we have to compute edge index offsets for each + * map. */ + Array edge_index_offsets(edge_maps.size()); + edge_index_offsets[0] = 0; + for (const int i : IndexRange(edge_maps.size() - 1)) { + edge_index_offsets[i + 1] = edge_index_offsets[i] + edge_maps[i].size(); + } + + threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { + const int task_index = &edge_map - &edge_maps[0]; + + int new_edge_index = edge_index_offsets[task_index]; + for (EdgeMap::MutableItem item : edge_map.items()) { + MEdge &new_edge = new_edges[new_edge_index]; + const MEdge *orig_edge = item.value.original_edge; + if (orig_edge != nullptr) { + /* Copy values from original edge. */ + new_edge = *orig_edge; + } + else { + /* Initialize new edge. */ + new_edge.v1 = item.key.v_low; + new_edge.v2 = item.key.v_high; + new_edge.flag = new_edge_flag; + } + item.value.index = new_edge_index; + new_edge_index++; + } + }); +} + +static void update_edge_indices_in_poly_loops(Mesh *mesh, + Span edge_maps, + uint32_t parallel_mask) +{ + const MutableSpan loops{mesh->mloop, mesh->totloop}; + threading::parallel_for(IndexRange(mesh->totpoly), 100, [&](IndexRange range) { + for (const int poly_index : range) { + MPoly &poly = mesh->mpoly[poly_index]; + MutableSpan poly_loops = loops.slice(poly.loopstart, poly.totloop); + + MLoop *prev_loop = &poly_loops.last(); + for (MLoop &next_loop : poly_loops) { + int edge_index; + if (prev_loop->v != next_loop.v) { + OrderedEdge ordered_edge{prev_loop->v, next_loop.v}; + /* Double lookup: First find the map that contains the edge, then lookup the edge. */ + const EdgeMap &edge_map = edge_maps[parallel_mask & ordered_edge.hash2()]; + edge_index = edge_map.lookup(ordered_edge).index; + } + else { + /* This is an invalid edge; normally this does not happen in Blender, + * but it can be part of an imported mesh with invalid geometry. See + * T76514. */ + edge_index = 0; + } + prev_loop->e = edge_index; + prev_loop = &next_loop; + } + } + }); +} + +static int get_parallel_maps_count(const Mesh *mesh) +{ + /* Don't use parallelization when the mesh is small. */ + if (mesh->totpoly < 1000) { + return 1; + } + /* Use at most 8 separate hash tables. Using more threads has diminishing returns. These threads + * can better do something more useful instead. */ + const int system_thread_count = BLI_system_thread_count(); + return power_of_2_min_i(std::min(8, system_thread_count)); +} + +static void clear_hash_tables(MutableSpan edge_maps) +{ + threading::parallel_for_each(edge_maps, [](EdgeMap &edge_map) { edge_map.clear(); }); +} + +} // namespace blender::bke::calc_edges + +void BKE_mesh_calc_edges(Mesh *mesh, bool keep_existing_edges, const bool select_new_edges) +{ + using namespace blender; + using namespace blender::bke; + using namespace blender::bke::calc_edges; + + /* Parallelization is achieved by having multiple hash tables for different subsets of edges. + * Each edge is assigned to one of the hash maps based on the lower bits of a hash value. */ + const int parallel_maps = get_parallel_maps_count(mesh); + BLI_assert(is_power_of_2_i(parallel_maps)); + const uint32_t parallel_mask = static_cast(parallel_maps) - 1; + Array edge_maps(parallel_maps); + reserve_hash_maps(mesh, keep_existing_edges, edge_maps); + + /* Add all edges. */ + if (keep_existing_edges) { + calc_edges::add_existing_edges_to_hash_maps(mesh, edge_maps, parallel_mask); + } + calc_edges::add_polygon_edges_to_hash_maps(mesh, edge_maps, parallel_mask); + + /* Compute total number of edges. */ + int new_totedge = 0; + for (EdgeMap &edge_map : edge_maps) { + new_totedge += edge_map.size(); + } + + /* Create new edges. */ + MutableSpan new_edges{ + static_cast(MEM_calloc_arrayN(new_totedge, sizeof(MEdge), __func__)), new_totedge}; + const short new_edge_flag = (ME_EDGEDRAW | ME_EDGERENDER) | (select_new_edges ? SELECT : 0); + calc_edges::serialize_and_initialize_deduplicated_edges(edge_maps, new_edges, new_edge_flag); + calc_edges::update_edge_indices_in_poly_loops(mesh, edge_maps, parallel_mask); + + /* Free old CustomData and assign new one. */ + CustomData_free(&mesh->edata, mesh->totedge); + CustomData_reset(&mesh->edata); + CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, new_edges.data(), new_totedge); + mesh->totedge = new_totedge; + mesh->medge = new_edges.data(); + + /* Explicitly clear edge maps, because that way it can be parallelized. */ + clear_hash_tables(edge_maps); +} diff --git a/source/blender/blenkernel/intern/mesh_validate.cc b/source/blender/blenkernel/intern/mesh_validate.cc deleted file mode 100644 index 5c941c16137..00000000000 --- a/source/blender/blenkernel/intern/mesh_validate.cc +++ /dev/null @@ -1,251 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ - -/** \file - * \ingroup bke - */ - -#include "DNA_mesh_types.h" -#include "DNA_meshdata_types.h" -#include "DNA_object_types.h" - -#include "BLI_edgehash.h" -#include "BLI_map.hh" -#include "BLI_math_base.h" -#include "BLI_task.hh" -#include "BLI_threads.h" -#include "BLI_timeit.hh" - -#include "BKE_customdata.h" -#include "BKE_mesh.h" - -namespace blender::bke::calc_edges { - -/** This is used to uniquely identify edges in a hash map. */ -struct OrderedEdge { - int v_low, v_high; - - OrderedEdge(const int v1, const int v2) - { - if (v1 < v2) { - v_low = v1; - v_high = v2; - } - else { - v_low = v2; - v_high = v1; - } - } - - OrderedEdge(const uint v1, const uint v2) - : OrderedEdge(static_cast(v1), static_cast(v2)) - { - } - - uint64_t hash() const - { - return (this->v_low << 8) ^ this->v_high; - } - - /** Return a hash value that is likely to be different in the low bits from the normal `hash()` - * function. This is necessary to avoid collisions in #BKE_mesh_calc_edges. */ - uint64_t hash2() const - { - return this->v_low; - } - - friend bool operator==(const OrderedEdge &e1, const OrderedEdge &e2) - { - BLI_assert(e1.v_low < e1.v_high); - BLI_assert(e2.v_low < e2.v_high); - return e1.v_low == e2.v_low && e1.v_high == e2.v_high; - } -}; - -/* The map first contains an edge pointer and later an index. */ -union OrigEdgeOrIndex { - const MEdge *original_edge; - int index; -}; -using EdgeMap = Map; - -static void reserve_hash_maps(const Mesh *mesh, - const bool keep_existing_edges, - MutableSpan edge_maps) -{ - const int totedge_guess = std::max(keep_existing_edges ? mesh->totedge : 0, mesh->totpoly * 2); - threading::parallel_for_each( - edge_maps, [&](EdgeMap &edge_map) { edge_map.reserve(totedge_guess / edge_maps.size()); }); -} - -static void add_existing_edges_to_hash_maps(Mesh *mesh, - MutableSpan edge_maps, - uint32_t parallel_mask) -{ - /* Assume existing edges are valid. */ - threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { - const int task_index = &edge_map - &edge_maps[0]; - for (const MEdge &edge : Span(mesh->medge, mesh->totedge)) { - OrderedEdge ordered_edge{edge.v1, edge.v2}; - /* Only add the edge when it belongs into this map. */ - if (task_index == (parallel_mask & ordered_edge.hash2())) { - edge_map.add_new(ordered_edge, {&edge}); - } - } - }); -} - -static void add_polygon_edges_to_hash_maps(Mesh *mesh, - MutableSpan edge_maps, - uint32_t parallel_mask) -{ - const Span loops{mesh->mloop, mesh->totloop}; - threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { - const int task_index = &edge_map - &edge_maps[0]; - for (const MPoly &poly : Span(mesh->mpoly, mesh->totpoly)) { - Span poly_loops = loops.slice(poly.loopstart, poly.totloop); - const MLoop *prev_loop = &poly_loops.last(); - for (const MLoop &next_loop : poly_loops) { - /* Can only be the same when the mesh data is invalid. */ - if (prev_loop->v != next_loop.v) { - OrderedEdge ordered_edge{prev_loop->v, next_loop.v}; - /* Only add the edge when it belongs into this map. */ - if (task_index == (parallel_mask & ordered_edge.hash2())) { - edge_map.lookup_or_add(ordered_edge, {nullptr}); - } - } - prev_loop = &next_loop; - } - } - }); -} - -static void serialize_and_initialize_deduplicated_edges(MutableSpan edge_maps, - MutableSpan new_edges, - short new_edge_flag) -{ - /* All edges are distributed in the hash tables now. They have to be serialized into a single - * array below. To be able to parallelize this, we have to compute edge index offsets for each - * map. */ - Array edge_index_offsets(edge_maps.size()); - edge_index_offsets[0] = 0; - for (const int i : IndexRange(edge_maps.size() - 1)) { - edge_index_offsets[i + 1] = edge_index_offsets[i] + edge_maps[i].size(); - } - - threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) { - const int task_index = &edge_map - &edge_maps[0]; - - int new_edge_index = edge_index_offsets[task_index]; - for (EdgeMap::MutableItem item : edge_map.items()) { - MEdge &new_edge = new_edges[new_edge_index]; - const MEdge *orig_edge = item.value.original_edge; - if (orig_edge != nullptr) { - /* Copy values from original edge. */ - new_edge = *orig_edge; - } - else { - /* Initialize new edge. */ - new_edge.v1 = item.key.v_low; - new_edge.v2 = item.key.v_high; - new_edge.flag = new_edge_flag; - } - item.value.index = new_edge_index; - new_edge_index++; - } - }); -} - -static void update_edge_indices_in_poly_loops(Mesh *mesh, - Span edge_maps, - uint32_t parallel_mask) -{ - const MutableSpan loops{mesh->mloop, mesh->totloop}; - threading::parallel_for(IndexRange(mesh->totpoly), 100, [&](IndexRange range) { - for (const int poly_index : range) { - MPoly &poly = mesh->mpoly[poly_index]; - MutableSpan poly_loops = loops.slice(poly.loopstart, poly.totloop); - - MLoop *prev_loop = &poly_loops.last(); - for (MLoop &next_loop : poly_loops) { - int edge_index; - if (prev_loop->v != next_loop.v) { - OrderedEdge ordered_edge{prev_loop->v, next_loop.v}; - /* Double lookup: First find the map that contains the edge, then lookup the edge. */ - const EdgeMap &edge_map = edge_maps[parallel_mask & ordered_edge.hash2()]; - edge_index = edge_map.lookup(ordered_edge).index; - } - else { - /* This is an invalid edge; normally this does not happen in Blender, - * but it can be part of an imported mesh with invalid geometry. See - * T76514. */ - edge_index = 0; - } - prev_loop->e = edge_index; - prev_loop = &next_loop; - } - } - }); -} - -static int get_parallel_maps_count(const Mesh *mesh) -{ - /* Don't use parallelization when the mesh is small. */ - if (mesh->totpoly < 1000) { - return 1; - } - /* Use at most 8 separate hash tables. Using more threads has diminishing returns. These threads - * can better do something more useful instead. */ - const int system_thread_count = BLI_system_thread_count(); - return power_of_2_min_i(std::min(8, system_thread_count)); -} - -static void clear_hash_tables(MutableSpan edge_maps) -{ - threading::parallel_for_each(edge_maps, [](EdgeMap &edge_map) { edge_map.clear(); }); -} - -} // namespace blender::bke::calc_edges - -void BKE_mesh_calc_edges(Mesh *mesh, bool keep_existing_edges, const bool select_new_edges) -{ - using namespace blender; - using namespace blender::bke; - using namespace blender::bke::calc_edges; - - /* Parallelization is achieved by having multiple hash tables for different subsets of edges. - * Each edge is assigned to one of the hash maps based on the lower bits of a hash value. */ - const int parallel_maps = get_parallel_maps_count(mesh); - BLI_assert(is_power_of_2_i(parallel_maps)); - const uint32_t parallel_mask = static_cast(parallel_maps) - 1; - Array edge_maps(parallel_maps); - reserve_hash_maps(mesh, keep_existing_edges, edge_maps); - - /* Add all edges. */ - if (keep_existing_edges) { - calc_edges::add_existing_edges_to_hash_maps(mesh, edge_maps, parallel_mask); - } - calc_edges::add_polygon_edges_to_hash_maps(mesh, edge_maps, parallel_mask); - - /* Compute total number of edges. */ - int new_totedge = 0; - for (EdgeMap &edge_map : edge_maps) { - new_totedge += edge_map.size(); - } - - /* Create new edges. */ - MutableSpan new_edges{ - static_cast(MEM_calloc_arrayN(new_totedge, sizeof(MEdge), __func__)), new_totedge}; - const short new_edge_flag = (ME_EDGEDRAW | ME_EDGERENDER) | (select_new_edges ? SELECT : 0); - calc_edges::serialize_and_initialize_deduplicated_edges(edge_maps, new_edges, new_edge_flag); - calc_edges::update_edge_indices_in_poly_loops(mesh, edge_maps, parallel_mask); - - /* Free old CustomData and assign new one. */ - CustomData_free(&mesh->edata, mesh->totedge); - CustomData_reset(&mesh->edata); - CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, new_edges.data(), new_totedge); - mesh->totedge = new_totedge; - mesh->medge = new_edges.data(); - - /* Explicitly clear edge maps, because that way it can be parallelized. */ - clear_hash_tables(edge_maps); -} -- cgit v1.2.3