#include <SparseDynamicOctree3.h>

Inheritance diagram for UE::Geometry::FSparseDynamicOctree3:

Classes
struct	FStatistics

Public Member Functions
int	GetMaxTreeDepth ()

void	SetMaxTreeDepth (int MaxTreeDepthIn)

GEOMETRYCORE_API bool	ContainsObject (int32 ObjectID) const

GEOMETRYCORE_API void	InsertObject (int32 ObjectID, const FAxisAlignedBox3d &Bounds)

GEOMETRYCORE_API bool	RemoveObject (int32 ObjectID)

GEOMETRYCORE_API bool	ReinsertObject (int32 ObjectID, const FAxisAlignedBox3d &NewBounds, uint32 CellIDHint=InvalidCellID)

GEOMETRYCORE_API bool	CheckIfObjectNeedsReinsert (int32 ObjectID, const FAxisAlignedBox3d &NewBounds, uint32 &CellIDOut) const

GEOMETRYCORE_API int32	FindNearestHitObject (const FRay3d &Ray, TFunctionRef< FAxisAlignedBox3d(int)> GetObjectBoundsFunc, TFunctionRef< double(int, const FRay3d &)> HitObjectDistFunc, double MaxDistance=TNumericLimits< double >::Max()) const

GEOMETRYCORE_API void	ContainmentQuery (const FVector3d &Point, TFunctionRef< void(int)> ObjectIDFunc) const

GEOMETRYCORE_API bool	ContainmentQueryCancellable (const FVector3d &Point, TFunctionRef< bool(int)> ObjectIDFunc) const

GEOMETRYCORE_API void	RangeQuery (const FAxisAlignedBox3d &Bounds, TFunctionRef< void(int)> ObjectIDFunc) const

GEOMETRYCORE_API void	RangeQuery (const FAxisAlignedBox3d &Bounds, TArray< int > &ObjectIDsOut) const

GEOMETRYCORE_API void	ParallelRangeQuery (const FAxisAlignedBox3d &Bounds, TArray< int > &ObjectIDsOut) const

GEOMETRYCORE_API void	ParallelRangeQuery (const FAxisAlignedBox3d &RangeBoundsHint, TFunctionRef< bool(const FAxisAlignedBox3d &CellBounds)> BoundsOverlapFn, TArray< int32 > &ObjectIDs) const

GEOMETRYCORE_API int	ParallelOverlapAnyQuery (const FAxisAlignedBox3d &ShapeBounds, TFunctionRef< bool(int32)> ObjectOverlapFn, TFunctionRef< bool(const FAxisAlignedBox3d &)> BoundsOverlapFn) const

int	ParallelOverlapAnyQuery (const FAxisAlignedBox3d &ShapeBounds, TFunctionRef< bool(int32)> ObjectOverlapFn) const

GEOMETRYCORE_API void	CheckValidity (TFunctionRef< bool(int)> IsValidObjectIDFunc, TFunctionRef< FAxisAlignedBox3d(int)> GetObjectBoundsFunc, EValidityCheckFailMode FailMode=EValidityCheckFailMode::Check, bool bVerbose=false, bool bFailOnMissingObjects=false) const

GEOMETRYCORE_API void	ComputeStatistics (FStatistics &StatsOut) const

Public Attributes
double	RootDimension = 1000.0

double	MaxExpandFactor = 0.25

Static Public Attributes
static constexpr uint32	MaxSupportedTreeDepth = 0x1F

Protected Member Functions
double	GetCellWidth (uint32 Level) const

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

FAxisAlignedBox3d	GetCellBox (const FSparseOctreeCell &Cell, double ExpandFactor=0) const

FVector3d	GetCellCenter (const FSparseOctreeCell &Cell) const

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

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

bool	CanFit (const FSparseOctreeCell &Cell, const FAxisAlignedBox3d &Bounds) const

uint32	GetCellForObject (int32 ObjectID) const

GEOMETRYCORE_API FSparseOctreeCell	FindCurrentContainingCell (const FAxisAlignedBox3d &Bounds) const

GEOMETRYCORE_API void	Insert_Spill (int32 ObjectID, const FAxisAlignedBox3d &Bounds)

