Octree (object)¶
The Octree type implements an octree spatial partition structure, which is equivalent of a “3D sort” of objects enabling fast searches among multiple objects in space.
The Octree subdivides the space in a sparse hierarchy of cells, in order to quickly isolate empty space. This then enables to perform queries such as raycast by testing only a portion of the objects.
This Octree implementation tries to provide a good balance between speed, memory usage and the ability to update incrementally. The ability to update incrementally implies that the octree has the ability to update only objects that changed. Additionally, octree’s construction can be done only partially while maintaining its valid state, which allows for a balance between construction and query time.
Because Octree.raycast and Octree.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.
All query (read) methods are thread-safe as long as the Octree is not modified (Octree.updateObjectVolume, Octree.removeObject and Octree.prepare).
Methods¶
| Octree ( in Octree other ) | |
| Octree ( in UInt8 maxDepth, in Boolean keepSubCellObjectList, in Scalar smallestWorldCellSize ) | |
| Octree () | |
| Octree | 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 SpatialQueryData data ) | |
| Box3 | getObjectBBox ? ( in Size index ) |
| getObjectBSphere ? ( in Size index, io Vec3 center, io Scalar radius ) | |
| Size | getObjectCount ? () |
| getObjectsInBBox ? ( in Vec3 min, in Vec3 max, io SpatialQueryData data ) | |
| getObjectsInBSphere ? ( in Vec3 center, in Scalar radius, io SpatialQueryData data ) | |
| Box3 | getWorldBBox ! () |
| incrementalUpdateObjectCount ! ( in Size objectCount ) | |
| localBVolQuery ? ( in Mat44 transform, in LocalBoundingVolume localBVol, out IndexSet result ) | |
| localBVolQuery ? ( in Mat44 transform, in LocalBoundingVolume localBVol, out IndexSet result, in BitVector objectMask ) | |
| Boolean | prepare ! ( in Size approximateNumberOfQueries ) |
| raycast ? ( in Ray ray, in Boolean doubleSided, in Scalar maxDistance, io SpatialQueryData data, io Ref<RaycastResult> result ) | |
| removeObject ! ( in UInt32 index ) | |
| updateObjectVolume ! ( in UInt32 index, in Mat44 transform, in LocalBoundingVolume localBVol ) | |
| Boolean | updateObjectVolume ! ( in UInt32 index, in Vec3 center, in Scalar radius ) |
| updateObjectVolume ! ( in UInt32 index, in Vec3 min, in Vec3 max ) |
Methods in detail¶
copy constructor
Octree ( in UInt8 maxDepth, in Boolean keepSubCellObjectList, in Scalar smallestWorldCellSize )
Constructs an Octree.
| maxDepth | maximum subdivision depth (<= 14) |
| keepSubCellObjectList | True if we want that leaves maintain a full list of their recursive childrens’ objects. This will accelerate volume queries such as ‘localBVolQuery()’, but will increase memory usage by 35%. |
Octree ()
clone method
Octree.getClosest? ( in Vec3 position, in Vec3 scaling, in Scalar maxUnscaledDistance, io SpatialQueryData data, io Ref<ClosestResult> result )
Gets the closest object of the Octree. 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. |
Octree.getLineIntersectedObjects? ( in Vec3 start, in Vec3 end, in UInt8 intersectionLineTypeEnum, io SpatialQueryData data )
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 Octree returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same data for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the Octree is not modified
| data | Resulting object indices will be added to data.visitedItems. Important: the actual object count is data.visitedItems.size() and not data.visitedItems.indices.size() (see IndexSet). |
Box3 Octree.getObjectBBox? ( in Size index )
Returns the bounding box of an Object. An empty Box3 will be returned if the object is not valid, and an infinite Box3 will be returned for infinite objects.
Octree.getObjectBSphere? ( in Size index, io Vec3 center, io Scalar radius )
Returns the bounding sphere of an Object. A negative radius will be returned if the object is not valid, and an infinite radius will be returned for infinite objects.
Size Octree.getObjectCount? ()
Returns the object index range.
注釈
Some of the indices between 0 and Octree.getObjectCount might be unused, if Octree.updateObjectVolume was never called or if Octree.removeObject was called for an object.
Octree.getObjectsInBBox? ( in Vec3 min, in Vec3 max, io SpatialQueryData data )
Returns objects intersecting the specified local bounding box.
注釈
Depending on the case, it is possible that the Octree returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same data for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the Octree is not modified
| data | Resulting object indices will be added to data.visitedItems. Important: the actual object count is data.visitedItems.size() and not data.visitedItems.indices.size() (see IndexSet). |
Octree.getObjectsInBSphere? ( in Vec3 center, in Scalar radius, io SpatialQueryData data )
Returns objects intersecting the specified local bounding sphere.
注釈
Depending on the case, it is possible that the Octree returns too many objects by including some that are close to the queried volume but not actually intersecting it.
注釈
Reusing the same data for multiple queries will improve performance by reducing the amount of temporary heap allocations
注釈
This function is threadsafe if the Octree is not modified
| data | Resulting object indices will be added to data.visitedItems. Important: the actual object count is data.visitedItems.size() and not data.visitedItems.indices.size() (see IndexSet). |
Returns the bounding box the Octree, which encloses loosely all its objects, but excluding those with an infinite bounding volume (if any).
注釈
This bounding box might be bigger than the union of objects’ bounding volumes, particularly if these have been varying during updates.
Octree.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 by Octree.updateObjectVolume
注釈
If existing objects get truncated, these will be automatically removed from the tree, incrementally (no need to call Octree.removeObject first).
Octree.localBVolQuery? ( in Mat44 transform, in LocalBoundingVolume localBVol, out IndexSet result )
Queries the Octree for objects intersecting a transformed bounding volume.
注釈
Depending on the case, it is possible that the Octree returns too many objects by including some that are close to the queried volume but not actually intersecting it.
| result | Indices of the intersected objects. Important: the actual object count is result.size() and not result.indices.size() (see IndexSet). |
Octree.localBVolQuery? ( in Mat44 transform, in LocalBoundingVolume localBVol, out IndexSet result, in BitVector objectMask )
Queries the Octree for objects intersecting a transformed bounding volume.
注釈
Depending on the case, it is possible that the Octree returns too many objects by including some that are close to the queried volume but not actually intersecting it.
| result | Indices of the intersected objects. Important: the actual object count is IndexSet.size and not IndexSet.indices.size (see IndexSet). |
| objectMask | Ignored if empty (size = 0). Else, it is expected to be of size Lkl-ref:Octree.objectCount, and only Octree objects corresponding to set bits will be tested. |
Boolean Octree.prepare! ( in Size approximateNumberOfQueries )
Incrementally updates the Octree after Octree.updateObjectVolume calls. After calls to Octree.updateObjectVolume, this method must be called in order to have a valid octree.
For an optimal performance, wait until all the Octree.updateObjectVolume calls are done before calling this method.
Because this method causes an incremental update, each call to this method might further subdivide the Octree, until it is considered as fully subdivided.
注釈
The Octree.update internal method gives a lower-level control over the update amount
注釈
This method is not thread-safe.
| approximateNumberOfQueries | Approximate number of queries (eg: Octree.raycast) to be issued to the Octree. Since yhe cost of fully updating the Octree can be higher than the cost of the spatial queries, using the right approximation can be important. |
Octree.raycast? ( in Ray ray, in Boolean doubleSided, in Scalar maxDistance, io SpatialQueryData data, io Ref<RaycastResult> result )
Raycasts the objects of the Octree. 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. |
Octree.removeObject! ( in UInt32 index )
Removes an object from the octree, while maintaining its validity (no need to call Octree.prepare).
注釈
This method is not thread-safe.
Octree.updateObjectVolume! ( in UInt32 index, in Mat44 transform, in LocalBoundingVolume localBVol )
Updates the volume of an object based on a transformed LocalBoundingVolume. This will not update the Octree: Octree.prepare must be called (incremental update) for the Octree to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= Octree.getObjectCount, the count will be increased automatically
注釈
The Octree might store a larger approximation of that volume
注釈
This method is not thread-safe.
Boolean Octree.updateObjectVolume! ( in UInt32 index, in Vec3 center, in Scalar radius )
Updates the volume of an object based on a bounding sphere. This will not update the Octree: Octree.prepare must be called (incremental update) for the Octree to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= Octree.getObjectCount, the count will be increased automatically
注釈
The Octree might store a larger approximation of that volume
注釈
This method is not thread-safe.
Octree.updateObjectVolume! ( in UInt32 index, in Vec3 min, in Vec3 max )
Updates the volume of an object based on a bounding box. This will not update the Octree: Octree.prepare must be called (incremental update) for the Octree to be valid again once all objects’ volumes have been set.
注釈
if objectIndex >= Octree.getObjectCount, the count will be increased automatically
注釈
The Octree might store a larger approximation of the specified volume
注釈
This method is not thread-safe.
