Implementation of semi-general purpose axis-aligned bounding box hierarchy. More...

#include <AABB.h>

Public Types
typedef DerivedV::Scalar	Scalar
	Scalar type of vertex positions (e.g., `double`)

typedef Eigen::Matrix< Scalar, 1, DIM >	RowVectorDIMS
	Fixed-size (`DIM`) RowVector type using `Scalar`

typedef Eigen::Matrix< Scalar, DIM, 1 >	VectorDIMS
	Fixed-size (`DIM`) (Column)Vector type using `Scalar`

typedef Eigen::Matrix< Scalar, Eigen::Dynamic, DIM >	MatrixXDIMS
	Fixed-width (`DIM`) Matrix type using `Scalar`

Public Member Functions
template<typename DerivedEle , typename Derivedbb_mins , typename Derivedbb_maxs , typename Derivedelements >
IGL_INLINE void	init (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< Derivedbb_mins > &bb_mins, const Eigen::MatrixBase< Derivedbb_maxs > &bb_maxs, const Eigen::MatrixBase< Derivedelements > &elements, const int i=0)
	Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB tree.

template<typename DerivedEle >
IGL_INLINE void	init (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele)
	Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB tree.

template<typename DerivedEle , typename DerivedSI , typename DerivedI >
IGL_INLINE void	init (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedSI > &SI, const Eigen::MatrixBase< DerivedI > &I)
	Build an Axis-Aligned Bounding Box tree for a given mesh.

IGL_INLINE bool	is_leaf () const
	Return whether at leaf node.

template<typename DerivedEle , typename Derivedq >
IGL_INLINE std::vector< int >	find (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< Derivedq > &q, const bool first=false) const
	Find the indices of elements containing given point: this makes sense when Ele is a co-dimension 0 simplex (tets in 3D, triangles in 2D).

IGL_INLINE int	subtree_size () const
	Number of nodes contained in subtree.

template<typename Derivedbb_mins , typename Derivedbb_maxs , typename Derivedelements >
IGL_INLINE void	serialize (Eigen::PlainObjectBase< Derivedbb_mins > &bb_mins, Eigen::PlainObjectBase< Derivedbb_maxs > &bb_maxs, Eigen::PlainObjectBase< Derivedelements > &elements, const int i=0) const
	Serialize this class into 3 arrays (so we can pass it pack to matlab)

