1. Epic GamesDeveloper
  3. FSparseDynamicOctree3

FSparseDynamicOctree3

[FSparseDynamicOctree3](API\Runtime\GeometryCore\Spatial\FSparseDynamicOctree3) sorts objects with axis-aligned bounding boxes into a dynamic sparse octree of axis-aligned uniform grid cells.

API > API/Runtime > API/Runtime/GeometryCore > API/Runtime/GeometryCore/Spatial

Inheritance Hierarchy

References

   
Module GeometryCore
Header /Engine/Source/Runtime/GeometryCore/Public/Spatial/SparseDynamicOctree3.h
Include #include "Spatial/SparseDynamicOctree3.h"

Syntax

class FSparseDynamicOctree3

Remarks

FSparseDynamicOctree3 sorts objects with axis-aligned bounding boxes into a dynamic sparse octree of axis-aligned uniform grid cells. At the top level we have an infinite grid of "root cells" of size RootDimension, which then contain 8 children, and so on. (So in fact each cell is a separate octree, and we have a uniform grid of octrees)

The objects and their bounding-boxes are not stored in the tree. You must have an integer identifier (ObjectID) for each object, and call Insert(ObjectID, BoundingBox). Some query functions will require you to provide a lambda/etc that can be called to retrieve the bounding box for a given ObjectID.

Objects are currently inserted at the maximum possible depth, ie smallest cell that will contain them, or MaxTreeDepth. The tree boxes are expanded by MaxExpandFactor to allow for deeper insertion. If MaxExpandFactor > 0 then the tree does not strictly partition space, IE adjacent cells overlap.

The octree is dynamic. Objects can be removed and re-inserted.

Variables

  Type Name Description
Protected variable FSmallListSet CellObjectLists  
Protected variable FRefCountVector CellRefCounts Reference counts for Cells list.
Protected variable TDynamicVector< FSparseOctreeCell > Cells List of cells. Note that some cells may be unused, depending on CellRefCounts
Public variable double MaxExpandFactor Fraction we expand the dimension of any cell, to allow extra space to fit objects.
Protected variable int MaxTreeDepth Objects will not be inserted more than this many levels deep from a Root cell
Protected variable TDynamicVector< uint32 > ObjectIDToCellMap  
Protected variable TSparseGrid3< uint32 > RootCells RootCells are the top-level cells of the octree, of size RootDimension.
Public variable double RootDimension Potential optimizations/improvements
Protected variable TSet< int32 > SpillObjectSet  
Protected variable FDynamicFlagArray ValidObjectIDs  

Functions

  Type Name Description
Protected function Const void

BranchRangeQuery ( const FSparseOctreeCell* ParentCell,
const FAxisAlignedBox3d& Bounds,
TArray< int >& ObjectIDs
)

  
Protected function Const bool

CanFit ( const FSparseOctreeCell& Cell,
const FAxisAlignedBox3d& Bounds
)

  
Public function Const bool

CheckIfObjectNeedsReinsert ( int32 ObjectID,
const FAxisAlignedBox3d& NewBounds,
uint32& CellIDOut
)

 Check if the object needs to be reinserted, if it has NewBounds.
Public function Const void

CheckValidity ( TFunctionRef< bool(int)> IsValidObjectIDFunc,
TFunctionRef< FAxisAlignedBox3d(int)> GetObjectBoundsFunc,
EValidityCheckFailMode FailMode,
bool bVerbose,
bool bFailOnMissingObjects
)

 Check that the octree is internally valid
Public function Const void Populate given FStatistics with info about the octree
Public function Const void

ContainmentQuery ( const FVector3d& Point,
TFunctionRef< void(int)> ObjectIDFunc
)

 Process ObjectIDs from all the cells with bounding boxes that contain query point
Public function Const bool

ContainmentQueryCancellable ( const FVector3d& Point,
TFunctionRef< bool(int)> ObjectIDFunc
)

 Process ObjectIDs from all the cells with bounding boxes that contain query point
Public function Const bool

ContainsObject ( int32 ObjectID
)

 Test if an object is stored in the tree
Protected function Const FSparseOctreeCell  
Public function Const int32

FindNearestHitObject ( const FRay3d& Ray,
TFunctionRef< FAxisAlignedBox3d(int)> GetObjectBoundsFunc,
TFunctionRef< double(int, const FRay3d&)> HitObjectDistFunc,
double MaxDistance
)

 Find nearest ray-hit point with objects in tree
Protected function Const double

FindNearestRayCellIntersection ( const FSparseOctreeCell& Cell,
const FRay3d& Ray
)

  
Protected function Const FAxisAlignedBox3d

GetBox ( uint32 Level,
const FVector3i& Index,
double ExpandFactor
)

  
Protected function Const FAxisAlignedBox3d

GetCellBox ( const FSparseOctreeCell& Cell,
double ExpandFactor
)

  
Protected function Const FVector3d  
Protected function Const uint32

GetCellForObject ( int32 ObjectID
)

  
Protected function Const double

GetCellWidth ( uint32 Level
)

 Calculate the base width of a cell at a given level
Public function int  
Protected function void

Insert_NewChildCell ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds,
int ParentCellID,
FSparseOctreeCell NewChildCell,
int ChildIdx
)

  
Protected function void

Insert_NewRoot ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds,
FSparseOctreeCell NewRootCell
)

  
Protected function void

Insert_Spill ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds
)

  
Protected function void

Insert_ToCell ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds,
const FSparseOctreeCell& ExistingCell
)

  
Public function void

InsertObject ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds
)

 Insert ObjectID into the Octree
Public function Const void

ParallelRangeQuery ( const FAxisAlignedBox3d& Bounds,
TArray< int >& ObjectIDsOut
)

 Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds.
Protected function Const FVector3i

PointToIndex ( uint32 Level,
const FVector3d& Position
)

 Warning: result here appears to be unstable (due to optimization?) if any of the position values are on the border of a cell (in testing, pragma-optimization-disabled code produced off-by-one result from calling this function)
Public function Const void

RangeQuery ( const FAxisAlignedBox3d& Bounds,
TFunctionRef< void(int)> ObjectIDFunc
)

 Process ObjectIDs from all the cells with bounding boxes that intersect Bounds
Public function Const void

RangeQuery ( const FAxisAlignedBox3d& Bounds,
TArray< int >& ObjectIDsOut
)

 Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds
Public function bool

ReinsertObject ( int32 ObjectID,
const FAxisAlignedBox3d& NewBounds,
uint32 CellIDHint
)

 Update the position of an object in the octree. This is more efficient than doing a remove+insert
Public function bool

RemoveObject ( int32 ObjectID
)

 Remove an object from the octree
Public function void

SetMaxTreeDepth ( int MaxTreeDepthIn
)

 Sets max tree depth w/ protection against setting beyond supported max
Protected function Const int

ToChildCellIndex ( const FSparseOctreeCell& Cell,
const FVector3d& Position
)

  

Classes

  Type Name Description
Public struct FStatistics Statistics about internal structure of the octree  

Constants

Name Description
InvalidCellID This identifier is used for unknown cells
MaxSupportedTreeDepth  
SpillCellID If an object is in the spill cell, that means it didn't fit in the tree

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page