compare kdtree and octree
| Criteria | KD-Tree (pcl::search::KdTree) |
Octree (pcl::octree::OctreePointCloudSearch) |
|---|---|---|
| Data Structure | Binary space partitioning (splits along data dimensions) | 3D grid partitioning (divides space into octants) |
| Memory Usage | Lower, adapts to data distribution | Higher, due to uniform grid structure |
| Search Speed (kNN) | Faster for small K (logarithmic time complexity) | Slower for small K (tree traversal overhead) |
| Search Speed (Radius) | Slower for large radius (global query scope) | Faster for large radius (local queries) |
| Performance on Sparse Data | Works well (adaptive splitting) | Wastes memory due to empty octants |
| Performance on Dense Data | Can be slower due to deep recursion | Works well (fixed resolution) |
| Best Use Case | General nearest-neighbor queries, feature estimation | Point cloud compression, normal estimation, voxel grid filtering. reuse the same spatial grid heavily. fast inserts/erases |
fixed-radius neighbor search
For fixed-radius neighbor search, a kd-tree is usually more efficient than an octree for normal estimation, especially in PCL.
Search behavior matches the problem
A kd-tree:
- prunes branches using distance to splitting planes,
- directly minimizes point–query distance checks,
- adapts naturally to non-uniform point distributions.
An octree:
- subdivides space uniformly into voxels,
- does not adapt to density variations,
- may visit many empty or nearly empty nodes unless voxel size is well tuned.
No voxel-resolution tuning
With an octree, performance depends heavily on leaf size:
Too large → too many candidate points per leaf Too small → too many nodes visited
There is no single voxel size that is optimal for all radii and densities.
A kd-tree has no such parameter; it self-balances by construction.
Lower constant factors in PCL
In PCL specifically:
pcl::search::KdTree (FLANN backend) is highly optimized Octree radius search involves: voxel traversal, bounding-box checks, collecting candidate indices before distance filtering
For millions of queries (normals), those constant costs matter more than asymptotic complexity.
downsample dense cloud
step:
- voxel downsample the dense cloud
- for each voxel representative, cache the original points belonging to that voxel
- build an octree on the downsampled cloud
- do radius search on the downsampled cloud
- map the neighbor voxels back to their cached original points
The final step, restoring original points, can give back a lot of the cost. If there are many queries, it’s usually valuable.