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

#include <DynamicTree.hpp>

Collaboration diagram for playrho::d2::DynamicTree:

Classes
struct	BranchData
	Branch data of a tree node. More...

struct	LeafData
	Leaf data of a tree node. More...

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

struct	UnusedData
	Unused data of a tree node. More...

union	VariantData
	Variant data. More...

Public Types
using	Size = ContactCounter
	Size type.

using	Height = ContactCounter
	Type for heights. More...

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

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

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

	DynamicTree (DynamicTree &&other) noexcept
	Move constructor.

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

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

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

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

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

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

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

void	SetLeafData (Size index, LeafData value) noexcept
	Sets the leaf data for the element at the given index to the given value.

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

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

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

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

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

Size	GetFreeIndex () const noexcept
	Gets the free index.

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

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

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

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

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

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

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

Static Public Member Functions
static constexpr Size	GetInvalidSize () noexcept
	Gets the invalid size value.

static constexpr Height	GetInvalidHeight () noexcept
	Gets the invalid height value.

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

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

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

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

Private Member Functions
Size	AllocateNode () noexcept
	Allocates a node. More...

void	FreeNode (Size index) noexcept
	Frees the specified node. More...

Private Attributes
Size	m_nodeCount {0u}
	Node count. More...

Size	m_leafCount {0u}
	Leaf count. More...

Size	m_rootIndex {GetInvalidSize()}
	Index of root element in m_nodes or `GetInvalidSize()`.

Size	m_freeIndex {GetInvalidSize()}
	Free list. More...

Size	m_nodeCapacity {0u}
	Node capacity. More...

TreeNode *	m_nodes {nullptr}
	Nodes. More...

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

Related Functions
(Note that these are not member functions.)
DynamicTree::Height	GetHeight (const DynamicTree &tree) noexcept
	Gets the height of the binary tree. More...

AABB	GetAABB (const DynamicTree &tree) noexcept
	Gets the AABB for the given dynamic 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.; This data structure is 32-bytes large (on at least one 64-bit platform).

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 = ContactCounter

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/2]

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.

Exceptions

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

◆ DynamicTree() [2/2]

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

Copy constructor.

Exceptions

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

Member Function Documentation

◆ AllocateNode()

DynamicTree::Size playrho::d2::DynamicTree::AllocateNode ( )

privatenoexcept

Allocates a node.

This allocates a node from the free list that can be used as either a leaf node or a branch node.

Precondition: GetNodeCapacity() returns a value at least one greater than the value returned from GetNodeCount().

Warning: Behavior is undefined unless the number of nodes allocated (as reported by GetNodeCount()) is less than GetNodeCapacity().

Note: Call Reserve(GetNodeCount() + 1u) before this if uncertain of whether any entries are available on the free list.

Returns: Value not equal to GetInvalidSize().

See also: GetNodeCount()

Referenced by CreateLeaf(), and RebuildBottomUp().

◆ 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 GetInvalidSize().; GetFreeIndex() will return 0 if this tree had any node capacity, else the value of GetInvalidSize().

Referenced by playrho::d2::WorldImpl::Clear().

◆ CreateLeaf()

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

Creates a new leaf node.

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

Warning: Behavior is undefined unless the number of nodes already allocated (as reported by GetNodeCount()) is less than std::numeric_limits<Size>::max().

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

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

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

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.

Postcondition: The leaf count will be decremented by one.

Warning: Behavior is undefined if the given index is not valid.

◆ 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 GetInvalidSize().

◆ FreeNode()

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

privatenoexcept

Frees the specified node.

Warning: Behavior is undefined if the given index is not valid.; Specified node must be a "leaf" or "branch" node.

Precondition: Specified node's other index is the invalid size index.; Specified node isn't referenced by any other nodes.

Postcondition: The free list links to the given index.

Referenced by RebuildBottomUp().

◆ GetAABB()

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

inlinenoexcept

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

Warning: Behavior is undefined if the given index is not valid.

Parameters

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

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

◆ GetBranchData()

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

inlinenoexcept

Gets the branch data for the identified node.

Warning: Behavior is undefined if the given index in not a valid branch node.

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.

Warning: Behavior is undefined if the given index is not valid.

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.

Examples: World.cpp.

◆ GetLeafData()

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

inlinenoexcept

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

Warning: Behavior is undefined if the given index is not valid.

Parameters

index Identifier of node to get the leaf data for.

Returns: Leaf data for the specified node.

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

◆ 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).

Examples: World.cpp.

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.

Warning: Behavior is undefined if the given index is not valid.

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: GetInvalidSize() 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 method 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 ( 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.

Referenced by playrho::d2::WorldImpl::ShiftOrigin().

◆ UpdateLeaf()

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

Updates a leaf node with a new AABB value.

Warning: Behavior is undefined if the given index is not valid.

Parameters

index	Leaf node's ID. Behavior is undefined if this is not a valid ID.
aabb	New axis aligned bounding box for the leaf node.

Referenced by playrho::d2::WorldImpl::Synchronize().

Friends And Related Function Documentation

◆ 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

Member Data Documentation

◆ m_freeIndex

Size playrho::d2::DynamicTree::m_freeIndex {GetInvalidSize()}

private

Free list.

Index to free nodes.

Referenced by AllocateNode(), Clear(), GetFreeIndex(), and Reserve().

◆ m_leafCount

Size playrho::d2::DynamicTree::m_leafCount {0u}

private

Leaf count.

Count of currently allocated leaf nodes.

Referenced by Clear(), CreateLeaf(), GetLeafCount(), and GetRootIndex().

◆ m_nodeCapacity

Size playrho::d2::DynamicTree::m_nodeCapacity {0u}

private

Node capacity.

Size of buffer allocated for nodes.

Referenced by AllocateNode(), Clear(), GetNodeCapacity(), GetRootIndex(), RebuildBottomUp(), Reserve(), and UpdateLeaf().

◆ m_nodeCount

Size playrho::d2::DynamicTree::m_nodeCount {0u}

private

Node count.

Count of currently allocated nodes.

Referenced by AllocateNode(), Clear(), DynamicTree(), GetNodeCount(), RebuildBottomUp(), and Reserve().

◆ m_nodes

TreeNode* playrho::d2::DynamicTree::m_nodes {nullptr}

private

Nodes.

Initialized on construction.

Referenced by AllocateNode(), Clear(), CreateLeaf(), RebuildBottomUp(), Reserve(), UpdateLeaf(), and ~DynamicTree().

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

DynamicTree.hpp
DynamicTree.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

◆ Height

Constructor & Destructor Documentation

◆ DynamicTree() [1/2]

◆ DynamicTree() [2/2]

Member Function Documentation

◆ AllocateNode()

◆ Clear()

◆ CreateLeaf()

◆ DestroyLeaf()

◆ FindReference()

◆ FreeNode()

◆ GetAABB()

◆ GetBranchData()

◆ GetHeight()

◆ GetLeafCount()

◆ GetLeafData()

◆ GetNodeCapacity()

◆ GetNodeCount()

◆ GetOther()

◆ GetRootIndex()

◆ operator=()

◆ RebuildBottomUp()

◆ Reserve()

◆ ShiftOrigin()

◆ UpdateLeaf()

Friends And Related Function Documentation

◆ GetAABB()

◆ GetHeight()

◆ swap

Member Data Documentation

◆ m_freeIndex

◆ m_leafCount

◆ m_nodeCapacity

◆ m_nodeCount

◆ m_nodes