GEOMETRYCORE_API void	Insert_NewRoot (int32 ObjectID, const FAxisAlignedBox3d &Bounds, FSparseOctreeCell NewRootCell)

GEOMETRYCORE_API void	Insert_ToCell (int32 ObjectID, const FAxisAlignedBox3d &Bounds, const FSparseOctreeCell &ExistingCell)

GEOMETRYCORE_API void	Insert_NewChildCell (int32 ObjectID, const FAxisAlignedBox3d &Bounds, int ParentCellID, FSparseOctreeCell NewChildCell, int ChildIdx)

GEOMETRYCORE_API double	FindNearestRayCellIntersection (const FSparseOctreeCell &Cell, const FRay3d &Ray) const

GEOMETRYCORE_API void	BranchRangeQuery (const FSparseOctreeCell *ParentCell, const FAxisAlignedBox3d &Bounds, TArray< int > &ObjectIDs) const

Protected Attributes
int	MaxTreeDepth = 10

FRefCountVector	CellRefCounts

TDynamicVector< FSparseOctreeCell >	Cells

FSmallListSet	CellObjectLists

TSet< int32 >	SpillObjectSet

TDynamicVector< uint32 >	ObjectIDToCellMap

FDynamicFlagArray	ValidObjectIDs

TSparseGrid3< uint32 >	RootCells

Static Protected Attributes
static constexpr uint32	InvalidCellID = FSparseOctreeCell::InvalidID

static constexpr uint32	SpillCellID = InvalidCellID - 1

Detailed Description

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.

Member Function Documentation

◆ BranchRangeQuery()

void FSparseDynamicOctree3::BranchRangeQuery	(	const FSparseOctreeCell *	ParentCell,
		const FAxisAlignedBox3d &	Bounds,
		TArray< int > &	ObjectIDs
	)		const

protected

◆ CanFit()

bool UE::Geometry::FSparseDynamicOctree3::CanFit	(	const FSparseOctreeCell &	Cell,
		const FAxisAlignedBox3d &	Bounds
	)		const

inlineprotected

◆ CheckIfObjectNeedsReinsert()

bool FSparseDynamicOctree3::CheckIfObjectNeedsReinsert	(	int32	ObjectID,
		const FAxisAlignedBox3d &	NewBounds,
		uint32 &	CellIDOut
	)		const

Check if the object needs to be reinserted, if it has NewBounds.

Parameters

ObjectID	ID of the object
NewBounds	new bounding box of the object
CellIDOut	returned CellID of the object, if it is in the tree. This can be passed to ReinsertObject() to save some computation.

Returns: false if ObjectID is already in the tree, and NewBounds fits within the cell that currently contains ObjectID

◆ CheckValidity()

void FSparseDynamicOctree3::CheckValidity	(	TFunctionRef< bool(int)>	IsValidObjectIDFunc,
		TFunctionRef< FAxisAlignedBox3d(int)>	GetObjectBoundsFunc,
		EValidityCheckFailMode	FailMode = `EValidityCheckFailMode::Check`,
		bool	bVerbose = `false`,
		bool	bFailOnMissingObjects = `false`
	)		const

Check that the octree is internally valid

Parameters

IsValidObjectIDFunc	function that returns true if given ObjectID is valid
GetObjectBoundSFunc	function that returns bounding box of object identified by ObjectID
FailMode	how should validity checks fail
bVerbose	if true, print some debug info via UE_LOG
bFailOnMissingObjects	if true, assume ObjectIDs are dense and that all ObjectIDs must be in the tree

◆ ComputeStatistics()

void FSparseDynamicOctree3::ComputeStatistics ( FStatistics & StatsOut ) const

Populate given FStatistics with info about the octree

◆ ContainmentQuery()

void FSparseDynamicOctree3::ContainmentQuery	(	const FVector3d &	Point,
		TFunctionRef< void(int)>	ObjectIDFunc
	)		const

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

Parameters

Point	query point
ObjectIDFunc	this function is called for each ObjectID

◆ ContainmentQueryCancellable()

bool FSparseDynamicOctree3::ContainmentQueryCancellable	(	const FVector3d &	Point,
		TFunctionRef< bool(int)>	ObjectIDFunc
	)		const

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

Parameters

