3D Spatial Tree Performance Benchmarks 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)
Construction
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
1,000,000 entries 3 (0.262s) 6 (0.153s) 2 (0.352s) 3 (0.294s)
Elements In Range
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (~span/2) (r=49.50) 20 24 33 17 Half (~span/4) (r=24.75) 152 187 263 169 Quarter (~span/8) (r=12.38) 1,032 1,358 1,668 1,502 Tiny (~span/1000) (r=1) 23,725 23,819 133,282 71,954
Get Elements In Bounds
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (size≈99.00x99.00x99.00) 35 40 233 24 Half (size≈49.50x49.50x49.50) 48 56 1,241 278 Quarter (size≈24.75x24.75x24.75) 49 56 3,651 2,511 Unit (size=1) 51 52 163,170 73,047
Approximate Nearest Neighbors
Approximate Nearest Neighbors
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
500 neighbors 6,242 10,607 2,321 303 100 neighbors 63,305 72,469 10,872 3,283 10 neighbors 295,644 307,373 15,979 7,236 1 neighbor 336,117 352,619 19,661 8,156
Construction
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
100,000 entries 13 (0.072s) 94 (0.011s) 64 (0.016s) 44 (0.023s)
Elements In Range
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (~span/2) (r=49.50) 385 591 774 211 Half (~span/4) (r=24.75) 1,141 1,732 1,991 838 Quarter (~span/8) (r=12.38) 2,862 4,731 6,020 3,407 Tiny (~span/1000) (r=1) 27,681 31,623 167,236 94,401
Get Elements In Bounds
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (size≈99.00x99.00x9) 624 731 2,794 356 Half (size≈49.50x49.50x4.5) 717 854 8,996 3,486 Quarter (size≈24.75x24.75x2.25) 727 875 43,443 23,687 Unit (size=1) 733 884 211,599 94,890
Approximate Nearest Neighbors
Approximate Nearest Neighbors
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
500 neighbors 6,943 12,516 1,654 269 100 neighbors 39,660 45,252 9,316 2,180 10 neighbors 323,237 260,287 19,047 7,206 1 neighbor 332,074 263,010 29,490 11,252
Construction
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
10,000 entries 123 (0.008s) 773 (0.001s) 597 (0.002s) 433 (0.002s)
Elements In Range
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (~span/2) (r=49.50) 4,887 5,106 9,173 2,188 Half (~span/4) (r=24.75) 6,293 7,075 9,001 4,230 Quarter (~span/8) (r=12.38) 6,291 7,455 11,198 7,437 Tiny (~span/1000) (r=1) 41,933 39,762 207,044 143,782
Get Elements In Bounds
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (size≈99.00x9x9) 6,244 6,165 28,264 3,509 Half (size≈49.50x4.5x4.5) 7,000 6,986 42,239 35,660 Quarter (size≈24.75x2.25x2.25) 7,125 7,161 149,019 111,164 Unit (size=1) 7,204 7,177 274,570 146,522
Approximate Nearest Neighbors
Approximate Nearest Neighbors
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
500 neighbors 10,178 11,176 636 185 100 neighbors 48,653 69,038 5,954 2,208 10 neighbors 228,792 322,319 26,632 12,390 1 neighbor 346,732 403,633 43,798 20,882
Construction
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
1,000 entries 5,027 (0.000s) 7,342 (0.000s) 4,194 (0.000s) 3,855 (0.000s)
Elements In Range
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (~span/2) (r=4.5) 13,216 15,836 24,528 21,168 Half (~span/4) (r=2.25) 54,776 65,071 119,223 134,932 Quarter (~span/8) (r=1.13) 63,672 66,530 305,884 197,776 Tiny (~span/1000) (r=1) 63,668 66,291 306,143 196,875
Get Elements In Bounds
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (size≈9x9x9) 56,539 60,422 289,848 34,779 Half (size≈4.5x4.5x4.5) 59,917 65,887 172,693 158,343 Quarter (size≈2.25x2.25x2.25) 60,874 67,913 408,245 202,987 Unit (size=1) 60,594 68,914 408,355 202,835
Approximate Nearest Neighbors
Approximate Nearest Neighbors
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
500 neighbors 16,594 15,570 3,265 616 100 neighbors 69,991 66,103 15,462 4,020 10 neighbors 324,837 305,601 70,301 29,522 1 neighbor 399,134 428,885 78,576 38,531
Construction
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
100 entries 36,363 (0.000s) 39,062 (0.000s) 28,409 (0.000s) 11,389 (0.000s)
Elements In Range
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (~span/2) (r=4.5) 134,264 133,125 268,794 173,242 Half (~span/4) (r=2.25) 155,435 157,119 287,851 244,592 Quarter (~span/8) (r=1.13) 156,564 158,685 347,661 328,932 Tiny (~span/1000) (r=1) 155,612 158,148 350,184 329,295
Get Elements In Bounds
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
Full (size≈9x4x1) 445,137 442,162 1,133,386 269,238 Half (size≈4.5x2x1) 456,470 460,381 413,163 351,246 Quarter (size≈2.25x1x1) 470,424 465,685 581,178 493,257 Unit (size=1) 469,798 465,875 578,881 473,813
Approximate Nearest Neighbors
Approximate Nearest Neighbors
KDTree3D (Balanced)
KDTree3D (Unbalanced)
OctTree3D
RTree3D
100 neighbors (max) 87,276 85,347 63,437 65,384 10 neighbors 361,756 369,204 94,888 82,476 1 neighbor 504,598 421,747 150,382 156,721
All numbers represent operations per second (higher is better), except for construction times which show operations per second and absolute time.
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
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