A single node of an octree, representing a single octant of the 8 that make up its parent region. More...

#include <spatial_query_octree.hpp>

Inheritance diagram for ToyMaker::OctreeNode:

Public Types
enum	OctantSpecifier : Octant { RIGHT =0x1 , TOP =0x2 , FRONT =0x4 }
	Mask values which, when applied to the octant value, tell you which sub-region of the parent region this node represents.

enum	AddressMasks : Address { DEPTH_MASK = -(1ull << kDepthBitOffset) , ROUTE_MASK = ~(-(1ull << knRouteBits)) }
	Mask values for retrieving the different sections of an Address.

using	Octant = uint8_t
	A number representing the portion of the parent region represented by this node.

using	Depth = uint8_t
	The depth of this node relative to the overall octree; the number of hops to go from this node up to the root node of the tree.

using	Address = uint64_t
	The full address of this node, where every three bits right-to-left represent the octant in the hierarchy to select in order to reach it, and the leftmost bits represent the depth at which it is found.

Public Member Functions
std::vector< std::pair< EntityID, AxisAlignedBounds > >	findAllMemberEntities () const
	Retrieves all entities in this octant and its descendants.

std::vector< std::pair< EntityID, AxisAlignedBounds > >	findEntitiesOverlapping (const AxisAlignedBounds &searchBounds) const
	Retrieves all entities that intersect with the region described by searchBounds.

std::vector< std::pair< EntityID, AxisAlignedBounds > >	findEntitiesOverlapping (const Ray &searchRay) const
	Retrieves all entities that intersect with the ray described by searchRay.

uint8_t	getChildCount () const
	Gets the number of active child octants this octant has.

Address	getAddress () const
	Gets the address value for this node.

AxisAlignedBounds	getWorldBounds () const
	Retrieves the AABB representing the region this node covers.

Address	insertEntity (EntityID entityID, const AxisAlignedBounds &entityWorldBounds)
	Adds an entity to this node or its subtree, per its configuration and the bounds of the object.

std::shared_ptr< OctreeNode >	removeEntity (EntityID entityID, Address entityAddressHint=kNoAddress)
	Removes an entity situated at a node at some address (or on a descendant node).

std::shared_ptr< OctreeNode >	getNode (Address octantAddress)
	Gets a descendant of this node (or this node itself) by its address.

std::shared_ptr< OctreeNode >	nextNodeInAddress (Address octantAddress)
	Gets the child node corresponding to the next node in the argument's route section relative to the this node.

std::shared_ptr< OctreeNode >	getSmallestNodeContaining (const AxisAlignedBounds &entityWorldBounds)
	Gets the node whose region just encompasses the bounds provided as input.

std::shared_ptr< OctreeNode >	findCandidateRoot ()
	Gets the smallest node, this node or a descendant, whose region encompasses all entities remaining in the Octree.

Address	getBaseRoute (Address address) const
	Gets the route section of the address up to the current node's depth.

Depth	getDepth () const
	The depth of this node relative to the root of the Octree it is a part of.

Octant	getOctant () const
	Gets the octant value of this node relative to its parent.

Octant	nextOctant (Address address) const
	Fetches the octant of the next node in the route section of the argument address.

void	shrinkTreeAndBecomeRoot ()
	Trims the addresses of this node and its children (and consequently their entities) such that this node is the root.

Static Public Member Functions
static Address	MakeAddress (Octant childOctant, Address parentAddress)
	Prepends the address of a child octant to the address of its parent in order to make the child's address.

static Depth	GetDepth (Address address)
	Gets the depth value of a node based on its address.

static Octant	ToGrowthDirection (Octant octant)
	Maps an octant to its corresponding growth direction.

static Octant	ToOctant (Octant growthDirection)
	Converts a growth direction to its corresponding octant.

static Octant	GetOctant (Address address)
	Returns the 3 bits representing just this node's octant value, relative to its own parent.

static Address	GetBaseRouteMask (Depth baseDepth)
	Gets a bit mask covering the first 3*depth bits based on a given depth value.

static Address	GetBaseRoute (Address address, Depth baseDepth)
	Gets the value of the route section of an address up to some specified depth.

