1. Epic GamesDeveloper
  3. FSparseDynamicPointOctree3

FSparseDynamicPointOctree3

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

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.

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

Syntax

class FSparseDynamicPointOctree3

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/SparseDynamicPointOctree3.h

Variables

Public

Name Type Remarks Include Path Unreal Specifiers
MaxPointsPerCell int 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 Spatial/SparseDynamicPointOctree3.h  
MaxTreeDepth int Points will not be inserted more than this many levels deep from a Root cell Spatial/SparseDynamicPointOctree3.h  
RootDimension double Potential optimizations/improvements Spatial/SparseDynamicPointOctree3.h  

Functions

Public

Name Remarks Include Path Unreal Specifiers

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

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

void ComputeStatistics ( FStatistics& StatsOut
) const

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

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

bool ContainsPoint ( int32 PointID
) const

 Test if an Point is stored in the tree Spatial/SparseDynamicPointOctree3.h  

int32 FindClosestPoint ( FVector3d QueryPt,
double DistanceThreshold,
TFunctionRef< bool(int32)> PredicateFunc,
TFunctionRef< double(int32)> DistSqFunc,
TArray< const FSparsePointOctreeCell* >* TempBuffer
) const

 Find closest point in the tree, relative to a query point, within a search distance Spatial/SparseDynamicPointOctree3.h  

void FindKClosestPoints ( FVector3d QueryPt,
double DistanceThreshold,
int32 NumToFind,
TArray< TPair< int32, double > >& FoundPoints,
TFunctionRef< bool(int32)> PredicateFunc,
TFunctionRef< double(int32)> DistSqFunc,
TArray< const FSparsePointOctreeCell* >* TempBuffer
) const

 Find the K closest point in the tree, relative to a query point, within a search distance Spatial/SparseDynamicPointOctree3.h  

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

 Find nearest ray-hit point with Points in tree Spatial/SparseDynamicPointOctree3.h  

void InsertPoint ( int32 PointID,
const FVector3d& Position
)

 Insert PointID into the Octree at maximum depth. Spatial/SparseDynamicPointOctree3.h  

void InsertPoint_DynamicExpand ( int32 PointID,
TFunctionRef< FVector3d(int)> GetPositionFunc
)

 Insert PointID into the Octree. Dynamically expands cells that have more than MaxPointsPerCell Spatial/SparseDynamicPointOctree3.h  

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

 Insert a set of dense points with IDs in range [0, MaxPointID-1], in parallel. Spatial/SparseDynamicPointOctree3.h  

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

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

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

 Collect PointIDs from all the cells with bounding boxes that intersect Bounds, where PredicateFunc passes Spatial/SparseDynamicPointOctree3.h  

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

bool RemovePoint ( int32 PointID
)

 Remove a Point from the octree Spatial/SparseDynamicPointOctree3.h  

void RemovePointUnsafe ( int32 PointID
)

 Remove a Point from the octree. Spatial/SparseDynamicPointOctree3.h  

Protected

Name Remarks Include Path Unreal Specifiers

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

   Spatial/SparseDynamicPointOctree3.h  

uint32 CreateNewRootCell ( FSparsePointOctreeCell NewRootCell,
bool bInitializeCellPointList
)

   Spatial/SparseDynamicPointOctree3.h  

FSparsePointOctreeCell FindCurrentContainingCell ( const FVector3d& Position
) const

   Spatial/SparseDynamicPointOctree3.h  

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

   Spatial/SparseDynamicPointOctree3.h  

FAxisAlignedBox3d GetCellBox ( uint32 Level,
const FVector3i& Index
) const

   Spatial/SparseDynamicPointOctree3.h  

FAxisAlignedBox3d GetCellBox ( const FSparsePointOctreeCell& Cell
) const

   Spatial/SparseDynamicPointOctree3.h  

FVector3d GetCellCenter ( uint32 Level,
const FVector3i& Index
) const

   Spatial/SparseDynamicPointOctree3.h  

FVector3d GetCellCenter ( const FSparsePointOctreeCell& Cell
) const

   Spatial/SparseDynamicPointOctree3.h  

uint32 GetCellForPoint ( int32 PointID
) const

   Spatial/SparseDynamicPointOctree3.h  

double GetCellWidth ( uint32 Level
) const

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

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

   Spatial/SparseDynamicPointOctree3.h  

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

   Spatial/SparseDynamicPointOctree3.h  

void Insert_ToCell ( int32 PointID,
const FVector3d& Position,
const FSparsePointOctreeCell& ExistingCell
)

   Spatial/SparseDynamicPointOctree3.h  

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

   Spatial/SparseDynamicPointOctree3.h  

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

   Spatial/SparseDynamicPointOctree3.h  

int ToChildCellIndex ( uint32 Level,
const FVector3i& Index,
const FVector3d& Position
) const

   Spatial/SparseDynamicPointOctree3.h  

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page