A class representing a non-recursive axis-aligned bounding box tree (AABB tree). More...

#include <Tree.hxx>

Classes
struct	Node

struct	Statistics

Public Member Functions
	~Tree ()=default

	Tree ()=default

BoxUniquePtrList const &	boxes () const

BoxUniquePtr const &	box (Integer const i) const

void	max_nodal_objects (Integer const n)

Integer	max_nodal_objects () const

void	separation_ratio_tolerance (Real const ratio)

Real	separation_ratio_tolerance () const

std::vector< Node > const &	structure () const

Node const &	node (Integer const i) const

Integer	size () const

void	enable_dumping_mode ()

void	disable_dumping_mode ()

void	dumping_mode (bool const mode)

bool	is_empty () const

void	clear ()

void	build (std::unique_ptr< BoxUniquePtrList > boxes_ptr)

template<typename Object>
bool	intersect (Object const &obj, IndexSet &candidates) const

bool	intersect (Tree const &tree, IndexMap &candidates) const

bool	self_intersect (IndexSet &candidates) const

template<typename Object>
Real	distance (Object const &obj, IndexSet &candidates) const

Real	distance (Tree const &tree, IndexMap &candidates) const

template<typename Object, typename Function = std::function<Real(Object const &, Box const &)>>
Real	closest (Object const &obj, Integer const n, IndexSet &candidates, Function distance_function=[](Object const &o, Box const &b) {return b.interior_distance(o);}) const

template<typename Object, typename Function = std::function<Real(Object const &, Box const &)>>
bool	within_distance (Object const &obj, Real const max_distance, IndexSet &candidates, Function distance_function=[](Object const &o, Box const &b) {return b.interior_distance(o);}) const

void	depth (Integer const i, Integer &d) const

void	nodes (Integer const i, Integer &l, Integer &n, Integer &b) const

void	stats (Statistics &stats) const

void	print (OutStream &os) const

Static Public Attributes
static constexpr Real	EPS {std::numeric_limits<Real>::epsilon()}

static constexpr Real	INF {std::numeric_limits<Real>::infinity()}

static constexpr Real	DUMMY_TOL {EPS*static_cast<Real>(100.0)}

Private Types
using	Box = AABBtree::Box<Real, N>

using	BoxUniquePtr = AABBtree::BoxUniquePtr<Real, N>

using	BoxUniquePtrList = AABBtree::BoxUniquePtrList<Real, N>

using	Vector = AABBtree::Vector<Real, N>

using	Point = AABBtree::Point<Real, N>

using	QueueItem = std::tuple<Integer, Integer, Real>

using	PriorityQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, std::function<bool(QueueItem, QueueItem)>>

Private Attributes
std::unique_ptr< BoxUniquePtrList >	m_boxes_ptr {nullptr}

std::vector< Node >	m_tree_structure

IndexList	m_tree_boxes_map

bool	m_dumping_mode {true}

Integer	m_max_nodal_objects {10}

Real	m_separation_ratio_tolerance {0.25}

Real	m_balance_ratio_tolerance {0.3}

Integer	m_check_counter {0}

Integer	m_dump_counter {0}

IndexList	m_stack

PriorityQueue	m_queue

Detailed Description

template<typename Real, Integer N>
class AABBtree::Tree< Real, N >

The Tree class provides an efficient way to store and query a set of axis-aligned bounding boxes non-recursively. It supports various operations such as building the tree, adding axis-aligned boxes, and performing intersection queries. The Tree class is templated on the type of the real numbers and the dimensions of the bounding boxes and is based, as the name suggests, on a novel non-recursive algorithm.

Template Parameters

Real	Type of the scalar coefficients
N	Dimension of the ambient space.

Member Typedef Documentation

◆ Box

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Box = AABBtree::Box<Real, N>

private

◆ BoxUniquePtr

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::BoxUniquePtr = AABBtree::BoxUniquePtr<Real, N>

private

◆ BoxUniquePtrList

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::BoxUniquePtrList = AABBtree::BoxUniquePtrList<Real, N>

private

