[Bf-blender-cvs] [e83f46ea763] master: Geometry Nodes: Use Mesh instead of BMesh in split edges node
Wannes Malfait
noreply at git.blender.org
Sun Nov 20 22:42:30 CET 2022
Commit: e83f46ea7630163ae836f04cff867eee99032efa
Author: Wannes Malfait
Date: Sun Nov 20 15:42:10 2022 -0600
Branches: master
https://developer.blender.org/rBe83f46ea7630163ae836f04cff867eee99032efa
Geometry Nodes: Use Mesh instead of BMesh in split edges node
Rewrite the edge split code to operate directly on Mesh instead
of BMesh. This allows for the use of multi-threading and makes
the node around 2 times faster. Around 15% of the time is spent
just on the creation of the topology maps, so these being cached
on the mesh could cause an even greater speedup. The new node
gave identical results compared to the BMesh version on all the
meshes I tested it on (up to permutation of the indices).
Here are some of the results on a few simple test cases:
(Intel i7-7700HQ (8 cores) @ 2.800GHz , with 50% of edges selected)
| | 370x370 UV Sphere | 400x400 Grid | Suzanne 4 subdiv levels |
| ----- | ----------------- | -------------- | --------------------- |
| Mesh | 89ms | 111ms | 76ms |
| BMesh | 200ms | 276ms | 208ms |
Differential Revision: https://developer.blender.org/D16399
===================================================================
M source/blender/blenkernel/BKE_mesh_mapping.h
M source/blender/blenkernel/intern/mesh_mapping.cc
M source/blender/nodes/geometry/nodes/node_geo_edge_split.cc
M tests/python/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenkernel/BKE_mesh_mapping.h b/source/blender/blenkernel/BKE_mesh_mapping.h
index c5c81b31b79..a0ded44f630 100644
--- a/source/blender/blenkernel/BKE_mesh_mapping.h
+++ b/source/blender/blenkernel/BKE_mesh_mapping.h
@@ -352,11 +352,21 @@ Array<int> build_loop_to_poly_map(Span<MPoly> polys, int loops_num);
Array<Vector<int>> build_vert_to_edge_map(Span<MEdge> edges, int verts_num);
Array<Vector<int>> build_vert_to_loop_map(Span<MLoop> loops, int verts_num);
+Array<Vector<int>> build_edge_to_loop_map(Span<MLoop> loops, int edges_num);
+Vector<Vector<int>> build_edge_to_loop_map_resizable(Span<MLoop> loops, int edges_num);
inline int previous_poly_loop(const MPoly &poly, int loop_i)
{
return loop_i - 1 + (loop_i == poly.loopstart) * poly.totloop;
}
+inline int next_poly_loop(const MPoly &poly, int loop_i)
+{
+ if (loop_i == poly.loopstart + poly.totloop - 1) {
+ return poly.loopstart;
+ }
+ return loop_i + 1;
+}
+
} // namespace blender::bke::mesh_topology
#endif
diff --git a/source/blender/blenkernel/intern/mesh_mapping.cc b/source/blender/blenkernel/intern/mesh_mapping.cc
index ed4ae94da7f..98fb8a7fb42 100644
--- a/source/blender/blenkernel/intern/mesh_mapping.cc
+++ b/source/blender/blenkernel/intern/mesh_mapping.cc
@@ -586,6 +586,24 @@ Array<Vector<int>> build_vert_to_loop_map(const Span<MLoop> loops, const int ver
return map;
}
+Array<Vector<int>> build_edge_to_loop_map(const Span<MLoop> loops, const int edges_num)
+{
+ Array<Vector<int>> map(edges_num);
+ for (const int64_t i : loops.index_range()) {
+ map[loops[i].e].append(int(i));
+ }
+ return map;
+}
+
+Vector<Vector<int>> build_edge_to_loop_map_resizable(const Span<MLoop> loops, const int edges_num)
+{
+ Vector<Vector<int>> map(edges_num);
+ for (const int64_t i : loops.index_range()) {
+ map[loops[i].e].append(int(i));
+ }
+ return map;
+}
+
} // namespace blender::bke::mesh_topology
/** \} */
diff --git a/source/blender/nodes/geometry/nodes/node_geo_edge_split.cc b/source/blender/nodes/geometry/nodes/node_geo_edge_split.cc
index 0b4d5bd53f3..1a19897a148 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_edge_split.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_edge_split.cc
@@ -1,13 +1,15 @@
/* SPDX-License-Identifier: GPL-2.0-or-later */
+#include "BLI_array_utils.hh"
+#include "BLI_task.hh"
+
#include "DNA_mesh_types.h"
+#include "BKE_attribute_math.hh"
#include "BKE_mesh.h"
+#include "BKE_mesh_mapping.h"
#include "BKE_mesh_runtime.h"
-#include "bmesh.h"
-#include "bmesh_tools.h"
-
#include "node_geometry_util.hh"
namespace blender::nodes::node_geo_edge_split_cc {
@@ -19,30 +21,410 @@ static void node_declare(NodeDeclarationBuilder &b)
b.add_output<decl::Geometry>(N_("Mesh"));
}
-static Mesh *mesh_edge_split(const Mesh &mesh, const IndexMask selection)
+/* Naively checks if the first vertices and the second vertices are the same. */
+static inline bool naive_edges_equal(const MEdge &edge1, const MEdge &edge2)
+{
+ return edge1.v1 == edge2.v1 && edge1.v2 == edge2.v2;
+}
+
+static void transfer_attributes(const Map<AttributeIDRef, AttributeKind> &attributes,
+ const Span<int> new_to_old_verts_map,
+ const Span<int> new_to_old_edges_map,
+ const AttributeAccessor src_attributes,
+ MutableAttributeAccessor dst_attributes)
+{
+ for (Map<AttributeIDRef, AttributeKind>::Item entry : attributes.items()) {
+ const AttributeIDRef attribute_id = entry.key;
+ GAttributeReader src_attribute = src_attributes.lookup(attribute_id);
+ if (!src_attribute) {
+ continue;
+ }
+ const eCustomDataType data_type = bke::cpp_type_to_custom_data_type(
+ src_attribute.varray.type());
+ GSpanAttributeWriter dst_attribute = dst_attributes.lookup_or_add_for_write_only_span(
+ attribute_id, src_attribute.domain, data_type);
+ if (!dst_attribute) {
+ continue;
+ }
+
+ attribute_math::convert_to_static_type(data_type, [&](auto dummy) {
+ using T = decltype(dummy);
+ VArraySpan<T> span{src_attribute.varray.typed<T>()};
+ MutableSpan<T> dst_span = dst_attribute.span.typed<T>();
+ switch (src_attribute.domain) {
+ case ATTR_DOMAIN_POINT:
+ array_utils::gather(span, new_to_old_verts_map, dst_span);
+ break;
+ case ATTR_DOMAIN_EDGE:
+ array_utils::gather(span, new_to_old_edges_map, dst_span);
+ break;
+ case ATTR_DOMAIN_FACE:
+ dst_span.copy_from(span);
+ break;
+ case ATTR_DOMAIN_CORNER:
+ dst_span.copy_from(span);
+ break;
+ default:
+ BLI_assert_unreachable();
+ }
+ });
+ dst_attribute.finish();
+ }
+}
+
+/**
+ * Merge the new_edge into the original edge.
+ *
+ * NOTE: This function is very specific to the situation and makes a lot of assumptions.
+ */
+static void merge_edges(const int orig_edge_i,
+ const int new_edge_i,
+ MutableSpan<MLoop> new_loops,
+ Vector<Vector<int>> &edge_to_loop_map,
+ Vector<MEdge> &new_edges,
+ Vector<int> &new_to_old_edges_map)
+{
+ /* Merge back into the original edge by undoing the topology changes. */
+ BLI_assert(edge_to_loop_map[new_edge_i].size() == 1);
+ const int loop_i = edge_to_loop_map[new_edge_i][0];
+ new_loops[loop_i].e = orig_edge_i;
+
+ /* We are putting the last edge in the location of new_edge in all the maps, to remove
+ * new_edge efficiently. We have to update the topology information for this last edge
+ * though. Essentially we are replacing every instance of last_edge_i with new_edge_i. */
+ const int last_edge_i = new_edges.size() - 1;
+ if (last_edge_i != new_edge_i) {
+ BLI_assert(edge_to_loop_map[last_edge_i].size() == 1);
+ const int last_edge_loop_i = edge_to_loop_map[last_edge_i][0];
+ new_loops[last_edge_loop_i].e = new_edge_i;
+ }
+
+ /* We can now safely swap-remove. */
+ new_edges.remove_and_reorder(new_edge_i);
+ edge_to_loop_map.remove_and_reorder(new_edge_i);
+ new_to_old_edges_map.remove_and_reorder(new_edge_i);
+}
+
+/**
+ * Replace the vertex of an edge with a new one, and update the connected loops.
+ *
+ * NOTE: This only updates the loops containing the edge and the old vertex. It should therefore
+ * also be called on the adjacent edge.
+ */
+static void swap_vertex_of_edge(MEdge &edge,
+ const int old_vert,
+ const int new_vert,
+ MutableSpan<MLoop> loops,
+ const Span<int> connected_loops)
+{
+ if (edge.v1 == old_vert) {
+ edge.v1 = new_vert;
+ }
+ else if (edge.v2 == old_vert) {
+ edge.v2 = new_vert;
+ }
+ else {
+ BLI_assert_unreachable();
+ }
+
+ for (const int loop_i : connected_loops) {
+ if (loops[loop_i].v == old_vert) {
+ loops[loop_i].v = new_vert;
+ }
+ /* The old vertex is on the loop containing the adjacent edge. Since this function is also
+ * called on the adjacent edge, we don't replace it here. */
+ }
+}
+
+/** Split the vertex into duplicates so that each fan has a different vertex. */
+static void split_vertex_per_fan(const int vertex,
+ const int start_offset,
+ const Span<int> fans,
+ const Span<int> fan_sizes,
+ const Span<Vector<int>> edge_to_loop_map,
+ MutableSpan<MEdge> new_edges,
+ MutableSpan<MLoop> new_loops,
+ MutableSpan<int> new_to_old_verts_map)
+{
+ int fan_start = 0;
+ /* We don't need to create a new vertex for the last fan. That fan can just be connected to the
+ * original vertex. */
+ for (const int i : fan_sizes.index_range().drop_back(1)) {
+ const int new_vert_i = start_offset + i;
+ new_to_old_verts_map[new_vert_i] = vertex;
+
+ for (const int edge_i : fans.slice(fan_start, fan_sizes[i])) {
+ swap_vertex_of_edge(
+ new_edges[edge_i], vertex, new_vert_i, new_loops, edge_to_loop_map[edge_i]);
+ }
+ fan_start += fan_sizes[i];
+ }
+}
+
+/**
+ * Get the index of the adjacent edge to a loop connected to a vertex. In other words, for the
+ * given polygon return the unique edge connected to the given vertex and not on the given loop.
+ */
+static int adjacent_edge(Span<MLoop> loops, const int loop_i, const MPoly &poly, const int vertex)
+{
+ const int adjacent_loop_i = (loops[loop_i].v == vertex) ?
+ bke::mesh_topology::previous_poly_loop(poly, loop_i) :
+ bke::mesh_topology::next_poly_loop(poly, loop_i);
+ return loops[adjacent_loop_i].e;
+}
+
+/**
+ * Calculate the disjoint fans connected to the vertex, where a fan is a group of edges connected
+ * through polygons. The connected_edges vector is rearranged in such a way that edges in the same
+ * fan are grouped together. The r_fans_sizes Vector gives the sizes of the different fans, and can
+ * be used to retreive the fans from connected_edges.
+ */
+static void calc_vertex_fans(const int vertex,
+ const Span<MLoop> new_loops,
+ const Span<MPoly> polys,
+ const Span<Vector<int>> edge_to_loop_map,
+ const Span<int> loop_to_poly_map,
+ MutableSpan<int> connected_edges,
+ Vector<int> &r_fan_sizes)
+{
+ if (connected_edges.size() <= 1) {
+ r_fan_sizes.append(connected_edges.size());
+ return;
+ }
+
+ Vector<int> search_edges;
+ int total_found_edges_num = 0;
+ int fan_size = 0;
+ const int total_edge_num = connected_edges.size();
+ /* Iteratively go through the connected edges. The front contains already handled edges, while
+ * the back contains unhandled edges. */
+ while (true) {
+ /* This edge has not been visited yet. */
+ in
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list