template<typename DerivedEle >
IGL_INLINE Scalar	squared_distance (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
	Compute squared distance to a query point.

template<typename DerivedEle >
IGL_INLINE Scalar	squared_distance (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, const Scalar low_sqr_d, const Scalar up_sqr_d, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
	Compute squared distance to a query point if within `low_sqr_d` and `up_sqr_d`.

template<typename DerivedEle >
IGL_INLINE Scalar	squared_distance (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &p, const Scalar up_sqr_d, int &i, Eigen::PlainObjectBase< RowVectorDIMS > &c) const
	Compute squared distance to a query point (default `low_sqr_d`)

template<typename DerivedEle >
IGL_INLINE bool	intersect_ray (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, std::vector< igl::Hit > &hits) const
	Intersect a ray with the mesh return all hits.

template<typename DerivedEle >
IGL_INLINE bool	intersect_ray (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, igl::Hit &hit) const
	Intersect a ray with the mesh return first hit.

template<typename DerivedEle >
IGL_INLINE bool	intersect_ray (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const RowVectorDIMS &origin, const RowVectorDIMS &dir, const Scalar min_t, igl::Hit &hit) const
	Intersect a ray with the mesh return first hit farther than `min_t`

template<typename DerivedEle , typename DerivedP , typename DerivedsqrD , typename DerivedI , typename DerivedC >
IGL_INLINE void	squared_distance (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedP > &P, Eigen::PlainObjectBase< DerivedsqrD > &sqrD, Eigen::PlainObjectBase< DerivedI > &I, Eigen::PlainObjectBase< DerivedC > &C) const
	Compute the squared distance from all query points in P to the closest points on the primitives stored in the AABB hierarchy for the mesh (V,Ele).

template<typename DerivedEle , typename Derivedother_V , typename Derivedother_Ele , typename DerivedsqrD , typename DerivedI , typename DerivedC >
IGL_INLINE void	squared_distance (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const AABB< Derivedother_V, DIM > &other, const Eigen::MatrixBase< Derivedother_V > &other_V, const Eigen::MatrixBase< Derivedother_Ele > &other_Ele, Eigen::PlainObjectBase< DerivedsqrD > &sqrD, Eigen::PlainObjectBase< DerivedI > &I, Eigen::PlainObjectBase< DerivedC > &C) const
	Compute the squared distance from all query points in P already stored in its own AABB hierarchy to the closest points on the primitives stored in the AABB hierarchy for the mesh (V,Ele).

Public Attributes
AABB *	m_left
	Pointer to "left" child node (`nullptr` if leaf)

AABB *	m_right
	Pointer to "right" child node (`nullptr` if leaf)

Eigen::AlignedBox< Scalar, DIM >	m_box
	Axis-Aligned Bounding Box containing this node.

int	m_primitive
	Index of single primitive in this node if full leaf, otherwise -1 for non-leaf.

Friends
void	swap (AABB &first, AABB &second)

Detailed Description

template<typename DerivedV, int DIM>
class igl::AABB< DerivedV, DIM >

Implementation of semi-general purpose axis-aligned bounding box hierarchy.

The mesh (V,Ele) is stored and managed by the caller and each routine here simply takes it as references (it better not change between calls).

It's a little annoying that the Dimension is a template parameter and not picked up at run time from V. This leads to duplicated code for 2d/3d (up to dim).

Template Parameters

DerivedV	Matrix type of vertex positions (e.g., `Eigen::MatrixXd`)
DIM	Dimension of mesh vertex positions (2 or 3)

Member Typedef Documentation

◆ Scalar

template<typename DerivedV , int DIM>

typedef DerivedV::Scalar igl::AABB< DerivedV, DIM >::Scalar

Scalar type of vertex positions (e.g., double)

◆ RowVectorDIMS

template<typename DerivedV , int DIM>

typedef Eigen::Matrix<Scalar,1,DIM> igl::AABB< DerivedV, DIM >::RowVectorDIMS

Fixed-size (DIM) RowVector type using Scalar

◆ VectorDIMS

template<typename DerivedV , int DIM>

typedef Eigen::Matrix<Scalar,DIM,1> igl::AABB< DerivedV, DIM >::VectorDIMS

Fixed-size (DIM) (Column)Vector type using Scalar

◆ MatrixXDIMS

template<typename DerivedV , int DIM>

typedef Eigen::Matrix<Scalar,Eigen::Dynamic,DIM> igl::AABB< DerivedV, DIM >::MatrixXDIMS

Fixed-width (DIM) Matrix type using Scalar

Member Function Documentation

◆ init() [1/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle , typename Derivedbb_mins , typename Derivedbb_maxs , typename Derivedelements >

IGL_INLINE void igl::AABB< DerivedV, DIM >::init	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< Derivedbb_mins > &	bb_mins,
		const Eigen::MatrixBase< Derivedbb_maxs > &	bb_maxs,
		const Eigen::MatrixBase< Derivedelements > &	elements,
		const int	i = `0`
	)

Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB tree.

Parameters

[in]	V	#V by dim list of mesh vertex positions.
[in]	Ele	#Ele by dim+1 list of mesh indices into #V.
[in]	bb_mins	max_tree by dim list of bounding box min corner positions
[in]	bb_maxs	max_tree by dim list of bounding box max corner positions
[in]	elements	max_tree list of element or (not leaf id) indices into Ele
[in]	i	recursive call index {0}

◆ init() [2/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE void igl::AABB< DerivedV, DIM >::init	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele
	)

Build an Axis-Aligned Bounding Box tree for a given mesh and given serialization of a previous AABB tree.

Parameters

[in]	V	#V by dim list of mesh vertex positions.
[in]	Ele	#Ele by dim+1 list of mesh indices into #V.

◆ init() [3/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle , typename DerivedSI , typename DerivedI >

IGL_INLINE void igl::AABB< DerivedV, DIM >::init	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< DerivedSI > &	SI,
		const Eigen::MatrixBase< DerivedI > &	I
	)

Build an Axis-Aligned Bounding Box tree for a given mesh.

Parameters

[in]	V	#V by dim list of mesh vertex positions.
[in]	Ele	#Ele by dim+1 list of mesh indices into #V.
[in]	SI	#Ele by dim list revealing for each coordinate where Ele's barycenters would be sorted: SI(e,d) = i --> the dth coordinate of the barycenter of the eth element would be placed at position i in a sorted list.
[in]	I	#I list of indices into Ele of elements to include (for recursive calls)

◆ is_leaf()

template<typename DerivedV , int DIM>

IGL_INLINE bool igl::AABB< DerivedV, DIM >::is_leaf ( ) const

Return whether at leaf node.

◆ find()

template<typename DerivedV , int DIM>

template<typename DerivedEle , typename Derivedq >

IGL_INLINE std::vector< int > igl::AABB< DerivedV, DIM >::find	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< Derivedq > &	q,
		const bool	first = `false`
	)		const

Find the indices of elements containing given point: this makes sense when Ele is a co-dimension 0 simplex (tets in 3D, triangles in 2D).

Parameters

[in]	V	#V by dim list of mesh vertex positions. Should be same as used to construct mesh.
[in]	Ele	#Ele by dim+1 list of mesh indices into #V. Should be same as used to construct mesh.
[in]	q	dim row-vector query position
[in]	first	whether to only return first element containing q

Returns: list of indices of elements containing q

◆ subtree_size()

template<typename DerivedV , int DIM>

IGL_INLINE int igl::AABB< DerivedV, DIM >::subtree_size ( ) const

Number of nodes contained in subtree.

Returns: Number of elements m then total tree size should be 2*h where h is the deepest depth 2^ceil(log(#Ele*2-1))

◆ serialize()

template<typename DerivedV , int DIM>

template<typename Derivedbb_mins , typename Derivedbb_maxs , typename Derivedelements >

IGL_INLINE void igl::AABB< DerivedV, DIM >::serialize	(	Eigen::PlainObjectBase< Derivedbb_mins > &	bb_mins,
		Eigen::PlainObjectBase< Derivedbb_maxs > &	bb_maxs,
		Eigen::PlainObjectBase< Derivedelements > &	elements,
		const int	i = `0`
	)		const

Serialize this class into 3 arrays (so we can pass it pack to matlab)

Parameters

[out]	bb_mins	max_tree by dim list of bounding box min corner positions
[out]	bb_maxs	max_tree by dim list of bounding box max corner positions
[out]	elements	max_tree list of element or (not leaf id) indices into Ele
[in]	i	recursive call index into these arrays {0}

◆ squared_distance() [1/5]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::squared_distance	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	p,
		int &	i,
		Eigen::PlainObjectBase< RowVectorDIMS > &	c
	)		const

Compute squared distance to a query point.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	p	dim-long query point
[out]	i	facet index corresponding to smallest distances
[out]	c	closest point

Returns: squared distance

Precondition: Currently assumes Elements are triangles regardless of dimension.

◆ squared_distance() [2/5]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::squared_distance	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	p,
		const Scalar	low_sqr_d,
		const Scalar	up_sqr_d,
		int &	i,
		Eigen::PlainObjectBase< RowVectorDIMS > &	c
	)		const

Compute squared distance to a query point if within low_sqr_d and up_sqr_d.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	p	dim-long query point
[in]	low_sqr_d	lower bound on squared distance, specified maximum squared distance
[in]	up_sqr_d	current upper bounded on squared distance, current minimum squared distance (only consider distances less than this), see output.
[out]	i	facet index corresponding to smallest distances
[out]	c	closest point

Returns: squared distance

Precondition: currently assumes Elements are triangles regardless of dimension.

◆ squared_distance() [3/5]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::squared_distance	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	p,
		const Scalar	up_sqr_d,
		int &	i,
		Eigen::PlainObjectBase< RowVectorDIMS > &	c
	)		const

