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
IGL_INLINE bool	is_leaf () const
	Return whether at leaf node.
IGL_INLINE bool	is_root () const
	Return whether at root node.
IGL_INLINE AABB< DerivedV, DIM > *	root () const
	Return the root node of this node's tree by following its parent.
IGL_INLINE AABB< DerivedV, DIM > *	detach ()
IGL_INLINE void	refit_lineage ()
IGL_INLINE std::vector< AABB< DerivedV, DIM > * >	gather_leaves (const int m)
	Get a vector of leaves indexed by their m_primitive id (these better be non-negative and tightly packed.
IGL_INLINE std::vector< AABB< DerivedV, DIM > * >	gather_leaves ()
IGL_INLINE AABB< DerivedV, DIM > *	pad (const std::vector< AABB< DerivedV, DIM > * > &leaves, const Scalar pad, const int polish_rotate_passes=0)
	Pad leaves by pad in each dimension.
IGL_INLINE AABB< DerivedV, DIM > *	update (const Eigen::AlignedBox< Scalar, DIM > &new_box, const Scalar pad=0)
IGL_INLINE AABB< DerivedV, DIM > *	insert (AABB *other)
	Insert a (probably a leaf) AABB other into this AABB tree.
IGL_INLINE AABB< DerivedV, DIM > *	insert_as_sibling (AABB *other)
	Insert other as a sibling to this by creating a new internal node to be their shared parent.
IGL_INLINE Scalar	rotate (const bool dry_run=false)
	Try to swap this node with its close relatives if it will decrease total internal surface area.
IGL_INLINE Scalar	rotate_across (const bool dry_run=false)
	Try to swap this node with its cousins if it will decrease total internal surface area.
IGL_INLINE Scalar	rotate_up (const bool dry_run=false)
	Try to swap this node with its pibling if it will decrease total internal surface area.
IGL_INLINE Scalar	rotate_down (const bool dry_run=false)
	Try to swap this node with one of its niblings if it will decrease total internal surface area.
IGL_INLINE void	rotate_lineage ()
IGL_INLINE int	subtree_size () const
	Number of nodes contained in subtree (is it?).
IGL_INLINE bool	append_intersecting_leaves (const Eigen::AlignedBox< Scalar, DIM > &box, std::vector< const AABB< DerivedV, DIM > * > &leaves) const
IGL_INLINE DerivedV::Scalar	internal_surface_area () const
	Compute sum of surface area of all internal (non-root, non-leaf) boxes.
IGL_INLINE void	validate () const
	Validate the subtree under this node by running a bunch of assertions.
IGL_INLINE void	print (const int depth=0) const
	print the memory addresses of the tree in a somewhat legible way
IGL_INLINE int	size () const
IGL_INLINE int	height () const
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.
template<typename DerivedEle>
IGL_INLINE AABB< DerivedV, DIM > *	update_primitive (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Scalar pad=0)
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).
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< typename DerivedV::Scalar > > &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< typename DerivedV::Scalar > &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< typename DerivedV::Scalar > &hit) const
	Intersect a ray with the mesh return first hit farther than min_t.
template<typename DerivedEle, typename DerivedOrigin, typename DerivedDir, typename DerivedI, typename DerivedT, typename DerivedUV>
IGL_INLINE void	intersect_ray (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedOrigin > &origin, const Eigen::MatrixBase< DerivedDir > &dir, const Scalar min_t, Eigen::PlainObjectBase< DerivedI > &I, Eigen::PlainObjectBase< DerivedT > &T, Eigen::PlainObjectBase< DerivedUV > &UV)
	Intersect a rays with the mesh return first hit for each.
template<typename DerivedEle, typename DerivedOrigin, typename DerivedDir>
IGL_INLINE void	intersect_ray (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedEle > &Ele, const Eigen::MatrixBase< DerivedOrigin > &origin, const Eigen::MatrixBase< DerivedDir > &dir, std::vector< std::vector< igl::Hit< typename DerivedV::Scalar > > > &hits)
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).

Static Public Member Functions
static IGL_INLINE Scalar	rotate_up (const bool dry_run, AABB< DerivedV, DIM > reining, AABB< DerivedV, DIM > grandparent, AABB< DerivedV, DIM > parent, AABB< DerivedV, DIM > challenger, AABB< DerivedV, DIM > *sibling)
	"Rotate" (swap) reining with challenger.

Public Attributes
AABB *	m_left
	Pointer to "left" child node (nullptr if leaf).
AABB *	m_right
	Pointer to "right" child node (nullptr if leaf).
AABB *	m_parent
	Pointer to "parent" node (nullptr if root).
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.

