Class ScyllaKDTree3

Burst/DOTS-friendly 3D KD-tree for nearest-neighbor queries over point sets. Items are identified by an int itemID; payload is owned and stored by the caller.

Inheritance
object
ScyllaKDTree3
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public sealed class ScyllaKDTree3 : IScyllaCollection, IDisposable
Remarks
  • This KD-tree is optimized for mostly-static point sets. For dynamic points, rebuild periodically.
  • Thread-safety: unsynchronized by default (matches Scylla collection patterns). Use external synchronization if accessed concurrently.
  • Query methods do not allocate; callers must provide Unity.Collections.NativeList<T> buffers. To avoid allocations inside those buffers, ensure they have sufficient capacity before querying.
  • Determinism:
  • Builds are deterministic given identical inputs.
  • Tie-breaks use smaller itemID when distances (or axis values) are equal.
  • k-NN and radius results are returned sorted by ascending distance, then ascending itemID.
// Direct construction
var kdTree = new ScyllaKDTree3(allocator: Allocator.Persistent);
// Using fluent builder for complex configuration
var kdTree = ScyllaKDTree3.CreateBuilder()
.WithAllocator(Allocator.Persistent)
.WithPointCapacity(256)
.WithNodeCapacity(512)
.Build();

Constructors

ScyllaKDTree3(Allocator, int, int)

Creates a new managed KD-tree instance backed by a ScyllaKDTree3Core.

Declaration
public ScyllaKDTree3(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 minimum 1).
int initialNodeCapacity

Initial capacity hint for node storage (clamped to minimum 1).
Remarks

Delegates allocation entirely to ScyllaKDTree3Core(Allocator, int, int). The instance starts empty; call Build(NativeArray<int>, NativeArray<float3>) to populate the tree from a point set. Use the fluent CreateBuilder() API when multiple configuration parameters need to be set.

Exceptions
Type Condition
ArgumentException

Thrown when allocator is Unity.Collections.Allocator.None.

Properties

Capabilities

Capability flags supported by this collection instance.

Declaration
public ScyllaCollectionCapabilities Capabilities { get; }
Property Value
Type Description
ScyllaCollectionCapabilities

Core

Exposes the underlying Burst-friendly core for job usage.

Declaration
public ScyllaKDTree3Core Core { get; }
Property Value
Type Description
ScyllaKDTree3Core

Count

Number of points currently stored.

Declaration
public int Count { get; }
Property Value
Type Description
int

IsEmpty

Convenience property indicating whether the KD-tree contains no points.

Declaration
public bool IsEmpty { get; }
Property Value
Type Description
bool

SyncRoot

Synchronization root for externally coordinating operations with this collection. For unsynchronized collections this is null.

Declaration
public object SyncRoot { get; }
Property Value
Type Description
object

ThreadSafety

Declares the thread-safety guarantees provided by this collection instance.

Declaration
public ScyllaCollectionThreadSafety ThreadSafety { get; }
Property Value
Type Description
ScyllaCollectionThreadSafety

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 (one per point).
NativeArray<float3> points

Point positions (one per item).
Exceptions
Type Condition
ArgumentException

Thrown when arrays have different lengths.
ArgumentException

Thrown when any point contains non-finite components.

Clear()

Removes all points from the KD-tree.

Declaration
public void Clear()

CreateBuilder()

Creates a new builder instance for configuring a ScyllaKDTree3.

Declaration
public static ScyllaKDTree3.Builder CreateBuilder()
Returns
Type Description
ScyllaKDTree3.Builder

A new builder instance

Dispose()

Disposes the KD-tree and its native containers.

Declaration
public void Dispose()

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.
int k

Number of neighbors to return (must be at least 1).
NativeList<int> results

Destination list for item IDs. This list is cleared before writing.
NativeList<float> distances

Destination list for distances. This list is cleared before writing.
Returns
Type Description
int

The number of results written.
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.

Declaration
public int QueryRadius(float3 queryPoint, float radius, NativeList<int> results, NativeList<float> distances)
Parameters
Type Name Description
float3 queryPoint

Query point.
float radius

Search radius (must be non-negative).
NativeList<int> results

Destination list for item IDs. This list is cleared before writing.
NativeList<float> distances

Destination list for distances. This list is cleared before writing.
Returns
Type Description
int

The number of results written.
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.
int itemID

When this method returns, contains the nearest item ID if found; otherwise 0.
float distance

When this method returns, contains the distance to the nearest point if found; otherwise 0.
Returns
Type Description
bool

True if a nearest neighbor exists; false if the tree is empty.

Implements

Extension Methods