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 2 (0.340s) 5 (0.193s) 2 (0.443s) 1 (0.560s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 30 33 32 14 Half (~span/4) (r=24.75) 258 288 251 161 Quarter (~span/8) (r=12.38) 1,878 2,274 1,747 1,567 Tiny (~span/1000) (r=1) 68,467 68,902 140,371 70,584
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x99.00) 32 35 197 18 Half (size≈49.50x49.50x49.50) 44 49 1,121 279 Quarter (size≈24.75x24.75x24.75) 45 52 3,249 2,901 Unit (size=1) 48 53 146,797 72,976
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 14,952 31,212 2,559 1,285 100 neighbors 158,435 175,623 12,733 6,641 10 neighbors 488,977 323,353 18,726 9,150 1 neighbor 555,407 278,327 22,921 9,414
100,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100,000 entries 42 (0.024s) 80 (0.012s) 56 (0.018s) 27 (0.036s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 412 489 642 213 Half (~span/4) (r=24.75) 1,464 1,876 1,920 836 Quarter (~span/8) (r=12.38) 4,746 7,000 6,304 3,454 Tiny (~span/1000) (r=1) 74,640 83,016 182,424 94,286
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x99.00x9) 587 726 2,580 399 Half (size≈49.50x49.50x4.5) 673 847 8,002 4,047 Quarter (size≈24.75x24.75x2.25) 683 855 38,898 27,884 Unit (size=1) 706 836 190,116 96,833
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 22,842 37,790 1,826 1,170 100 neighbors 111,561 118,529 10,595 4,356 10 neighbors 548,563 443,954 22,855 8,878 1 neighbor 553,853 392,851 35,431 13,695
10,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 10,000 entries 519 (0.002s) 596 (0.002s) 545 (0.002s) 320 (0.003s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=49.50) 4,295 4,316 6,192 2,171 Half (~span/4) (r=24.75) 7,371 7,900 7,999 4,246 Quarter (~span/8) (r=12.38) 10,441 12,003 12,626 7,274 Tiny (~span/1000) (r=1) 116,107 110,829 240,202 143,509
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈99.00x9x9) 6,021 5,941 24,715 4,112 Half (size≈49.50x4.5x4.5) 6,889 6,760 37,847 42,414 Quarter (size≈24.75x2.25x2.25) 6,869 6,894 136,372 118,433 Unit (size=1) 6,944 7,020 261,198 148,865
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 28,062 29,396 638 858 100 neighbors 130,380 170,968 6,926 5,238 10 neighbors 494,527 428,416 35,432 16,135 1 neighbor 608,641 604,545 55,460 25,402
1,000 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 1,000 entries 4,191 (0.000s) 5,927 (0.000s) 3,631 (0.000s) 3,231 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 28,247 31,777 29,009 22,421 Half (~span/4) (r=2.25) 141,701 167,956 149,245 138,145 Quarter (~span/8) (r=1.13) 171,864 177,662 358,881 199,969 Tiny (~span/1000) (r=1) 171,026 175,651 358,054 197,144
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x9x9) 55,367 60,588 231,924 42,034 Half (size≈4.5x4.5x4.5) 60,826 64,675 158,172 166,422 Quarter (size≈2.25x2.25x2.25) 59,881 65,929 383,738 208,592 Unit (size=1) 61,340 67,222 383,240 209,228
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 500 neighbors 34,915 37,952 3,499 2,843 100 neighbors 153,489 165,612 18,697 13,630 10 neighbors 536,964 398,357 93,470 44,258 1 neighbor 640,037 650,403 104,003 55,357
100 entries Construction Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 entries 38,759 (0.000s) 10,030 (0.000s) 24,213 (0.000s) 15,698 (0.000s)
Elements In Range Elements In Range KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (~span/2) (r=4.5) 266,801 266,250 302,534 192,410 Half (~span/4) (r=2.25) 341,789 349,460 356,948 281,973 Quarter (~span/8) (r=1.13) 346,927 326,452 425,838 359,988 Tiny (~span/1000) (r=1) 340,885 355,813 433,093 358,502
Get Elements In Bounds Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D Full (size≈9x4x1) 479,348 475,542 1,205,263 322,799 Half (size≈4.5x2x1) 491,498 501,104 391,708 381,900 Quarter (size≈2.25x1x1) 498,882 495,579 549,227 536,053 Unit (size=1) 491,599 486,230 548,382 528,585
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D 100 neighbors (max) 192,205 196,614 109,799 155,845 10 neighbors 615,894 563,599 139,741 217,289 1 neighbor 625,397 641,929 212,152 352,882
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