Oscar G. Lorenzo

Jonatan B. Bastos, Francisco F. Rivera, Oscar G. Lorenzo et al.

With the advancement of 3D scanning technologies, point clouds have become fundamental for representing 3D spatial data, with applications that span across various scientific and technological fields. Practical analysis of this data depends crucially on available neighborhood descriptors to accurately characterize the local geometries of the point cloud. This paper introduces LitS, a novel neighborhood descriptor for 2D and 3D point clouds. LitS are piecewise constant functions on the unit circle that allow points to keep track of their surroundings. Each element in LitS' domain represents a direction with respect to a local reference system. Once constructed, evaluating LitS at any given direction gives us information about the number of neighbors in a cone-like region centered around that same direction. Thus, LitS conveys a lot of information about the local neighborhood of a point, which can be leveraged to gain global structural understanding by analyzing how LitS changes between close points. In addition, LitS comes in two versions ('regular' and 'cumulative') and has two parameters, allowing them to adapt to various contexts and types of point clouds. Overall, they are a versatile neighborhood descriptor, capable of capturing the nuances of local point arrangements and resilient to common point cloud data issues such as variable density and noise.

Pablo D. Viñambres, Miguel Yermo, Silvia R. Alcaraz et al.

This work presents an efficient approach for neighbourhood searching in 3D point clouds by combining spatial reordering leveraging Space-Filling Curves (SFC), specifically Morton and Hilbert curves, with a linear Octree implementation. We also propose specialised search algorithms for fixed-radius and kNN queries, based on our linear Octree structures. Additionally, we introduce the novel concept of kNN locality histogram, which can be easily computed to characterise locality in data accesses, and we found to be directly related to cache misses and search performance. Our experiments reveal that SFC reordering significantly improves access to spatial data, reducing the number of cache misses from 25% to 75% and runtime by up to 50%. Moreover, we compare our proposal with several widely used Octree and KDTree implementations. Our method achieves a significant reduction in search time, up to 10$\times$ faster than existing solutions. Additionally, we analysed the performance of our neighbourhood searches (parallelised using OpenMP), demonstrating high scalability with the number of cores and the problem size. Notably, we observed a speedup of up to $36\times$ when executing fixed-radius searches in a system with 40 cores. The results obtained indicate that our methods provide a robust and efficient solution for applications that require fast access to large-scale 3D point neighbour sets.