Base class for Axis Aligned Bounding Box trees. More...

#include <geogram/mesh/mesh_AABB.h>

Inheritance diagram for GEO::AABB< BOX >:

Protected Member Functions
void	initialize (index_t nb, std::function< void(BOX &, index_t)> get_bbox)
	Initializes this AABB.

void	bbox_intersect_recursive (std::function< void(index_t)> action, const BOX &box, index_t node, index_t b, index_t e) const
	Computes all the elements that have a bbox that intersects a given bbox in a sub-tree of the AABB tree.

void	self_intersect_recursive (std::function< void(index_t, index_t)> action, index_t node1, index_t b1, index_t e1, index_t node2, index_t b2, index_t e2) const
	Computes all the pairs of intersecting elements for two sub-trees of the AABB tree.

void	other_intersect_recursive (std::function< void(index_t, index_t)> action, index_t node1, index_t b1, index_t e1, const AABB< BOX > *other, index_t node2, index_t b2, index_t e2) const
	Computes all the pairs of intersecting elements for two sub-trees of two AABB trees.

void	init_bboxes_recursive (index_t node_index, index_t b, index_t e, std::function< void(BOX &, index_t)> get_bbox)
	Computes the hierarchy of bounding boxes recursively.

bool	indirect () const
	Tests whether this AABB is indirect or in-place.

index_t	element_in_leaf (index_t i) const
	Gets the element stored in a leaf node.

Static Protected Member Functions
static index_t	max_node_index (index_t node_index, index_t b, index_t e)
	Computes the maximum node index in a subtree.

Protected Attributes
index_t	nb_

vector< BOX >	bboxes_

vector< index_t >	reorder_

Detailed Description

template<class BOX>
class GEO::AABB< BOX >

Base class for Axis Aligned Bounding Box trees.

Template Parameters

BOX	the box class (Box2d or Box3d).

Definition at line 71 of file mesh_AABB.h.

Member Function Documentation

◆ bbox_intersect_recursive()

template<class BOX >

void GEO::AABB< BOX >::bbox_intersect_recursive	(	std::function< void(index_t)>	action,
		const BOX &	box,
		index_t	node,
		index_t	b,
		index_t	e
	)		const

inlineprotected

Computes all the elements that have a bbox that intersects a given bbox in a sub-tree of the AABB tree.

Note that the tree structure is completely implicit, therefore the bounds of the (continuous) facet indices sequences that correspond to the elements contained in the two nodes are sent as well as the node indices.

Parameters

[in]	action	a function that takes as argument an index_t (cell index) invoked for all cells that has a bounding box that overlaps `box`.
[in]	box	the query box
[in]	node	index of the first node of the AABB tree
[in]	b	index of the first facet in `node`
[in]	e	one position past the index of the last facet in `node`

Definition at line 109 of file mesh_AABB.h.

◆ element_in_leaf()

template<class BOX >

index_t GEO::AABB< BOX >::element_in_leaf ( index_t i ) const

inlineprotected

Gets the element stored in a leaf node.

If the AABB is indirect, looks-up the element in the reorder_ permutation, else returns n.

Parameters

[in] i the leaf index, between 0 and nb elements - 1

Returns: the element stored in the leaf node n

Definition at line 345 of file mesh_AABB.h.

◆ indirect()

template<class BOX >

bool GEO::AABB< BOX >::indirect ( ) const

inlineprotected

Tests whether this AABB is indirect or in-place.

An AABB can be indirect (stores a permutation in a vector) or in-place (elements are reordered in the mesh for instance).

Return values

true	if the AABB is indirect
false	if the AABB uses in-place reordering

Definition at line 334 of file mesh_AABB.h.

◆ init_bboxes_recursive()

template<class BOX >

void GEO::AABB< BOX >::init_bboxes_recursive	(	index_t	node_index,
		index_t	b,
		index_t	e,
		std::function< void(BOX &, index_t)>	get_bbox
	)

inlineprotected

Computes the hierarchy of bounding boxes recursively.

This function is generic and can be used to compute a bbox hierarchy of arbitrary elements.

Parameters

[in]	node_index	the index of the root of the subtree
[in]	b	first element index in the subtree
[in]	e	one position past the last element index in the subtree
[in]	get_bbox	a function that takes a Box3d& and an index_t, that computes the bbox of an element.

