-
Notifications
You must be signed in to change notification settings - Fork 7
Performance Spatial Tree 3d Performance
github-actions[bot] edited this page Jan 26, 2026
·
6 revisions
- 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.
- 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)
| 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 | 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 | 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 | 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 |
| 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 | 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 | 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 | 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 |
| 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 | 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 | 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 | 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 |
| 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 | 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 | 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 | 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 |
| 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 | 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 | 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 | 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 |
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
📦 Unity Helpers | 📖 Documentation | 🐛 Issues | 📜 MIT License
- Inspector Button
- Inspector Conditional Display
- Inspector Grouping Attributes
- Inspector Inline Editor
- Inspector Overview
- Inspector Selection Attributes
- Inspector Settings
- Inspector Validation Attributes
- Utility Components
- Visual Components
- Data Structures
- Helper Utilities
- Math And Extensions
- Pooling Guide
- Random Generators
- Reflection Helpers
- Singletons