Struct ScyllaBVHCore
High-performance Bounding Volume Hierarchy (BVH) core for broad-phase spatial queries in 3D space.
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
[BurstCompile]
public struct ScyllaBVHCore : IDisposableRemarks
This is the low-level, Burst-compatible BVH implementation designed for maximum performance in DOTS contexts.
Architecture:
- Uses a binary tree structure with internal nodes and leaf nodes
- Each item is stored in a dedicated leaf node with a "fattened" AABB (expanded by FatteningMargin)
- Internal nodes store the union bounds of their children
- Items are identified by integer IDs (user-managed)
Key Features:
- Dynamic insertion/removal with automatic tree restructuring
- Bulk build using Surface Area Heuristic (SAH) partitioning
- Multiple query types: AABB overlap, ray intersection, sphere intersection
- Fattening margin reduces update churn for moving objects
- Node pooling for efficient memory reuse
Usage Pattern:
- Create with appropriate allocator (Temp, TempJob, or Persistent)
- Optionally pre-reserve capacity to avoid allocations in jobs
- Build from arrays (bulk) or add items incrementally
- Perform queries (overlap, ray, sphere)
- Update item bounds as objects move
- Dispose when done to prevent memory leaks
Thread Safety:
This struct is NOT thread-safe. Use external synchronization if accessed from multiple threads. However, it can be safely used within a single job when properly scheduled.
Managed Wrapper:
For convenience and validation, use ScyllaBVH which wraps this core and provides parameter validation, exception handling, and a built-in query scratch stack.
Constructors
ScyllaBVHCore(Allocator, int, int, float)
Creates a new BVH core and allocates all required native containers.
Declaration
public ScyllaBVHCore(Allocator allocator, int initialItemCapacity = 64, int initialNodeCapacity = 128, float fatteningMargin = 0.1)Parameters
| Type | Name | Description |
|---|---|---|
| Allocator | allocator | Allocator used for all internal native containers (must not be Allocator.None) |
| int | initialItemCapacity | Initial capacity for item storage (clamped to minimum 1) |
| int | initialNodeCapacity | Initial capacity for node storage (clamped to minimum 1) |
| float | fatteningMargin | Margin to expand leaf AABBs (must be finite and >= 0, typical: 0.05-0.2) |
Remarks
This constructor allocates the following native containers using the specified allocator:
- Nodes array (NativeList)
- Item IDs and bounds arrays (NativeList)
- Hash maps for item and node lookups (NativeHashMap)
- Free node index pool (NativeList)
- Build and query scratch buffers (NativeList) All containers are initialized with at least capacity 1, even if you specify 0 for initial capacities.
Parameter Validation:
- Allocator must not be Allocator.None (throws ArgumentException)
- Capacities must be >= 0 (throws ArgumentOutOfRangeException)
- FatteningMargin must be finite and >= 0 (throws ArgumentOutOfRangeException) After construction, IsCreated will return true. Always call Dispose() when done.
Exceptions
| Type | Condition |
|---|---|
| ArgumentException | Thrown when allocator is Allocator.None |
| ArgumentOutOfRangeException | Thrown when capacity or margin parameters are invalid |
Properties
Count
Number of items currently stored.
Declaration
public int Count { get; }Property Value
| Type | Description |
|---|---|
| int |
FatteningMargin
Fattening margin used to expand leaf bounds.
Declaration
public float FatteningMargin { get; }Property Value
| Type | Description |
|---|---|
| float |
IsCreated
Returns true if this BVH core has been properly constructed and all native containers are allocated.
Declaration
public bool IsCreated { get; }Property Value
| Type | Description |
|---|---|
| bool |
Remarks
This property checks all internal native containers to ensure they have been created. Returns false if:
- The core was created with default struct initialization (not via constructor)
- Dispose() has been called Always check IsCreated before using a BVH core that might be in an indeterminate state.
Methods
Add(int, ScyllaAABB3)
Adds a new item to the BVH dynamically.
Declaration
public void Add(int itemID, ScyllaAABB3 bounds)Parameters
| Type | Name | Description |
|---|---|---|
| int | itemID | Unique identifier for the item |
| ScyllaAABB3 | bounds | Axis-aligned bounding box for the item |
Remarks
This method performs an incremental insertion:
- Creates a new leaf node with fattened bounds (expanded by FatteningMargin)
- Finds the best sibling node to pair with using Surface Area Heuristic
- Creates a new parent node to group the leaf and sibling
- Refits ancestor bounds up to the root If the item ID already exists or bounds are invalid, the operation is silently ignored. For bulk initialization, prefer using Build() for better performance.
Build(NativeArray<int>, NativeArray<ScyllaAABB3>)
Constructs a complete BVH from arrays of item IDs and their corresponding axis-aligned bounding boxes.
Declaration
public void Build(NativeArray<int> itemIDs, NativeArray<ScyllaAABB3> bounds)Parameters
| Type | Name | Description |
|---|---|---|
| NativeArray<int> | itemIDs | Array of unique item identifiers |
| NativeArray<ScyllaAABB3> | bounds | Array of axis-aligned bounding boxes corresponding to each item ID |
Remarks
This method performs a top-down bulk build using the Surface Area Heuristic (SAH) partitioning strategy. The algorithm:
- Clears the existing BVH structure
- Reserves sufficient capacity for the build (prevents allocations)
- Iteratively partitions items along the longest axis using median split
- Constructs a balanced binary tree of nodes
- Each leaf node stores a single item with fattened bounds This is more efficient than incremental Add() calls for bulk initialization. The method is Burst-friendly when all required capacities are pre-reserved. If array lengths don't match, the method returns early without modifying the BVH.
Clear()
Removes all items and clears the BVH structure.
Declaration
public void Clear()Remarks
Clears all nodes, items, and internal mappings. The BVH becomes empty with no root node. Internal container capacities are preserved for efficient re-use. After calling Clear(), you can rebuild or add items without reallocating memory (up to previous capacity).
Contains(int)
Returns true if an item with the specified ID is currently stored in the BVH.
Declaration
public bool Contains(int itemID)Parameters
| Type | Name | Description |
|---|---|---|
| int | itemID | The unique identifier of the item to check |
Returns
| Type | Description |
|---|---|
| bool | True if the item exists in the BVH, false otherwise |
Remarks
This is an O(1) operation using a hash map lookup.
Dispose()
Disposes all native containers owned by this core and releases unmanaged memory.
Declaration
public void Dispose()Remarks
Disposes the following native containers:
- Node storage
- Item ID and bounds arrays
- Hash maps for item and node lookups
- Free node index list
- Build scratch buffers After calling Dispose(), the core is no longer usable and IsCreated will return false. It is safe to call Dispose() multiple times (subsequent calls are no-ops). Always call Dispose() when done to prevent memory leaks.
QueryOverlap(ScyllaAABB3, NativeList<int>, NativeList<int>)
Performs an AABB overlap query and appends all intersecting item IDs to the results list.
Declaration
public void QueryOverlap(ScyllaAABB3 query, NativeList<int> results, NativeList<int> traversalStackScratch)Parameters
| Type | Name | Description |
|---|---|---|
| ScyllaAABB3 | query | Query axis-aligned bounding box |
| NativeList<int> | results | Result list to append matching item IDs (not cleared by this method) |
| NativeList<int> | traversalStackScratch | Scratch stack used for iterative traversal (cleared at method start) |
Remarks
Uses iterative depth-first traversal to efficiently cull the BVH hierarchy. The algorithm:
- Tests each node's bounds against the query AABB
- Skips entire subtrees when node bounds don't overlap
- For leaf nodes, performs exact overlap test using stored item bounds
- Appends matching item IDs to the results list Results are appended (not cleared), allowing multiple queries to accumulate results. The traversal stack is cleared at the start of each query. If query bounds are invalid or the BVH is empty, no results are added. Traversal order is deterministic: Left child before Right child.
QueryRay(ScyllaRay3, float, NativeList<int>, NativeList<int>)
Performs a ray intersection query and appends all intersecting item IDs to the results list.
Declaration
public void QueryRay(ScyllaRay3 ray, float maxDistance, NativeList<int> results, NativeList<int> traversalStackScratch)Parameters
| Type | Name | Description |
|---|---|---|
| ScyllaRay3 | ray | Ray with origin, direction, and precomputed inverse direction |
| float | maxDistance | Maximum ray distance to test (forms segment [0, maxDistance]) |
| NativeList<int> | results | Result list to append matching item IDs (not cleared by this method) |
| NativeList<int> | traversalStackScratch | Scratch stack used for iterative traversal (cleared at method start) |
Remarks
Uses iterative depth-first traversal with ray-AABB intersection tests (slab method). The algorithm:
- Tests each node's bounds against the ray segment [0, maxDistance]
- Skips entire subtrees when node bounds don't intersect the ray
- For leaf nodes, performs exact ray-AABB test using stored item bounds
- Appends matching item IDs to the results list The ScyllaRay3 struct contains cached inverse direction for efficient slab-method intersection tests. Results are appended (not cleared), allowing multiple queries to accumulate results. The traversal stack is cleared at the start of each query. If maxDistance is negative or the BVH is empty, no results are added.
QuerySphere(float3, float, NativeList<int>, NativeList<int>)
Performs a sphere intersection query and appends all intersecting item IDs to the results list.
Declaration
public void QuerySphere(float3 center, float radius, NativeList<int> results, NativeList<int> traversalStackScratch)Parameters
| Type | Name | Description |
|---|---|---|
| float3 | center | Sphere center point |
| float | radius | Sphere radius (must be non-negative) |
| NativeList<int> | results | Result list to append matching item IDs (not cleared by this method) |
| NativeList<int> | traversalStackScratch | Scratch stack used for iterative traversal (cleared at method start) |
Remarks
Uses iterative depth-first traversal with sphere-AABB distance tests. The algorithm:
- Tests each node's bounds against the sphere using squared distance
- Skips entire subtrees when the minimum distance from node bounds to sphere center exceeds radius
- For leaf nodes, performs exact distance test using stored item bounds
- Appends matching item IDs to the results list Distance calculations use squared distance to avoid expensive square root operations. Results are appended (not cleared), allowing multiple queries to accumulate results. The traversal stack is cleared at the start of each query. If radius is negative or the BVH is empty, no results are added.
Remove(int)
Removes an item from the BVH by its unique identifier.
Declaration
public bool Remove(int itemID)Parameters
| Type | Name | Description |
|---|---|---|
| int | itemID | Unique identifier of the item to remove |
Returns
| Type | Description |
|---|---|
| bool | True if the item existed and was removed, false if the item was not found |
Remarks
This method performs the following steps:
- Locates the leaf node containing the item
- Detaches the leaf from the tree (promotes its sibling to replace the parent)
- Removes the item from internal storage using swap-back removal
- Refits ancestor bounds up to the root
- Recycles the freed node for future allocations The swap-back removal strategy maintains cache efficiency but does not preserve item order.
Reserve(int, int, int)
Reserves internal capacity for items, nodes, and scratch buffers.
Declaration
public void Reserve(int itemCapacity, int nodeCapacity, int scratchCapacity)Parameters
| Type | Name | Description |
|---|---|---|
| int | itemCapacity | Minimum capacity for item storage (IDs and bounds) |
| int | nodeCapacity | Minimum capacity for BVH node storage |
| int | scratchCapacity | Minimum capacity for build and query scratch buffers |
Remarks
Call this method outside jobs to pre-allocate memory and avoid reallocations during Burst/job execution. This ensures that subsequent operations (Add, Build, queries) do not trigger allocations when running in jobs. Negative capacity values are clamped to zero.
Update(int, ScyllaAABB3)
Updates an existing item’s bounds using a refit-or-reinsert strategy.
Declaration
public bool Update(int itemID, ScyllaAABB3 newBounds)Parameters
| Type | Name | Description |
|---|---|---|
| int | itemID | Unique identifier of the item to update. |
| ScyllaAABB3 | newBounds | New axis-aligned bounding box representing the item’s current extent. Must be valid. |
Returns
| Type | Description |
|---|---|
| bool | True if the item existed and was updated; false if the item ID was not found or |
Remarks
Fast path (refit): If the new bounds are fully contained within the leaf’s current fattened bounds, only the ancestor bounds are walked upward and recomputed. The leaf’s position in the tree is unchanged.
Slow path (reinsert): When the new bounds exceed the fattened leaf bounds, the leaf is detached, re-expanded by the fattening margin, and reinserted at the best position found by the SAH descent.
The fattening margin intentionally creates a hysteresis window: small movements that stay within the padded volume are essentially free, while only large movements trigger a full reinsert.