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.

Choose your operating system:

Windows

macOS

Linux

Inheritance Hierarchy

FSparseDynamicOctree3

FDynamicMeshOctree3

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

Name Description

Protected variable

FSmallListSet

 

CellObjectLists

Protected variable

FRefCountVector

 

CellRefCounts

Reference counts for Cells list.

Protected variable

TDynamicVector<...

 

Cells

List of cells.

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<...

 

ObjectIDToCellMap

Protected variable

TSparseGrid3< u...

 

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

FDynamicFlagArr...

 

ValidObjectIDs

Functions

Name Description

Protected function Const

void

 

BranchRangeQuery

(
    const FSparseOctreeCell* Paren...,
    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> IsValidObj...,
    TFunctionRef< FAxisAlignedBox3d FailMode,
    bool bVerbose,
    bool bFailOnMissingObjects
)

Check that the octree is internally valid

Public function Const

void

 

ComputeStatistics

(
    FStatistics& StatsOut
)

Populate given FStatistics with info about the octree

Public function Const

void

 

ContainmentQuery

(
    const FVector3d& Point,
    TFunctionRef< void> ObjectIDFu...
)

Process ObjectIDs from all the cells with bounding boxes that contain query point

Public function Const

bool

 

ContainmentQueryCancellable

(
    const FVector3d& Point,
    TFunctionRef< bool> ObjectIDFu...
)

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

FSparseOctre...

 

FindCurrentContainingCell

(
    const FAxisAlignedBox3d& Bounds
)

Public function Const

int32

 

FindNearestHitObject

(
    const FRay3d& Ray,
    TFunctionRef< FAxisAlignedBox3d< double(int, const FRa...,
    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

FAxisAligned...

 

GetBox

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

Protected function Const

FAxisAligned...

 

GetCellBox

(
    const FSparseOctreeCell& Cell,
    double ExpandFactor
)

Protected function Const

FVector3d

 

GetCellCenter

(
    const FSparseOctreeCell& Cell
)

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

 

GetMaxTreeDepth()

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& ExistingC...
)

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> ObjectIDFu...
)

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

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