AABB tree structure. More...

#include <aabb.h>

Inheritance diagram for RINGMesh::AABBTree< DIMENSION >:

Public Member Functions
index_t	nb_bboxes () const

template<typename EvalDistance >
std::tuple< index_t, vecn< DIMENSION >, double >	closest_element_box (const vecn< DIMENSION > &query, const EvalDistance &action) const
	Gets the closest element box to a point. More...

template<class EvalIntersection >
void	compute_bbox_element_bbox_intersections (const Box< DIMENSION > &box, EvalIntersection &action) const

template<class EvalIntersection >
void	compute_self_element_bbox_intersections (EvalIntersection &action) const

Static Public Attributes
static const index_t	ROOT_INDEX = 1

Protected Member Functions
	AABBTree ()=default

virtual	~AABBTree ()=default

void	initialize_tree (const std::vector< Box< DIMENSION > > &bboxes)
	Builds the tree. More...

bool	is_leaf (index_t box_begin, index_t box_end) const

void	get_recursive_iterators (index_t node_index, index_t box_begin, index_t box_end, index_t &middle_box, index_t &child_left, index_t &child_right) const

const Box< DIMENSION > &	node (index_t i) const

Box< DIMENSION > &	node (index_t i)

Protected Attributes
std::vector< Box< DIMENSION > >	tree_ {}

std::vector< index_t >	mapping_morton_ {}

Private Member Functions
	ringmesh_disable_copy_and_move (AABBTree)

	ringmesh_template_assert_2d_or_3d (DIMENSION)

index_t	max_node_index (index_t node_index, index_t box_begin, index_t box_end)
	Gets the number of nodes in the tree subset. More...

void	initialize_tree_recursive (const std::vector< Box< DIMENSION > > &bboxes, index_t node_index, index_t element_begin, index_t element_end)
	The recursive instruction used in initialize_tree() More...

template<typename ACTION >
void	closest_element_box_recursive (const vecn< DIMENSION > &query, index_t &nearest_box, vecn< DIMENSION > &nearest_point, double &distance, index_t node_index, index_t element_begin, index_t element_end, const ACTION &action) const
	The recursive instruction used in closest_element_box() More...

template<class ACTION >
void	bbox_intersect_recursive (const Box< DIMENSION > &box, index_t node_index, index_t element_begin, index_t element_end, ACTION &action) const

template<class ACTION >
void	self_intersect_recursive (index_t node_index1, index_t element_begin1, index_t element_end1, index_t node_index2, index_t element_begin2, index_t element_end2, ACTION &action) const

std::tuple< index_t, vecn< DIMENSION >, double >	get_nearest_element_box_hint (const vecn< DIMENSION > &query) const
	Gets an hint of the result. More...

virtual vecn< DIMENSION >	get_point_hint_from_box (const Box< DIMENSION > &box, index_t element_id) const =0
	Gets an element point from its box. More...

Detailed Description

template<index_t DIMENSION>
class RINGMesh::AABBTree< DIMENSION >

AABB tree structure.

The tree is store in s single vector following this example: ROOT / \ A1 A2 / \ / \ B1 B2 B3 B4 where B* are the input bboxes Storage: |empty|ROOT|A1|A2|B1|B2|B3|B4|

Definition at line 63 of file aabb.h.

Constructor & Destructor Documentation

◆ AABBTree()

template<index_t DIMENSION>

RINGMesh::AABBTree< DIMENSION >::AABBTree ( )

protecteddefault

◆ ~AABBTree()

template<index_t DIMENSION>

virtual RINGMesh::AABBTree< DIMENSION >::~AABBTree ( )

protectedvirtualdefault

Member Function Documentation

◆ bbox_intersect_recursive()

template<index_t DIMENSION>

template<typename ACTION >

void RINGMesh::AABBTree< DIMENSION >::bbox_intersect_recursive	(	const Box< DIMENSION > &	box,
		index_t	node_index,
		index_t	element_begin,
		index_t	element_end,
		ACTION &	action
	)		const

private

Definition at line 493 of file aabb.h.

◆ closest_element_box()

template<index_t DIMENSION>

template<typename EvalDistance >

std::tuple< index_t, vecn< DIMENSION >, double > RINGMesh::AABBTree< DIMENSION >::closest_element_box	(	const vecn< DIMENSION > &	query,
		const EvalDistance &	action
	)		const

