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.258s)	6 (0.154s)	2 (0.386s)	3 (0.297s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	20	23	29	14
Half (~span/4) (r=24.75)	151	166	164	116
Quarter (~span/8) (r=12.38)	1,024	1,260	1,550	1,286
Tiny (~span/1000) (r=1)	23,627	22,558	130,696	72,437

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x99.00x99.00)	30	35	172	20
Half (size≈49.50x49.50x49.50)	40	48	1,270	218
Quarter (size≈24.75x24.75x24.75)	40	51	3,601	2,338
Unit (size=1)	42	53	161,979	70,789

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	6,071	10,425	2,251	301
100 neighbors	63,996	71,939	10,430	3,189
10 neighbors	295,220	302,020	15,148	6,980
1 neighbor	326,786	340,479	18,325	7,588

100,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100,000 entries	49 (0.020s)	97 (0.010s)	63 (0.016s)	8 (0.120s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	381	592	769	176
Half (~span/4) (r=24.75)	1,135	1,650	1,860	727
Quarter (~span/8) (r=12.38)	2,814	4,499	5,946	3,021
Tiny (~span/1000) (r=1)	26,910	30,212	163,640	93,042

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x99.00x9)	597	688	3,044	352
Half (size≈49.50x49.50x4.5)	674	850	8,858	3,459
Quarter (size≈24.75x24.75x2.25)	710	870	42,334	23,513
Unit (size=1)	728	880	208,362	92,740

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	6,826	12,399	1,582	266
100 neighbors	39,102	44,932	8,701	2,065
10 neighbors	320,222	258,261	18,061	6,748
1 neighbor	329,497	259,583	27,859	10,618

10,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
10,000 entries	232 (0.004s)	776 (0.001s)	599 (0.002s)	435 (0.002s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=49.50)	5,010	5,079	9,139	1,721
Half (~span/4) (r=24.75)	6,250	7,021	8,493	3,453
Quarter (~span/8) (r=12.38)	6,336	7,326	10,677	6,600
Tiny (~span/1000) (r=1)	42,213	38,535	199,646	142,424

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈99.00x9x9)	6,158	6,040	31,575	3,564
Half (size≈49.50x4.5x4.5)	6,862	6,784	41,741	36,487
Quarter (size≈24.75x2.25x2.25)	7,035	7,114	147,595	111,575
Unit (size=1)	6,857	7,135	273,980	147,480

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	9,990	10,905	633	181
100 neighbors	49,033	67,725	5,928	2,087
10 neighbors	222,009	313,530	25,978	11,079
1 neighbor	352,912	395,316	42,060	18,631

1,000 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
1,000 entries	5,047 (0.000s)	7,017 (0.000s)	4,221 (0.000s)	4,056 (0.000s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=4.5)	13,309	15,407	24,555	19,376
Half (~span/4) (r=2.25)	54,631	64,832	119,069	122,189
Quarter (~span/8) (r=1.13)	63,809	66,230	302,733	190,679
Tiny (~span/1000) (r=1)	63,925	66,775	297,025	189,076

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈9x9x9)	56,025	60,364	285,851	34,830
Half (size≈4.5x4.5x4.5)	60,435	65,721	167,043	160,053
Quarter (size≈2.25x2.25x2.25)	60,892	67,241	408,947	203,923
Unit (size=1)	60,859	66,633	408,812	205,130

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
500 neighbors	15,079	15,221	3,229	617
100 neighbors	66,517	65,354	15,372	3,961
10 neighbors	326,664	303,344	69,259	27,619
1 neighbor	372,951	425,921	78,021	35,781

100 entries

Construction

Construction	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100 entries	38,461 (0.000s)	36,496 (0.000s)	26,178 (0.000s)	18,552 (0.000s)

Elements In Range

Elements In Range	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (~span/2) (r=4.5)	128,838	126,647	268,664	156,643
Half (~span/4) (r=2.25)	132,912	157,069	283,144	241,941
Quarter (~span/8) (r=1.13)	155,589	157,614	341,201	328,411
Tiny (~span/1000) (r=1)	156,184	155,346	349,424	328,728

Get Elements In Bounds

Get Elements In Bounds	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
Full (size≈9x4x1)	444,834	441,395	1,132,436	267,317
Half (size≈4.5x2x1)	458,537	464,441	413,889	347,753
Quarter (size≈2.25x1x1)	468,261	464,503	578,248	476,261
Unit (size=1)	469,295	459,734	573,732	477,462

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree3D (Balanced)	KDTree3D (Unbalanced)	OctTree3D	RTree3D
100 neighbors (max)	87,622	81,758	60,944	57,383
10 neighbors	381,364	355,350	93,401	74,007
1 neighbor	439,990	402,016	146,308	149,981

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