SparseGrid (object)¶
The SparseGrid is a spatial acceleration structure that subdivides the 3D space as a regular grid of cubic cells. The SparseGrid object can hold objects that are described as points, or as a bounding volume (box or sphere).
The grid is sparse because, similarly to a hash table, only cells that contain some objects are allocated. In order to offer a good performance, the SparseGrid offers: Before issuing queries, the SparseGrid.updateGrid method must be called if grid objects were modified (SparseGrid.updatePointObject, SparseGrid.updateBBoxObject, SparseGrid.updateBSphereObject, SparseGrid.removeObject).
By default, the cell size will be adjusted automatically based on the number of objects and their volume. However it is possible to adjust the cell size using a multiplication factor (see SparseGrid.setAutoCellSize) or an explicit size (see SparseGrid.setExplicitCellSize).
Because SparseGrid.raycast and SparseGrid.getClosest need to be more precise than simple bounding volume intersection, these require specialized object intersections for the actual geometry (polygon, edge, geometry) to be implemented through the RaycastResult and ClosestResult interfaces.
Query (read) methods are threadsafe if the grid not modified (not being updated, or its objects are not changed).
- Compact memory: all data is managed into a few arrays, reducing global memory consumption and improving speed due to memory locality
- Auto-adjusting cell size: allows the grid to adjust relatively optimally to various object sizes and placement. The SparseGrid tracks the various parameters and will update the cell size if conditions change too much.
- Incremental update: only objects that move between cells will cause changes.
Methods¶
| SparseGrid ( in SparseGrid other ) | |
| SparseGrid () | |
| bBoxQuery ? ( in Vec3 min, in Vec3 max, io IndexSet result ) | |
| bSphereQuery ? ( in Vec3 center, in Scalar radius, io IndexSet result ) | |
| SparseGrid | clone ? () |
| getClosest ? ( in Vec3 position, in Vec3 scaling, in Scalar maxUnscaledDistance, io SpatialQueryData data, io Ref<ClosestResult> result ) | |
| getLineIntersectedObjects ? ( in Vec3 start, in Vec3 end, in UInt8 intersectionLineTypeEnum, io IndexSet result ) | |
| Size | getObjectCount ? () |
| incrementalUpdateObjectCount ! ( in Size objectCount ) | |
| raycast ? ( in Ray ray, in Boolean doubleSided, in Scalar maxDistance, io SpatialQueryData data, io Ref<RaycastResult> result ) | |
| removeObject ! ( in UInt32 objectIndex ) | |
| setAutoCellSize ! ( in Scalar autoCellSizeMultiplierHint ) | |
| setAutoCellSize ! () | |
| setExplicitCellSize ! ( in Scalar cellSize ) | |
| updateBBoxObject ! ( in UInt32 objectIndex, in Vec3 min, in Vec3 max ) | |
| updateBSphereObject ! ( in UInt32 objectIndex, in Vec3 center, in Scalar radius ) | |
| updateGrid ! () | |
| updatePointObject ! ( in UInt32 objectIndex, in Vec3 position ) |
Methods in detail¶
SparseGrid ( in SparseGrid other )
copy constructor
SparseGrid ()
SparseGrid.bBoxQuery? ( in Vec3 min, in Vec3 max, io IndexSet result )
Returns objects intersecting the specified local bounding box.
注釈
Depending on the case, it is possible that the SparseGrid returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same result for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the SparseGrid is not modified
| result | Contains resulting object indices. Important: the actual object count is result.size() and not result.indices.size() (see IndexSet). |
SparseGrid.bSphereQuery? ( in Vec3 center, in Scalar radius, io IndexSet result )
Returns objects intersecting the specified local bounding sphere.
注釈
Depending on the case, it is possible that the SparseGrid returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same result for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the SparseGrid is not modified
| result | Contains resulting object indices. Important: the actual object count is result.size() and not result.indices.size() (see IndexSet). |
SparseGrid SparseGrid.clone? ()
clone method
SparseGrid.getClosest? ( in Vec3 position, in Vec3 scaling, in Scalar maxUnscaledDistance, io SpatialQueryData data, io Ref<ClosestResult> result )
Gets the closest object of the SparseGrid. See SpatialQueryable.getClosest for a description of the other parameters.
| data | Temporary data used for processing the query. Reusing the same data for multiple queries will improve performance by reducing the amount of temporary heap allocations. |
| result | Implements specialized object intersection through the ClosestResult interface, and will hold the final result. |
SparseGrid.getLineIntersectedObjects? ( in Vec3 start, in Vec3 end, in UInt8 intersectionLineTypeEnum, io IndexSet result )
Returns objects intersecting the specified line, semi-line or line segment.
- if lineIntersectionType == 0 (SpatialQuery_lineIntersection) : intersects with an infinite line passing through start and end
- if lineIntersectionType == 1 (SpatialQuery_semiLineIntersection) : intersects with a semi-line starting at start, passing through end and continuing infinitely in that direction
- if lineIntersectionType == 2 (SpatialQuery_segmentIntersection) : intersects with a segment starting at start and ending at end
注釈
Depending on the case, it is possible that the SparseGrid returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same result for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the SparseGrid is not modified
| result | Contains resulting object indices. Important: the actual object count is result.size() and not result.indices.size() (see IndexSet). |
Size SparseGrid.getObjectCount? ()
Returns the object index range.
注釈
Some of the indices between 0 and SparseGrid.getObjectCount might be unused, if object’s volume was never specified (eg: with SparseGrid.updateBSphereObject) or if SparseGrid.removeObject was called for an object.
SparseGrid.incrementalUpdateObjectCount! ( in Size objectCount )
Updates the object count, with no changes to remaining objects. Added objects will have no effect until their volume is specified (eg: with SparseGrid.updateBSphereObject).
注釈
If existing objects get truncated, these will be automatically removed from the grid, incrementally (no need to call SparseGrid.removeObject first).
SparseGrid.raycast? ( in Ray ray, in Boolean doubleSided, in Scalar maxDistance, io SpatialQueryData data, io Ref<RaycastResult> result )
Raycasts the objects of the SparseGrid. See SpatialQueryable.raycast for a description of the other parameters.
| data | Temporary data used for processing the query. Reusing the same data for multiple queries will improve performance by reducing the amount of temporary heap allocations. |
| result | Implements specialized object intersection through the RaycastResult interface, and will hold the final result. |
SparseGrid.removeObject! ( in UInt32 objectIndex )
Removes an object. The SparseGrid remains valid.
注釈
This method is not thread-safe.
SparseGrid.setAutoCellSize! ( in Scalar autoCellSizeMultiplierHint )
Enables auto-cell-size mode, and the cell size determined by the SparseGrid heuristic will then be multiplied by autoCellSizeMultiplierHint (value > 1.0 will lead to less grid cells, value < 1.0 will lead to more grid cells)
SparseGrid.setAutoCellSize! ()
Enables auto-cell-size mode.
SparseGrid.setExplicitCellSize! ( in Scalar cellSize )
Forces a specific cell size. Disables ‘auto-cell-size’ mode.
SparseGrid.updateBBoxObject! ( in UInt32 objectIndex, in Vec3 min, in Vec3 max )
Adds or updates a bounding box object. This will not update the SparseGrid: SparseGrid.updateGrid must be called (incremental update) for the SparseGrid to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= SparseGrid.getObjectCount, the count will be increased automatically
注釈
This method is not thread-safe.
SparseGrid.updateBSphereObject! ( in UInt32 objectIndex, in Vec3 center, in Scalar radius )
Adds or updates a bounding sphere object. This will not update the SparseGrid: SparseGrid.updateGrid must be called (incremental update) for the SparseGrid to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= SparseGrid.getObjectCount, the count will be increased automatically
注釈
This method is not thread-safe.
SparseGrid.updateGrid! ()
Must be called after all changes are done to update the SparseGrid incrementally. Potential changes include calls to:
- SparseGrid.setExplicitCellSize or SparseGrid.setAutoCellSize
- SparseGrid.updatePointObject, SparseGrid.updateBBoxObject or SparseGrid.updateBSphereObject
- SparseGrid.removeObject
Otherwise, results are unpredictable.
注釈
This function is not thread-safe.
SparseGrid.updatePointObject! ( in UInt32 objectIndex, in Vec3 position )
Adds or updates a point object. This will not update the SparseGrid: SparseGrid.updateGrid must be called (incremental update) for the SparseGrid to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= SparseGrid.getObjectCount, the count will be increased automatically
注釈
This method is not thread-safe.
