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

#include <DynamicTree.hpp>

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. More...

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

Public Member Functions
	DynamicTree () noexcept
	Default constructor. More...

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

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

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

	DynamicTree (DynamicTree &&other) noexcept
	Move constructor. More...

DynamicTree &	operator= (DynamicTree other) noexcept
	Unifying assignment operator. 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 user 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. More...

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. More...

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

void	ShiftOrigin (Length2 newOrigin)
	Shifts the world origin. 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	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 PLAYRHO_CONSTEXPR Size	GetInvalidSize () noexcept
	Gets the invalid size value. More...

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

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

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

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

static PLAYRHO_CONSTEXPR Size	GetDefaultInitialNodeCapacity () noexcept
	Gets the default initial node capacity. More...

Static Public Attributes
static const PLAYRHO_CONSTEXPR auto	InvalidHeight = static_cast<Height>(-1)
	Invalid height constant value. 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. More...

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")

Definition at line 71 of file DynamicTree.hpp.

Member Typedef Documentation

◆ Size

using playrho::d2::DynamicTree::Size = ContactCounter

Size type.

Definition at line 75 of file DynamicTree.hpp.

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

Definition at line 92 of file DynamicTree.hpp.

Constructor & Destructor Documentation

◆ DynamicTree() [1/4]

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

defaultnoexcept

Default constructor.

◆ DynamicTree() [2/4]

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

explicit

Size initializing constructor.

Definition at line 381 of file DynamicTree.cpp.

◆ ~DynamicTree()

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

noexcept

Destroys the tree, freeing the node pool.

Definition at line 423 of file DynamicTree.cpp.

◆ DynamicTree() [3/4]

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

Copy constructor.

Definition at line 398 of file DynamicTree.cpp.

◆ DynamicTree() [4/4]

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

noexcept

Move constructor.

Definition at line 409 of file DynamicTree.cpp.

Member Function Documentation

◆ GetInvalidSize()

static PLAYRHO_CONSTEXPR Size playrho::d2::DynamicTree::GetInvalidSize ( )

inlinestaticnoexcept

Gets the invalid size value.

Definition at line 84 of file DynamicTree.hpp.

◆ GetInvalidHeight()

static PLAYRHO_CONSTEXPR Height playrho::d2::DynamicTree::GetInvalidHeight ( )

inlinestaticnoexcept

Gets the invalid height value.

Definition at line 98 of file DynamicTree.hpp.

◆ IsUnused()

static PLAYRHO_CONSTEXPR bool playrho::d2::DynamicTree::IsUnused ( Height value )

inlinestaticnoexcept

Gets whether the given height is the height for an "unused" node.

Definition at line 104 of file DynamicTree.hpp.

◆ IsLeaf()

static PLAYRHO_CONSTEXPR bool playrho::d2::DynamicTree::IsLeaf ( Height value )

inlinestaticnoexcept

Gets whether the given height is the height for a "leaf" node.

Definition at line 110 of file DynamicTree.hpp.

◆ IsBranch()

static PLAYRHO_CONSTEXPR bool playrho::d2::DynamicTree::IsBranch ( Height value )

inlinestaticnoexcept

Gets whether the given height is a height for a "branch" node.

Definition at line 116 of file DynamicTree.hpp.

◆ GetDefaultInitialNodeCapacity()

PLAYRHO_CONSTEXPR DynamicTree::Size playrho::d2::DynamicTree::GetDefaultInitialNodeCapacity ( )

inlinestaticnoexcept

Gets the default initial node capacity.

Definition at line 538 of file DynamicTree.hpp.

◆ 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

Definition at line 415 of file DynamicTree.cpp.

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

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 will be incremented by one.

Returns: The index of the created leaf node.

Definition at line 516 of file DynamicTree.cpp.

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

Definition at line 533 of file DynamicTree.cpp.

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

Definition at line 566 of file DynamicTree.cpp.

◆ GetLeafData()

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

inlinenoexcept

Gets the user 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 user data for.

Returns: User data for the specified node.

Definition at line 602 of file DynamicTree.hpp.

◆ SetLeafData()

void playrho::d2::DynamicTree::SetLeafData	(	Size	index,
		LeafData	value
	)

inlinenoexcept

Sets the leaf data for the element at the given index to the given value.

Definition at line 610 of file DynamicTree.hpp.

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

Definition at line 586 of file DynamicTree.hpp.

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

Definition at line 572 of file DynamicTree.hpp.

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

Definition at line 579 of file DynamicTree.hpp.

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

Definition at line 594 of file DynamicTree.hpp.

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

Definition at line 543 of file DynamicTree.hpp.

◆ GetFreeIndex()

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

inlinenoexcept

Gets the free index.

Definition at line 550 of file DynamicTree.hpp.

◆ RebuildBottomUp()

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

Builds an optimal tree.

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

Definition at line 583 of file DynamicTree.cpp.

◆ ShiftOrigin()

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

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.

Definition at line 652 of file DynamicTree.cpp.

◆ GetNodeCapacity()

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

inlinenoexcept

Gets the current node capacity of this tree.

Definition at line 555 of file DynamicTree.hpp.

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

Definition at line 560 of file DynamicTree.hpp.

◆ GetLeafCount()

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

inlinenoexcept

Gets the current leaf node count.

Examples: World.cpp.

Definition at line 565 of file DynamicTree.hpp.

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

Definition at line 496 of file DynamicTree.cpp.

Friends And Related Function Documentation

◆ swap

void swap	(	DynamicTree &	lhs,
		DynamicTree &	rhs
	)

friend

Customized swap function for DynamicTree objects.

Note: This satisfies the Swappable concept.

See also: http://en.cppreference.com/w/cpp/concept/Swappable

Definition at line 666 of file DynamicTree.cpp.

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

Definition at line 673 of file DynamicTree.hpp.

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

Definition at line 684 of file DynamicTree.hpp.

◆ TestOverlap()

bool TestOverlap	(	const DynamicTree &	tree,
		DynamicTree::Size	leafIdA,
		DynamicTree::Size	leafIdB
	)

Definition at line 692 of file DynamicTree.hpp.

Member Data Documentation

◆ InvalidHeight

const PLAYRHO_CONSTEXPR auto playrho::d2::DynamicTree::InvalidHeight = static_cast<Height>(-1)

static

Invalid height constant value.

Definition at line 95 of file DynamicTree.hpp.

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

Collision/DynamicTree.hpp
Collision/DynamicTree.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

◆ Size

◆ Height

Constructor & Destructor Documentation

◆ DynamicTree() [1/4]

◆ DynamicTree() [2/4]

◆ ~DynamicTree()

◆ DynamicTree() [3/4]

◆ DynamicTree() [4/4]

Member Function Documentation

◆ GetInvalidSize()

◆ GetInvalidHeight()

◆ IsUnused()

◆ IsLeaf()

◆ IsBranch()

◆ GetDefaultInitialNodeCapacity()

◆ operator=()

◆ CreateLeaf()

◆ DestroyLeaf()

◆ UpdateLeaf()

◆ GetLeafData()

◆ SetLeafData()

◆ GetAABB()

◆ GetHeight()

◆ GetOther()

◆ GetBranchData()

◆ GetRootIndex()

◆ GetFreeIndex()

◆ RebuildBottomUp()

◆ ShiftOrigin()

◆ GetNodeCapacity()

◆ GetNodeCount()

◆ GetLeafCount()

◆ FindReference()

Friends And Related Function Documentation

◆ swap

◆ GetHeight()

◆ GetAABB()

◆ TestOverlap()

Member Data Documentation

◆ InvalidHeight