AXOM
Axom provides a robust, flexible software infrastructure for the development of multi-physics applications and computational tools.
axom::spin::SpatialOctree< DIM, BlockDataType > Class Template Reference

Adds spatial extents to an OctreeBase, allowing point location. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/docs-essman-container_strict/src/axom/spin/SpatialOctree.hpp>

Inheritance diagram for axom::spin::SpatialOctree< DIM, BlockDataType >:

Public Types

using GeometricBoundingBox = primal::BoundingBox< double, DIM >
 
using SpacePt = primal::Point< double, DIM >
 
using SpaceVector = primal::Vector< double, DIM >
 
using BaseOctree = OctreeBase< DIM, BlockDataType >
 
using GridPt = typename BaseOctree::GridPt
 
using CoordType = typename GridPt::CoordType
 
using BlockIndex = typename BaseOctree::BlockIndex
 
using SpaceVectorLevelMap = slam::Map< slam::Set<>, SpaceVector >
 
using GridVec = primal::Vector< CoordType, DIM >
 
using MAX_LEVEL_SIZE = slam::policies::CompileTimeSize< CoordType, std::numeric_limits< CoordType >::digits >
 
using OctreeLevels = slam::OrderedSet< CoordType, CoordType, MAX_LEVEL_SIZE >
 
using OctreeLevelType = OctreeLevel< DIM, BlockDataType >
 
using LeafIndicesLevelMap = slam::Map< slam::Set< CoordType, CoordType >, OctreeLevelType * >
 

Public Member Functions

 SpatialOctree (const GeometricBoundingBox &bb)
 Construct a spatial octree from a spatial bounding box. More...
 
const GeometricBoundingBoxboundingBox () const
 Returns a reference to the octree's bounding box (i.e. the bounding box of the root block) More...
 
GeometricBoundingBox blockBoundingBox (const BlockIndex &block) const
 Return the spatial bounding box of a grid cell at the given level or resolution. More...
 
GeometricBoundingBox blockBoundingBox (const GridPt &gridPt, int level) const
 Return the spatial bounding box of a grid cell at the given level or resolution. More...
 
const SpaceVectorspacingAtLevel (int level) const
 
BlockIndex findLeafBlock (const SpacePt &pt, int startingLevel=-1) const
 Finds the index of the leaf block covering the query point pt. More...
 
GridPt findGridCellAtLevel (const SpacePt &pt, int lev) const
 Utility function to find the quantized grid cell at level lev for query point pt. More...
 
int maxLeafLevel () const
 The max level for leaf blocks of the octree. More...
 
int maxInternalLevel () const
 The max level for internal blocks of the octree. More...
 
OctreeLevelTypegetOctreeLevel (int lev)
 Accessor for a reference to the octree level instance at level lev. More...
 
const OctreeLevelTypegetOctreeLevel (int lev) const
 Const accessor for a reference to the octree level instance at level lev. More...
 
bool isLevelValid (int lev) const
 Predicate to determine if level lev is in the range. More...
 
bool isLeaf (const GridPt &pt, int lev) const
 Determine whether the octree contains a leaf block associated with grid point pt at level lev. More...
 
bool isLeaf (const BlockIndex &block) const
 Determine whether the octree contains a leaf block associated with this BlockIndex. More...
 
bool isInternal (const GridPt &pt, int lev) const
 Determine whether the octree contains an internal block associated with grid point pt at level lev. More...
 
bool isInternal (const BlockIndex &block) const
 Determine whether the octree contains an internal block associated with this BlockIndex. More...
 
bool hasBlock (const GridPt &pt, int lev) const
 Determine whether the octree contains a block (internal or leaf) associated with grid point pt at level lev. More...
 
bool hasBlock (const BlockIndex &block) const
 Determine whether the octree contains a block (internal or leaf) associated with this BlockIndex. More...
 
bool inBounds (const GridPt &pt, int lev) const
 Determine whether the octree block associated with grid point pt and level lev is a possible block in this octree. More...
 
bool inBounds (const BlockIndex &block) const
 Determine whether the octree block associated with BlockIndex is a possible block in this octree. More...
 
void refineLeaf (const BlockIndex &leafBlock)
 Refines the given leaf block in the octree. More...
 
