Skip to content

spatial-tree-3d-performance.md

Latest commit

 

History

History
462 lines (393 loc) · 20 KB

spatial-tree-3d-performance.md

File metadata and controls

462 lines (393 loc) · 20 KB

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 3D
  • KdTree3D - Balanced and unbalanced variants available
  • RTree3D - Optimized for 3D bounding box queries
  • SpatialHash3D - Efficient for uniformly distributed moving objects (stable)

Performance Benchmarks

Datasets

1,000,000 entries

Construction
Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
1,000,000 entries3 (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)20223214
Half (~span/4) (r=24.75)149152250140
Quarter (~span/8) (r=12.38)9751,0961,6151,095
Tiny (~span/1000) (r=1)7,0644,7337,8884,196
Get Elements In Bounds
Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
Full (size≈99.00x99.00x99.00)333719920
Half (size≈49.50x49.50x49.50)44491,078242
Quarter (size≈24.75x24.75x24.75)47532,1031,303
Unit (size=1)48535,5232,789
Approximate Nearest Neighbors
Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
500 neighbors2,7171,6361,585289
100 neighbors2,9801,8492,9681,958
10 neighbors1,9441,8961,8952,512
1 neighbor1,9521,9461,7701,659

100,000 entries

Construction
Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
100,000 entries49 (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)358498688173
Half (~span/4) (r=24.75)8921,3201,509573
Quarter (~span/8) (r=12.38)1,8042,5892,9581,466
Tiny (~span/1000) (r=1)4,8434,9535,6732,832
Get Elements In Bounds
Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
Full (size≈99.00x99.00x9)5456371,908303
Half (size≈49.50x49.50x4.5)6257343,4931,480
Quarter (size≈24.75x24.75x2.25)6357505,1062,543
Unit (size=1)6427525,5902,829
Approximate Nearest Neighbors
Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
500 neighbors1,4961,666871239
100 neighbors1,8671,8191,6071,044
10 neighbors1,9341,8741,7701,530
1 neighbor1,8931,8991,8301,660

10,000 entries

Construction
Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
10,000 entries602 (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,7522,6823,3421,113
Half (~span/4) (r=24.75)3,0103,0733,4581,576
Quarter (~span/8) (r=12.38)3,0053,2513,7441,993
Tiny (~span/1000) (r=1)5,0395,1345,5282,789
Get Elements In Bounds
Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
Full (size≈99.00x9x9)2,9122,9884,7991,516
Half (size≈49.50x4.5x4.5)3,1753,1665,0282,635
Quarter (size≈24.75x2.25x2.25)3,1703,1865,3572,722
Unit (size=1)3,2143,1975,7022,771
Approximate Nearest Neighbors
Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
500 neighbors1,6141,629456161
100 neighbors1,8711,8621,4001,015
10 neighbors1,9171,9001,7211,638
1 neighbor1,9421,8901,8201,751

1,000 entries

Construction
Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
1,000 entries5,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,0084,2044,6872,445
Half (~span/4) (r=2.25)5,1465,3415,4972,805
Quarter (~span/8) (r=1.13)5,3105,3335,6472,851
Tiny (~span/1000) (r=1)5,2165,2455,6942,866
Get Elements In Bounds
Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
Full (size≈9x9x9)5,2345,2225,6752,649
Half (size≈4.5x4.5x4.5)5,1355,3445,5842,832
Quarter (size≈2.25x2.25x2.25)5,1625,3435,7452,877
Unit (size=1)5,2405,3815,7662,879
Approximate Nearest Neighbors
Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
500 neighbors1,7081,6971,174462
100 neighbors1,8591,8681,7051,263
10 neighbors1,9191,9241,8621,765
1 neighbor1,9361,9391,8501,829

100 entries

Construction
Construction KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
100 entries42,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,5875,6015,7022,837
Half (~span/4) (r=2.25)5,6235,6255,7072,873
Quarter (~span/8) (r=1.13)5,6155,6185,7042,889
Tiny (~span/1000) (r=1)5,5925,6235,7122,886
Get Elements In Bounds
Get Elements In Bounds KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
Full (size≈9x4x1)5,7655,7815,8122,853
Half (size≈4.5x2x1)5,7805,7775,6882,868
Quarter (size≈2.25x1x1)5,7635,7515,7482,911
Unit (size=1)5,7525,7635,7982,916
Approximate Nearest Neighbors
Approximate Nearest Neighbors KDTree3D (Balanced) KDTree3D (Unbalanced) OctTree3D RTree3D
100 neighbors (max)1,8661,8831,8651,869
10 neighbors1,9451,9211,9001,880
1 neighbor1,9391,9391,8991,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