Compute squared distance to a query point (default low_sqr_d)

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	p	dim-long query point
[in]	up_sqr_d	current upper bounded on squared distance, current minimum squared distance (only consider distances less than this), see output.
[out]	i	facet index corresponding to smallest distances
[out]	c	closest point

Returns: squared distance

◆ intersect_ray() [1/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE bool igl::AABB< DerivedV, DIM >::intersect_ray	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	origin,
		const RowVectorDIMS &	dir,
		std::vector< igl::Hit > &	hits
	)		const

Intersect a ray with the mesh return all hits.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	origin	dim-long ray origin
[in]	dir	dim-long ray direction
[out]	hits	list of hits

Returns: true if any hits

◆ intersect_ray() [2/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE bool igl::AABB< DerivedV, DIM >::intersect_ray	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	origin,
		const RowVectorDIMS &	dir,
		igl::Hit &	hit
	)		const

Intersect a ray with the mesh return first hit.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	origin	dim-long ray origin
[in]	dir	dim-long ray direction
[out]	hit	first hit

Returns: true if any hit

◆ intersect_ray() [3/3]

template<typename DerivedV , int DIM>

template<typename DerivedEle >

IGL_INLINE bool igl::AABB< DerivedV, DIM >::intersect_ray	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const RowVectorDIMS &	origin,
		const RowVectorDIMS &	dir,
		const Scalar	min_t,
		igl::Hit &	hit
	)		const