BlockDataType & operator[] (const BlockIndex &block)
 Accessor to the data associated with block. More...
 
const BlockDataType & operator[] (const BlockIndex &block) const
 Const accessor to the data associated with block. More...
 
BlockIndex coveringLeafBlock (const BlockIndex &blk, bool checkInBounds=true) const
 Finds the finest octree leaf covering BlockIndex blk. More...
 
BlockIndex parent (const GridPt &pt, int level) const
 Finds the grid index and level of the current octree block's parent. More...
 
BlockIndex parent (const BlockIndex &block) const
 Finds the BlockIndex of the given block's parent. More...
 
BlockIndex child (const GridPt &pt, int level, int childIndex) const
 Finds the BlockIndex of the given block's child. More...
 
BlockIndex child (const BlockIndex &block, int childIndex) const
 Finds the BlockIndex of the given block's child. More...
 

Static Public Member Functions

static CoordType maxCoordAtLevel (int level)
 Utility function to find the number of (possible) grid cells at a given level or resolution. More...
 
static BlockIndex root ()
 

Protected Member Functions

TreeBlockStatus blockStatus (const GridPt &pt, int lev) const
 Helper function to determine the status of a BlockIndex within an octree instance. More...
 
TreeBlockStatus blockStatus (const BlockIndex &blk) const
 Helper function to determine the status of a BlockIndex within an octree instance. More...
 

Protected Attributes

SpaceVectorLevelMap m_deltaLevelMap
 
SpaceVectorLevelMap m_invDeltaLevelMap
 
GeometricBoundingBox m_boundingBox
 
OctreeLevels m_levels
 
LeafIndicesLevelMap m_leavesLevelMap
 

Detailed Description

template<int DIM, typename BlockDataType>
class axom::spin::SpatialOctree< DIM, BlockDataType >

Adds spatial extents to an OctreeBase, allowing point location.

Member Typedef Documentation

◆ GeometricBoundingBox

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::GeometricBoundingBox = primal::BoundingBox<double, DIM>

◆ SpacePt

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::SpacePt = primal::Point<double, DIM>

◆ SpaceVector

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::SpaceVector = primal::Vector<double, DIM>

◆ BaseOctree

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::BaseOctree = OctreeBase<DIM, BlockDataType>

◆ GridPt

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::GridPt = typename BaseOctree::GridPt

◆ CoordType

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::CoordType = typename GridPt::CoordType

◆ BlockIndex

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::BlockIndex = typename BaseOctree::BlockIndex

◆ SpaceVectorLevelMap

template<int DIM, typename BlockDataType>
using axom::spin::SpatialOctree< DIM, BlockDataType >::SpaceVectorLevelMap = slam::Map<slam::Set<>, SpaceVector>

◆ GridVec

template<int DIM, typename BlockDataType>
using axom::spin::OctreeBase< DIM, BlockDataType >::GridVec = primal::Vector<CoordType, DIM>
inherited

◆ MAX_LEVEL_SIZE

template<int DIM, typename BlockDataType>
using axom::spin::OctreeBase< DIM, BlockDataType >::MAX_LEVEL_SIZE = slam::policies::CompileTimeSize<CoordType, std::numeric_limits<CoordType>::digits>
inherited

◆ OctreeLevels

template<int DIM, typename BlockDataType>
using axom::spin::OctreeBase< DIM, BlockDataType >::OctreeLevels = slam::OrderedSet<CoordType, CoordType, MAX_LEVEL_SIZE>
inherited

◆ OctreeLevelType

template<int DIM, typename BlockDataType>
using axom::spin::OctreeBase< DIM, BlockDataType >::OctreeLevelType = OctreeLevel<DIM, BlockDataType>
inherited

◆ LeafIndicesLevelMap

template<int DIM, typename BlockDataType>
using axom::spin::OctreeBase< DIM, BlockDataType >::LeafIndicesLevelMap = slam::Map<slam::Set<CoordType, CoordType>, OctreeLevelType*>
inherited

Constructor & Destructor Documentation

◆ SpatialOctree()

template<int DIM, typename BlockDataType>
axom::spin::SpatialOctree< DIM, BlockDataType >::SpatialOctree ( const GeometricBoundingBox bb)
inline

