Struct ScyllaLooseOctreeCore

Burst-friendly loose octree core that stores items by integer ID and 3D AABBs. Intended for fast broad-phase queries (overlap/sphere/ray) and many moving items.

Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
[BurstCompile]
public struct ScyllaLooseOctreeCore : IDisposable
Remarks

Looseness expands each node’s query bounds (loose bounds) relative to the tight cell bounds. This reduces reinsertion churn for moving items: as long as an item stays within its assigned node’s loose bounds, Update(int, ScyllaAABB3) will only update bounds without reinserting.

Update vs Rebuild: - Use Update(int, ScyllaAABB3) when only a subset of items move each tick. - Use Rebuild(NativeArray<int>, NativeArray<ScyllaAABB3>) when most items move every tick; rebuilding can be cheaper than repeated reinsertion churn.

Complexity (typical): - Insert: O(depth) descent + occasional redistribution when splitting. - Remove: O(k) where k is the number of items in the node (bounded by MaxItemsPerNode in typical usage). - Queries: proportional to visited nodes + returned candidates.

Determinism: - Traversal is deterministic (fixed child order, iterative stack traversal). - Item iteration within a node is deterministic for the same sequence of adds/updates, but items are stored in a singly-linked list with O(1) head insertion, so result order is not “insertion order”.

Constructors

ScyllaLooseOctreeCore(ScyllaAABB3, int, int, float, Allocator, int)

Initializes a new ScyllaLooseOctreeCore and allocates its underlying native containers. The tree begins with a single root node and no items.

Declaration
public ScyllaLooseOctreeCore(ScyllaAABB3 rootBounds, int maxDepth, int maxItemsPerNode, float looseness, Allocator allocator, int initialItemCapacity = 64)
Parameters
Type Name Description
ScyllaAABB3 rootBounds

Tight root bounds of the octree. All inserted items must fit entirely within the root loose bounds, which are rootBounds expanded by looseness. The bounds must be valid (IsValid must be true) and have positive size on all axes.
int maxDepth

Maximum subdivision depth. A value of 0 disables all subdivision; nodes will accumulate all items regardless of maxItemsPerNode. Must be >= 0.
int maxItemsPerNode

Maximum number of items a node may hold before it is subdivided into eight children. Subdivision is skipped when maxDepth is reached. Must be >= 1.
float looseness

Looseness multiplier applied to tight node half-sizes to compute loose half-sizes. Must be a finite value >= 1.0. A value of 1.0 produces standard (non-loose) bounds. Typical range: 1.0 to 2.0.
Allocator allocator

Memory allocator for the internal native node list and item map.
int initialItemCapacity

Initial bucket capacity of the item hash map. Values below 1 are clamped to 1. Set this close to the expected maximum item count to reduce rehashing.
Exceptions
Type Condition
ArgumentException

Thrown when rootBounds is invalid or has non-positive size on any axis.
ArgumentOutOfRangeException

Thrown when maxDepth is negative, maxItemsPerNode is less than 1, or looseness is less than 1.0, NaN, or infinite.

Properties

Count

Total number of items currently stored across all nodes in the tree.

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

IsCreated

Returns true when both the node list and item map have been successfully allocated. This is false for a default-constructed struct or after Dispose() is called.

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

Looseness

Looseness multiplier used to expand tight node half-sizes into loose half-sizes. Always >= 1.0. A value of 1.0 produces a standard (non-loose) octree; higher values widen each node's loose bounds and reduce reinsertion churn at the cost of increased query overlap between sibling nodes.

Declaration
public float Looseness { get; }
Property Value
Type Description
float

MaxDepth

Maximum subdivision depth. Nodes at this depth are never split further, even if they exceed MaxItemsPerNode. A value of 0 disables all subdivision.

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

MaxItemsPerNode

Maximum number of items a node may hold directly before subdivision into eight child octants. Subdivision is skipped when the node is already at MaxDepth.

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

RootLooseBounds

Loose root bounds of the tree: the tight root bounds expanded by the Looseness factor. All inserted and updated item bounds must fit entirely within these bounds.

Declaration
public ScyllaAABB3 RootLooseBounds { get; }
Property Value
Type Description
ScyllaAABB3

RootTightBounds