◆ Point

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Point = AABBtree::Point<Real, N>

private

◆ PriorityQueue

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::PriorityQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, std::function<bool(QueueItem, QueueItem)>>

private

◆ QueueItem

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::QueueItem = std::tuple<Integer, Integer, Real>

private

◆ Vector

template<typename Real, Integer N>

using AABBtree::Tree< Real, N >::Vector = AABBtree::Vector<Real, N>

private

Constructor & Destructor Documentation

◆ ~Tree()

template<typename Real, Integer N>

AABBtree::Tree< Real, N >::~Tree ( )

default

Class destructor for the non-recursive axis-aligned bounding box tree.

◆ Tree()

template<typename Real, Integer N>

AABBtree::Tree< Real, N >::Tree ( )

default

Class constructor for the non-recursive axis-aligned bounding box tree.

Member Function Documentation

◆ box()

template<typename Real, Integer N>

BoxUniquePtr const & AABBtree::Tree< Real, N >::box ( Integer const i ) const

inline

Get a look at the i-th unique pointer to the bounding box.

Parameters

[in] i Index of the unique pointer to the bounding box.

Returns: A const reference to the i-th unique pointer to the bounding box.

◆ boxes()

template<typename Real, Integer N>

BoxUniquePtrList const & AABBtree::Tree< Real, N >::boxes ( ) const

inline

Get a look at the vector of unique pointers to the bounding boxes.

Returns: A const reference to the vector of unique pointers to the bounding boxes.

◆ build()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::build ( std::unique_ptr< BoxUniquePtrList > boxes_ptr )

inline

Build the tree given the bounding boxes.

Parameters

[in] boxes_ptr Bounding boxes to build the tree from.

◆ clear()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::clear ( )

inline

Clear the tree.

◆ closest()

template<typename Real, Integer N>

template<typename Object, typename Function = std::function<Real(Object const &, Box const &)>>

Real AABBtree::Tree< Real, N >::closest	(	Object const &	obj,
		Integer const	n,
		IndexSet &	candidates,
		Function	distance_function = [] (Object const & o, Box const & b) {return b.interior_distance(o);} ) const

inline

Find the first \( n \) candidates from an object, using a custom distance function.

Parameters

[in]	obj	Object to compute the distance to.
[in]	n	Number of candidates to find.
[out]	candidates	First \( n \) candidates.
[in]	distance_function	Custom distance function (default is the interior distance).

Returns: The maximum distance between the candidates and the point. The return value is negative if no candidates are found.

Template Parameters

Object	Type of the object to compute the distance to.
Function	Type of the custom distance function.

◆ depth()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::depth	(	Integer const	i,
		Integer &	d ) const

inline

Compute the depth of the tree from a given node.

Parameters

[in]	i	Index of the node to compute the depth from.
[out]	d	Depth of the tree from the given node.

◆ disable_dumping_mode()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::disable_dumping_mode ( )

inline

Disable dumping mode while building the tree.

◆ distance() [1/2]

template<typename Real, Integer N>

template<typename Object>

Real AABBtree::Tree< Real, N >::distance	(	Object const &	obj,
		IndexSet &	candidates ) const

inline

Compute the minimum distance between an object and the tree.

Parameters

[in]	obj	Object to compute the distance to.
[out]	candidates	Minimum distance candidates.

Returns: The minimum distance between the object and the tree.

Template Parameters

Object Type of the object to compute the distance to.

Note: Object must have a method interior_distance that computes the distance to a box.

◆ distance() [2/2]

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::distance	(	Tree< Real, N > const &	tree,
		IndexMap &	candidates ) const

inline

Compute the minimum distance between the current tree and another tree.

Parameters

[in]	tree	Tree to compute the distance to.
[out]	candidates	Minimum distance candidates.

Returns: The minimum distance between the trees.

◆ dumping_mode()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::dumping_mode ( bool const mode )

inline

Set dumping mode while building the tree.

Parameters

[in] mode Dumping mode.

◆ enable_dumping_mode()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::enable_dumping_mode ( )

inline

Enable dumping mode while building the tree.