Construct a spatial octree from a spatial bounding box.

Parameters
[in]bbThe spatial extent to be indexed by the octree

Member Function Documentation

◆ boundingBox()

template<int DIM, typename BlockDataType>
const GeometricBoundingBox& axom::spin::SpatialOctree< DIM, BlockDataType >::boundingBox ( ) const
inline

Returns a reference to the octree's bounding box (i.e. the bounding box of the root block)

◆ blockBoundingBox() [1/2]

template<int DIM, typename BlockDataType>
GeometricBoundingBox axom::spin::SpatialOctree< DIM, BlockDataType >::blockBoundingBox ( const BlockIndex block) const
inline

Return the spatial bounding box of a grid cell at the given level or resolution.

Referenced by axom::spin::SpatialOctree< DIM, InOutBlockData >::blockBoundingBox().

◆ blockBoundingBox() [2/2]

template<int DIM, typename BlockDataType>
GeometricBoundingBox axom::spin::SpatialOctree< DIM, BlockDataType >::blockBoundingBox ( const GridPt gridPt,
int  level 
) const
inline

Return the spatial bounding box of a grid cell at the given level or resolution.

◆ spacingAtLevel()

template<int DIM, typename BlockDataType>
const SpaceVector& axom::spin::SpatialOctree< DIM, BlockDataType >::spacingAtLevel ( int  level) const
inline

Returns the width of an octree block at level of resolution level

Parameters
levelThe level of resolution that we are checking

◆ findLeafBlock()

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::SpatialOctree< DIM, BlockDataType >::findLeafBlock ( const SpacePt pt,
int  startingLevel = -1 
) const
inline

Finds the index of the leaf block covering the query point pt.

Parameters
[in]ptThe query point in space
[in]startingLevel(Optional) starting level for the query
Precondition
pt must be in the bounding box of the octree (i.e. boundingBox.contains(pt) == true )
Note
The collection of leaves covers the bounding box, and the interiors of the leaves do not intersect, so every point in the bounding box should be located in a unique leaf block.
We are assuming a half-open interval on the bounding boxes.
Returns
The block index (i.e. grid point and level) of the leaf block containing the query point

◆ findGridCellAtLevel()

template<int DIM, typename BlockDataType>
GridPt axom::spin::SpatialOctree< DIM, BlockDataType >::findGridCellAtLevel ( const SpacePt pt,
int  lev 
) const
inline

Utility function to find the quantized grid cell at level lev for query point pt.

Parameters
[in]ptThe point at which we are querying.
[in]levThe level or resolution.
Precondition
\( 0 \le lev < octree.maxLeafLevel() \)
Postcondition
Each coordinate of the returned gridPt is in range \( [0, 2^{lev}) \)
Returns
The grid point of the block covering this point at this level

Referenced by axom::spin::SpatialOctree< DIM, InOutBlockData >::findLeafBlock().

◆ maxLeafLevel()

template<int DIM, typename BlockDataType>
int axom::spin::OctreeBase< DIM, BlockDataType >::maxLeafLevel ( ) const
inlineinherited

The max level for leaf blocks of the octree.

Referenced by axom::spin::SpatialOctree< DIM, InOutBlockData >::findLeafBlock().

◆ maxInternalLevel()

template<int DIM, typename BlockDataType>
int axom::spin::OctreeBase< DIM, BlockDataType >::maxInternalLevel ( ) const
inlineinherited

The max level for internal blocks of the octree.

◆ maxCoordAtLevel()

template<int DIM, typename BlockDataType>
static CoordType axom::spin::OctreeBase< DIM, BlockDataType >::maxCoordAtLevel ( int  level)
inlinestaticinherited

Utility function to find the number of (possible) grid cells at a given level or resolution.

