derivadas.dev

Pablo Díaz Viñambres

MSc Informatics @ TUM

Study and improvement of octree structures' performance for neighbour search in 3D point clouds

C++OpenMPLiDARThesis


In my Informatics BSc thesis, I developed fast algorithms for spatial queries in 3D point clouds PR3\mathcal{P} \subset \mathbb{R}^3. The tasks are quite simple, given a center pPp \in \mathcal{P}, we either find all points within a given distance r>0r > 0 (fixed-radius queries) or we find the kk closest points (kNN queries). These two neighbourhood-finding operations are extremely common and often become a computational bottleneck in large cloud processing for remote sensing and photogrammetry. We develop two approaches to make them as fast as possible:

  • Point cloud reordering via Space Filling Curves (SFCs), where we alter the order of the cloud in-memory to reduce cache misses and improve performance by as much as 75%.
  • An optimized linear octree data structure with a novel algorithm for fast point retrieval in fixed-radius searches, and an adaptation of a known algorithm for kNN searches to it. Both of these algorithms excel in performance and even beat SoTA libraries in terms of performance (up to 10x faster, better scalability on rr and kk), memory usage (70% less, compact layout) and construction time (parallel construction, up to 30x faster).

The thesis received the maximum grade (10/10) and was recognized with honors as one of the best BSc Thesis in the class. After my graduation, me and my supervisors kept working on this project and we expanded it to a short paper for the SARTECO Parallelism Conference 2025 and a full journal paper submitted and available in arXiv. Check the research project entry for more details.