This implements a merge by distance operation for point clouds.
Besides the geometry input, there are two others-- a selection
input to limit the operation to certain points, and the merge
distance. While it would be a reasonable feature, the distance
does not support a field currently, since that would make
the algorithm significantly more complex.
All attributes are merged to the merged points, with the values
mixed together. This same generic method is used for all attributes,
including position. The id attribute uses the value from the
first index merged into it.
For the implementation, I fiddled for quite a trying to give the
algorithm an optimal structure. Some parts are inherently single-
threaded, like finding the final indices accounting for the merged
points. However, by far most of the time is spend balancing the
KD tree.
Here's a test with 2.4 million points merging into 110, with four
attributes to merge, including position (on a Ryzen 3700x):
| Action | Time | Portion of Total (618ms) |
|---|---|---|
| BLI_kdtree_3d_balance | 432 ms | 70% |
| BLI_kdtree_3d_calc_duplicates_fast | 94 ms | 15% |
| Attribute mixing | 36 ms | 6% |
| BLI_kdtree_3d_insert | 21 ms | 3% |
| Build merge_map | 8 ms | 1% |
| Build merge_indices | 7 ms | 1% |
| BLI_kdtree_3d_free | 4 ms | 0.7% |
| Build src_to_dst_indices | 4 ms | 0.6% |
| Build map_offsets | 0.25 ms | 0% |
The total is probably be a bit higher, because these timings don't
include allocations of temporary arrays and the new point cloud.
This is a first step towards implementing T86913. I'm adding a patch
for point cloud support separately, because this is new code. The weld
modifier code will be adapted for the mesh case.
