Subdiv: Avoid quadratic runtime for loose edges

Currently, when subdividing every single vertex on every loose edge,
Blender iterates over all other edges to find neighbors. This has
quadratic runtime and can be very slow. Instead, first create a
map of edges connected to each vertex.

With about 10000 edges, the performance goes from very slow to very
smooth in my tests. Because of the nature of quadratic runtime, the
improvement will depend massively on the number of elements.

The only downside to this is that the map will still be built when
there are only a couple loose edges, but that case is probably not
so common.

Differential Revision: https://developer.blender.org/D15923

1 files changed, 6 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_subdiv_mesh.h b/source/blender/blenkernel/BKE_subdiv_mesh.h
index b24db517143..49c45efafe0 100644
--- a/source/blender/blenkernel/BKE_subdiv_mesh.h
+++ b/source/blender/blenkernel/BKE_subdiv_mesh.h
@@ -14,7 +14,9 @@ extern "C" {
 #endif
 
 struct Mesh;
+struct MeshElemMap;
 struct MEdge;
+struct MVert;
 struct Subdiv;
 
 typedef struct SubdivToMeshSettings {
@@ -37,8 +39,10 @@ struct Mesh *BKE_subdiv_to_mesh(struct Subdiv *subdiv,
 /* Interpolate a position along the `coarse_edge` at the relative `u` coordinate. If `is_simple` is
  * false, this will perform a B-Spline interpolation using the edge neighbors, otherwise a linear
  * interpolation will be done base on the edge vertices. */
-void BKE_subdiv_mesh_interpolate_position_on_edge(const struct Mesh *coarse_mesh,
-                                                  const struct MEdge *coarse_edge,
+void BKE_subdiv_mesh_interpolate_position_on_edge(const struct MVert *coarse_verts,
+                                                  const struct MEdge *coarse_edges,
+                                                  const struct MeshElemMap *vert_to_edge_map,
+                                                  int coarse_edge_index,
                                                   bool is_simple,
                                                   float u,
                                                   float pos_r[3]);