1. Epic GamesDeveloper
  3. FSparseDynamicOctree3

FSparseDynamicOctree3

[FSparseDynamicOctree3](API\Runtime\GeometryCore\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

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.

   
Name FSparseDynamicOctree3
Type class
Header File /Engine/Source/Runtime/GeometryCore/Public/Spatial/SparseDynamicOctree3.h
Include Path #include "Spatial/SparseDynamicOctree3.h"

Syntax

class FSparseDynamicOctree3

Derived Classes

Structs

Name Remarks
FStatistics Statistics about internal structure of the octree

Constants

Name Type Remarks Include Path
InvalidCellID uint32 This identifier is used for unknown cells Spatial/SparseDynamicOctree3.h
MaxSupportedTreeDepth uint32   Spatial/SparseDynamicOctree3.h
SpillCellID uint32 If an object is in the spill cell, that means it didn't fit in the tree Spatial/SparseDynamicOctree3.h

Variables

Public

Name Type Remarks Include Path Unreal Specifiers
MaxExpandFactor double Fraction we expand the dimension of any cell, to allow extra space to fit objects. Spatial/SparseDynamicOctree3.h  
RootDimension double Potential optimizations/improvements Spatial/SparseDynamicOctree3.h  

Functions

Public

Name Remarks Include Path Unreal Specifiers

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

 Check if the object needs to be reinserted, if it has NewBounds. Spatial/SparseDynamicOctree3.h  

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

 Check that the octree is internally valid Spatial/SparseDynamicOctree3.h  

void ComputeStatistics ( FStatistics& StatsOut
) const

 Populate given FStatistics with info about the octree Spatial/SparseDynamicOctree3.h  

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

 Process ObjectIDs from all the cells with bounding boxes that contain query point Spatial/SparseDynamicOctree3.h  

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

 Process ObjectIDs from all the cells with bounding boxes that contain query point Spatial/SparseDynamicOctree3.h  

bool ContainsObject ( int32 ObjectID
) const

 Test if an object is stored in the tree Spatial/SparseDynamicOctree3.h  

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

 Find nearest ray-hit point with objects in tree Spatial/SparseDynamicOctree3.h  

int GetMaxTreeDepth()

   Spatial/SparseDynamicOctree3.h  

void InsertObject ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds
)

 Insert ObjectID into the Octree Spatial/SparseDynamicOctree3.h  

int ParallelOverlapAnyQuery ( const FAxisAlignedBox3d& ShapeBounds,
TFunctionRef< bool(int32)> ObjectOverlapFn
) const

 Find any overlap between a caller-defined query and any object ID. Spatial/SparseDynamicOctree3.h  

int ParallelOverlapAnyQuery ( const FAxisAlignedBox3d& ShapeBounds,
TFunctionRef< bool(int32)> ObjectOverlapFn,
TFunctionRef< bool(const FAxisAlignedBox3d&)> BoundsOverlapFn
) const

 Find any overlap between a caller-defined query and any object ID. Spatial/SparseDynamicOctree3.h  

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

 Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds. Spatial/SparseDynamicOctree3.h  

void ParallelRangeQuery ( const FAxisAlignedBox3d& RangeBoundsHint,
TFunctionRef< bool(const FAxisAlignedBox3d&CellBounds)> BoundsOverlapFn,
TArray< int32 >& ObjectIDs
) const

 Collect ObjectIDs from all the leaf cells that have bounding boxes that pass BoundsOverlapFn Spatial/SparseDynamicOctree3.h  

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

 Process ObjectIDs from all the cells with bounding boxes that intersect Bounds Spatial/SparseDynamicOctree3.h  

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

 Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds Spatial/SparseDynamicOctree3.h  

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 Spatial/SparseDynamicOctree3.h  

bool RemoveObject ( int32 ObjectID
)

 Remove an object from the octree Spatial/SparseDynamicOctree3.h  

void SetMaxTreeDepth ( int MaxTreeDepthIn
)

 Sets max tree depth w/ protection against setting beyond supported max Spatial/SparseDynamicOctree3.h  

Protected

Name Remarks Include Path Unreal Specifiers

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

   Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

FSparseOctreeCell FindCurrentContainingCell ( const FAxisAlignedBox3d& Bounds
) const

   Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

FAxisAlignedBox3d GetCellBox ( const FSparseOctreeCell& Cell,
double ExpandFactor
) const

   Spatial/SparseDynamicOctree3.h  

FVector3d GetCellCenter ( const FSparseOctreeCell& Cell
) const

   Spatial/SparseDynamicOctree3.h  

uint32 GetCellForObject ( int32 ObjectID
) const

   Spatial/SparseDynamicOctree3.h  

double GetCellWidth ( uint32 Level
) const

 Calculate the base width of a cell at a given level Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

void Insert_Spill ( int32 ObjectID,
const FAxisAlignedBox3d& Bounds
)

   Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

FVector3i PointToIndex ( uint32 Level,
const FVector3d& Position
) const

 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) Spatial/SparseDynamicOctree3.h  

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

   Spatial/SparseDynamicOctree3.h  

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page