A dynamic AABB tree broad-phase. More...

#include <playrho/d2/DynamicTree.hpp>

Classes
class	TreeNode
	A node in the dynamic tree. More...

Public Types
using	Height = DynamicTreeSize
	Type for heights. More...

using	Size = DynamicTreeSize
	Size type.

Public Member Functions
	DynamicTree () noexcept
	Non-throwing default constructor. More...

	DynamicTree (const DynamicTree &other)
	Copy constructor. More...

	DynamicTree (DynamicTree &&other) noexcept
	Move constructor.

	DynamicTree (Size nodeCapacity)
	Size initializing constructor. More...

	~DynamicTree () noexcept
	Destroys the tree, freeing the node pool.

void	Clear () noexcept
	Clears the dynamic tree. More...

Size	CreateLeaf (const AABB &aabb, const Contactable &data)
	Creates a new leaf node. More...

void	DestroyLeaf (Size index) noexcept
	Destroys a leaf node. More...

Size	FindReference (Size index) const noexcept
	Finds first node which references the given index. More...

AABB	GetAABB (Size index) const noexcept
	Gets the AABB for a leaf or branch (a non-unused node). More...

DynamicTreeBranchData	GetBranchData (Size index) const noexcept
	Gets the branch data for the identified node. More...

Size	GetFreeIndex () const noexcept
	Gets the free index.

Height	GetHeight (Size index) const noexcept
	Gets the height value for the identified node. More...

Size	GetLeafCount () const noexcept
	Gets the current leaf node count. More...

Contactable	GetLeafData (Size index) const noexcept
	Gets the leaf data for the node identified by the given identifier. More...

const TreeNode &	GetNode (Size index) const noexcept
	Gets the node identified by the given identifier. More...

Size	GetNodeCapacity () const noexcept
	Gets the current node capacity of this tree. More...

Size	GetNodeCount () const noexcept
	Gets the current count of allocated nodes. More...

Size	GetOther (Size index) const noexcept
	Gets the "other" index for the node at the given index. More...

Size	GetRootIndex () const noexcept
	Gets the index of the "root" node if this tree has one. More...

DynamicTree &	operator= (DynamicTree other) noexcept
	Unifying assignment operator. More...

void	RebuildBottomUp ()
	Builds an optimal tree. More...

void	Reserve (Size value)
	Reserves at least as much capacity as requested. More...

void	ShiftOrigin (const Length2 &newOrigin) noexcept
	Shifts the world origin. More...

void	UpdateLeaf (Size index, const AABB &aabb)
	Updates a leaf node with a new AABB value. More...

Static Public Member Functions
static constexpr bool	IsBranch (Height value) noexcept
	Gets whether the given height is a height for a "branch" node.

static constexpr bool	IsLeaf (Height value) noexcept
	Gets whether the given height is the height for a "leaf" node.

static constexpr bool	IsUnused (Height value) noexcept
	Gets whether the given height is the height for an "unused" node.

Static Public Attributes
static constexpr auto	InvalidHeight = static_cast<Height>(-1)
	Invalid height constant value.

static constexpr auto	InvalidSize = static_cast<Size>(-1)
	Invalid size constant value.

Friends
void	swap (DynamicTree &lhs, DynamicTree &rhs) noexcept
	Customized swap function for `DynamicTree` objects. More...

Related Functions
(Note that these are not member functions.)
auto	FindIndex (const DynamicTree &tree, const Contactable &c) noexcept -> DynamicTree::Size
	Finds index of node matching given contactble using a linear search. More...

AABB	GetAABB (const DynamicTree &tree) noexcept
	Gets the AABB for the given dynamic tree. More...

DynamicTree::Height	GetHeight (const DynamicTree &tree) noexcept
	Gets the height of the binary tree. More...

bool	TestOverlap (const DynamicTree &tree, DynamicTree::Size leafIdA, DynamicTree::Size leafIdB) noexcept
	Tests for overlap of the elements identified in the given dynamic tree.

Detailed Description

A dynamic AABB tree broad-phase.

A dynamic tree arranges data in a binary tree to accelerate queries such as volume queries and ray casts. Leafs are proxies with an AABB.