Parameters
[in]levelThe level or resolution.
Precondition
\( 0 \le lev */ static GridPt maxGridCellAtLevel(int level) { return GridPt(maxCoordAtLevel(level)); } /** \brief Finds the highest coordinate value at a given level or resolution \param [in] level The level or resolution. \pre \) 0 lev

Referenced by axom::spin::SpatialOctree< DIM, InOutBlockData >::findGridCellAtLevel().

◆ root()

template<int DIM, typename BlockDataType>
static BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::root ( )
inlinestaticinherited

Auxiliary function to return the root of the octree

Note
The root block has no parent. Its parent is an invalid BlockIndex. I.e. octree.parent( octree.root()).isValid() = false.

◆ parent() [1/2]

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::parent ( const GridPt pt,
int  level 
) const
inlineinherited

Finds the grid index and level of the current octree block's parent.

Note
The root level is 0 and its children are at level 1
The root node has no parent. The returned level will be '-1'
Parameters
[in]ptThe grid index of the block whose parent we want to find.
[in]levelThe level of the block whose parent we want to find.
Returns
The parent of the provided octree leaf.

◆ parent() [2/2]

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::parent ( const BlockIndex block) const
inlineinherited

Finds the BlockIndex of the given block's parent.

Parameters
[in]blockThe block whose parent we want to find
Returns
The BlockIndex of the parent of the provided octree leaf.

◆ child() [1/2]

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::child ( const GridPt pt,
int  level,
int  childIndex 
) const
inlineinherited

Finds the BlockIndex of the given block's child.

Parameters
[in]ptThe grid index of the block whose child we want to find.
[in]levelThe level of the block whose child we want to find.
[in]childIndexThe index of the child to find
Precondition
\( 0 \le childIndex < 2^{DIM} \)
Returns
The BlockIndex of the child of the provided octree leaf.

◆ child() [2/2]

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::child ( const BlockIndex block,
int  childIndex 
) const
inlineinherited

Finds the BlockIndex of the given block's child.

Parameters
[in]blockThe block whose child we want to find
[in]childIndexThe index of the child to find
Precondition
\( 0 \le childIndex < 2^{DIM} \)
Returns
The BlockIndex of the child of the provided octree leaf.

◆ getOctreeLevel() [1/2]

template<int DIM, typename BlockDataType>
OctreeLevelType& axom::spin::OctreeBase< DIM, BlockDataType >::getOctreeLevel ( int  lev)
inlineinherited

Accessor for a reference to the octree level instance at level lev.

◆ getOctreeLevel() [2/2]

template<int DIM, typename BlockDataType>
const OctreeLevelType& axom::spin::OctreeBase< DIM, BlockDataType >::getOctreeLevel ( int  lev) const
inlineinherited

Const accessor for a reference to the octree level instance at level lev.

◆ isLevelValid()

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::isLevelValid ( int  lev) const
inlineinherited

Predicate to determine if level lev is in the range.

Note
lev is in range if 0 <= lev <= maxLeafLevel()

◆ isLeaf() [1/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::isLeaf ( const GridPt pt,
int  lev 
) const
inlineinherited

Determine whether the octree contains a leaf block associated with grid point pt at level lev.

Parameters
[in]ptThe grid point to check
[in]levThe level of the grid point
Returns
true if the associated block is a leaf in the octree, false otherwise

◆ isLeaf() [2/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::isLeaf ( const BlockIndex block) const
inlineinherited

Determine whether the octree contains a leaf block associated with this BlockIndex.

Parameters
[in]blockThe BlockIndex of the tree to check
Returns
true if the associated block is a leaf in the octree, false otherwise

◆ isInternal() [1/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::isInternal ( const GridPt pt,
int  lev 
) const
inlineinherited

Determine whether the octree contains an internal block associated with grid point pt at level lev.

Parameters
[in]ptThe grid point to check
[in]levThe level of the grid point
Returns
true if the associated block is an internal block of the octree, false otherwise

◆ isInternal() [2/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::isInternal ( const BlockIndex block) const
inlineinherited

Determine whether the octree contains an internal block associated with this BlockIndex.

Parameters
[in]blockThe BlockIndex of the tree to check
Returns
true if the associated block is an internal block of the octree, false otherwise

◆ hasBlock() [1/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::hasBlock ( const GridPt pt,
int  lev 
) const
inlineinherited

Determine whether the octree contains a block (internal or leaf) associated with grid point pt at level lev.

Parameters
[in]ptThe grid point to check
[in]levThe level of the grid point
Returns
true if the associated block is in the octree, false otherwise

◆ hasBlock() [2/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::hasBlock ( const BlockIndex block) const
inlineinherited

Determine whether the octree contains a block (internal or leaf) associated with this BlockIndex.

Parameters
[in]blockThe BlockIndex of the tree to check
Returns
true if the associated block is a block of the octree, false otherwise

◆ inBounds() [1/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::inBounds ( const GridPt pt,
int  lev 
) const
inlineinherited

Determine whether the octree block associated with grid point pt and level lev is a possible block in this octree.

Note
A block index is out of bounds if its level is not in the tree, or its grid point is out of the range of possible grid points for its level

◆ inBounds() [2/2]

template<int DIM, typename BlockDataType>
bool axom::spin::OctreeBase< DIM, BlockDataType >::inBounds ( const BlockIndex block) const
inlineinherited

Determine whether the octree block associated with BlockIndex is a possible block in this octree.

Note
A block index is out of bounds if its level is not in the tree, or its grid point is out of the range of possible grid points for its level

◆ refineLeaf()

template<int DIM, typename BlockDataType>
void axom::spin::OctreeBase< DIM, BlockDataType >::refineLeaf ( const BlockIndex leafBlock)
inlineinherited

Refines the given leaf block in the octree.

Marks leafBlock as internal (non-leaf) and adds its children to the tree

Precondition
leafBlock is a valid leaf block in the octree.

◆ operator[]() [1/2]

template<int DIM, typename BlockDataType>
BlockDataType& axom::spin::OctreeBase< DIM, BlockDataType >::operator[] ( const BlockIndex block)
inlineinherited

Accessor to the data associated with block.

Parameters
blockA block (internal or leaf) in the tree
Precondition
block is a leaf in the tree

◆ operator[]() [2/2]

template<int DIM, typename BlockDataType>
const BlockDataType& axom::spin::OctreeBase< DIM, BlockDataType >::operator[] ( const BlockIndex block) const
inlineinherited

Const accessor to the data associated with block.

Parameters
blockA block (internal or leaf) in the tree
Precondition
block is a leaf in the tree

◆ coveringLeafBlock()

template<int DIM, typename BlockDataType>
BlockIndex axom::spin::OctreeBase< DIM, BlockDataType >::coveringLeafBlock ( const BlockIndex blk,
bool  checkInBounds = true 
) const
inlineinherited

Finds the finest octree leaf covering BlockIndex blk.

Parameters
blkA BlockIndex, not necessarily in the octree
checkInBoundsA flag to determine if we should check that the block lies within the octree bounds (default=true)
Postcondition
The returned block, if valid, is blk or one of its ancestor blocks.
Returns
The blockIndex of the finest octree leaf covering blk, if it exists, BlockIndex::invalid_index otherwise (e.g. blk is an internal block of the tree or is out of bounds)

◆ blockStatus() [1/2]

template<int DIM, typename BlockDataType>
TreeBlockStatus axom::spin::OctreeBase< DIM, BlockDataType >::blockStatus ( const GridPt pt,
int  lev 
) const
inlineprotectedinherited

Helper function to determine the status of a BlockIndex within an octree instance.

Note
This function is meant to help with implementing basic octree functionality and is not meant to be exposed in the public API
Parameters
ptThe grid point of the block index that we are testing
levThe level of the block index that we are testing

Referenced by axom::spin::SpatialOctree< DIM, InOutBlockData >::findLeafBlock().

◆ blockStatus() [2/2]

template<int DIM, typename BlockDataType>
TreeBlockStatus axom::spin::OctreeBase< DIM, BlockDataType >::blockStatus ( const BlockIndex blk) const
inlineprotectedinherited

Helper function to determine the status of a BlockIndex within an octree instance.

Note
This function is meant to help with implementing basic octree functionality and is not meant to be exposed in the public API
Parameters
blkThe block index we are testing

Member Data Documentation

◆ m_deltaLevelMap

◆ m_invDeltaLevelMap

◆ m_boundingBox

◆ m_levels

template<int DIM, typename BlockDataType>
OctreeLevels axom::spin::OctreeBase< DIM, BlockDataType >::m_levels
protectedinherited

◆ m_leavesLevelMap

template<int DIM, typename BlockDataType>
LeafIndicesLevelMap axom::spin::OctreeBase< DIM, BlockDataType >::m_leavesLevelMap
protectedinherited

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