Determine if collapse the edge e would create new intersections.

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)

Parameters

[in]	e	index into E of edge to try to collapse. E(e,:) = [s d] or [d s] so that s<d, then d is collapsed to s.
[in]	p	dim list of vertex position where to place merged vertex [mesh inputs]
[in,out]	V	#V by dim list of vertex positions, lesser index of E(e,:) will be set to midpoint of edge.
[in,out]	F	#F by 3 list of face indices into V.
[in,out]	E	#E by 2 list of edge indices into V.
[in,out]	EMAP	#F*3 list of indices into E, mapping each directed edge to unique unique edge in E
[in,out]	EF	#E by 2 list of edge flaps, EF(e,0)=f means e=(i-->j) is the edge of F(f,:) opposite the vth corner, where EI(e,0)=v. Similarly EF(e,1) " e=(j->i)
[in,out]	EI	#E by 2 list of edge flap corners (see above). [mesh inputs]
[in]	tree	AABB tree whose leaves correspond to the current (non-null) faces in (V,F)

See also: collapse_edge

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

◆ is_leaf()

template<typename DerivedV, int DIM>

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

Return whether at leaf node.

◆ is_root()

template<typename DerivedV, int DIM>

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

Return whether at root node.

◆ root()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::root ( ) const

Return the root node of this node's tree by following its parent.

◆ detach()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::detach ( )

◆ refit_lineage()

template<typename DerivedV, int DIM>

IGL_INLINE void igl::AABB< DerivedV, DIM >::refit_lineage ( )

◆ gather_leaves() [1/2]

template<typename DerivedV, int DIM>

IGL_INLINE std::vector< AABB< DerivedV, DIM > * > igl::AABB< DerivedV, DIM >::gather_leaves ( const int m )