Point	query point
ObjectIDFunc	this function is called for each ObjectID. Returns true to continue query and false to abort

Returns: true if query finished, false if it exited

◆ ContainsObject()

bool FSparseDynamicOctree3::ContainsObject ( int32 ObjectID ) const

Test if an object is stored in the tree

Parameters

ObjectID ID of the object

Returns: true if ObjectID is stored in this octree

◆ FindCurrentContainingCell()

FSparseOctreeCell FSparseDynamicOctree3::FindCurrentContainingCell ( const FAxisAlignedBox3d & Bounds ) const

protected

◆ FindNearestHitObject()

int32 FSparseDynamicOctree3::FindNearestHitObject	(	const FRay3d &	Ray,
		TFunctionRef< FAxisAlignedBox3d(int)>	GetObjectBoundsFunc,
		TFunctionRef< double(int, const FRay3d &)>	HitObjectDistFunc,
		double	MaxDistance = `TNumericLimits<double>::Max()`
	)		const

Find nearest ray-hit point with objects in tree

Parameters

Ray	the ray
GetObjectBoundsFunc	function that returns bounding box of object identified by ObjectID
HitObjectDistFunc	function that returns distance along ray to hit-point on object identified by ObjectID (or TNumericLimits<double>::Max() on miss)
MaxDistance	maximum hit distance

Returns: ObjectID of hit object, or -1 on miss

◆ FindNearestRayCellIntersection()

double FSparseDynamicOctree3::FindNearestRayCellIntersection	(	const FSparseOctreeCell &	Cell,
		const FRay3d &	Ray
	)		const

protected

◆ GetBox()

FAxisAlignedBox3d UE::Geometry::FSparseDynamicOctree3::GetBox	(	uint32	Level,
		const FVector3i &	Index,
		double	ExpandFactor
	)		const

inlineprotected

◆ GetCellBox()

FAxisAlignedBox3d UE::Geometry::FSparseDynamicOctree3::GetCellBox	(	const FSparseOctreeCell &	Cell,
		double	ExpandFactor = `0`
	)		const

inlineprotected

◆ GetCellCenter()

FVector3d UE::Geometry::FSparseDynamicOctree3::GetCellCenter ( const FSparseOctreeCell & Cell ) const

inlineprotected

◆ GetCellForObject()

uint32 UE::Geometry::FSparseDynamicOctree3::GetCellForObject ( int32 ObjectID ) const

inlineprotected

◆ GetCellWidth()

double UE::Geometry::FSparseDynamicOctree3::GetCellWidth ( uint32 Level ) const

inlineprotected

◆ GetMaxTreeDepth()

int UE::Geometry::FSparseDynamicOctree3::GetMaxTreeDepth ( )

inline

◆ Insert_NewChildCell()

void FSparseDynamicOctree3::Insert_NewChildCell	(	int32	ObjectID,
		const FAxisAlignedBox3d &	Bounds,
		int	ParentCellID,
		FSparseOctreeCell	NewChildCell,
		int	ChildIdx
	)

protected

◆ Insert_NewRoot()

void FSparseDynamicOctree3::Insert_NewRoot	(	int32	ObjectID,
		const FAxisAlignedBox3d &	Bounds,
		FSparseOctreeCell	NewRootCell
	)

protected

◆ Insert_Spill()

void FSparseDynamicOctree3::Insert_Spill	(	int32	ObjectID,
		const FAxisAlignedBox3d &	Bounds
	)

protected

◆ Insert_ToCell()

void FSparseDynamicOctree3::Insert_ToCell	(	int32	ObjectID,
		const FAxisAlignedBox3d &	Bounds,
		const FSparseOctreeCell &	ExistingCell
	)

protected

◆ InsertObject()

void FSparseDynamicOctree3::InsertObject	(	int32	ObjectID,
		const FAxisAlignedBox3d &	Bounds
	)

Insert ObjectID into the Octree

Parameters

ObjectID	ID of the object to insert
Bounds	bounding box of the object

◆ ParallelOverlapAnyQuery() [1/2]

int UE::Geometry::FSparseDynamicOctree3::ParallelOverlapAnyQuery	(	const FAxisAlignedBox3d &	ShapeBounds,
		TFunctionRef< bool(int32)>	ObjectOverlapFn
	)		const