Tight (un-expanded) root bounds of the tree as provided at construction time. Items do not need to fit within these bounds; they must fit within RootLooseBounds.

Declaration
public ScyllaAABB3 RootTightBounds { get; }
Property Value
Type Description
ScyllaAABB3

Methods

Clear()

Removes all items and resets the tree to a single root node.

Declaration
public void Clear()

Contains(int)

Determines whether an item with the given ID is currently stored in the tree.

Declaration
public bool Contains(int itemID)
Parameters
Type Name Description
int itemID

The item ID to look up.
Returns
Type Description
bool

true if the item exists; false otherwise.

Dispose()

Releases the native containers owned by this core (_nodes and _items).

Declaration
public void Dispose()
Remarks

Only disposes each container if it was created (checks IsCreated first). Safe to call even if construction partially failed or if the core was never used. After disposal, IsCreated returns false.

Do not use the core after calling this method.

QueryOverlap(ScyllaAABB3, NativeList<int>, NativeList<int>)

AABB overlap query: appends the IDs of all items whose stored bounds overlap the given query bounds.

Declaration
public void QueryOverlap(ScyllaAABB3 query, NativeList<int> results, NativeList<int> traversalStackScratch)
Parameters
Type Name Description
ScyllaAABB3 query

The axis-aligned bounding box to test against all stored items.
NativeList<int> results

Native list that receives the IDs of matching items. Existing contents are preserved; matches are appended to the end.
NativeList<int> traversalStackScratch

Caller-provided scratch buffer used as the traversal work stack. Its contents are cleared at the start of the query; the buffer must be writable and allocated with a compatible allocator.
Remarks

The results list is appended to - it is not cleared before the query. The caller is responsible for clearing it between queries if needed.

Traversal uses traversalStackScratch as an iterative work stack (which is cleared at the start of the query). Nodes whose Scylla.Core.Structures.ScyllaLooseOctreeCore.Node.LooseBounds do not overlap the query are pruned without descending into their children.

Returns immediately without traversing the tree if query is invalid (i.e., IsValid is false).

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

Sphere query: appends the IDs of all items whose stored bounds intersect the sphere defined by center and radius.

Declaration
public void QueryRadius(float3 center, float radius, NativeList<int> results, NativeList<int> traversalStackScratch)
Parameters
Type Name Description
float3 center

World-space center of the query sphere.
float radius

Radius of the query sphere in world units. Negative values cause the method to return immediately with no results.
NativeList<int> results

Native list that receives the IDs of matching items. Existing contents are preserved; matches are appended to the end.
NativeList<int> traversalStackScratch

Caller-provided scratch buffer used as the traversal work stack. Its contents are cleared at the start of the query; the buffer must be writable and allocated with a compatible allocator.
Remarks

The results list is appended to - it is not cleared before the query. The caller is responsible for clearing it between queries if needed.

Intersection is tested using squared-distance from the sphere center to the nearest point on each item's AABB (DistanceSqToPoint(float3)). Nodes are pruned when the squared distance from the center to their loose bounds exceeds radius * radius.

Returns immediately without traversing if radius is negative.

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

Ray query: appends the IDs of all items whose stored bounds intersect the ray segment defined by the half-open interval [tMin, tMax] along the given ray.

Declaration
public void QueryRay(float3 origin, float3 invDir, float tMin, float tMax, NativeList<int> results, NativeList<int> traversalStackScratch)
Parameters
Type Name Description
float3 origin

World-space origin point of the ray.
float3 invDir

Component-wise reciprocal of the ray direction (1/dir.x, 1/dir.y, 1/dir.z). For axis-aligned rays with a zero direction component, use RcpSafe(float3) to produce +Infinity instead of NaN.
float tMin

Minimum ray parameter (distance from origin). Use 0 for a ray starting at the origin.
float tMax

Maximum ray parameter (distance from origin). Use float.PositiveInfinity for an infinite ray.
NativeList<int> results

Native list that receives the IDs of matching items. Existing contents are preserved; matches are appended to the end.
NativeList<int> traversalStackScratch

Caller-provided scratch buffer used as the traversal work stack. Its contents are cleared at the start of the query; the buffer must be writable and allocated with a compatible allocator.
Remarks

