Struct ScyllaKDTree3Core

Burst/DOTS-friendly core implementation of a 3D KD-tree for nearest-neighbor and radius queries.

Implements

IDisposable

Inherited Members

ValueType.Equals(object)

ValueType.GetHashCode()

ValueType.ToString()

object.Equals(object, object)

object.GetType()

object.ReferenceEquals(object, object)

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

[BurstCompile]
public struct ScyllaKDTree3Core : IDisposable

Remarks

Memory Layout:

Nodes are stored in a contiguous Unity.Collections.NativeList<T> array in pre-order traversal layout after a Build(NativeArray<int>, NativeArray<float3>) call. Each ScyllaKDTree3Core.Node's PointIndex field is an index into the parallel _points and _itemIDs arrays, keeping all data flat and cache-friendly.

Tree Construction:

The tree is built iteratively (no recursion) using median splitting along the axis with the greatest point-cloud extent, producing a balanced tree with deterministic structure for identical inputs.

Query Traversal:

All queries are iterative and use a stack-local Unity.Collections.FixedList4096Bytes<T> to avoid heap allocations. The far child of each split is pruned whenever its splitting-plane distance exceeds the current best threshold, reducing the number of nodes visited.

Ownership and Thread Safety:

This struct owns native containers. Always call Dispose() when done to prevent memory leaks. Not thread-safe; do not query or modify concurrently from multiple threads without external synchronization.

Managed Wrapper:

For parameter validation, dispose safety, and framework integration, prefer ScyllaKDTree3. Use this struct directly only in Burst-compiled jobs or other performance-critical paths.

Constructors

ScyllaKDTree3Core(Allocator, int, int)

Creates a new KD-tree core instance and allocates all required native containers.

Declaration

public ScyllaKDTree3Core(Allocator allocator, int initialPointCapacity = 64, int initialNodeCapacity = 128)

Parameters

Type	Name	Description
Allocator	allocator	Allocator used for all internal native containers. Must not be Unity.Collections.Allocator.None.
int	initialPointCapacity	Initial capacity hint for point and item ID storage. Clamped to a minimum of 1.
int	initialNodeCapacity	Initial capacity hint for node storage. Clamped to a minimum of 1.

Remarks

Allocates three native containers using the specified allocator:

_nodes - flat node array pre-sized to initialNodeCapacity.
_points - point coordinate array pre-sized to initialPointCapacity.
_itemIDs - item ID array pre-sized to initialPointCapacity.

Both capacity parameters are clamped to a minimum of 1 to ensure valid initial container sizes. After construction, IsCreated returns true. Always call Dispose() when done.

Exceptions

Type	Condition
ArgumentException	Thrown when `allocator` is Unity.Collections.Allocator.None.

Properties

Count

Number of points currently stored.

Declaration

public int Count { get; }

Property Value

Type	Description
int

IsCreated

Returns true if this core has allocated its native containers.

Declaration

public bool IsCreated { get; }

Property Value

Type	Description
bool

Methods

Build(NativeArray<int>, NativeArray<float3>)

Bulk builds the KD-tree from arrays of item IDs and point positions.

Declaration

public void Build(NativeArray<int> itemIDs, NativeArray<float3> points)

Parameters

Type	Name	Description
NativeArray<int>	itemIDs	Item identifiers; `itemIDs[i]` is the caller-defined ID for `points[i]`. Must have the same length as `points`.
NativeArray<float3>	points	Point positions in 3D space. All components must be finite (no NaN or Infinity).

Remarks

Clears any existing tree state, then constructs a new balanced KD-tree using a top-down median-split strategy. The algorithm:

Copies all points and item IDs into internal storage after validating finiteness.
Iteratively pops subtask ranges from a temporary stack. For each range, selects the split axis with the largest point-cloud extent (ChooseAxisByExtent(NativeArray<int>, int, int)) and places the median point at its final position via Quickselect(NativeArray<int>, int, int, int, byte).
Pushes the left subtree (indices before median) and right subtree (indices after median) for subsequent processing. Right is pushed before left so the left subtree is processed first (LIFO), producing a deterministic pre-order node layout in _nodes.
Shrinks _nodes to the exact node count after the build completes.

The temporary build stack and index buffer are allocated with Unity.Collections.Allocator.Temp and disposed in a finally block, so the method is safe even if an exception is thrown.

Precondition: itemIDs and points must have the same length. If they differ, behavior is undefined - the managed wrapper ScyllaKDTree3 enforces this with an explicit check before calling this method.

Exceptions

Type	Condition
ArgumentException	Thrown when any element in `points` contains a non-finite component (NaN or Infinity).

Clear()

Removes all points and nodes from the KD-tree (does not deallocate).

Declaration

public void Clear()

Dispose()

Disposes all native containers owned by this core and releases their unmanaged memory.

Declaration

