 |
UDocumentation UE5.7 10.02.2026 (Source)
API documentation for Unreal Engine 5.7
|
|
UDocumentation UE5.7 10.02.2026 (Source)
API documentation for Unreal Engine 5.7
|
#include <SparseDynamicPointOctree3.h>
Inheritance diagram for UE::Geometry::FSparseDynamicPointOctree3:Classes | |
| struct | FStatistics |
Public Attributes | |
| double | RootDimension = 1000.0 |
| int | MaxTreeDepth = 10 |
| int | MaxPointsPerCell = 1000 |
Protected Attributes | |
| FRefCountVector | CellRefCounts |
| TDynamicVector< FSparsePointOctreeCell > | Cells |
| TSparseListSet< int32 > | CellPointLists |
| TDynamicVector< uint32 > | PointIDToCellMap |
| TSparseGrid3< uint32 > | RootCells |
Static Protected Attributes | |
| static constexpr uint32 | InvalidCellID = FSparsePointOctreeCell::InvalidID |
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.
|
inlineprotected |
|
inline |
Check that the octree is internally valid
| IsValidPointIDFunc | function that returns true if given PointID is valid |
| GetPointFunc | function that returns point position identified by PointID |
| FailMode | how should validity checks fail |
| bVerbose | if true, print some debug info via UE_LOG |
| bFailOnMissingPoints | if true, assume PointIDs are dense and that all PointIDs must be in the tree |
|
inline |
Populate given FStatistics with info about the octree
|
inline |
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. This is primarily intended to be used with ParallelInsertDensePointSet()
Test if an Point is stored in the tree
| PointID | ID of the Point |
|
inlineprotected |
| int32 UE::Geometry::FSparseDynamicPointOctree3::FindClosestPoint | ( | FVector3d | QueryPt, |
| double | DistanceThreshold, | ||
| TFunctionRef< bool(int32)> | PredicateFunc, | ||
| TFunctionRef< double(int32)> | DistSqFunc, | ||
| TArray< const FSparsePointOctreeCell * > * | TempBuffer = nullptr |
||
| ) | const |
Find closest point in the tree, relative to a query point, within a search distance
| QueryPt | Find the point closest to this query point |
| DistanceThreshold | Limit the search to this distance |
| PredicateFunc | Return true if point should be included (i.e., this is a filter) |
| DistSqFunc | User-provided squared distance between the point with the given ID and the QueryPt |
| TempBuffer | Optional temporary buffer to store a queue of cells (to avoid memory allocations) |
|
inlineprotected |
| void UE::Geometry::FSparseDynamicPointOctree3::FindKClosestPoints | ( | FVector3d | QueryPt, |
| double | DistanceThreshold, | ||
| int32 | NumToFind, | ||
| TArray< TPair< int32, double > > & | FoundPoints, | ||
| TFunctionRef< bool(int32)> | PredicateFunc, | ||
| TFunctionRef< double(int32)> | DistSqFunc, | ||
| TArray< const FSparsePointOctreeCell * > * | TempBuffer = nullptr |
||
| ) | const |
Find the K closest point in the tree, relative to a query point, within a search distance
| QueryPt | Find the points closest to this query point |
| DistanceThreshold | Limit the search to this distance |
| NumToFind | The maximum number of closest points to find |
| FoundPoints | The found closest points will be added to this array |
| PredicateFunc | Return true if point should be included (i.e., this is a filter) |
| DistSqFunc | User-provided squared distance between the point with the given ID and the QueryPt |
| TempBuffer | Optional temporary buffer to store a queue of cells (to avoid memory allocations) |
|
inline |
Find nearest ray-hit point with Points in tree
| Ray | the ray |
| HitPointDistFunc | function that returns distance along ray to hit-point on Point identified by PointID (or TNumericLimits<double>::Max() on miss) |
| MaxDistance | maximum hit distance |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
|
inline |
Insert PointID into the Octree at maximum depth. Currently only expands at most one depth-level per insertion. This is sub-optimal.
| PointID | ID of the Point to insert |
| Position | position of the Point |
|
inline |
Insert PointID into the Octree. Dynamically expands cells that have more than MaxPointsPerCell
| PointID | ID of the Point to insert |
| GetPositionFunc | function that returns position of point (Required to reinsert points on expand) |
|
inline |
Insert a set of dense points with IDs in range [0, MaxPointID-1], in parallel. The points are only inserted in leaf nodes, at MaxTreeDepth level, so that value should be set conservatively. Parallel insertion is across root cells, so if the RootDimension is larger than the point set bounds, this will be slower than incremental construction. ConfigureFromPointCountEstimate() provides reasonable values for large point sets.
| GetPositionFunc | function that returns position of point (Required to reinsert points on expand) |
|
inline |
Collect PointIDs from all the cells with bounding boxes that intersect Bounds, where PredicateFunc passes Query is parallelized across Root cells. So if there is only one Root cell, it's actually slower than RangeQuery() due to internal temp buffers.
| Bounds | query box |
| PredicateFunc | return true if point should be included (ie this is a filter) |
| PointIDsOut | collected PointIDs are stored here |
| TempBuffer | optional temporary buffer to store a queue of cells (to avoid memory allocations) |
|
inlineprotected |
|
inline |
Collect PointIDs from all the cells with bounding boxes that intersect Bounds, where PredicateFunc passes
| Bounds | query box |
| PredicateFunc | return true if point should be included (ie this is a filter) |
| PointIDsOut | collected PointIDs are stored here |
| TempBuffer | optional temporary buffer to store a queue of cells (to avoid memory allocations) |
|
inline |
Update the position of an Point in the octree. This is more efficient than doing a remove+insert
| PointID | ID of the Point |
| NewBounds | enw bounding box of the Point |
Remove a Point from the octree
| PointID | ID of the Point |
Remove a Point from the octree. This function must only be called with PointIDs that are certain to be in the tree.
| PointID | ID of the Point. |
|
inlineprotected |
|
inlineprotected |
|
protected |
|
protected |
|
protected |
|
staticconstexprprotected |
| int UE::Geometry::FSparseDynamicPointOctree3::MaxPointsPerCell = 1000 |
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 UE::Geometry::FSparseDynamicPointOctree3::MaxTreeDepth = 10 |
Points will not be inserted more than this many levels deep from a Root cell
|
protected |
|
protected |
| double UE::Geometry::FSparseDynamicPointOctree3::RootDimension = 1000.0 |
Size of the Root cells of the octree.
1.9.8 