The results list is appended to - it is not cleared before the query. The caller is responsible for clearing it between queries if needed.

Intersection uses the standard slab method via RayIntersects(float3, float3, float, float). Pass the component-wise reciprocal of the ray direction as invDir to avoid repeated division inside the traversal loop. Use RcpSafe(float3) to safely handle zero direction components (axis-aligned rays).

Nodes whose loose bounds do not intersect the ray segment are pruned. All candidates that pass the node test are then individually tested against the ray segment.

This method returns candidates only - the caller should perform exact intersection tests on the returned IDs for precise hit determination.

Rebuild(NativeArray<int>, NativeArray<ScyllaAABB3>)

Clears the entire octree and rebuilds it from scratch by inserting all items in the provided arrays.

Declaration
public void Rebuild(NativeArray<int> itemIDs, NativeArray<ScyllaAABB3> bounds)
Parameters
Type Name Description
NativeArray<int> itemIDs

Array of unique item IDs to insert. Must have the same length as bounds.
NativeArray<ScyllaAABB3> bounds

Array of spatial bounds, parallel to itemIDs.
Remarks

Calling this method is equivalent to calling Clear() followed by TryAdd(int, ScyllaAABB3) for each pair. It is more efficient than many individual Update(int, ScyllaAABB3) calls when most or all items have moved, because it avoids the per-item unlink/relink overhead and starts from a clean single-root state.

If itemIDs and bounds have different lengths the call returns immediately without modifying the tree.

Items whose bounds lie outside the root loose bounds are silently skipped.

Remove(int)

Removes the item with the given ID from the octree.

Declaration
public bool Remove(int itemID)
Parameters
Type Name Description
int itemID

ID of the item to remove.
Returns
Type Description
bool

true if the item existed and was removed successfully; false if no item with itemID exists.
Remarks

Unlinking the item from its node's singly-linked list is O(k), where k is the number of items stored in the same node. In typical usage k is bounded by MaxItemsPerNode, but items that could not fit any child node may accumulate at an ancestor, increasing k above the threshold.

No tree restructuring (node merging) is performed on removal.

TryAdd(int, ScyllaAABB3)

Attempts to insert a new item into the octree.

Declaration
public bool TryAdd(int itemID, ScyllaAABB3 bounds)
Parameters
Type Name Description
int itemID

Unique integer identifier for the item. Must not already be present in the tree; duplicate IDs cause this method to return false without modifying the tree.
ScyllaAABB3 bounds

Spatial bounds of the item. Must be fully contained by RootLooseBounds; items outside the root loose bounds are rejected.
Returns
Type Description
bool

true if the item was successfully inserted. false if an item with itemID already exists, or if bounds lie outside RootLooseBounds.
Remarks

The item is placed in the deepest node whose Scylla.Core.Structures.ScyllaLooseOctreeCore.Node.LooseBounds fully contain bounds. If the receiving node exceeds MaxItemsPerNode, subdivision and item redistribution are attempted automatically.

Update(int, ScyllaAABB3)

Updates the spatial bounds of an existing item.

Declaration
public bool Update(int itemID, ScyllaAABB3 newBounds)
Parameters
Type Name Description
int itemID

ID of the item whose bounds are being updated.
ScyllaAABB3 newBounds

New spatial bounds for the item. Must be fully contained by RootLooseBounds.
Returns
Type Description
bool

true if the item existed and its bounds were updated. false if no item with itemID exists, or if newBounds lie outside the root loose bounds.
Remarks

Fast path (no reinsertion): When the item's new bounds still fit entirely within its currently assigned node's Scylla.Core.Structures.ScyllaLooseOctreeCore.Node.LooseBounds, only the stored Scylla.Core.Structures.ScyllaLooseOctreeCore.ItemRecord.Bounds is updated - no unlink/relink is performed. This is the common case for slowly moving objects and runs in O(1).

Slow path (reinsertion): When the item escapes its assigned node's loose bounds, it is unlinked from its current node and re-descended from the root to find the best fitting node. This path is O(depth) and may trigger subdivision.

When the majority of items move every frame, consider Rebuild(NativeArray<int>, NativeArray<ScyllaAABB3>) instead, which can be cheaper than many individual reinsertions.

Implements