Get a vector of leaves indexed by their m_primitive id (these better be non-negative and tightly packed.

Parameters

[in] m number of leaves/elements (Ele.rows())

Returns: leaves m list of pointers to leaves

◆ gather_leaves() [2/2]

template<typename DerivedV, int DIM>

IGL_INLINE std::vector< AABB< DerivedV, DIM > * > igl::AABB< DerivedV, DIM >::gather_leaves ( )

◆ pad()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::pad	(	const std::vector< AABB< DerivedV, DIM > * > &	leaves,
		const Scalar	pad,
		const int	polish_rotate_passes = 0 )

Pad leaves by pad in each dimension.

Parameters

[in]	pad	padding amount
[in]	polish_rotate_passes	number of passes to polish rotations

Returns: pointer to (potentially new) root

◆ update()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::update	(	const Eigen::AlignedBox< Scalar, DIM > &	new_box,
		const Scalar	pad = 0 )

Returns: this if no update was needed, otherwise returns pointer to (potentially new) root

Example:

auto * up = leaf->update(new_box);
if(up != leaf)
{
  tree = up->root();
}else
{
  printf("no update occurred\n");
}
 
// or simply
tree = leaf->update(new_box)->root();

◆ insert()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::insert ( AABB< DerivedV, DIM > * other )

Insert a (probably a leaf) AABB other into this AABB tree.

If other's box is contained in this AABB's box then insert it as a child recursively.

If other's box is not contained in this AABB's box then insert it as a sibling.

It's a very good idea to call either rotate (faster, less good) or rotate_lineage (slower, better) after insertion. Rotating continues to improve the tree's quality so after doing a bunch of insertions you might even consider calling rotate on all nodes.

insert attempts to minimize total internal surface area. Where as init is top-down and splits boxes based on the median along the longest dimension. When initializing a tree, init seems to result in great trees (small height and small total internal surface area).

Parameters

[in] other pointer to another AABB node

Returns: pointer to the parent of other or other itself. This could be == to a newly created internal node or to other if this==other. Calling ->root() on this returned node will give you the root of the tree.

Example

// Create a tree (use pointer to track changes to root)
auto * tree = new igl::AABB<DerivedV,3>::AABB();
// Fill the tree (e.g., using ->init())
…
// Create a new leafe node
auto * leaf = new igl::AABB<DerivedV,3>::AABB();
// Fill the leaf node with a primitive and box
…
// Insert into the tree and find the possibly new root
tree = tree->insert(leaf)->root();

◆ insert_as_sibling()

template<typename DerivedV, int DIM>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::insert_as_sibling ( AABB< DerivedV, DIM > * other )

Insert other as a sibling to this by creating a new internal node to be their shared parent.

Before
         parent
         ╱     ╲
     this(C)  sibling
       ╱   ╲
     left right

After
         parent
         ╱     ╲
      newbie   sibling
       ╱    ╲
    this    other
    ╱     ╲
  left  right

Parameters

[in] other pointer to another AABB node

Returns: pointer to the new shared parent.

◆ rotate()

template<typename DerivedV, int DIM>

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::rotate ( const bool dry_run = false )

Try to swap this node with its close relatives if it will decrease total internal surface area.

       grandparent
       ╱          ╲
    parent       pibling°
    ╱     ╲          ╱     ╲
sibling  this   cuz1°  cuz2°
 ╱     ╲
nib1° nib2°

°Swap Candidates

Parameters

[in] dry_run if true then don't actually swap

Returns: [in] the change in total internal surface area, 0 if no improvement and rotate won't be carried out.

◆ rotate_across()

template<typename DerivedV, int DIM>

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::rotate_across ( const bool dry_run = false )

Try to swap this node with its cousins if it will decrease total internal surface area.

Parameters

[in] dry_run if true then don't actually swap

Returns

[in] the change in total internal surface area, 0 if no improvement and rotate won't be carried out.

Before
       grandparent
       ╱          ╲
    parent       pibling
    ╱     ╲          ╱     ╲
sibling  this    cuz1  cuz2


Candidates
       grandparent
       ╱          ╲
    parent       pibling
    ╱     ╲          ╱     ╲
sibling  cuz1   this   cuz2

Or
       grandparent
       ╱          ╲
    parent       pibling
    ╱     ╲          ╱     ╲
sibling  cuz2    cuz1  this

◆ rotate_up() [1/2]

template<typename DerivedV, int DIM>

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::rotate_up ( const bool dry_run = false )

Try to swap this node with its pibling if it will decrease total internal surface area.

Parameters

[in] dry_run if true then don't actually swap

Returns

[in] the change in total internal surface area, 0 if no improvement and rotate won't be carried out.

Before
   grandparent
      ╱     ╲
    other  parent
           ╱   ╲
        this  sibling


Candidate
   grandparent
      ╱     ╲
   this    parent
           ╱   ╲
       other  sibling

◆ rotate_down()

template<typename DerivedV, int DIM>

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::rotate_down ( const bool dry_run = false )

Try to swap this node with one of its niblings if it will decrease total internal surface area.

Parameters

[in] dry_run if true then don't actually swap

Returns

[in] the change in total internal surface area, 0 if no improvement and rotate won't be carried out.

Before
      parent
      ╱     ╲
    this   sibling
           ╱   ╲
        left  right


Candidates
      parent
      ╱     ╲
  left     sibling
           ╱   ╲
       this   right

Or

      parent
      ╱     ╲
  right    sibling
           ╱   ╲
       left   this

◆ rotate_up() [2/2]

template<typename DerivedV, int DIM>

IGL_INLINE Scalar igl::AABB< DerivedV, DIM >::rotate_up	(	const bool	dry_run,
		AABB< DerivedV, DIM > *	reining,
		AABB< DerivedV, DIM > *	grandparent,
		AABB< DerivedV, DIM > *	parent,
		AABB< DerivedV, DIM > *	challenger,
		AABB< DerivedV, DIM > *	sibling )

static

"Rotate" (swap) reining with challenger.

Before
   grandparent
      ╱       ╲
 reining      parent
              ╱     ╲
       challenger  sibling


Candidate
   grandparent
      ╱       ╲
challenger    parent
              ╱     ╲
         reining   sibling

Parameters

[in]	reining	pointer to AABB node to be rotated
[in]	grandparent	pointer to challenger's grandparent
[in]	parent	pointer to challenger's parent
[in]	challenger	pointer to AABB node to be rotated
[in]	sibling	pointer to challenger's sibling

Returns: true only if rotation was possible and successfully carried out.

◆ rotate_lineage()

template<typename DerivedV, int DIM>

IGL_INLINE void igl::AABB< DerivedV, DIM >::rotate_lineage ( )

◆ subtree_size()

template<typename DerivedV, int DIM>

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

Number of nodes contained in subtree (is it?).

Note: At best, this function has a dubious name. This is really an internal helper function for the serialization.

See also: size()

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

◆ append_intersecting_leaves()

template<typename DerivedV, int DIM>

IGL_INLINE bool igl::AABB< DerivedV, DIM >::append_intersecting_leaves	(	const Eigen::AlignedBox< Scalar, DIM > &	box,
		std::vector< const AABB< DerivedV, DIM > * > &	leaves ) const

Parameters

[in]	box	query box
[in,out]	leaves	list of leaves to append to

◆ internal_surface_area()

template<typename DerivedV, int DIM>

IGL_INLINE DerivedV::Scalar igl::AABB< DerivedV, DIM >::internal_surface_area ( ) const

Compute sum of surface area of all internal (non-root, non-leaf) boxes.

◆ validate()

template<typename DerivedV, int DIM>

IGL_INLINE void igl::AABB< DerivedV, DIM >::validate ( ) const

Validate the subtree under this node by running a bunch of assertions.

Does nothing when not in debug mode

◆ print()

template<typename DerivedV, int DIM>

IGL_INLINE void igl::AABB< DerivedV, DIM >::print ( const int depth = 0 ) const

print the memory addresses of the tree in a somewhat legible way

◆ size()

template<typename DerivedV, int DIM>

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

Returns: Actual size of tree. Total number of nodes in tree. A singleton root has size 1.

See also: subtree_size

◆ height()

template<typename DerivedV, int DIM>

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

Returns: Height of the tree. A singleton root has height 1.

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

◆ update_primitive()

template<typename DerivedV, int DIM>

template<typename DerivedEle>

IGL_INLINE AABB< DerivedV, DIM > * igl::AABB< DerivedV, DIM >::update_primitive	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Scalar	pad = 0 )