inline

Find any overlap between a caller-defined query and any object ID. Returns the first overlap it finds.

Parameters

ShapeBounds	Overall bounds of the custom query shape
ObjectOverlapFn	Custom function that indicates if the given ObjectID overlaps the query shape

Returns: index of overlapping ObjectID or INDEX_NONE if no overlaps are found

◆ ParallelOverlapAnyQuery() [2/2]

int FSparseDynamicOctree3::ParallelOverlapAnyQuery	(	const FAxisAlignedBox3d &	ShapeBounds,
		TFunctionRef< bool(int32)>	ObjectOverlapFn,
		TFunctionRef< bool(const FAxisAlignedBox3d &)>	BoundsOverlapFn
	)		const

Find any overlap between a caller-defined query and any object ID. Returns the first overlap it finds.

Parameters

ShapeBounds	Overall bounds of the custom query shape
ObjectOverlapFn	Custom function that indicates if the given ObjectID overlaps the query shape
BoundsOverlapFn	Optional custom function that indicates if the given bounding box overlaps the query shape, used to filter the octree search. Note the bounds overlap with ShapeBounds will already be called before calling this; only provide this if a more accurate overlap can be quickly checked.

Returns: index of overlapping ObjectID or INDEX_NONE if no overlaps are found

◆ ParallelRangeQuery() [1/2]

void FSparseDynamicOctree3::ParallelRangeQuery	(	const FAxisAlignedBox3d &	Bounds,
		TArray< int > &	ObjectIDsOut
	)		const

Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds. Current implementation creates a separate TArray for each thread.

Parameters

Bounds	query box
ObjectIDsOut	collected ObjectIDs are stored here

◆ ParallelRangeQuery() [2/2]

void FSparseDynamicOctree3::ParallelRangeQuery	(	const FAxisAlignedBox3d &	RangeBoundsHint,
		TFunctionRef< bool(const FAxisAlignedBox3d &CellBounds)>	BoundsOverlapFn,
		TArray< int32 > &	ObjectIDs
	)		const

Collect ObjectIDs from all the leaf cells that have bounding boxes that pass BoundsOverlapFn

Parameters

RangeBoundsHint	A box to potentially limit the iteration range across cells. Note that this might be ignored if the allocation of cells is such that trying to check for cells in that range would take more time than just iterating over all allocated cells.
BoundsOverlapFn	Must be thread-safe. Used to determine if the cell is part of the desired range.
ObjectIDsOut	collected ObjectIDs are stored here

◆ PointToIndex()

FVector3i UE::Geometry::FSparseDynamicOctree3::PointToIndex	(	uint32	Level,
		const FVector3d &	Position
	)		const

inlineprotected

◆ RangeQuery() [1/2]

void FSparseDynamicOctree3::RangeQuery	(	const FAxisAlignedBox3d &	Bounds,
		TArray< int > &	ObjectIDsOut
	)		const

Collect ObjectIDs from all the cells with bounding boxes that intersect Bounds

Parameters

Bounds	query box
ObjectIDsOut	collected ObjectIDs are stored here

◆ RangeQuery() [2/2]

void FSparseDynamicOctree3::RangeQuery	(	const FAxisAlignedBox3d &	Bounds,
		TFunctionRef< void(int)>	ObjectIDFunc
	)		const

Process ObjectIDs from all the cells with bounding boxes that intersect Bounds

Parameters

Bounds	query box
ObjectIDFunc	this function is called for each ObjectID

◆ ReinsertObject()

bool FSparseDynamicOctree3::ReinsertObject	(	int32	ObjectID,
		const FAxisAlignedBox3d &	NewBounds,
		uint32	CellIDHint = `InvalidCellID`
	)

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

Parameters

ObjectID	ID of the object
NewBounds	new bounding box of the object

Returns: true if object was reinserted, false if the object was fine in it's existing cell

◆ RemoveObject()

bool FSparseDynamicOctree3::RemoveObject ( int32 ObjectID )

Remove an object from the octree

Parameters

ObjectID ID of the object

Returns: true if the object was in the tree and removed

◆ SetMaxTreeDepth()

void UE::Geometry::FSparseDynamicOctree3::SetMaxTreeDepth ( int MaxTreeDepthIn )