Invariant: A dynamic tree with a capacity of N nodes will always have N minus M "free" nodes and M "allocated" nodes where M is never more than N.; Freed nodes' "other" nodes are valid "next" older freed nodes, or they have the invalid size value indicating that they are the oldest freed node.; Allocated nodes' "other" nodes are valid "parent" nodes, or they have the invalid size value indicating that they are parentless.; The root node's index is either the index to the node at the root of the tree or it's the invalid size value indicating that this tree is empty.; The root node's "other" index will be the invalid size value.; Allocated nodes can only be "branch" or "leaf" nodes.; Branch nodes always have two valid "child" nodes.; Branch nodes always have a "height" of 1 plus the maximum height of its children.; Branch nodes' AABBs are always the AABB which minimally encloses its children.; Leaf nodes always have a "height" of zero.; Freed nodes always have a "height" of the maximum value of the height type.

Note: This code was inspired by Nathanael Presson's btDbvt.; Nodes are pooled and relocatable, so we use node indices rather than pointers.

See also: http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/; http://www.cs.utah.edu/~thiago/papers/rotations.pdf ("Fast, Effective BVH Updates for Animated Scenes")

Member Typedef Documentation

◆ Height

using playrho::d2::DynamicTree::Height = DynamicTreeSize

Type for heights.

Note: The maximum height of a tree can never exceed half of the max value of the Size type due to the binary nature of this tree structure.

Constructor & Destructor Documentation

◆ DynamicTree() [1/3]

playrho::d2::DynamicTree::DynamicTree ( )

defaultnoexcept

Non-throwing default constructor.

Postcondition: GetNodeCapacity() returns 0.; GetNodeCount() returns 0.; GetFreeIndex() and GetRootIndex() return InvalidSize.

◆ DynamicTree() [2/3]

playrho::d2::DynamicTree::DynamicTree ( Size nodeCapacity )

explicit

Size initializing constructor.

Parameters

nodeCapacity Node capacity. If zero, this is the same as calling the default constructor except this isn't recognized as non-throwing.

Postcondition: GetNodeCapacity() returns value of the next power of two of the result of nodeCapacity minus one, where a nodeCapacity of zero results in GetNodeCapacity() returning zero.; GetNodeCount() returns 0.; GetFreeIndex() and GetRootIndex() return InvalidSize.

Exceptions

std::bad_alloc If unable to allocate non-zero sized memory.

◆ DynamicTree() [3/3]

playrho::d2::DynamicTree::DynamicTree ( const DynamicTree & other )

Copy constructor.

Exceptions

std::bad_alloc If unable to allocate non-zero sized memory.

Member Function Documentation

◆ Clear()

void playrho::d2::DynamicTree::Clear ( )

noexcept

Clears the dynamic tree.

Clears the leafs and branches from this tree. This does not deallocate any memory nor reduce this tree's capacity; this only reduces this tree's usage of that capacity.

Postcondition: GetLeafCount() will return 0.; GetNodeCount() will return 0.; GetRootIndex() will return InvalidSize.; GetFreeIndex() will return 0 if this tree had any node capacity, else the value of InvalidSize.

◆ CreateLeaf()

DynamicTree::Size playrho::d2::DynamicTree::CreateLeaf	(	const AABB &	aabb,
		const Contactable &	data
	)

Creates a new leaf node.

Creates a leaf node for a tight fitting AABB and the given data.

Note: The indices of leaf nodes that have been destroyed get reused for new nodes.

Precondition: The number of leaves already allocated (as reported by GetLeafCount()) is less than std::numeric_limits<Size>::max().; The number of nodes already allocated (as reported by GetNodeCount()) is at least one or two less than std::numeric_limits<Size>::max() depending on whether root index is InvalidSize or not.

Postcondition: If the root index had been the InvalidSize, then it will be set to the index returned from this function.; The leaf count per GetLeafCount() is incremented by one.; The node count (as reported by GetNodeCount()) will be incremented by one or two (if the root index had not been InvalidSize).

Returns: The index of the created leaf node. This will be a value not equal to InvalidSize.

Exceptions