static Octant	GetOctantAt (Address address, Depth depth)
	Gets the octant corresponding to a specific depth within an address.

static Address	GrowAddress (Address address, Address rootAddress)
	Adds root-address' route to address' route.

static Address	ShrinkAddress (Address address, Depth depthRemoved)
	Shrinks an address according to the depth removed.

static bool	SharesBranch (Address one, Address two)
	Tests whether two nodes are present on the same branch of an octree (or in other words, whether one is the descendant or ancestor of the other).

static std::shared_ptr< OctreeNode >	CreateRootNode (uint8_t subdivisionThreshold, AxisAlignedBounds boundRegion)
	Produces a node for the root of an octree that encloses the region to be divided.

static std::shared_ptr< OctreeNode >	GrowTreeAndCreateRoot (std::shared_ptr< OctreeNode > oldRoot, const AxisAlignedBounds &regionToCover)
	Expands an octree such that it encloses a previously unmapped region, and creates a node to be used as the new root node for the octree.

Static Public Attributes
static constexpr uint8_t	knDepthBits { 5 }
	The number of bits on the left hand side of a node address giving the depth of this node.

static constexpr uint8_t	kDepthBitOffset { sizeof(Address)*8 - knDepthBits }
	(Computed) The number of bits by which to shift the address right in order to retrieve the depth value of the node.

static constexpr uint8_t	knRouteBits { (kDepthBitOffset/3) * 3}
	The number of bits of the address, starting from the right, representing the route to follow in the Octree hierarchy in order to reach this node.

static constexpr Depth	kMaxDepthInclusive
	The total depth representable given the value range of the depth-section of the address, and the space available in the route-section.

static constexpr Address	kNoAddress { 0x0 }
	A special value reserved for the absence of an address, as in the root node of the Octree.

Private Member Functions
	OctreeNode (Address octantAddress, uint8_t subdivisionThreshold, AxisAlignedBounds worldBounds, std::shared_ptr< OctreeNode > parent)
	Constructs a new OctreeNode.

Private Attributes
Address	mAddress { 0x0 }
	The address of this node, where kNoAddress is the address of the root node of an octree.

uint8_t	mSubdivisionThreshold { 40 }
	The number of member entities a node (or its descendant) may have, beyond which the node's subdivision should be attempted.

AxisAlignedBounds	mWorldBounds {}
	The region, as an AABB, encompassed by this node.

std::weak_ptr< OctreeNode >	mParent {}
	The parent of this node, which this node is an octant of.

std::array< std::shared_ptr< OctreeNode >, 8 >	mChildren {}
	An array of up to 8 child nodes maintained by this node, where each index corresponds to one possible value of an Octant.

std::map< EntityID, AxisAlignedBounds >	mEntities {}
	The member entities of this node.

Detailed Description

A single node of an octree, representing a single octant of the 8 that make up its parent region.

Member Typedef Documentation

◆ Octant

using ToyMaker::OctreeNode::Octant = uint8_t

A number representing the portion of the parent region represented by this node.

See also: OctantSpecifier

Constructor & Destructor Documentation

◆ OctreeNode()

ToyMaker::OctreeNode::OctreeNode	(	Address	octantAddress,
		uint8_t	subdivisionThreshold,
		AxisAlignedBounds	worldBounds,
		std::shared_ptr< OctreeNode >	parent )

inlineprivate

Constructs a new OctreeNode.

Parameters

octantAddress	The address this node is initialized with.
subdivisionThreshold	The number of member entities a node may have beyond which its subdivision should be attempted.
worldBounds	The total region (as an AABB) to be enclosed by this node.
parent	A reference to the parent of this node.

Member Function Documentation

◆ CreateRootNode()

std::shared_ptr< OctreeNode > OctreeNode::CreateRootNode	(	uint8_t	subdivisionThreshold,
		AxisAlignedBounds	boundRegion )

static

Produces a node for the root of an octree that encloses the region to be divided.

Parameters

subdivisionThreshold	The number of objects on a single node beyond which a subdivision of the node should be attempted.
boundRegion	The region containing all of the axis aligned bounds to be enclosed by this octree.

Returns: std::shared_ptr<OctreeNode> The newly created node representing the root of a new octree.

◆ findAllMemberEntities()