Definition at line 304 of file mesh_AABB.h.

◆ initialize()

template<class BOX >

void GEO::AABB< BOX >::initialize	(	index_t	nb,
		std::function< void(BOX &, index_t)>	get_bbox
	)

inlineprotected

Initializes this AABB.

Parameters

[in]	nb	number of items.
[in]	get_bbox	a function(Box&, index_t) that computes the Box associated with a given index, in [0..nb-1].

Definition at line 81 of file mesh_AABB.h.

◆ max_node_index()

template<class BOX >

static index_t GEO::AABB< BOX >::max_node_index	(	index_t	node_index,
		index_t	b,
		index_t	e
	)

inlinestaticprotected

Computes the maximum node index in a subtree.

Parameters

[in]	node_index	node index of the root of the subtree
[in]	b	first facet index in the subtree
[in]	e	one position past the last facet index in the subtree

Returns: the maximum node index in the subtree rooted at node_index

Definition at line 280 of file mesh_AABB.h.

◆ other_intersect_recursive()

template<class BOX >

void GEO::AABB< BOX >::other_intersect_recursive	(	std::function< void(index_t, index_t)>	action,
		index_t	node1,
		index_t	b1,
		index_t	e1,
		const AABB< BOX > *	other,
		index_t	node2,
		index_t	b2,
		index_t	e2
	)		const

inlineprotected

Computes all the pairs of intersecting elements for two sub-trees of two AABB trees.

Note that the tree structure is completely implicit, therefore the bounds of the (continuous) facet indices sequences that correspond to the elementss contained in the two nodes are sent as well as the node indices.

Parameters

[in]	action	a function taking as arguments two index_t's, invoked of all pairs of elements that have overlapping bounding boxes.
[in]	node1	index of the first node of the AABB tree
[in]	b1	index of the first facet in `node1`
[in]	e1	one position past the index of the last facet in `node1`
[in]	other	the second AABB tree
[in]	node2	index of the second node of the second AABB tree
[in]	b2	index of the first facet in `node2`
[in]	e2	one position past the index of the second facet in `node2`

Definition at line 225 of file mesh_AABB.h.

◆ self_intersect_recursive()

template<class BOX >

void GEO::AABB< BOX >::self_intersect_recursive	(	std::function< void(index_t, index_t)>	action,
		index_t	node1,
		index_t	b1,
		index_t	e1,
		index_t	node2,
		index_t	b2,
		index_t	e2
	)		const

inlineprotected

Computes all the pairs of intersecting elements for two sub-trees of the AABB tree.

Note that the tree structure is completely implicit, therefore the bounds of the (continuous) facet indices sequences that correspond to the elementss contained in the two nodes are sent as well as the node indices.

Parameters

[in]	action	a function taking as arguments two index_t's, invoked of all pairs of elements that have overlapping bounding boxes.
[in]	node1	index of the first node of the AABB tree
[in]	b1	index of the first facet in `node1`
[in]	e1	one position past the index of the last facet in `node1`
[in]	node2	index of the second node of the AABB tree
[in]	b2	index of the first facet in `node2`
[in]	e2	one position past the index of the second facet in `node2`

Definition at line 156 of file mesh_AABB.h.

Member Data Documentation

◆ bboxes_

template<class BOX >

vector<BOX> GEO::AABB< BOX >::bboxes_

protected

Definition at line 351 of file mesh_AABB.h.

◆ nb_

template<class BOX >

index_t GEO::AABB< BOX >::nb_

protected

Definition at line 350 of file mesh_AABB.h.

◆ reorder_

template<class BOX >

vector<index_t> GEO::AABB< BOX >::reorder_

protected

used if indirect, or unused if in-place

Definition at line 352 of file mesh_AABB.h.

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

geogram/mesh/mesh_AABB.h

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ bbox_intersect_recursive()

◆ element_in_leaf()

◆ indirect()

◆ init_bboxes_recursive()

◆ initialize()

◆ max_node_index()

◆ other_intersect_recursive()

◆ self_intersect_recursive()

Member Data Documentation

◆ bboxes_

◆ nb_

◆ reorder_