From 12c235a1c515d41a18c497d6647253698579c01d Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Fri, 9 Sep 2022 08:13:37 -0500 Subject: 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 --- source/blender/blenkernel/BKE_subdiv_mesh.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'source/blender/blenkernel/BKE_subdiv_mesh.h') 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]); -- cgit v1.2.3