◆ intersect() [1/2]

template<typename Real, Integer N>

template<typename Object>

bool AABBtree::Tree< Real, N >::intersect	(	Object const &	obj,
		IndexSet &	candidates ) const

inline

Intersect the tree with an object.

Parameters

[in]	obj	Object to intersect with.
[out]	candidates	Intersection result (boxes indexes).

Returns: True if the object intersects the tree, false otherwise.

Template Parameters

Object Type of the object to intersect with.

Note: Object must have a method intersects that computes the intersection with a box.

◆ intersect() [2/2]

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::intersect	(	Tree< Real, N > const &	tree,
		IndexMap &	candidates ) const

inline

Intersect the tree with another tree.

Parameters

[in]	tree	Tree to intersect with.
[out]	candidates	Intersection result (boxes indexes).

Returns: True if the point intersects the tree, false otherwise.

◆ is_empty()

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::is_empty ( ) const

inline

Check if tree is empty.

Returns: True if the tree is empty, false otherwise.

◆ max_nodal_objects() [1/2]

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::max_nodal_objects ( ) const

inline

Get the maximum number of objects per node.

Returns: The maximum number of objects per node.

◆ max_nodal_objects() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::max_nodal_objects ( Integer const n )

inline

Set the maximum number of objects per node.

Parameters

[in] n Maximum number of objects per node.

◆ node()

template<typename Real, Integer N>

Node const & AABBtree::Tree< Real, N >::node ( Integer const i ) const

inline

Get the i-th tree node.

Parameters

[in] i Index of the node.

Returns: The i-th tree node.

◆ nodes()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::nodes	(	Integer const	i,
		Integer &	l,
		Integer &	n,
		Integer &	b ) const

inline

Compute the number of leafs, nodes, and long boxes of the tree from a given node.

Parameters

[in]	i	Index of the node to start the computation from.
[out]	l	Number of leafs of the tree from the given node.
[out]	n	Number of nodes of the tree from the given node.
[out]	b	Number of long boxes of the tree from the given node.

◆ print()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::print ( OutStream & os ) const

inline

Print the tree info to an output stream.

Parameters

[in] os Output stream to print the tree info to.

◆ self_intersect()

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::self_intersect ( IndexSet & candidates ) const

inline

Self-intersect the tree (i.e., intersect the tree with itself to find all the intersecting boxes).

Parameters

[out] candidates Intersection result (boxes indexes).

Returns: True if the tree intersects itself, false otherwise.

◆ separation_ratio_tolerance() [1/2]

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::separation_ratio_tolerance ( ) const

inline

Get the balance ratio tolerance for bounding boxes.

Returns: The balance ratio tolerance for bounding boxes.

◆ separation_ratio_tolerance() [2/2]

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::separation_ratio_tolerance ( Real const ratio )

inline

Set the balance ratio tolerance for bounding boxes.

Parameters

[in] ratio Balance ratio tolerance for bounding boxes.

◆ size()

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::size ( ) const

inline

Get the number of nodes in the tree.

Returns: The number of nodes in the tree.

◆ stats()

template<typename Real, Integer N>

void AABBtree::Tree< Real, N >::stats ( Statistics & stats ) const

inline

Compute some statistics about the current tree.

Parameters

[out] stats Statistics about the tree.

◆ structure()

template<typename Real, Integer N>

std::vector< Node > const & AABBtree::Tree< Real, N >::structure ( ) const

inline

Get the tree structure.

Returns: The tree structure.

◆ within_distance()

template<typename Real, Integer N>

template<typename Object, typename Function = std::function<Real(Object const &, Box const &)>>

bool AABBtree::Tree< Real, N >::within_distance	(	Object const &	obj,
		Real const	max_distance,
		IndexSet &	candidates,
		Function	distance_function = [] (Object const & o, Box const & b) {return b.interior_distance(o);} ) const

inline

Find the candidates that are within a given distance from a object, using a custom distance function.

Parameters

