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

0 files changed, 0 insertions, 0 deletions