public void Dispose()

Remarks

Disposes the following native containers (each is guarded by an Unity.Collections.NativeList<T>.IsCreated check to handle partially-initialized or default-struct instances safely):

_nodes - the flat node array.
_points - the point coordinate array.
_itemIDs - the item ID array.

After disposal, IsCreated returns false and all further method calls will throw ObjectDisposedException or InvalidOperationException. It is safe to call Dispose() multiple times; subsequent calls are no-ops.

FindKNearest(float3, int, NativeList<int>, NativeList<float>)

Finds the k nearest neighbors (k-NN) to queryPoint.

Declaration

public int FindKNearest(float3 queryPoint, int k, NativeList<int> results, NativeList<float> distances)

Parameters

Type	Name	Description
float3	queryPoint	Query point in 3D space.
int	k	Maximum number of neighbors to return. Must be at least 1.
NativeList<int>	results	Destination list for item IDs. Cleared before writing. On return, contains up to `min(k, Count)` item IDs.
NativeList<float>	distances	Destination list for Euclidean distances. Cleared before writing. Parallel to `results`.

Returns

Type	Description
int	The number of results written into `results` and `distances`.

Remarks

Uses an iterative traversal with an in-place max-heap bounded to k entries. The heap is stored in the caller-supplied results and distances lists (as parallel arrays) and ordered so that the heap root is always the worst (farthest) candidate currently accepted. This allows O(log k) replacement of the worst candidate when a closer point is found.

Subtree pruning works identically to TryFindNearest(float3, out int, out float): the far child of each split is skipped when its splitting-plane distance squared exceeds the worst accepted distance squared. When fewer than k candidates have been found, the threshold is PositiveInfinity (no pruning).

If the tree contains fewer than k points, all points are returned. Results are sorted by ascending distance, then ascending item ID, before returning. Distances in the output lists are Euclidean (L2) distances, not squared.

Exceptions

Type	Condition
ArgumentOutOfRangeException	Thrown when `k` is less than 1.
ArgumentNullException	Thrown when `results` or `distances` is not created.

QueryRadius(float3, float, NativeList<int>, NativeList<float>)

Queries all points within radius of queryPoint, returning them sorted by ascending distance, then ascending item ID.

Declaration

public int QueryRadius(float3 queryPoint, float radius, NativeList<int> results, NativeList<float> distances)

Parameters

Type	Name	Description
float3	queryPoint	Query point in 3D space.
float	radius	Search radius. Must be non-negative. Points at exactly this distance are included.
NativeList<int>	results	Destination list for item IDs. Cleared before writing. On return, contains all items within `radius`.
NativeList<float>	distances	Destination list for Euclidean distances. Cleared before writing. Parallel to `results`.

Returns

Type	Description
int	The number of results written into `results` and `distances`.

Remarks

Uses an iterative traversal backed by a Unity.Collections.FixedList4096Bytes<T> stack (no heap allocations). At each node the algorithm:

Tests whether the node's point falls within the radius using squared distance to avoid a sqrt.
Determines the near/far child split on the node's axis. The far child is only enqueued when its splitting-plane squared distance is within radiusSq, pruning subtrees that are entirely outside the search sphere.

All accepted squared distances are converted to Euclidean distances via sqrt before returning. Results are sorted by ascending distance, then ascending item ID, for deterministic output. A radius of 0 is valid and returns only points that are exactly coincident with queryPoint.

Exceptions

Type	Condition
ArgumentOutOfRangeException	Thrown when `radius` is negative.
ArgumentNullException	Thrown when `results` or `distances` is not created.

TryFindNearest(float3, out int, out float)

Attempts to find the single nearest neighbor (1-NN) to queryPoint.

Declaration

public bool TryFindNearest(float3 queryPoint, out int itemID, out float distance)

Parameters

Type	Name	Description
float3	queryPoint	Query point in 3D space.
int	itemID	When this method returns, contains the nearest item ID if a point was found; otherwise 0.
float	distance	When this method returns, contains the Euclidean distance to the nearest point if found; otherwise 0.

Returns

Type	Description
bool	`true` if a nearest neighbor was found; `false` if the tree is empty.

Remarks

Uses an iterative best-first traversal backed by a Unity.Collections.FixedList4096Bytes<T> stack (no heap allocations). At each node the algorithm:

Evaluates the node's stored point and updates the best candidate if closer (or ties on item ID).
Determines the near and far child relative to queryPoint on the node's split axis. The far child is only enqueued when its splitting plane is within the current best distance (deltaSq <= bestDistSq), pruning entire subtrees that cannot improve the result.
The near child is always enqueued (if present) since it is guaranteed to be closer to the split plane.

Tie-breaking between points at equal squared distance is deterministic: the point with the smaller item ID is preferred. Distance in the output is the Euclidean (L2) distance, not squared.

Implements

IDisposable