SparseGrid.kl¶
Types¶
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 ) |