Intersect a ray with the mesh return first hit farther than min_t

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	origin	dim-long ray origin
[in]	dir	dim-long ray direction
[in]	min_t	minimum t value to consider
[out]	hit	first hit

Returns: true if any hit

◆ squared_distance() [4/5]

template<typename DerivedV , int DIM>

template<typename DerivedEle , typename DerivedP , typename DerivedsqrD , typename DerivedI , typename DerivedC >

IGL_INLINE void igl::AABB< DerivedV, DIM >::squared_distance	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< DerivedP > &	P,
		Eigen::PlainObjectBase< DerivedsqrD > &	sqrD,
		Eigen::PlainObjectBase< DerivedI > &	I,
		Eigen::PlainObjectBase< DerivedC > &	C
	)		const

Compute the squared distance from all query points in P to the closest points on the primitives stored in the AABB hierarchy for the mesh (V,Ele).

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	P	#P by dim list of query points
[out]	sqrD	#P list of squared distances
[out]	I	#P list of indices into Ele of closest primitives
[out]	C	#P by dim list of closest points

◆ squared_distance() [5/5]

template<typename DerivedV , int DIM>

template<typename DerivedEle , typename Derivedother_V , typename Derivedother_Ele , typename DerivedsqrD , typename DerivedI , typename DerivedC >

IGL_INLINE void igl::AABB< DerivedV, DIM >::squared_distance	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const AABB< Derivedother_V, DIM > &	other,
		const Eigen::MatrixBase< Derivedother_V > &	other_V,
		const Eigen::MatrixBase< Derivedother_Ele > &	other_Ele,
		Eigen::PlainObjectBase< DerivedsqrD > &	sqrD,
		Eigen::PlainObjectBase< DerivedI > &	I,
		Eigen::PlainObjectBase< DerivedC > &	C
	)		const

Compute the squared distance from all query points in P already stored in its own AABB hierarchy to the closest points on the primitives stored in the AABB hierarchy for the mesh (V,Ele).

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	other	AABB hierarchy of another set of primitives (must be points)
[in]	other_V	#other_V by dim list of query points
[in]	other_Ele	#other_Ele by ss list of simplex indices into other_V (must be simple list of points: ss == 1)
[out]	sqrD	#P list of squared distances
[out]	I	#P list of indices into Ele of closest primitives
[out]	C	#P by dim list of closest points

Friends And Related Symbol Documentation

◆ swap

template<typename DerivedV , int DIM>

void swap	(	AABB< DerivedV, DIM > &	first,
		AABB< DerivedV, DIM > &	second
	)

friend

Member Data Documentation

◆ m_left

template<typename DerivedV , int DIM>

AABB* igl::AABB< DerivedV, DIM >::m_left

Pointer to "left" child node (nullptr if leaf)

◆ m_right

template<typename DerivedV , int DIM>

AABB* igl::AABB< DerivedV, DIM >::m_right

Pointer to "right" child node (nullptr if leaf)

◆ m_box

template<typename DerivedV , int DIM>

Eigen::AlignedBox<Scalar,DIM> igl::AABB< DerivedV, DIM >::m_box

Axis-Aligned Bounding Box containing this node.

◆ m_primitive

template<typename DerivedV , int DIM>

int igl::AABB< DerivedV, DIM >::m_primitive

Index of single primitive in this node if full leaf, otherwise -1 for non-leaf.

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

include/igl/AABB.h

Public Types

Public Member Functions

Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Scalar

◆ RowVectorDIMS

◆ VectorDIMS

◆ MatrixXDIMS

Member Function Documentation

◆ init() [1/3]

◆ init() [2/3]

◆ init() [3/3]

◆ is_leaf()

◆ find()

◆ subtree_size()

◆ serialize()

◆ squared_distance() [1/5]

◆ squared_distance() [2/5]

◆ squared_distance() [3/5]

◆ intersect_ray() [1/3]

◆ intersect_ray() [2/3]

◆ intersect_ray() [3/3]

◆ squared_distance() [4/5]

◆ squared_distance() [5/5]

Friends And Related Symbol Documentation

◆ swap

Member Data Documentation

◆ m_left

◆ m_right

◆ m_box

◆ m_primitive