In an attempt to replace BKE_mesh_merge_verts (see D16755) a loss in
performance of around 20% (worst case) was observed.
The most time-consuming operation in merge by distance is to find
duplicate faces (faces that are different but have the same vertices).
Therefore, some strategies were planned to optimize this algorithm:
- Store the corner indices in an array thus avoiding multiple calls of weld_iter_loop_of_poly_next;
- Create a map of polygons linked to edges instead of linked to vertices - this decreases the number of connections and reduces the calculation of the intersection of polygon indices.
There are other fields to optimize, like reusing the wpolys array
instead of creating a new array of corner offsets. And join some arrays
as members of the same struct to be used in the same buffer.
But for now, it is already a nice optimization. And the new
poly_find_doubles function can be reused in the future to create a
generic utility.
The result of the optimization varies greatly depending on the number
of polygons, the size of each polygon and the number of duplicates.
On average it was something around 2 times faster.
Worst case tested (old vs new): 0.1ms vs 0.3ms
Best case tested (old vs new): 10.0ms vs 3.2ms