Performance Spatial Tree 3d Performance

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 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