Returns: this if no update was needed, otherwise returns pointer to (potentially new) root

◆ 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

◆ 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/5]

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< typename DerivedV::Scalar > > &	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/5]

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< typename DerivedV::Scalar > &	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/5]

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< typename DerivedV::Scalar > &	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

◆ intersect_ray() [4/5]

template<typename DerivedV, int DIM>

template<typename DerivedEle, typename DerivedOrigin, typename DerivedDir, typename DerivedI, typename DerivedT, typename DerivedUV>

IGL_INLINE void igl::AABB< DerivedV, DIM >::intersect_ray	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< DerivedOrigin > &	origin,
		const Eigen::MatrixBase< DerivedDir > &	dir,
		const Scalar	min_t,
		Eigen::PlainObjectBase< DerivedI > &	I,
		Eigen::PlainObjectBase< DerivedT > &	T,
		Eigen::PlainObjectBase< DerivedUV > &	UV )

Intersect a rays with the mesh return first hit for each.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	Ele	#Ele by dim list of simplex indices
[in]	origin	#ray by dim+1 list of ray origins
[in]	dir	#ray by dim list of ray directions
[in]	min_t	minimum t value to consider
[out]	I	#ray list of indices into Ele of closest primitives (-1 indicates no hit)
[out]	T	#ray list of t values (nan indicates no hit)
[out]	UV	#ray by dim list of barycentric coordinates

◆ intersect_ray() [5/5]

template<typename DerivedV, int DIM>

template<typename DerivedEle, typename DerivedOrigin, typename DerivedDir>

IGL_INLINE void igl::AABB< DerivedV, DIM >::intersect_ray	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedEle > &	Ele,
		const Eigen::MatrixBase< DerivedOrigin > &	origin,
		const Eigen::MatrixBase< DerivedDir > &	dir,
		std::vector< std::vector< igl::Hit< typename DerivedV::Scalar > > > &	hits )

◆ 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

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

template<typename DerivedV, int DIM>

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

Pointer to "parent" node (nullptr if root).

◆ 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

Static Public Member Functions

Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Scalar

◆ RowVectorDIMS

◆ VectorDIMS

◆ MatrixXDIMS

Member Function Documentation

◆ is_leaf()

◆ is_root()

◆ root()

◆ detach()

◆ refit_lineage()

◆ gather_leaves() [1/2]

◆ gather_leaves() [2/2]

◆ pad()

◆ update()

◆ insert()

Example

◆ insert_as_sibling()

◆ rotate()

◆ rotate_across()

◆ rotate_up() [1/2]

◆ rotate_down()

◆ rotate_up() [2/2]

◆ rotate_lineage()

◆ subtree_size()

◆ append_intersecting_leaves()

◆ internal_surface_area()

◆ validate()

◆ print()

◆ size()

◆ height()

◆ init() [1/3]

◆ init() [2/3]

◆ init() [3/3]

◆ update_primitive()

◆ find()

◆ serialize()

◆ squared_distance() [1/5]

◆ squared_distance() [2/5]

◆ squared_distance() [3/5]

◆ intersect_ray() [1/5]

◆ intersect_ray() [2/5]

◆ intersect_ray() [3/5]

◆ intersect_ray() [4/5]

◆ intersect_ray() [5/5]

◆ squared_distance() [4/5]

◆ squared_distance() [5/5]

Friends And Related Symbol Documentation

◆ swap

Member Data Documentation

◆ m_left

◆ m_right

◆ m_parent

◆ m_box

◆ m_primitive