inline

Gets the closest element box to a point.

Parameters

[in]	query	the point to test
[in]	action	the functor to compute the distance between the `query` and the tree element boxes

Returns

a tuple containing:

the index of the closest element box.
the nearest point on the element box.
the distance between the query. and nearest_point.

Template Parameters

EvalDistance this functor should have an operator() defined like this: std::tuple< double, vecn< DIMENSION > > operator()( const vecn< DIMENSION >& query, index_t cur_box ) const ; where query is the same than query, cur_box is the element box index (e.g. in the case of SurfaceAABBTree, this index is a polygon index). The returned tuple contains the distance of the nearest point and the nearest point computed using the element in the cur_box.

Definition at line 100 of file aabb.h.

◆ closest_element_box_recursive()

template<index_t DIMENSION>

template<typename ACTION >

void RINGMesh::AABBTree< DIMENSION >::closest_element_box_recursive	(	const vecn< DIMENSION > &	query,
		index_t &	nearest_box,
		vecn< DIMENSION > &	nearest_point,
		double &	distance,
		index_t	node_index,
		index_t	element_begin,
		index_t	element_end,
		const ACTION &	action
	)		const

private

The recursive instruction used in closest_element_box()

Definition at line 418 of file aabb.h.

◆ compute_bbox_element_bbox_intersections()

template<index_t DIMENSION>

template<class EvalIntersection >

void RINGMesh::AABBTree< DIMENSION >::compute_bbox_element_bbox_intersections	(	const Box< DIMENSION > &	box,
		EvalIntersection &	action
	)		const

inline

Definition at line 126 of file aabb.h.

◆ compute_self_element_bbox_intersections()

template<index_t DIMENSION>

template<class EvalIntersection >

void RINGMesh::AABBTree< DIMENSION >::compute_self_element_bbox_intersections ( EvalIntersection & action ) const

inline

Definition at line 142 of file aabb.h.

◆ get_nearest_element_box_hint()

template<index_t DIMENSION>

std::tuple< index_t, vecn< DIMENSION >, double > RINGMesh::AABBTree< DIMENSION >::get_nearest_element_box_hint ( const vecn< DIMENSION > & query ) const

private

Gets an hint of the result.

Compute the result by approximating each bbox to its barycenter. This result is then used to speed-up the computation by minimizing the distance computation between query and the real elements inside the bboxes

Definition at line 274 of file aabb.cpp.

◆ get_point_hint_from_box()

template<index_t DIMENSION>

virtual vecn< DIMENSION > RINGMesh::AABBTree< DIMENSION >::get_point_hint_from_box	(	const Box< DIMENSION > &	box,
		index_t	element_id
	)		const

privatepure virtual

Gets an element point from its box.

This function is used to get a result from the selected hint box

Implemented in RINGMesh::VolumeAABBTree< DIMENSION >, RINGMesh::SurfaceAABBTree< DIMENSION >, RINGMesh::LineAABBTree< DIMENSION >, and RINGMesh::BoxAABBTree< DIMENSION >.

◆ get_recursive_iterators()

template<index_t DIMENSION>

void RINGMesh::AABBTree< DIMENSION >::get_recursive_iterators	(	index_t	node_index,
		index_t	box_begin,
		index_t	box_end,
		index_t &	middle_box,
		index_t &	child_left,
		index_t &	child_right
	)		const

inlineprotected

Definition at line 165 of file aabb.h.

◆ initialize_tree()

template<index_t DIMENSION>

void RINGMesh::AABBTree< DIMENSION >::initialize_tree ( const std::vector< Box< DIMENSION > > & bboxes )

protected

Builds the tree.

Comptes the morton order and build the tree using the ordered bboxes

Parameters

[in] bboxes the set of unordered bboxes

Definition at line 211 of file aabb.cpp.

◆ initialize_tree_recursive()

template<index_t DIMENSION>

void RINGMesh::AABBTree< DIMENSION >::initialize_tree_recursive	(	const std::vector< Box< DIMENSION > > &	bboxes,
		index_t	node_index,
		index_t	box_begin,
		index_t	box_end
	)

private

The recursive instruction used in initialize_tree()

Computes the hierarchy of bounding boxes recursively.

Parameters

