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	3 (0.256s)	6 (0.153s)	4 (0.238s)	2 (0.382s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	20	24	34	16
Half (~span/4) (r=24.75)	151	188	260	156
Quarter (~span/8) (r=12.38)	1,028	1,374	1,682	1,467
Tiny (~span/1000) (r=1)	23,737	23,914	133,257	72,647

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x99.00x99.00)	35	42	228	24
Half (size≈49.50x49.50x49.50)	49	57	1,209	284
Quarter (size≈24.75x24.75x24.75)	51	58	3,618	2,523
Unit (size=1)	52	60	162,557	73,981

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	6,154	10,636	2,320	304
100 neighbors	65,120	72,381	10,891	3,340
10 neighbors	261,874	302,986	15,976	7,609
1 neighbor	381,614	313,660	19,656	8,296

100,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100,000 entries	50 (0.020s)	98 (0.010s)	64 (0.015s)	8 (0.122s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	386	597	796	217
Half (~span/4) (r=24.75)	1,144	1,749	2,086	850
Quarter (~span/8) (r=12.38)	2,842	4,709	6,047	3,435
Tiny (~span/1000) (r=1)	27,496	31,671	168,945	94,784

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x99.00x9)	623	736	2,630	359
Half (size≈49.50x49.50x4.5)	717	855	9,027	3,487
Quarter (size≈24.75x24.75x2.25)	728	876	43,670	23,965
Unit (size=1)	740	881	212,758	96,799

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	6,992	12,494	1,655	272
100 neighbors	39,589	45,270	9,207	2,236
10 neighbors	317,480	256,693	18,699	7,360
1 neighbor	327,660	262,031	29,513	11,781

10,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
10,000 entries	289 (0.003s)	787 (0.001s)	610 (0.002s)	452 (0.002s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	5,217	5,130	9,221	2,175
Half (~span/4) (r=24.75)	6,217	7,080	8,945	4,209
Quarter (~span/8) (r=12.38)	6,364	7,488	11,223	7,465
Tiny (~span/1000) (r=1)	42,363	39,974	207,069	143,938

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x9x9)	6,245	6,229	27,073	3,589
Half (size≈49.50x4.5x4.5)	6,994	7,036	42,332	36,924
Quarter (size≈24.75x2.25x2.25)	7,134	7,165	148,393	113,215
Unit (size=1)	7,211	7,204	275,229	148,701

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	10,497	11,245	638	185
100 neighbors	48,703	68,760	5,974	2,209
10 neighbors	246,093	328,128	26,618	12,395
1 neighbor	420,534	408,499	43,894	20,887

1,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
1,000 entries	5,107 (0.000s)	7,117 (0.000s)	3,891 (0.000s)	3,972 (0.000s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=4.5)	13,378	15,815	24,439	20,143
Half (~span/4) (r=2.25)	54,916	63,837	119,238	128,411
Quarter (~span/8) (r=1.13)	64,266	66,774	306,084	195,836
Tiny (~span/1000) (r=1)	64,239	66,833	306,092	196,339

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈9x9x9)	56,558	61,009	288,591	35,120
Half (size≈4.5x4.5x4.5)	60,663	66,569	173,235	161,208
Quarter (size≈2.25x2.25x2.25)	61,430	67,553	410,060	205,823
Unit (size=1)	61,371	69,008	408,577	206,353

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	16,331	15,307	3,271	618
100 neighbors	67,919	65,395	15,590	4,017
10 neighbors	299,103	302,785	70,394	29,508
1 neighbor	426,607	422,916	79,102	38,349

100 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100 entries	38,610 (0.000s)	36,101 (0.000s)	26,737 (0.000s)	19,646 (0.000s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=4.5)	133,468	134,274	270,334	166,407
Half (~span/4) (r=2.25)	157,259	157,078	288,266	259,133
Quarter (~span/8) (r=1.13)	156,534	158,490	346,499	329,501
Tiny (~span/1000) (r=1)	155,973	158,478	347,165	330,562

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈9x4x1)	447,338	447,555	1,136,124	273,185
Half (size≈4.5x2x1)	463,043	467,574	412,620	355,479
Quarter (size≈2.25x1x1)	472,263	467,929	582,307	497,201
Unit (size=1)	472,033	468,178	583,276	497,977

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100 neighbors (max)	89,495	86,128	65,050	65,207
10 neighbors	374,582	359,364	96,849	81,157
1 neighbor	508,620	412,021	150,941	156,727

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