inline

Sets max tree depth w/ protection against setting beyond supported max

◆ ToChildCellIndex()

int UE::Geometry::FSparseDynamicOctree3::ToChildCellIndex	(	const FSparseOctreeCell &	Cell,
		const FVector3d &	Position
	)		const

inlineprotected

Member Data Documentation

◆ CellObjectLists

FSmallListSet UE::Geometry::FSparseDynamicOctree3::CellObjectLists

protected

◆ CellRefCounts

FRefCountVector UE::Geometry::FSparseDynamicOctree3::CellRefCounts

protected

◆ Cells

TDynamicVector<FSparseOctreeCell> UE::Geometry::FSparseDynamicOctree3::Cells

protected

◆ InvalidCellID

constexpr uint32 FSparseDynamicOctree3::InvalidCellID = FSparseOctreeCell::InvalidID

staticconstexprprotected

◆ MaxExpandFactor

double UE::Geometry::FSparseDynamicOctree3::MaxExpandFactor = 0.25

Fraction we expand the dimension of any cell, to allow extra space to fit objects.

◆ MaxSupportedTreeDepth

constexpr uint32 FSparseDynamicOctree3::MaxSupportedTreeDepth = 0x1F

staticconstexpr

◆ MaxTreeDepth

int UE::Geometry::FSparseDynamicOctree3::MaxTreeDepth = 10

protected

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

◆ ObjectIDToCellMap

TDynamicVector<uint32> UE::Geometry::FSparseDynamicOctree3::ObjectIDToCellMap

protected

◆ RootCells

TSparseGrid3<uint32> UE::Geometry::FSparseDynamicOctree3::RootCells

protected

◆ RootDimension

double UE::Geometry::FSparseDynamicOctree3::RootDimension = 1000.0

Size of the Root cells of the octree. Objects that don't fit in a Root cell are added to a "Spill set"

◆ SpillCellID

constexpr uint32 FSparseDynamicOctree3::SpillCellID = InvalidCellID - 1

staticconstexprprotected

◆ SpillObjectSet

TSet<int32> UE::Geometry::FSparseDynamicOctree3::SpillObjectSet

protected

◆ ValidObjectIDs

FDynamicFlagArray UE::Geometry::FSparseDynamicOctree3::ValidObjectIDs

protected

The documentation for this class was generated from the following files:

Engine/Source/Runtime/GeometryCore/Public/Spatial/SparseDynamicOctree3.h
Engine/Source/Runtime/GeometryCore/Private/Spatial/SparseDynamicOctree3.cpp

Classes

Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Function Documentation

◆ BranchRangeQuery()

◆ CanFit()

◆ CheckIfObjectNeedsReinsert()

◆ CheckValidity()

◆ ComputeStatistics()

◆ ContainmentQuery()

◆ ContainmentQueryCancellable()

◆ ContainsObject()

◆ FindCurrentContainingCell()

◆ FindNearestHitObject()

◆ FindNearestRayCellIntersection()

◆ GetBox()

◆ GetCellBox()

◆ GetCellCenter()

◆ GetCellForObject()

◆ GetCellWidth()

◆ GetMaxTreeDepth()

◆ Insert_NewChildCell()

◆ Insert_NewRoot()

◆ Insert_Spill()

◆ Insert_ToCell()

◆ InsertObject()

◆ ParallelOverlapAnyQuery() [1/2]

◆ ParallelOverlapAnyQuery() [2/2]

◆ ParallelRangeQuery() [1/2]

◆ ParallelRangeQuery() [2/2]

◆ PointToIndex()

◆ RangeQuery() [1/2]

◆ RangeQuery() [2/2]

◆ ReinsertObject()

◆ RemoveObject()

◆ SetMaxTreeDepth()

◆ ToChildCellIndex()

Member Data Documentation

◆ CellObjectLists

◆ CellRefCounts

◆ Cells

◆ InvalidCellID

◆ MaxExpandFactor

◆ MaxSupportedTreeDepth

◆ MaxTreeDepth

◆ ObjectIDToCellMap

◆ RootCells

◆ RootDimension

◆ SpillCellID

◆ SpillObjectSet

◆ ValidObjectIDs