std::bad_alloc If unable to allocate necessary memory. If this exception is thrown, this function has no effect.

See also: GetLeafCount(), GetNodeCount()

◆ DestroyLeaf()

void playrho::d2::DynamicTree::DestroyLeaf ( Size index )

noexcept

Destroys a leaf node.

Parameters

index Identifier of node to destroy.

Precondition: index is less than GetNodeCapacity() and IsLeaf(GetNode(index).GetHeight()) is true.

Postcondition: The leaf count per GetLeafCount() is decremented by one.

See also: GetLeafCount().

◆ FindReference()

DynamicTree::Size playrho::d2::DynamicTree::FindReference ( Size index ) const

noexcept

Finds first node which references the given index.

Note: Primarily intended for unit testing and/or debugging.

Returns: Index of node referencing the given index, or the value of InvalidSize.

◆ GetAABB()

AABB playrho::d2::DynamicTree::GetAABB ( Size index ) const

inlinenoexcept

Gets the AABB for a leaf or branch (a non-unused node).

Parameters

index Leaf or branch node's ID. Must be a valid ID.

Precondition: index is less than GetNodeCapacity() and IsUnused(GetNode(index).GetHeight()) is false.

Referenced by playrho::d2::Query(), playrho::d2::RayCast(), and RebuildBottomUp().

◆ GetBranchData()

DynamicTreeBranchData playrho::d2::DynamicTree::GetBranchData ( Size index ) const

inlinenoexcept

Gets the branch data for the identified node.

Parameters

index Identifier of node to get branch data for.

Precondition: index is less than GetNodeCapacity().

Referenced by playrho::d2::Query(), and playrho::d2::RayCast().

◆ GetHeight()

DynamicTree::Height playrho::d2::DynamicTree::GetHeight ( Size index ) const

inlinenoexcept

Gets the height value for the identified node.

Parameters

index Identifier of node to get "height" for.

Precondition: index is less than GetNodeCapacity().

Referenced by playrho::d2::Query(), playrho::d2::RayCast(), RebuildBottomUp(), and UpdateLeaf().

◆ GetLeafCount()

DynamicTree::Size playrho::d2::DynamicTree::GetLeafCount ( ) const

inlinenoexcept

Gets the current leaf node count.

◆ GetLeafData()

Contactable playrho::d2::DynamicTree::GetLeafData ( Size index ) const

inlinenoexcept

Gets the leaf data for the node identified by the given identifier.

Parameters

index Identifier of node to get the leaf data for.

Precondition: index is less than GetNodeCapacity() and IsLeaf(GetNode(index).GetHeight()) is true.

Returns: Leaf data for the specified node.

Referenced by playrho::d2::Query(), and playrho::d2::RayCast().

◆ GetNode()

const DynamicTree::TreeNode & playrho::d2::DynamicTree::GetNode ( Size index ) const

inlinenoexcept

Gets the node identified by the given identifier.

Parameters

index Identifier of node to get.

Precondition: index is less than GetNodeCapacity().

◆ GetNodeCapacity()

DynamicTree::Size playrho::d2::DynamicTree::GetNodeCapacity ( ) const

inlinenoexcept

Gets the current node capacity of this tree.

See also: Reserve.

◆ GetNodeCount()

DynamicTree::Size playrho::d2::DynamicTree::GetNodeCount ( ) const

inlinenoexcept

Gets the current count of allocated nodes.

Returns: Count of existing proxies (count of nodes currently allocated).

Referenced by CreateLeaf(), and RebuildBottomUp().

◆ GetOther()

DynamicTree::Size playrho::d2::DynamicTree::GetOther ( Size index ) const

inlinenoexcept

Gets the "other" index for the node at the given index.

Note: For unused nodes, this is the index to the "next" unused node.; For used nodes (leaf or branch nodes), this is the index to the "parent" node.

Parameters

index Identifier of node to get "other" for.

Precondition: This tree has a node capacity greater than the given index.

Returns: The invalid index value or a value less than the node capacity.

Referenced by GetLeafCount(), GetRootIndex(), and UpdateLeaf().

◆ GetRootIndex()

DynamicTree::Size playrho::d2::DynamicTree::GetRootIndex ( ) const

