1. Epic GamesDeveloper
  3. FSparseDynamicPointOctree3

FSparseDynamicPointOctree3

[FSparseDynamicPointOctree3](API\Runtime\GeometryCore\Spatial\FSparseDynamicPointOctree3) sorts Points 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/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

  Type Name Description
Protected variable TSparseListSet< int32 > CellPointLists  
Protected variable FRefCountVector CellRefCounts Reference counts for Cells list.
Protected variable TDynamicVector< FSparsePointOctreeCell > 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< uint32 > PointIDToCellMap  
Protected variable TSparseGrid3< uint32 > RootCells RootCells are the top-level cells of the octree, of size RootDimension.
Public variable double RootDimension Potential optimizations/improvements

Functions

  Type Name Description
Protected function Const bool

CellContains ( const FSparsePointOctreeCell& Cell,
const FVector3d& Position
)

  
Public function Const void

CheckValidity ( TFunctionRef< bool(int)> IsValidPointIDFunc,
TFunctionRef< FVector3d(int)> GetPointFunc,
EValidityCheckFailMode FailMode,
bool bVerbose,
bool bFailOnMissingPoints
)

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

ConfigureFromPointCountEstimate ( double MaxBoundsDimension,
int CountEstimate
)

 Do a rough ballpark configuration of the RootDimension, MaxTreeDepth, and MaxPointsPerCell tree config values, given a bounding-box dimension and estimate of the total number of points that will be inserted.
Public function Const bool

ContainsPoint ( int32 PointID
)

 Test if an Point is stored in the tree
Protected function uint32

CreateNewRootCell ( FSparsePointOctreeCell NewRootCell,
bool bInitializeCellPointList
)

  
Protected function Const FSparsePointOctreeCell

FindCurrentContainingCell ( const FVector3d& Position
)

  
Public function Const int32

FindNearestHitPoint ( const FRay3d& Ray,
TFunctionRef< double(int, const FRay3d&)> HitPointDistFunc,
double MaxDistance
)

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

GetCellBox ( uint32 Level,
const FVector3i& Index
)

  
Protected function Const FAxisAlignedBox3d  
Protected function Const FVector3d

GetCellCenter ( uint32 Level,
const FVector3i& Index
)

  
Protected function Const FVector3d  
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& ExistingCell
)

  
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(int)> GetPositionFunc
)

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

ParallelInsertDensePointSet ( int32 MaxPointID,
TFunctionRef< FVector3d(int)> GetPositionFunc
)

 Insert a set of dense points with IDs in range [0, MaxPointID-1], in parallel.
Public function Const void

ParallelRangeQuery ( const FAxisAlignedBox3d& Bounds,
TFunctionRef< bool(int)> PredicateFunc,
TArray< int >& PointIDsOut,
TArray< const FSparsePointOctreeCell* >* TempBuffer
)

 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(int)> PredicateFunc,
TArray< int >& PointIDsOut,
TArray< const FSparsePointOctreeCell* >* TempBuffer
)

 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 a Point from the octree
Public function void

RemovePointUnsafe ( int32 PointID
)

 Remove a Point from the octree.
Protected function Const int

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

  
Protected function Const int

ToChildCellIndex ( uint32 Level,
const FVector3i& Index,
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

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page