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.258s) 6 (0.154s) 2 (0.386s) 3 (0.297s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 20 23 29 14 Half (~span/4) (r=24.75) 151 166 164 116 Quarter (~span/8) (r=12.38) 1,024 1,260 1,550 1,286 Tiny (~span/1000) (r=1) 23,627 22,558 130,696 72,437
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x99.00) 30 35 172 20 Half (size≈49.50x49.50x49.50) 40 48 1,270 218 Quarter (size≈24.75x24.75x24.75) 40 51 3,601 2,338 Unit (size=1) 42 53 161,979 70,789
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 6,071 10,425 2,251 301 100 neighbors 63,996 71,939 10,430 3,189 10 neighbors 295,220 302,020 15,148 6,980 1 neighbor 326,786 340,479 18,325 7,588
100,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100,000 entries 49 (0.020s) 97 (0.010s) 63 (0.016s) 8 (0.120s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 381 592 769 176 Half (~span/4) (r=24.75) 1,135 1,650 1,860 727 Quarter (~span/8) (r=12.38) 2,814 4,499 5,946 3,021 Tiny (~span/1000) (r=1) 26,910 30,212 163,640 93,042
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x9) 597 688 3,044 352 Half (size≈49.50x49.50x4.5) 674 850 8,858 3,459 Quarter (size≈24.75x24.75x2.25) 710 870 42,334 23,513 Unit (size=1) 728 880 208,362 92,740
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 6,826 12,399 1,582 266 100 neighbors 39,102 44,932 8,701 2,065 10 neighbors 320,222 258,261 18,061 6,748 1 neighbor 329,497 259,583 27,859 10,618
10,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 10,000 entries 232 (0.004s) 776 (0.001s) 599 (0.002s) 435 (0.002s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 5,010 5,079 9,139 1,721 Half (~span/4) (r=24.75) 6,250 7,021 8,493 3,453 Quarter (~span/8) (r=12.38) 6,336 7,326 10,677 6,600 Tiny (~span/1000) (r=1) 42,213 38,535 199,646 142,424
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x9x9) 6,158 6,040 31,575 3,564 Half (size≈49.50x4.5x4.5) 6,862 6,784 41,741 36,487 Quarter (size≈24.75x2.25x2.25) 7,035 7,114 147,595 111,575 Unit (size=1) 6,857 7,135 273,980 147,480
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 9,990 10,905 633 181 100 neighbors 49,033 67,725 5,928 2,087 10 neighbors 222,009 313,530 25,978 11,079 1 neighbor 352,912 395,316 42,060 18,631
1,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 1,000 entries 5,047 (0.000s) 7,017 (0.000s) 4,221 (0.000s) 4,056 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 13,309 15,407 24,555 19,376 Half (~span/4) (r=2.25) 54,631 64,832 119,069 122,189 Quarter (~span/8) (r=1.13) 63,809 66,230 302,733 190,679 Tiny (~span/1000) (r=1) 63,925 66,775 297,025 189,076
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x9x9) 56,025 60,364 285,851 34,830 Half (size≈4.5x4.5x4.5) 60,435 65,721 167,043 160,053 Quarter (size≈2.25x2.25x2.25) 60,892 67,241 408,947 203,923 Unit (size=1) 60,859 66,633 408,812 205,130
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 15,079 15,221 3,229 617 100 neighbors 66,517 65,354 15,372 3,961 10 neighbors 326,664 303,344 69,259 27,619 1 neighbor 372,951 425,921 78,021 35,781
100 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 entries 38,461 (0.000s) 36,496 (0.000s) 26,178 (0.000s) 18,552 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 128,838 126,647 268,664 156,643 Half (~span/4) (r=2.25) 132,912 157,069 283,144 241,941 Quarter (~span/8) (r=1.13) 155,589 157,614 341,201 328,411 Tiny (~span/1000) (r=1) 156,184 155,346 349,424 328,728
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x4x1) 444,834 441,395 1,132,436 267,317 Half (size≈4.5x2x1) 458,537 464,441 413,889 347,753 Quarter (size≈2.25x1x1) 468,261 464,503 578,248 476,261 Unit (size=1) 469,295 459,734 573,732 477,462
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 neighbors (max) 87,622 81,758 60,944 57,383 10 neighbors 381,364 355,350 93,401 74,007 1 neighbor 439,990 402,016 146,308 149,981
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