[in]	bboxes	the array of bounding boxes
[in]	node_index	the index of the root of the subtree
[in]	box_begin	first box index in the vector `bboxes`
[in]	box_end	one position past the last box index in the vector `bboxes`

Definition at line 246 of file aabb.cpp.

◆ is_leaf()

template<index_t DIMENSION>

bool RINGMesh::AABBTree< DIMENSION >::is_leaf	(	index_t	box_begin,
		index_t	box_end
	)		const

inlineprotected

Definition at line 161 of file aabb.h.

◆ max_node_index()

template<index_t DIMENSION>

index_t RINGMesh::AABBTree< DIMENSION >::max_node_index	(	index_t	node_index,
		index_t	box_begin,
		index_t	box_end
	)

private

Gets the number of nodes in the tree subset.

Definition at line 221 of file aabb.cpp.

◆ nb_bboxes()

template<index_t DIMENSION>

index_t RINGMesh::AABBTree< DIMENSION >::nb_bboxes ( ) const

inline

Definition at line 73 of file aabb.h.

◆ node() [1/2]

template<index_t DIMENSION>

const Box< DIMENSION >& RINGMesh::AABBTree< DIMENSION >::node ( index_t i ) const

inlineprotected

Definition at line 177 of file aabb.h.

◆ node() [2/2]

template<index_t DIMENSION>

Box< DIMENSION >& RINGMesh::AABBTree< DIMENSION >::node ( index_t i )

inlineprotected

Definition at line 183 of file aabb.h.

◆ ringmesh_disable_copy_and_move()

template<index_t DIMENSION>

RINGMesh::AABBTree< DIMENSION >::ringmesh_disable_copy_and_move ( AABBTree< DIMENSION > )

private

◆ ringmesh_template_assert_2d_or_3d()

template<index_t DIMENSION>

RINGMesh::AABBTree< DIMENSION >::ringmesh_template_assert_2d_or_3d ( DIMENSION )

private

◆ self_intersect_recursive()

template<index_t DIMENSION>

template<class ACTION >

void RINGMesh::AABBTree< DIMENSION >::self_intersect_recursive	(	index_t	node_index1,
		index_t	element_begin1,
		index_t	element_end1,
		index_t	node_index2,
		index_t	element_begin2,
		index_t	element_end2,
		ACTION &	action
	)		const

private

Definition at line 530 of file aabb.h.

Member Data Documentation

◆ mapping_morton_

template<index_t DIMENSION>

std::vector< index_t > RINGMesh::AABBTree< DIMENSION >::mapping_morton_ {}

protected

Definition at line 254 of file aabb.h.

◆ ROOT_INDEX

template<index_t DIMENSION>

const index_t RINGMesh::AABBTree< DIMENSION >::ROOT_INDEX = 1

static

The index where to store the root. It starts to one for algorithm trick.

Definition at line 71 of file aabb.h.

◆ tree_

template<index_t DIMENSION>

std::vector< Box< DIMENSION > > RINGMesh::AABBTree< DIMENSION >::tree_ {}

protected

Definition at line 253 of file aabb.h.

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

D:/dev/RINGMesh/include/ringmesh/mesh/aabb.h
D:/dev/RINGMesh/src/ringmesh/mesh/aabb.cpp

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

template<index_t DIMENSION> class RINGMesh::AABBTree< DIMENSION >

Constructor & Destructor Documentation

◆ AABBTree()

◆ ~AABBTree()

Member Function Documentation

◆ bbox_intersect_recursive()

◆ closest_element_box()

◆ closest_element_box_recursive()

◆ compute_bbox_element_bbox_intersections()

◆ compute_self_element_bbox_intersections()

◆ get_nearest_element_box_hint()

◆ get_point_hint_from_box()

◆ get_recursive_iterators()

◆ initialize_tree()

◆ initialize_tree_recursive()

◆ is_leaf()

◆ max_node_index()

◆ nb_bboxes()

◆ node() [1/2]

◆ node() [2/2]

◆ ringmesh_disable_copy_and_move()

◆ ringmesh_template_assert_2d_or_3d()

◆ self_intersect_recursive()

Member Data Documentation

◆ mapping_morton_

◆ ROOT_INDEX

◆ tree_

template<index_t DIMENSION>
class RINGMesh::AABBTree< DIMENSION >