FSparseDynamicPointOctree3

[FSparseDynamicPointOctree3](API\Plugins\GeometricObjects\Spatial\FSparseDynamicPointOctree3) sorts Points with axis-aligned bounding boxes into a dynamic sparse octree of axis-aligned uniform grid cells.

Windows
MacOS
Linux

Inheritance Hierarchy

FSparseDynamicPointOctree3

TDynamicVerticesOctree3

References

Module

GeometricObjects

Header

/Engine/Plugins/Experimental/GeometryProcessing/Source/GeometricObjects/Public/Spatial/SparseDynamicPointOctree3.h

Include

#include "Spatial/SparseDynamicPointOctree3.h"

Syntax

class FSparseDynamicPointOctree3

Remarks

FSparseDynamicPointOctree3 sorts Points 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 Points and their bounding-boxes are not stored in the tree. You must have an integer identifier (PointID) for each Point, and call Insert(PointID, BoundingBox). Some query functions will require you to provide a lambda/etc that can be called to retrieve the bounding box for a given PointID.

By default Points are currently inserted at the maximum possible depth, ie smallest cell that will contain them, or MaxTreeDepth.

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

Variables

Name Description

Protected variable

FSmallListSet

 

CellPointLists

Protected variable

FRefCountVector

 

CellRefCounts

Reference counts for Cells list.

Protected variable

TDynamicVector<...

 

Cells

List of cells. Note that some cells may be unused, depending on CellRefCounts

Public variable

int

 

MaxPointsPerCell

If using the InsertPoint_DynamicExpand() insertion path, then when a cell gets to this many points, and has depth < MaxTreeDepth, it will be expanded and its points moved down

Public variable

int

 

MaxTreeDepth

Points will not be inserted more than this many levels deep from a Root cell

Protected variable

TDynamicVector<...

 

PointIDToCellMap

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

FDynamicFlagArr...

 

ValidPointIDs

Functions

Name Description

Protected function Const

bool

 

CellContains

(
    const FSparsePointOctreeCell& Cell,
    const FVector3d& Position
)

Public function Const

void

 

CheckValidity

(
    TFunctionRef< bool> IsValidPoi...,
    TFunctionRef< FVector3d> GetPo...,
    EValidityCheckFailMode FailMode,
    bool bVerbose,
    bool bFailOnMissingPoints
)

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

bool

 

ContainsPoint

(
    int32 PointID
)

Test if an Point is stored in the tree

Protected function Const

FSparsePoint...

 

FindCurrentContainingCell

(
    const FVector3d& Position
)

Public function Const

int32

 

FindNearestHitPoint

(
    const FRay3d& Ray,
    TFunctionRef< double(int, const FRa...,
    double MaxDistance
)

Find nearest ray-hit point with Points in tree

Protected function Const

double

 

FindNearestRayCellIntersection

(
    const FSparsePointOctreeCell& Cell,
    const FRay3d& Ray
)

Protected function Const

FAxisAligned...

 

GetCellBox

(
    const FSparsePointOctreeCell& Cell
)

Protected function Const

FAxisAligned...

 

GetCellBox

(
    uint32 Level,
    const FVector3i& Index
)

Protected function Const

FVector3d

 

GetCellCenter

(
    const FSparsePointOctreeCell& Cell
)

Protected function Const

uint32

 

GetCellForPoint

(
    int32 PointID
)

Protected function Const

double

 

GetCellWidth

(
    uint32 Level
)

Calculate the base width of a cell at a given level

Protected function

void

 

Insert_NewChildCell

(
    int32 PointID,
    const FVector3d& Position,
    int ParentCellID,
    FSparsePointOctreeCell NewChildCell,
    int ChildIdx
)

Protected function

void

 

Insert_NewRoot

(
    int32 PointID,
    const FVector3d& Position,
    FSparsePointOctreeCell NewRootCell
)

Protected function

void

 

Insert_ToCell

(
    int32 PointID,
    const FVector3d& Position,
    const FSparsePointOctreeCell& Exis...
)

Public function

void

 

InsertPoint

(
    int32 PointID,
    const FVector3d& Position
)

Insert PointID into the Octree at maximum depth.

Public function

void

 

InsertPoint_DynamicExpand

(
    int32 PointID,
    TFunctionRef< FVector3d> GetPo...
)

Insert PointID into the Octree. Dynamically expands cells that have more than MaxPointsPerCell

Public function Const

void

 

ParallelRangeQuery

(
    const FAxisAlignedBox3d& Bounds,
    TFunctionRef< bool> PredicateF...,
    TArray< int >& PointIDsOut,
    TArray< const FSparsePointOctreeCel...
)

Collect PointIDs from all the cells with bounding boxes that intersect Bounds, where PredicateFunc passes Query is parallelized across Root cells.

Protected function Const

FVector3i

 

PointToIndex

(
    uint32 Level,
    const FVector3d& Position
)

Public function Const

void

 

RangeQuery

(
    const FAxisAlignedBox3d& Bounds,
    TFunctionRef< bool> PredicateF...,
    TArray< int >& PointIDsOut,
    TArray< const FSparsePointOctreeCel...
)

Collect PointIDs from all the cells with bounding boxes that intersect Bounds, where PredicateFunc passes

Public function

void

 

ReinsertPoint

(
    int32 PointID,
    const FVector3d& NewPosition
)

Update the position of an Point in the octree. This is more efficient than doing a remove+insert

Public function

bool

 

RemovePoint

(
    int32 PointID
)

Remove an Point from the octree

Protected function Const

int

 

ToChildCellIndex

(
    const FSparsePointOctreeCell& 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
Help shape the future of Unreal Engine documentation! Tell us how we're doing so we can serve you better.
Take our survey
Dismiss