[in]	obj	Object to compute the distance to.
[in]	max_distance	Maximum distance to consider.
[out]	candidates	Minimum distance candidates.
[in]	distance_function	Custom distance function (default is the interior distance).

Returns: True if at least one object is within the given distance, false otherwise.

Template Parameters

Object	Type of the object to compute the distance to.
Function	Type of the custom distance function.

Member Data Documentation

◆ DUMMY_TOL

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::DUMMY_TOL {EPS*static_cast<Real>(100.0)}

staticconstexpr

Default tolerance for the scalar type

◆ EPS

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::EPS {std::numeric_limits<Real>::epsilon()}

staticconstexpr

Machine epsilon for the scalar type.

◆ INF

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::INF {std::numeric_limits<Real>::infinity()}

staticconstexpr

Infinity value for the scalar type.

◆ m_balance_ratio_tolerance

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::m_balance_ratio_tolerance {0.3}

private

Tolerance for bounding boxes balance.

◆ m_boxes_ptr

template<typename Real, Integer N>

std::unique_ptr<BoxUniquePtrList> AABBtree::Tree< Real, N >::m_boxes_ptr {nullptr}

private

Vector of unique pointers to the bounding boxes.

◆ m_check_counter

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::m_check_counter {0}

mutableprivate

Number of collision check.

◆ m_dump_counter

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::m_dump_counter {0}

mutableprivate

Number of dumpings.

◆ m_dumping_mode

template<typename Real, Integer N>

bool AABBtree::Tree< Real, N >::m_dumping_mode {true}

private

Enable dumping while building the tree.

◆ m_max_nodal_objects

template<typename Real, Integer N>

Integer AABBtree::Tree< Real, N >::m_max_nodal_objects {10}

private

Maximum number of objects per node.

◆ m_queue

template<typename Real, Integer N>

PriorityQueue AABBtree::Tree< Real, N >::m_queue

mutableprivate

Queue for tree traversal.

◆ m_separation_ratio_tolerance

template<typename Real, Integer N>

Real AABBtree::Tree< Real, N >::m_separation_ratio_tolerance {0.25}

private

Tolerance for bounding boxes separation.

◆ m_stack

template<typename Real, Integer N>

IndexList AABBtree::Tree< Real, N >::m_stack

mutableprivate

Tree stack.

◆ m_tree_boxes_map

template<typename Real, Integer N>

IndexList AABBtree::Tree< Real, N >::m_tree_boxes_map

private

Reordering between the vector of boxes and the tree internal structure.

◆ m_tree_structure

template<typename Real, Integer N>

std::vector<Node> AABBtree::Tree< Real, N >::m_tree_structure

private

Tree structure.

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

include/AABBtree/Tree.hxx

Classes

Public Member Functions

Static Public Attributes

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Box

◆ BoxUniquePtr

◆ BoxUniquePtrList

◆ Point

◆ PriorityQueue

◆ QueueItem

◆ Vector

Constructor & Destructor Documentation

◆ ~Tree()

◆ Tree()

Member Function Documentation

◆ box()

◆ boxes()

◆ build()

◆ clear()

◆ closest()

◆ depth()

◆ disable_dumping_mode()

◆ distance() [1/2]

◆ distance() [2/2]

◆ dumping_mode()

◆ enable_dumping_mode()

◆ intersect() [1/2]

◆ intersect() [2/2]

◆ is_empty()

◆ max_nodal_objects() [1/2]

◆ max_nodal_objects() [2/2]

◆ node()

◆ nodes()

◆ print()

◆ self_intersect()

◆ separation_ratio_tolerance() [1/2]

◆ separation_ratio_tolerance() [2/2]

◆ size()

◆ stats()

◆ structure()

◆ within_distance()

Member Data Documentation

◆ DUMMY_TOL

◆ EPS

◆ INF

◆ m_balance_ratio_tolerance

◆ m_boxes_ptr

◆ m_check_counter

◆ m_dump_counter

◆ m_dumping_mode

◆ m_max_nodal_objects

◆ m_queue

◆ m_separation_ratio_tolerance

◆ m_stack

◆ m_tree_boxes_map

◆ m_tree_structure