octrees-benchmark

Background

LiDAR (Light and Ranging Detection) technology has now become the quintessential technique for collecting geospatial data from the earth's surface. This code implements a linearized octree based on ideas from Keller et al. and Behley et al. for fast fixed-radius neighbourhood searches, achieving better performance than other Octrees and KD-trees tested, such as nanoflann KD-tree, picoTree, PCL Octree and KD-Tree, and unibnOctree. We also analyze the performance of Morton and Hilbert Space Filling Curves (SFCs). SFC Reordering allows for faster searches and is essential for the construction of the linear Octree. Extensive benchmarking and result plotting code and scripts are also provided.

Publication

This code is associated with a research paper published as a preprint:

Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees

Authors: Pablo D. Viñambres, Miguel Yermo, Silvia R. Alcaraz, Oscar G. Lorenzo, Francisco F. Rivera, José C. Cabaleiro

arXiv Preprint: https://arxiv.org/abs/2603.06771 (PDF)

Citation

If you use this code in your research, please cite the associated paper using one of the following formats:

BibTeX:

@article{Viñambres2026,
  title={Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees},
  author={Viñambres, Pablo D. and Yermo, Miguel and Alcaraz, Silvia R. and Lorenzo, Oscar G. and Rivera, Francisco F. and Cabaleiro, José C.},
  journal={arXiv preprint arXiv:2603.06771},
  year={2026}
}

APA:

Viñambres, P. D., Yermo, M., Alcaraz, S. R., Lorenzo, O. G., Rivera, F. F., & Cabaleiro, J. C. (2026). Efficient neighbourhood search in 3D point clouds through space-filling curves and linear octrees. arXiv Preprint, 2603.06771.

DOI: https://doi.org/10.48550/arXiv.2603.06771

Installation

Dependencies

Install system-level dependencies and build required libraries using the provided installation scripts:

Build and install libraries: The project includes installation scripts in the scripts/ directory:

• LASlib (required):

  bash scripts/install_laslib.sh

• PAPI (required for cache profiling):

  bash scripts/install_papi.sh

• PCL (optional, for PCL benchmark comparisons):

  bash scripts/install_pcl.sh

  If PCL is not found during compilation, the code will compile successfully but without PCL Octree and KD-Tree benchmark support.

• Picotree (optional, for Picotree benchmark comparisons):

  bash scripts/install_picotree.sh

Compilation

In the project directory, just execute

cmake -B build -DCMAKE_BUILD_TYPE=Release .
cmake --build build

This creates the executable at build/octrees-benchmark.

Execution

We provide scripts for replicating our results, check bench_neighbors.bash for kNN and fixed-radius neighbor searches, bench_memory.bash for the measurements of Octree and KD-tree sizes, and bench_locality.bash for benchmarks analyzing how SFCs improve locality.

Under the folder plots we include all the python scripts for generating the figures seen in the publication.

Tests / Examples

A small usage example of the library features is provided under examples/example.cpp. It is automatically built alongside the main project.

make test_library
./tests/test_library

Running the full test suite

The project includes a comprehensive unit testing suite using GoogleTest. Build the project with option -DBUILD_TESTS=ON to enable it. After building the project, you can run all tests with:

make                # builds the library and all test executables
ctest --output-on-failure

You can also run individual test executables directly, e.g.:

./tests/test_points
./tests/test_encoders
./tests/test_octree
./tests/test_octree_advanced

To run a specific test case with CTest, use the -R option with the test name, for example:

ctest -R LinearOctreeTest.RadiusSearch

Main Options

Option	Alias	Description
-h	--help	Show help message.
-i	--input	Path to input file.
-c	--container-type	Container type to use. Default: AoS. Possible values: SoA, AoS.
-o	--output	Path to output file.
-r	--radii	Benchmark radii (comma-separated, e.g., 2.5,5.0,7.5).
-v	--kvalues	kNN benchmark k's (comma-separated, e.g., 10,50,250,1000).
-s	--searches	Number of searches (random centers, unless --sequential is set), type all to search over the whole cloud (with sequential indexing).
-t	--repeats	Number of repeats to do for each benchmark.
-k	--kernels	Specify which kernels to use (comma-separated or all). Possible values: sphere, cube, square, circle.
-a	--search-algo	Specify which search algorithms to run (comma-separated or all). Default: neighborsPtr,neighbors,neighborsPrune,neighborsStruct. Possible values: Radius Search:   • neighborsPtr – basic search on pointer-based octree   • neighbors – basic search on linear octree   • neighborsPrune – optimized linear octree search with octant pruning   • neighborsStruct – optimized linear search using index ranges   • neighborsApprox – approximate search (upper/lower bounds), requires --approx-tol   • neighborsUnibn – unibnOctree search   • neighborsPCLKD – PCL KD-tree search (if available)   • neighborsPCLOct – PCL Octree search (if available)   • neighborsPico – PicoTree search KNN Search:   • KNNV2 – linear octree KNN searches   • KNNNanoflann – nanoflann KNN searches   • KNNPCLKD – PCL KD-tree KNN search (if available)   • KNNPCLOCT – PCL Octree KNN search (if available)   • KNNPico – PicoTree KNN search
-e	--encodings	Select SFC encodings to reorder the cloud before the searches (comma-separated or all). Default: all. Possible values:   • none – no encoding, Linear Octree won't be built with it   • mort – Morton SFC Reordering   • hilb – Hilbert SFC Reordering
–	--debug	Enable debug mode (measures octree build and encoding times).
–	--build-enc	Run benchmarks for the encoding and build of selected structures (the ones with a representative on -a / --search-algo).
–	--memory	Run a simple benchmark for measuring the memory consumed by a structure for heap profiling. Possible values: ptrOct, linOct, unibnOct, nanoKD, pclOct, pclKD, picoTree.
–	--locality	Run benchmarks for analyzing the locality of the point cloud after given reorderings.
–	--cache-profiling	Enable cache profiling during search algo executions using PAPI.
–	--check	Enable result checking (legacy option; use avg_result_size to verify correctness).
–	--no-warmup	Disable warmup phase.
–	--approx-tol	Tolerance values for approximate search (comma-separated e.g., 10.0,50.0,100.0).
–	--num-threads	List of thread counts for scalability test (comma-separated e.g., 1,2,4,8,16,32). If not specified, OpenMP defaults to maximum threads and no scalability test is run.
–	--sequential	Make the search set sequential instead of random (usually faster). Automatically set when -s all is used.
–	--max-leaf	Max number of points per octree leaf (default = 128). Does not apply to PCL Octree.
–	--pcl-oct-resolution	Min octant size for subdivision in PCL Octree.

Authorship

Grupo de Arquitectura de Computadores (GAC)
Centro Singular de Investigación en Tecnologías Inteligentes (CiTIUS)
Universidad de Santiago de Compostela (USC)

Linear octree implementation, SFCs, benchmarking and plotting code from:

• Pablo Díaz Viñambres (pablo.diaz.vinambres@rai.usc.es)

Optimized search algorithm and vectorization of SFC encoders:

• Abel Rodríguez Calleja (GitHub profile)

Original pointer-based Octree, readers and program structure from:

• Miguel Yermo García (miguel.yermo@usc.es)
• Silvia Rodríguez Alcaraz (silvia.alcaraz@usc.es)