TL;DR — What Problem This Solves Need fast “what’s near X?” or “what’s inside this volume?” in 3D. These structures avoid scanning every object; queries touch only nearby data. Quick picks: OctTree3D for general 3D queries; KdTree3D for nearest‑neighbor on points; RTree3D for volumetric bounds. Note: KdTree3D, OctTree3D, and RTree3D are under active development and their APIs/performance may evolve. SpatialHash3D is stable and recommended for broad‑phase neighbor queries with many moving objects.
For boundary and result semantics across structures, see Spatial Tree Semantics
This document contains performance benchmarks for the 3D spatial tree implementations in Unity Helpers.
Available 3D Spatial Trees OctTree3D - Easiest to use, good all-around performance for 3DKdTree3D - Balanced and unbalanced variants availableRTree3D - Optimized for 3D bounding box queriesSpatialHash3D - Efficient for uniformly distributed moving objects (stable) Datasets 1,000,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 1,000,000 entries 3 (0.260s) 5 (0.168s) 1 (0.515s) 3 (0.314s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 20 22 32 14 Half (~span/4) (r=24.75) 149 152 250 140 Quarter (~span/8) (r=12.38) 975 1,096 1,615 1,095 Tiny (~span/1000) (r=1) 7,064 4,733 7,888 4,196
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x99.00) 33 37 199 20 Half (size≈49.50x49.50x49.50) 44 49 1,078 242 Quarter (size≈24.75x24.75x24.75) 47 53 2,103 1,303 Unit (size=1) 48 53 5,523 2,789
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 2,717 1,636 1,585 289 100 neighbors 2,980 1,849 2,968 1,958 10 neighbors 1,944 1,896 1,895 2,512 1 neighbor 1,952 1,946 1,770 1,659
100,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100,000 entries 49 (0.020s) 97 (0.010s) 61 (0.016s) 42 (0.024s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 358 498 688 173 Half (~span/4) (r=24.75) 892 1,320 1,509 573 Quarter (~span/8) (r=12.38) 1,804 2,589 2,958 1,466 Tiny (~span/1000) (r=1) 4,843 4,953 5,673 2,832
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x9) 545 637 1,908 303 Half (size≈49.50x49.50x4.5) 625 734 3,493 1,480 Quarter (size≈24.75x24.75x2.25) 635 750 5,106 2,543 Unit (size=1) 642 752 5,590 2,829
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 1,496 1,666 871 239 100 neighbors 1,867 1,819 1,607 1,044 10 neighbors 1,934 1,874 1,770 1,530 1 neighbor 1,893 1,899 1,830 1,660
10,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 10,000 entries 602 (0.002s) 742 (0.001s) 577 (0.002s) 447 (0.002s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 2,752 2,682 3,342 1,113 Half (~span/4) (r=24.75) 3,010 3,073 3,458 1,576 Quarter (~span/8) (r=12.38) 3,005 3,251 3,744 1,993 Tiny (~span/1000) (r=1) 5,039 5,134 5,528 2,789
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x9x9) 2,912 2,988 4,799 1,516 Half (size≈49.50x4.5x4.5) 3,175 3,166 5,028 2,635 Quarter (size≈24.75x2.25x2.25) 3,170 3,186 5,357 2,722 Unit (size=1) 3,214 3,197 5,702 2,771
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 1,614 1,629 456 161 100 neighbors 1,871 1,862 1,400 1,015 10 neighbors 1,917 1,900 1,721 1,638 1 neighbor 1,942 1,890 1,820 1,751
1,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 1,000 entries 5,192 (0.000s) 6,939 (0.000s) 2,725 (0.000s) 3,868 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 4,008 4,204 4,687 2,445 Half (~span/4) (r=2.25) 5,146 5,341 5,497 2,805 Quarter (~span/8) (r=1.13) 5,310 5,333 5,647 2,851 Tiny (~span/1000) (r=1) 5,216 5,245 5,694 2,866
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x9x9) 5,234 5,222 5,675 2,649 Half (size≈4.5x4.5x4.5) 5,135 5,344 5,584 2,832 Quarter (size≈2.25x2.25x2.25) 5,162 5,343 5,745 2,877 Unit (size=1) 5,240 5,381 5,766 2,879
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 1,708 1,697 1,174 462 100 neighbors 1,859 1,868 1,705 1,263 10 neighbors 1,919 1,924 1,862 1,765 1 neighbor 1,936 1,939 1,850 1,829
100 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 entries 42,016 (0.000s) 37,593 (0.000s) 14,662 (0.000s) 13,927 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 5,587 5,601 5,702 2,837 Half (~span/4) (r=2.25) 5,623 5,625 5,707 2,873 Quarter (~span/8) (r=1.13) 5,615 5,618 5,704 2,889 Tiny (~span/1000) (r=1) 5,592 5,623 5,712 2,886
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x4x1) 5,765 5,781 5,812 2,853 Half (size≈4.5x2x1) 5,780 5,777 5,688 2,868 Quarter (size≈2.25x1x1) 5,763 5,751 5,748 2,911 Unit (size=1) 5,752 5,763 5,798 2,916
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 neighbors (max) 1,866 1,883 1,865 1,869 10 neighbors 1,945 1,921 1,900 1,880 1 neighbor 1,939 1,939 1,899 1,898
Interpreting the Results All numbers represent operations per second (higher is better), except for construction times which show operations per second and absolute time.
Choosing the Right Tree OctTree3D :
Best for: General-purpose 3D spatial queries Strengths: Balanced performance, easy to use, good spatial locality Use cases: 3D collision detection, visibility culling, spatial audio KdTree3D (Balanced) :
Best for: Nearest-neighbor queries in 3D space Strengths: Fast point queries, good for smaller datasets Use cases: Pathfinding, AI spatial awareness, particle systems KdTree3D (Unbalanced) :
Best for: When you need fast construction and will rebuild frequently Strengths: Fastest construction, similar query performance to balanced Use cases: Dynamic environments, frequently changing spatial data RTree3D :
Best for: 3D bounding box queries, especially with volumetric data Strengths: Excellent for large bounding volumes, handles overlapping objects Use cases: Physics engines, frustum culling, volumetric effects Important Notes All spatial trees assume immutable positional data If positions change, you must reconstruct the tree Spatial queries are O(log n) vs O(n) for linear search 3D trees have higher construction costs than 2D variants due to additional dimension Construction cost is amortized over many queries