Speaker
Description
Radius-based neighbor search is a fundamental operation in 3D point cloud processing, with applications across many fields. It is usually accelerated with spatial data structures such as octrees or k-d trees, whose construction cost and irregular memory access patterns limit performance on large and irregular datasets.
We propose a preprocessing step that operates directly on the point cloud: we build a neighborhood graph and order the points with the Reverse Cuthill-McKee (RCM) algorithm, a bandwidth-reduction method for sparse matrices. The ordering places spatially close points contiguously in memory, so that a radius query only needs to scan a small window of the ordered array. Queries can therefore be bounded, executed sequentially and vectorized, improving cache locality and SIMD utilization, without any complex spatial data structures.
We evaluate the approach on 11 datasets of 11 to 721 million points and compare it with octrees. The results show that the proposed approach constitutes a promising alternative for neighbor searching in point clouds, achieving in numerous cases better performance than traditional solutions (up to 14x in the best case). Furthermore, this work highlights the advantages and limitations of the proposed approach and identifies new research directions that could broaden its scope of application and further improve its performance.