std::vector< std::pair< EntityID, AxisAlignedBounds > > OctreeNode::findAllMemberEntities ( ) const

Retrieves all entities in this octant and its descendants.

Available query methods

Returns: std::vector<std::pair<EntityID, AxisAlignedBounds>> All entities mapped to this node and its descendant nodes.

◆ findCandidateRoot()

std::shared_ptr< OctreeNode > OctreeNode::findCandidateRoot ( )

Gets the smallest node, this node or a descendant, whose region encompasses all entities remaining in the Octree.

Usually called after the removal of a node, when an Octree shrinkage may be in order.

Returns: std::shared_ptr<OctreeNode> The smallest node containing all the objects in the scene.

◆ findEntitiesOverlapping() [1/2]

std::vector< std::pair< EntityID, AxisAlignedBounds > > OctreeNode::findEntitiesOverlapping ( const AxisAlignedBounds & searchBounds ) const

Retrieves all entities that intersect with the region described by searchBounds.

Parameters

searchBounds The region whose entities we would like to fetch.

Returns: std::vector<std::pair<EntityID, AxisAlignedBounds>> The entities overlapping the search region.

◆ findEntitiesOverlapping() [2/2]

std::vector< std::pair< EntityID, AxisAlignedBounds > > OctreeNode::findEntitiesOverlapping ( const Ray & searchRay ) const

Retrieves all entities that intersect with the ray described by searchRay.

Parameters

searchRay The ray whose intersecting objects we would like to fetch.

Returns: std::vector<std::pair<EntityID, AxisAlignedBounds>> The entities intersecting with the search ray.

◆ getAddress()

Address ToyMaker::OctreeNode::getAddress ( ) const

inline

Gets the address value for this node.

Returns: Address This node's address.

◆ GetBaseRoute()

OctreeNode::Address OctreeNode::GetBaseRoute	(	Address	address,
		Depth	baseDepth )

static

Gets the value of the route section of an address up to some specified depth.

Parameters

address	The address whose route (up to baseDepth) we want to obtain.
baseDepth	The depth up to which we want the route for.

Returns: Address The value of the route up to base depth in the provided address.

◆ getBaseRoute()

OctreeNode::Address OctreeNode::getBaseRoute ( Address address ) const

Gets the route section of the address up to the current node's depth.

Parameters

address The address whose base route is being retrieved.

Returns: Address The base route of the argument address, up to this node's depth.

◆ GetBaseRouteMask()

OctreeNode::Address OctreeNode::GetBaseRouteMask ( Depth baseDepth )

static

Gets a bit mask covering the first 3*depth bits based on a given depth value.

Parameters

baseDepth The depth up to which we want the route bits for.

Returns: Address The mask covering all the route bits up to the specified depth.

◆ getChildCount()

uint8_t OctreeNode::getChildCount ( ) const

Gets the number of active child octants this octant has.

Returns: uint8_t The number of active children of this node.

◆ GetDepth()

OctreeNode::Depth OctreeNode::GetDepth ( Address address )

static

Gets the depth value of a node based on its address.

Parameters

address The address of the node.

Returns: Depth The depth of the node, or the number of hops from it to the root node.

◆ getDepth()

OctreeNode::Depth OctreeNode::getDepth ( ) const

The depth of this node relative to the root of the Octree it is a part of.

Returns: Depth This node's Octree depth.

◆ getNode()

std::shared_ptr< OctreeNode > OctreeNode::getNode ( Address octantAddress )

Gets a descendant of this node (or this node itself) by its address.

Parameters

octantAddress The octree address of the node being fetched.

Returns: std::shared_ptr<OctreeNode> The node at the address specified.

◆ GetOctant()

OctreeNode::Octant OctreeNode::GetOctant ( Address address )

static

Returns the 3 bits representing just this node's octant value, relative to its own parent.

Parameters

address The address of the node whose octant value we want.

Returns: Octant The node's octant value.

◆ getOctant()

OctreeNode::Octant OctreeNode::getOctant ( ) const

Gets the octant value of this node relative to its parent.

Returns: Octant This node's octant value relative to its parent.

◆ GetOctantAt()