inlinenoexcept

Gets the index of the "root" node if this tree has one.

Note: If the tree has a root node, then the "other" property of this node will be the invalid size.

Returns: InvalidSize if this tree is "empty", else index to "root" node.

Referenced by playrho::d2::Query(), and playrho::d2::RayCast().

◆ operator=()

DynamicTree & playrho::d2::DynamicTree::operator= ( DynamicTree other )

noexcept

Unifying assignment operator.

Note: This intentionally takes the argument by-value. Along with the move constructor, this assignment operator effectively doubles up as both copy assignment and move assignment support.

See also: https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap; https://stackoverflow.com/a/3279550/7410358

◆ RebuildBottomUp()

void playrho::d2::DynamicTree::RebuildBottomUp ( )

Builds an optimal tree.

Note: This operation is very expensive.; Meant for testing.

Exceptions

std::bad_alloc If unable to allocate necessary memory.

◆ Reserve()

void playrho::d2::DynamicTree::Reserve ( Size value )

Reserves at least as much capacity as requested.

Exceptions

std::bad_alloc If unable to allocate necessary memory. If this exception is thrown, this function has no effect.

Postcondition: GetNodeCapacity() returns a new capacity that's at least as much as the requested capacity if that's greater than before.; GetFreeIndex() returns the value of GetNodeCount() if the new capacity is greater than before.

See also: GetNodeCapacity, GetFreeIndex, GetNodeCount.

Referenced by CreateLeaf(), and RebuildBottomUp().

◆ ShiftOrigin()

void playrho::d2::DynamicTree::ShiftOrigin ( const Length2 & newOrigin )

noexcept

Shifts the world origin.

Note: Useful for large worlds.; The shift formula is: position -= newOrigin.

Parameters

newOrigin the new origin with respect to the old origin.

◆ UpdateLeaf()

void playrho::d2::DynamicTree::UpdateLeaf	(	Size	index,
		const AABB &	aabb
	)

Updates a leaf node with a new AABB value.

Parameters

index	Leaf node's ID.
aabb	New axis aligned bounding box for the leaf node.

Precondition: index is less than GetNodeCapacity() and IsLeaf(GetNode(index).GetHeight()) is true.

Friends And Related Function Documentation

◆ FindIndex()

auto FindIndex	(	const DynamicTree &	tree,
		const Contactable &	c
	)		-> DynamicTree::Size

Returns: Node index or DynamicTree::InvalidSize.

See also: DynamicTree::InvalidSize.

◆ GetAABB()

AABB GetAABB ( const DynamicTree & tree )

Gets the AABB that encloses all other AABB instances that are within the given dynamic tree.

Returns: Enclosing AABB or the "unset" AABB.

◆ GetHeight()

DynamicTree::Height GetHeight ( const DynamicTree & tree )

Returns: Height of the tree (as stored in the root node) or 0 if the root node is not valid.

◆ swap

void swap	(	DynamicTree &	lhs,
		DynamicTree &	rhs
	)

friend

Customized swap function for DynamicTree objects.

Note: This satisfies the Swappable named requirement.

See also: https://en.cppreference.com/w/cpp/named_req/Swappable

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

Library/include/playrho/d2/DynamicTree.hpp
Library/source/playrho/d2/DynamicTree.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

◆ Height

Constructor & Destructor Documentation

◆ DynamicTree() [1/3]

◆ DynamicTree() [2/3]

◆ DynamicTree() [3/3]

Member Function Documentation

◆ Clear()

◆ CreateLeaf()

◆ DestroyLeaf()

◆ FindReference()

◆ GetAABB()

◆ GetBranchData()

◆ GetHeight()

◆ GetLeafCount()

◆ GetLeafData()

◆ GetNode()

◆ GetNodeCapacity()

◆ GetNodeCount()

◆ GetOther()

◆ GetRootIndex()

◆ operator=()

◆ RebuildBottomUp()

◆ Reserve()

◆ ShiftOrigin()

◆ UpdateLeaf()

Friends And Related Function Documentation

◆ FindIndex()

◆ GetAABB()

◆ GetHeight()

◆ swap