 FSparseDynamicPointOctree3

Module 

Header 
/Engine/Plugins/Experimental/GeometryProcessing/Source/GeometricObjects/Public/Spatial/SparseDynamicPointOctree3.h 
Include 
#include "Spatial/SparseDynamicPointOctree3.h" 
class FSparseDynamicPointOctree3
FSparseDynamicPointOctree3 sorts Points with axisaligned bounding boxes into a dynamic sparse octree of axisaligned 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 boundingboxes 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 reinserted.
Name  Description  


CellPointLists 


CellRefCounts 
Reference counts for Cells list. 


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

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 

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

TDynamicVector<... 
PointIDToCellMap 


TSparseGrid3< u... 
RootCells 
RootCells are the toplevel cells of the octree, of size RootDimension. 

double 
RootDimension 
Potential optimizations/improvements 

ValidPointIDs 
Name  Description  


CellContains ( 


CheckValidity ( 
Check that the octree is internally valid 


ComputeStatistics ( 
Populate given FStatistics with info about the octree 


ContainsPoint ( 
Test if an Point is stored in the tree 


FSparsePoint... 
FindCurrentContainingCell ( 


FindNearestHitPoint ( 
Find nearest rayhit point with Points in tree 


double 
FindNearestRayCellIntersection ( 


FAxisAligned... 
GetCellBox ( 


FAxisAligned... 
GetCellBox 


GetCellCenter ( 


GetCellForPoint ( 


double 
GetCellWidth ( 
Calculate the base width of a cell at a given level 

Insert_NewChildCell ( 


Insert_NewRoot ( 


Insert_ToCell ( 


InsertPoint 
Insert PointID into the Octree at maximum depth. 


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


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


PointToIndex 


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


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


RemovePoint ( 
Remove an Point from the octree 


int 
ToChildCellIndex ( 
Name 
Description 



FStatistics 
Statistics about internal structure of the octree 
Name 
Description 

InvalidCellID 
This identifier is used for unknown cells 