OctreeNode::Octant OctreeNode::GetOctantAt	(	Address	address,
		Depth	depth )

static

Gets the octant corresponding to a specific depth within an address.

Parameters

address	The address in which the octant is present (as part of its route)
depth	The depth of the octant being retrieved.

Returns: Octant The 3-bit value of the octant itself.

◆ getSmallestNodeContaining()

std::shared_ptr< OctreeNode > OctreeNode::getSmallestNodeContaining ( const AxisAlignedBounds & entityWorldBounds )

Gets the node whose region just encompasses the bounds provided as input.

The region of the node retrieved is such that any sub-region would at most overlap, but not enclose, the argument bounds.

Parameters

entityWorldBounds The bounds which the node retrieved should just envelop.

Returns: std::shared_ptr<OctreeNode> The node enclosing the the argument bounds.

◆ getWorldBounds()

AxisAlignedBounds ToyMaker::OctreeNode::getWorldBounds ( ) const

inline

Retrieves the AABB representing the region this node covers.

Returns: AxisAlignedBounds The AABB representing the region this node covers.

◆ GrowAddress()

OctreeNode::Address OctreeNode::GrowAddress	(	Address	address,
		Address	rootAddress )

static

Adds root-address' route to address' route.

The depth of the root address is added to the old address (the first argument) in order to produce that node or object's new address.

This is used when the octree has grown to enclose a larger region, and its previous nodes must be recomputed relative to the new root of the octree.

Parameters

address	The (previous) address of an octant or object.
rootAddress	The address from the new root of the octree to the old root (or its leaf-most ancestor).

Returns: Address The new address for the octant or object.

◆ GrowTreeAndCreateRoot()

std::shared_ptr< OctreeNode > OctreeNode::GrowTreeAndCreateRoot	(	std::shared_ptr< OctreeNode >	oldRoot,
		const AxisAlignedBounds &	regionToCover )

static

Expands an octree such that it encloses a previously unmapped region, and creates a node to be used as the new root node for the octree.

Parameters

oldRoot	The root node prior to the addition of an object falling outside its bounds.
regionToCover	The region enclosing both the old octree as well as any new objects added falling outside of it.

Returns: std::shared_ptr<OctreeNode> The new root node for the octree.

◆ insertEntity()

OctreeNode::Address OctreeNode::insertEntity	(	EntityID	entityID,
		const AxisAlignedBounds &	entityWorldBounds )

Adds an entity to this node or its subtree, per its configuration and the bounds of the object.

Parameters

entityID	The ID of the object being added.
entityWorldBounds	The AABB of the entity.

Returns: Address The new address of the node, post-addition.

◆ MakeAddress()

OctreeNode::Address OctreeNode::MakeAddress	(	Octant	childOctant,
		Address	parentAddress )

static

Prepends the address of a child octant to the address of its parent in order to make the child's address.

Parameters

childOctant	The octant of the parent that the child will represent.
parentAddress	The (presumably valid) address of the parent.

Returns: Address The new address belonging to the child.

◆ nextNodeInAddress()

std::shared_ptr< OctreeNode > OctreeNode::nextNodeInAddress ( Address octantAddress )

Gets the child node corresponding to the next node in the argument's route section relative to the this node.

Parameters

octantAddress The address of the node being looked for.

Returns: std::shared_ptr<OctreeNode> The child node corresponding to the next 3 bits of the route section of the address.

◆ nextOctant()

OctreeNode::Octant OctreeNode::nextOctant ( Address address ) const

Fetches the octant of the next node in the route section of the argument address.

Parameters

address The address to a node or an entity contained by it.

Returns: Octant The octant of this node's child, which is the next node in the route beyond this one.

◆ removeEntity()

std::shared_ptr< OctreeNode > OctreeNode::removeEntity	(	EntityID	entityID,
		Address	entityAddressHint = kNoAddress )

Removes an entity situated at a node at some address (or on a descendant node).

Parameters

