Change Details

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 future improvement, 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`. When many points are merged to a single point, floating point inaccuracy has an effect. Averaging floats as doubles temporarily would help resolve that, but it would have a performance cost, and I don't expect it to be a common use case. 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. Merging the attributes is multi-threaded, though it might be possible to localize memory access there more. I expect most of the time to be spent in the KD tree anyway. 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.

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` | 94ms | 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.25ms | 0% | The total will 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.

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 fufeature improvement,, the distance the distance does not support a field currently, since that would make 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`. When many points are merged to a single point,The `id` attribute uses the value from the floating point inaccuracy has an effect. Averaging floats as doubles temporarily would help resolve that, but it would have a performance cost, and I don't expect it to be a common use caseirst 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. Merging the attributes is multi-threadedHowever, 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, though it mightincluding position (on a Ryzen 3700x): | Action | Time | Portion of Total (618ms) | ------- | --- | ------ | | `BLI_kdtree_3d_balance` | 432 ms | 70% | | `BLI_kdtree_3d_calc_duplicates_fast` | 94ms | 15% | be possible to localize memory access there more.| 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.25ms | 0% | The total will probably be a bit higher, I expect mostbecause these timings don't of the time to be spent ininclude allocations of temporary arrays and the KD tree anywaynew 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.