[Bf-blender-cvs] [04693f90748] master: Mesh: small optimization and better readability in Merge by Distance
Germano Cavalcante
noreply at git.blender.org
Thu Dec 8 03:11:49 CET 2022
Commit: 04693f90748e6761fab626f4a66bd68ab9b2b55b
Author: Germano Cavalcante
Date: Wed Dec 7 11:14:47 2022 -0300
Branches: master
https://developer.blender.org/rB04693f90748e6761fab626f4a66bd68ab9b2b55b
Mesh: small optimization and better readability in Merge by Distance
The optimization is done by removing the `len` member from the groups
and using fewer `for` loops.
But it's not a really impactful optimization.
Only 1.9% in the weld operation of a high poly mesh.
(disregarding getting the vertex map and all other operations on a
Blender frame).
The readability improvement comes from using more familiar types like
`int` and `int2` instead of `WeldGroup` and `WeldGroupEdge` structs.
===================================================================
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 2cafed66b83..5dce391c4f7 100644
--- a/source/blender/geometry/intern/mesh_merge_by_distance.cc
+++ b/source/blender/geometry/intern/mesh_merge_by_distance.cc
@@ -26,19 +26,6 @@ namespace blender::geometry {
/* indicates whether an edge or vertex in groups_map will be merged. */
#define ELEM_MERGED int(-2)
-/* Used to indicate a range in an array specifying a group. */
-struct WeldGroup {
- int len;
- int offs;
-};
-
-/* Edge groups that will be merged. Final vertices are also indicated. */
-struct WeldGroupEdge {
- struct WeldGroup group;
- int v1;
- int v2;
-};
-
struct WeldVert {
/* Indices relative to the original Mesh. */
int vert_dest;
@@ -83,22 +70,25 @@ struct WeldPoly {
/* Final Polygon Size. */
int loop_len;
/* Group of loops that will be affected. */
- struct WeldGroup loops;
+ struct {
+ int len;
+ int offs;
+ } loops;
};
};
};
struct WeldMesh {
/* Group of vertices to be merged. */
- Array<WeldGroup> vert_groups;
+ Array<int> vert_groups_offs;
Array<int> vert_groups_buffer;
/* Group of edges to be merged. */
- Array<WeldGroupEdge> edge_groups;
+ Array<int> edge_groups_offs;
Array<int> edge_groups_buffer;
- /* From the original index of the vertex, this indicates which group it is or is going to be
- * merged. */
+ /* From the original edge index, this indicates which group it is going to be merged. */
Array<int> edge_groups_map;
+ Array<int2> edge_groups_verts;
/* References all polygons and loops that will be affected. */
Vector<WeldLoop> wloop;
@@ -342,53 +332,62 @@ static Vector<WeldVert> weld_vert_ctx_alloc_and_setup(Span<int> vert_dest_map,
*/
static void weld_vert_groups_setup(Span<WeldVert> wvert,
Span<int> vert_dest_map,
+ const int vert_kill_len,
MutableSpan<int> r_vert_groups_map,
Array<int> &r_vert_groups_buffer,
- Array<WeldGroup> &r_vert_groups_offs)
+ Array<int> &r_vert_groups_offs)
{
- /* Get weld vert groups. */
+ /**
+ * Since `r_vert_groups_map` comes from `vert_dest_map`, we don't need to reset vertices out of
+ * context again.
+ *
+ * \code{.c}
+ * for (const int i : vert_dest_map.index_range()) {
+ * r_vert_groups_map[i] = OUT_OF_CONTEXT;
+ * }
+ * \endcode
+ */
+ BLI_assert(r_vert_groups_map.data() == vert_dest_map.data());
+
+ const int vert_groups_len = wvert.size() - vert_kill_len;
+
+ /* Add +1 to allow calculation of the length of the last group. */
+ r_vert_groups_offs.reinitialize(vert_groups_len + 1);
+ r_vert_groups_offs.fill(0);
int wgroups_len = 0;
- for (const int i : vert_dest_map.index_range()) {
- const int vert_dest = vert_dest_map[i];
- if (vert_dest != OUT_OF_CONTEXT) {
- if (vert_dest != i) {
- r_vert_groups_map[i] = ELEM_MERGED;
- }
- else {
- r_vert_groups_map[i] = wgroups_len;
- wgroups_len++;
- }
+ for (const WeldVert &wv : wvert) {
+ if (wv.vert_dest == wv.vert_orig) {
+ /* Indicate the index of the vertex group */
+ r_vert_groups_map[wv.vert_orig] = wgroups_len;
+ wgroups_len++;
}
else {
- r_vert_groups_map[i] = OUT_OF_CONTEXT;
+ r_vert_groups_map[wv.vert_orig] = ELEM_MERGED;
}
}
- r_vert_groups_offs.reinitialize(wgroups_len);
- r_vert_groups_offs.fill({0, 0});
-
for (const WeldVert &wv : wvert) {
int group_index = r_vert_groups_map[wv.vert_dest];
- r_vert_groups_offs[group_index].len++;
+ r_vert_groups_offs[group_index]++;
}
int offs = 0;
- for (WeldGroup &wg : r_vert_groups_offs) {
- wg.offs = offs;
- offs += wg.len;
+ for (const int i : IndexRange(vert_groups_len)) {
+ offs += r_vert_groups_offs[i];
+ r_vert_groups_offs[i] = offs;
}
+ r_vert_groups_offs[vert_groups_len] = offs;
BLI_assert(offs == wvert.size());
r_vert_groups_buffer.reinitialize(offs);
- for (const WeldVert &wv : wvert) {
- int group_index = r_vert_groups_map[wv.vert_dest];
- r_vert_groups_buffer[r_vert_groups_offs[group_index].offs++] = wv.vert_orig;
- }
- for (WeldGroup &wg : r_vert_groups_offs) {
- wg.offs -= wg.len;
+ /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
+ for (int i = wvert.size(); i--;) {
+ const WeldVert &wv = wvert[i];
+ int group_index = r_vert_groups_map[wv.vert_dest];
+ r_vert_groups_buffer[--r_vert_groups_offs[group_index]] = wv.vert_orig;
}
}
@@ -449,7 +448,7 @@ 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<WeldGroup> r_vlinks,
+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)
@@ -457,7 +456,7 @@ static void weld_edge_ctx_setup(MutableSpan<WeldGroup> r_vlinks,
/* Setup Edge Overlap. */
int edge_kill_len = 0;
- r_vlinks.fill({0, 0});
+ r_vlinks.fill(0);
for (WeldEdge &we : r_wedge) {
int dst_vert_a = we.vert_a;
@@ -471,20 +470,22 @@ static void weld_edge_ctx_setup(MutableSpan<WeldGroup> r_vlinks,
continue;
}
- r_vlinks[dst_vert_a].len++;
- r_vlinks[dst_vert_b].len++;
+ r_vlinks[dst_vert_a]++;
+ r_vlinks[dst_vert_b]++;
}
int link_len = 0;
- for (WeldGroup &vl : r_vlinks) {
- vl.offs = link_len;
- link_len += vl.len;
+ for (const int i : IndexRange(r_vlinks.size() - 1)) {
+ link_len += r_vlinks[i];
+ r_vlinks[i] = link_len;
}
+ r_vlinks.last() = link_len;
if (link_len > 0) {
Array<int> link_edge_buffer(link_len);
- for (const int i : r_wedge.index_range()) {
+ /* 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;
@@ -493,13 +494,8 @@ static void weld_edge_ctx_setup(MutableSpan<WeldGroup> r_vlinks,
int dst_vert_a = we.vert_a;
int dst_vert_b = we.vert_b;
- link_edge_buffer[r_vlinks[dst_vert_a].offs++] = i;
- link_edge_buffer[r_vlinks[dst_vert_b].offs++] = i;
- }
-
- for (WeldGroup &vl : r_vlinks) {
- /* Fix offset */
- vl.offs -= vl.len;
+ 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()) {
@@ -513,18 +509,18 @@ static void weld_edge_ctx_setup(MutableSpan<WeldGroup> r_vlinks,
int dst_vert_a = we.vert_a;
int dst_vert_b = we.vert_b;
- struct WeldGroup *link_a = &r_vlinks[dst_vert_a];
- struct WeldGroup *link_b = &r_vlinks[dst_vert_b];
+ const int link_a = r_vlinks[dst_vert_a];
+ const int link_b = r_vlinks[dst_vert_b];
- int edges_len_a = link_a->len;
- int edges_len_b = link_b->len;
+ int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a;
+ int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b;
if (edges_len_a <= 1 || edges_len_b <= 1) {
continue;
}
- int *edges_ctx_a = &link_edge_buffer[link_a->offs];
- int *edges_ctx_b = &link_edge_buffer[link_b->offs];
+ 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++) {
@@ -574,11 +570,12 @@ static void weld_edge_groups_setup(const int medge_len,
Span<int> wedge_map,
MutableSpan<int> r_edge_groups_map,
Array<int> &r_edge_groups_buffer,
- Array<WeldGroupEdge> &r_edge_groups_offs)
+ Array<int> &r_edge_groups_offs,
+ Array<int2> &r_edge_groups_verts)
{
int wgroups_len = wedge.size() - edge_kill_len;
- r_edge_groups_offs.reinitialize(wgroups_len);
- r_edge_groups_offs.fill({{0}});
+
+ r_edge_groups_verts.reinitialize(wgroups_len);
wgroups_len = 0;
for (const int i : IndexRange(medge_len)) {
@@ -592,8 +589,7 @@ static void weld_edge_groups_setup(const int medge_len,
}
else {
we->edge_dest = we->edge_orig;
- r_edge_groups_offs[wgroups_len].v1 = we->vert_a;
- r_edge_groups_offs[wgroups_len].v2 = we->vert_b;
+ r_edge_groups_verts[wgroups_len] = {we->vert_a, we->vert_b};
r_edge_groups_map[i] = wgroups_len;
wgroups_len++;
}
@@ -610,31 +606,35 @@ static void weld_edge_groups_setup(const int medge_len,
return;
}
+ /* Add +1 to allow calculation of the length of the last group. */
+ r_edge_groups_offs.reinitialize(wgroups_len + 1);
+ r_edge_groups_offs.fill(0);
+
for (const WeldEdge &we : wedge) {
if (we.flag == ELEM_COLLAPSED) {
continue;
}
int group_index = r_edge_groups_map[we.edge_dest];
- r_edge_groups_offs[group_index].group.len++;
+ r_edge_groups_offs[group_index]++;
}
int offs = 0;
- for (WeldGroupEdge &wegrp : r_edge_groups_offs) {
- wegrp.group.offs = offs;
- offs += wegrp.group.len;
+ for (const int i : IndexRange(wgroups_len)) {
+ offs += r_edge_groups_offs[i];
+ r_edge_groups_offs[i] = offs;
}
+ r_edge_groups_offs[wgroups_len] = offs;
r_edge_groups_buffer.reinitialize(offs);
- for (const WeldEdge &we : wedge) {
+
+ /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
+ for (int i = wedge.size(); i--;) {
+ const WeldEdge &we = wedge[i];
if (we.flag == ELEM_COLLAPSED) {
continue;
}
int group_i
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list