[Bf-blender-cvs] [25ce7056171] master: Merge by Distance: split code into more specialized functions
Germano Cavalcante
noreply at git.blender.org
Thu Jan 19 17:28:57 CET 2023
Commit: 25ce7056171f849b724ada0787b35504c3e16dca
Author: Germano Cavalcante
Date: Thu Jan 19 12:31:40 2023 -0300
Branches: master
https://developer.blender.org/rB25ce7056171f849b724ada0787b35504c3e16dca
Merge by Distance: split code into more specialized functions
Split the algorithms that find duplicates.
This improves readability and helps us find areas for optimization.
It may also facilitate the implementation of generic utilities.
No functional changes.
Differential Revision: https://developer.blender.org/D16918
===================================================================
M source/blender/geometry/intern/mesh_merge_by_distance.cc
===================================================================
diff --git a/source/blender/geometry/intern/mesh_merge_by_distance.cc b/source/blender/geometry/intern/mesh_merge_by_distance.cc
index b9addd8dd57..0d1cdf93133 100644
--- a/source/blender/geometry/intern/mesh_merge_by_distance.cc
+++ b/source/blender/geometry/intern/mesh_merge_by_distance.cc
@@ -15,7 +15,7 @@
#include "GEO_mesh_merge_by_distance.hh"
-//#define USE_WELD_DEBUG
+// #define USE_WELD_DEBUG
namespace blender::geometry {
@@ -404,13 +404,15 @@ static void weld_vert_groups_setup(Span<WeldVert> wvert,
* \return r_edge_dest_map: First step to create map of indices pointing edges that will be merged.
* \return r_edge_ctx_map: Map of indices pointing original edges to weld context edges.
*/
-static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
- Span<int> vert_dest_map,
- MutableSpan<int> r_edge_dest_map,
- MutableSpan<int> r_edge_ctx_map)
+static Vector<WeldEdge> weld_edge_ctx_alloc_and_find_collapsed(Span<MEdge> medge,
+ Span<int> vert_dest_map,
+ MutableSpan<int> r_edge_dest_map,
+ MutableSpan<int> r_edge_ctx_map,
+ int *r_edge_collapsed_len)
{
/* Edge Context. */
int wedge_len = 0;
+ int edge_collapsed_len = 0;
Vector<WeldEdge> wedge;
wedge.reserve(medge.size());
@@ -426,8 +428,17 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
we.vert_b = (v_dest_2 != OUT_OF_CONTEXT) ? v_dest_2 : v2;
we.edge_dest = OUT_OF_CONTEXT;
we.edge_orig = i;
+
+ if (we.vert_a == we.vert_b) {
+ we.flag = ELEM_COLLAPSED;
+ edge_collapsed_len++;
+ r_edge_dest_map[i] = ELEM_COLLAPSED;
+ }
+ else {
+ r_edge_dest_map[i] = i;
+ }
+
wedge.append(we);
- r_edge_dest_map[i] = i;
r_edge_ctx_map[i] = wedge_len++;
}
else {
@@ -436,6 +447,7 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
}
}
+ *r_edge_collapsed_len = edge_collapsed_len;
return wedge;
}
@@ -449,30 +461,30 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
* \return r_wedge: Weld edges. `flag` and `edge_dest` members will be set here.
* \return r_edge_kill_len: Number of edges to be destroyed by merging or collapsing.
*/
-static void weld_edge_ctx_setup(MutableSpan<int> r_vlinks,
- MutableSpan<int> r_edge_dest_map,
- MutableSpan<WeldEdge> r_wedge,
- int *r_edge_kill_len)
+static void weld_edge_find_doubles(int remain_edge_ctx_len,
+ MutableSpan<int> r_vlinks,
+ MutableSpan<int> r_edge_dest_map,
+ MutableSpan<WeldEdge> r_wedge,
+ int *r_edge_kill_len)
{
+ if (remain_edge_ctx_len == 0) {
+ return;
+ }
+
/* Setup Edge Overlap. */
- int edge_kill_len = 0;
+ int edge_double_len = 0;
r_vlinks.fill(0);
for (WeldEdge &we : r_wedge) {
- int dst_vert_a = we.vert_a;
- int dst_vert_b = we.vert_b;
-
- if (dst_vert_a == dst_vert_b) {
- BLI_assert(we.edge_dest == OUT_OF_CONTEXT);
- r_edge_dest_map[we.edge_orig] = ELEM_COLLAPSED;
- we.flag = ELEM_COLLAPSED;
- edge_kill_len++;
+ if (we.flag == ELEM_COLLAPSED) {
+ BLI_assert(r_edge_dest_map[we.edge_orig] == ELEM_COLLAPSED);
continue;
}
- r_vlinks[dst_vert_a]++;
- r_vlinks[dst_vert_b]++;
+ BLI_assert(we.vert_a != we.vert_b);
+ r_vlinks[we.vert_a]++;
+ r_vlinks[we.vert_b]++;
}
int link_len = 0;
@@ -482,80 +494,79 @@ static void weld_edge_ctx_setup(MutableSpan<int> r_vlinks,
}
r_vlinks.last() = link_len;
- if (link_len > 0) {
- Array<int> link_edge_buffer(link_len);
+ BLI_assert(link_len > 0);
+ Array<int> link_edge_buffer(link_len);
- /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
- for (int i = r_wedge.size(); i--;) {
- const WeldEdge &we = r_wedge[i];
- if (we.flag == ELEM_COLLAPSED) {
- continue;
- }
+ /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
+ for (int i = r_wedge.size(); i--;) {
+ const WeldEdge &we = r_wedge[i];
+ if (we.flag == ELEM_COLLAPSED) {
+ continue;
+ }
+
+ int dst_vert_a = we.vert_a;
+ int dst_vert_b = we.vert_b;
- int dst_vert_a = we.vert_a;
- int dst_vert_b = we.vert_b;
+ link_edge_buffer[--r_vlinks[dst_vert_a]] = i;
+ link_edge_buffer[--r_vlinks[dst_vert_b]] = i;
+ }
- link_edge_buffer[--r_vlinks[dst_vert_a]] = i;
- link_edge_buffer[--r_vlinks[dst_vert_b]] = i;
+ for (const int i : r_wedge.index_range()) {
+ const WeldEdge &we = r_wedge[i];
+ if (we.edge_dest != OUT_OF_CONTEXT) {
+ /* No need to retest edges.
+ * (Already includes collapsed edges). */
+ continue;
}
- for (const int i : r_wedge.index_range()) {
- const WeldEdge &we = r_wedge[i];
- if (we.edge_dest != OUT_OF_CONTEXT) {
- /* No need to retest edges.
- * (Already includes collapsed edges). */
- continue;
- }
+ int dst_vert_a = we.vert_a;
+ int dst_vert_b = we.vert_b;
+
+ const int link_a = r_vlinks[dst_vert_a];
+ const int link_b = r_vlinks[dst_vert_b];
- int dst_vert_a = we.vert_a;
- int dst_vert_b = we.vert_b;
+ int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a;
+ int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b;
- const int link_a = r_vlinks[dst_vert_a];
- const int link_b = r_vlinks[dst_vert_b];
+ if (edges_len_a <= 1 || edges_len_b <= 1) {
+ continue;
+ }
- int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a;
- int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b;
+ int *edges_ctx_a = &link_edge_buffer[link_a];
+ int *edges_ctx_b = &link_edge_buffer[link_b];
+ int edge_orig = we.edge_orig;
- if (edges_len_a <= 1 || edges_len_b <= 1) {
+ for (; edges_len_a--; edges_ctx_a++) {
+ int e_ctx_a = *edges_ctx_a;
+ if (e_ctx_a == i) {
continue;
}
-
- int *edges_ctx_a = &link_edge_buffer[link_a];
- int *edges_ctx_b = &link_edge_buffer[link_b];
- int edge_orig = we.edge_orig;
-
- for (; edges_len_a--; edges_ctx_a++) {
- int e_ctx_a = *edges_ctx_a;
- if (e_ctx_a == i) {
- continue;
- }
- while (edges_len_b && *edges_ctx_b < e_ctx_a) {
- edges_ctx_b++;
- edges_len_b--;
- }
- if (edges_len_b == 0) {
- break;
- }
- int e_ctx_b = *edges_ctx_b;
- if (e_ctx_a == e_ctx_b) {
- WeldEdge *we_b = &r_wedge[e_ctx_b];
- BLI_assert(ELEM(we_b->vert_a, dst_vert_a, dst_vert_b));
- BLI_assert(ELEM(we_b->vert_b, dst_vert_a, dst_vert_b));
- BLI_assert(we_b->edge_dest == OUT_OF_CONTEXT);
- BLI_assert(we_b->edge_orig != edge_orig);
- r_edge_dest_map[we_b->edge_orig] = edge_orig;
- we_b->edge_dest = edge_orig;
- edge_kill_len++;
- }
+ while (edges_len_b && *edges_ctx_b < e_ctx_a) {
+ edges_ctx_b++;
+ edges_len_b--;
+ }
+ if (edges_len_b == 0) {
+ break;
+ }
+ int e_ctx_b = *edges_ctx_b;
+ if (e_ctx_a == e_ctx_b) {
+ WeldEdge *we_b = &r_wedge[e_ctx_b];
+ BLI_assert(ELEM(we_b->vert_a, dst_vert_a, dst_vert_b));
+ BLI_assert(ELEM(we_b->vert_b, dst_vert_a, dst_vert_b));
+ BLI_assert(we_b->edge_dest == OUT_OF_CONTEXT);
+ BLI_assert(we_b->edge_orig != edge_orig);
+ r_edge_dest_map[we_b->edge_orig] = edge_orig;
+ we_b->edge_dest = edge_orig;
+ edge_double_len++;
}
}
+ }
+
+ *r_edge_kill_len += edge_double_len;
#ifdef USE_WELD_DEBUG
- weld_assert_edge_kill_len(r_wedge, edge_kill_len);
+ weld_assert_edge_kill_len(r_wedge, *r_edge_kill_len);
#endif
- }
-
- *r_edge_kill_len = edge_kill_len;
}
/**
@@ -995,204 +1006,225 @@ static void weld_poly_split_recursive(Span<int> vert_dest_map,
* done to reduce allocations.
* \return r_weld_mesh: Loop and poly members will be configured here.
*/
-static void weld_poly_loop_ctx_setup(Span<MLoop> mloop,
+static void weld_poly_loop_ctx_setup_collapsed_and_split(Span<MLoop> mloop,
#ifdef USE_WELD_DEBUG
- Span<MPoly> mpoly,
+ Span<MPoly> mpoly,
#endif
- const int mvert_len,
- Span<int> vert_dest_map,
- const int remain_edge_ctx_len,
- MutableSpan<int> r_vlinks,
- WeldMesh *r_weld_mesh)
+ Span<int> vert_dest_map,
+ const int remain_edge_ctx_len,
+ WeldMesh *r_weld_mesh)
{
+ if (remain_edge_ctx_len == 0) {
+ r_weld_mesh->poly_kill_len = r_weld_mesh->wpoly.size();
+ r_weld_mesh->loop_kill_len = r_weld_mesh->wloop.size();
+
+ for (WeldPoly &wp : r_weld_mesh->wpoly) {
+ wp.flag = ELEM_COLLAPSED;
+ }
+
+ return;
+ }
+
WeldPoly *wpoly = r_weld_mesh->wpoly.data();
MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
+
int poly_kill_len = 0;
int loop_kill_len = 0;
- Span<int> loop_map = r_weld_mesh->loop_map;
-
- if (remain_edge_ctx_len) {
-
- /* Setup Poly/Loop. */
- /* `wpoly.size()` may change during the loop,
- * so make it clear that we are only working with the original wpolys. */
- IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range();
- for (const int i : wpoly_original_range) {
- WeldPoly &wp = wpoly[i];
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list