entityID	The ID of the entity being removevd.
entityAddressHint	The address of the node (or that node's ancestor) at which the entity is present.

Returns: std::shared_ptr<OctreeNode> (If the octree must be shrunk) the node of the new to-be root node.

◆ SharesBranch()

bool OctreeNode::SharesBranch	(	Address	one,
		Address	two )

static

Tests whether two nodes are present on the same branch of an octree (or in other words, whether one is the descendant or ancestor of the other).

Parameters

one	The address of the first node.
two	The address of the second node.

Return values

true	Both addresses correspond to nodes or objects on the same branch of the octree;
false	The addresses diverge, and are not on the same branch of the octree;

◆ ShrinkAddress()

OctreeNode::Address OctreeNode::ShrinkAddress	(	Address	address,
		Depth	depthRemoved )

static

Shrinks an address according to the depth removed.

This is used when, after the removal of an object, octree nodes higher up in the tree are no longer required. A node that was previously a descendant node is promoted to the root node of the octree, and all addresses are changed accordingly.

Parameters

address	The (previous) address of a node or object, now being shrunk.
depthRemoved	The depth being removed from the address.

Returns: Address The new address after the shrinkage.

◆ ToGrowthDirection()

OctreeNode::Octant OctreeNode::ToGrowthDirection ( Octant octant )

static

Maps an octant to its corresponding growth direction.

The growth-directions are the directions in which each dimension of this octant would need to be doubled in order to convert it into its own parent region, per its octant value.

This method isn't really used, but is present for symmetry with ToOctant()

Parameters

octant The octant being converted into a "growth direction".

Returns: Octant The growth direction for this octant.

◆ ToOctant()

OctreeNode::Octant OctreeNode::ToOctant ( Octant growthDirection )

static

Converts a growth direction to its corresponding octant.

The growth direction tells you in which direction an octant's dimensions should be doubled in order to become its parent. Conversely, the direction of the subdivision of the enlarged region gives you the octant value for the original sub-region.

This is mainly used when the area to be encapsulated by the octree has expanded, say when an object is added which is outside of the Octree's currently enclosed region.

Once all the growth steps (a series of growth directions from the old root of the octree) have been computed, this operation produces the octant value for the node corresponding to each step.

Parameters

growthDirection The direction in which a smaller node was doubled in order to produce the larget one.

Returns: Octant The address of the smaller node, relative to the newly made larger one.

Member Data Documentation

◆ kDepthBitOffset

uint8_t ToyMaker::OctreeNode::kDepthBitOffset { sizeof(Address)*8 - knDepthBits }

staticconstexpr

(Computed) The number of bits by which to shift the address right in order to retrieve the depth value of the node.

See also: knDepthBits

◆ kMaxDepthInclusive

Depth ToyMaker::OctreeNode::kMaxDepthInclusive

staticconstexpr

Initial value:

{std::min(
            1 + knRouteBits/3, 
            1 + (1<<knDepthBits) 
        )}

The total depth representable given the value range of the depth-section of the address, and the space available in the route-section.

◆ mChildren

std::array<std::shared_ptr<OctreeNode>, 8> ToyMaker::OctreeNode::mChildren {}

private

An array of up to 8 child nodes maintained by this node, where each index corresponds to one possible value of an Octant.

See also: OctantSpecifier

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

src/engine/spatial_query_octree.hpp
src/engine/spatial_query_octree.cpp

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Octant

Constructor & Destructor Documentation

◆ OctreeNode()

Member Function Documentation

◆ CreateRootNode()

◆ findAllMemberEntities()

◆ findCandidateRoot()

◆ findEntitiesOverlapping() [1/2]

◆ findEntitiesOverlapping() [2/2]

◆ getAddress()

◆ GetBaseRoute()

◆ getBaseRoute()

◆ GetBaseRouteMask()

◆ getChildCount()

◆ GetDepth()

◆ getDepth()

◆ getNode()

◆ GetOctant()

◆ getOctant()

◆ GetOctantAt()

◆ getSmallestNodeContaining()

◆ getWorldBounds()

◆ GrowAddress()

◆ GrowTreeAndCreateRoot()

◆ insertEntity()

◆ MakeAddress()

◆ nextNodeInAddress()

◆ nextOctant()

◆ removeEntity()

◆ SharesBranch()

◆ ShrinkAddress()

◆ ToGrowthDirection()

◆ ToOctant()

Member Data Documentation

◆ kDepthBitOffset

◆ kMaxDepthInclusive

◆ mChildren