A simple bounding volume hierarchy based on AlignedBox. More...

Classes
struct	VectorComparator

Public Types
enum	{ Dim }

typedef int	Index

typedef _Object	Object

typedef const Object *	ObjectIterator

typedef std::vector< Object, aligned_allocator< Object > >	ObjectList

typedef Scalar_	Scalar

typedef AlignedBox< Scalar, Dim >	Volume

typedef const int *	VolumeIterator

typedef std::vector< Volume, aligned_allocator< Volume > >	VolumeList

Public Member Functions
void	getChildren (Index index, VolumeIterator &outVBegin, VolumeIterator &outVEnd, ObjectIterator &outOBegin, ObjectIterator &outOEnd) const

Index	getRootIndex () const

const Volume &	getVolume (Index index) const

template<typename Iter >
void	init (Iter begin, Iter end)

template<typename OIter , typename BIter >
void	init (OIter begin, OIter end, BIter boxBegin, BIter boxEnd)

	KdBVH ()

template<typename Iter >
	KdBVH (Iter begin, Iter end)

template<typename OIter , typename BIter >
	KdBVH (OIter begin, OIter end, BIter boxBegin, BIter boxEnd)

Private Types
typedef Matrix< Scalar, Dim, 1 >	VectorType

typedef internal::vector_int_pair< Scalar, Dim >	VIPair

typedef std::vector< VIPair, aligned_allocator< VIPair > >	VIPairList

Private Member Functions
void	build (VIPairList &objCenters, int from, int to, const VolumeList &objBoxes, int dim)

Private Attributes
VolumeList	boxes

std::vector< int >	children

ObjectList	objects

Detailed Description

template<typename Scalar_, int Dim_, typename _Object>
class Eigen::KdBVH< Scalar_, Dim_, _Object >

A simple bounding volume hierarchy based on AlignedBox.

Parameters

Scalar_	The underlying scalar type of the bounding boxes
Dim_	The dimension of the space in which the hierarchy lives
<em>Object	The object type that lives in the hierarchy. It must have value semantics. Either bounding_box(_Object) must be defined and return an AlignedBox<Scalar, Dim_> or bounding boxes must be provided to the tree initializer.

This class provides a simple (as opposed to optimized) implementation of a bounding volume hierarchy analogous to a Kd-tree. Given a sequence of objects, it computes their bounding boxes, constructs a Kd-tree of their centers and builds a BVH with the structure of that Kd-tree. When the elements of the tree are too expensive to be copied around, it is useful for _Object to be a pointer.

Definition at line 70 of file KdBVH.h.

Member Typedef Documentation

◆ Index

template<typename Scalar_ , int Dim_, typename _Object >

typedef int Eigen::KdBVH< Scalar_, Dim_, _Object >::Index

Definition at line 79 of file KdBVH.h.

◆ Object

template<typename Scalar_ , int Dim_, typename _Object >

typedef _Object Eigen::KdBVH< Scalar_, Dim_, _Object >::Object

Definition at line 74 of file KdBVH.h.

◆ ObjectIterator

template<typename Scalar_ , int Dim_, typename _Object >

typedef const Object* Eigen::KdBVH< Scalar_, Dim_, _Object >::ObjectIterator

Definition at line 81 of file KdBVH.h.

◆ ObjectList

template<typename Scalar_ , int Dim_, typename _Object >

typedef std::vector<Object, aligned_allocator<Object> > Eigen::KdBVH< Scalar_, Dim_, _Object >::ObjectList

Definition at line 75 of file KdBVH.h.

◆ Scalar

template<typename Scalar_ , int Dim_, typename _Object >

typedef Scalar_ Eigen::KdBVH< Scalar_, Dim_, _Object >::Scalar

Definition at line 76 of file KdBVH.h.

◆ VectorType

template<typename Scalar_ , int Dim_, typename _Object >

typedef Matrix<Scalar, Dim, 1> Eigen::KdBVH< Scalar_, Dim_, _Object >::VectorType

private

Definition at line 175 of file KdBVH.h.

◆ VIPair

template<typename Scalar_ , int Dim_, typename _Object >

typedef internal::vector_int_pair<Scalar, Dim> Eigen::KdBVH< Scalar_, Dim_, _Object >::VIPair

private

Definition at line 173 of file KdBVH.h.

◆ VIPairList

template<typename Scalar_ , int Dim_, typename _Object >

typedef std::vector<VIPair, aligned_allocator<VIPair> > Eigen::KdBVH< Scalar_, Dim_, _Object >::VIPairList

private

Definition at line 174 of file KdBVH.h.

◆ Volume

template<typename Scalar_ , int Dim_, typename _Object >

typedef AlignedBox<Scalar, Dim> Eigen::KdBVH< Scalar_, Dim_, _Object >::Volume

Definition at line 77 of file KdBVH.h.

◆ VolumeIterator

template<typename Scalar_ , int Dim_, typename _Object >

typedef const int* Eigen::KdBVH< Scalar_, Dim_, _Object >::VolumeIterator

Definition at line 80 of file KdBVH.h.

◆ VolumeList

template<typename Scalar_ , int Dim_, typename _Object >

typedef std::vector<Volume, aligned_allocator<Volume> > Eigen::KdBVH< Scalar_, Dim_, _Object >::VolumeList

Definition at line 78 of file KdBVH.h.

Member Enumeration Documentation

◆ anonymous enum

template<typename Scalar_ , int Dim_, typename _Object >

anonymous enum

Enumerator
Dim

Definition at line 73 of file KdBVH.h.

73 { Dim = Dim_ };

Eigen::KdBVH::Dim

@ Dim

Definition: KdBVH.h:73

Constructor & Destructor Documentation

◆ KdBVH() [1/3]

template<typename Scalar_ , int Dim_, typename _Object >

Eigen::KdBVH< Scalar_, Dim_, _Object >::KdBVH ( )

inline

Definition at line 83 of file KdBVH.h.

83 {}

◆ KdBVH() [2/3]

template<typename Scalar_ , int Dim_, typename _Object >

template<typename Iter >

Eigen::KdBVH< Scalar_, Dim_, _Object >::KdBVH	(	Iter	begin,
		Iter	end
	)

inline

Given an iterator range over Object references, constructs the BVH. Requires that bounding_box(Object) return a Volume.

Definition at line 86 of file KdBVH.h.

86 { init(begin, end, 0, 0); } //int is recognized by init as not being an iterator type

Eigen::KdBVH::init

void init(Iter begin, Iter end)

Definition: KdBVH.h:93

end

static const lastp1_t end

◆ KdBVH() [3/3]

template<typename Scalar_ , int Dim_, typename _Object >

template<typename OIter , typename BIter >

Eigen::KdBVH< Scalar_, Dim_, _Object >::KdBVH	(	OIter	begin,
		OIter	end,
		BIter	boxBegin,
		BIter	boxEnd
	)

inline

Given an iterator range over Object references and an iterator range over their bounding boxes, constructs the BVH

Definition at line 89 of file KdBVH.h.

89 { init(begin, end, boxBegin, boxEnd); }

Member Function Documentation

◆ build()

template<typename Scalar_ , int Dim_, typename _Object >

void Eigen::KdBVH< Scalar_, Dim_, _Object >::build	(	VIPairList &	objCenters,
		int	from,
		int	to,
		const VolumeList &	objBoxes,
		int	dim
	)

inlineprivate

Definition at line 186 of file KdBVH.h.

   {
     eigen_assert(to - from > 1);
     if(to - from == 2) {
       boxes.push_back(objBoxes[objCenters[from].second].merged(objBoxes[objCenters[from + 1].second]));
       children.push_back(from + (int)objects.size() - 1); //there are objects.size() - 1 tree nodes
       children.push_back(from + (int)objects.size());
     }
     else if(to - from == 3) {
       int mid = from + 2;
       std::nth_element(objCenters.begin() + from, objCenters.begin() + mid,
                         objCenters.begin() + to, VectorComparator(dim)); //partition
       build(objCenters, from, mid, objBoxes, (dim + 1) % Dim);
       int idx1 = (int)boxes.size() - 1;
       boxes.push_back(boxes[idx1].merged(objBoxes[objCenters[mid].second]));
       children.push_back(idx1);
       children.push_back(mid + (int)objects.size() - 1);
     }
     else {
       int mid = from + (to - from) / 2;
       nth_element(objCenters.begin() + from, objCenters.begin() + mid,
                   objCenters.begin() + to, VectorComparator(dim)); //partition
       build(objCenters, from, mid, objBoxes, (dim + 1) % Dim);
       int idx1 = (int)boxes.size() - 1;
       build(objCenters, mid, to, objBoxes, (dim + 1) % Dim);
       int idx2 = (int)boxes.size() - 1;
       boxes.push_back(boxes[idx1].merged(boxes[idx2]));
       children.push_back(idx1);
       children.push_back(idx2);
     }
   }

◆ getChildren()

template<typename Scalar_ , int Dim_, typename _Object >

void Eigen::KdBVH< Scalar_, Dim_, _Object >::getChildren	(	Index	index,
		VolumeIterator &	outVBegin,
		VolumeIterator &	outVEnd,
		ObjectIterator &	outOBegin,
		ObjectIterator &	outOEnd
	)		const

inline

Given an index of a node, on exit, outVBegin and outVEnd range over the indices of the volume children of the node and outOBegin and outOEnd range over the object children of the node

Definition at line 135 of file KdBVH.h.

   { //inlining this function should open lots of optimization opportunities to the compiler
     if(index < 0) {
       outVBegin = outVEnd;
       if(!objects.empty())
         outOBegin = &(objects[0]);
       outOEnd = outOBegin + objects.size(); //output all objects--necessary when the tree has only one object
       return;
     }
  
     int numBoxes = static_cast<int>(boxes.size());
  
     int idx = index * 2;
     if(children[idx + 1] < numBoxes) { //second index is always bigger
       outVBegin = &(children[idx]);
       outVEnd = outVBegin + 2;
       outOBegin = outOEnd;
     }
     else if(children[idx] >= numBoxes) { //if both children are objects
       outVBegin = outVEnd;
       outOBegin = &(objects[children[idx] - numBoxes]);
       outOEnd = outOBegin + 2;
     } else { //if the first child is a volume and the second is an object
       outVBegin = &(children[idx]);
       outVEnd = outVBegin + 1;
       outOBegin = &(objects[children[idx + 1] - numBoxes]);
       outOEnd = outOBegin + 1;
     }
   }

◆ getRootIndex()

template<typename Scalar_ , int Dim_, typename _Object >

Index Eigen::KdBVH< Scalar_, Dim_, _Object >::getRootIndex ( ) const

inline

Returns: the index of the root of the hierarchy

Definition at line 131 of file KdBVH.h.

131 { return (int)boxes.size() - 1; }

◆ getVolume()

template<typename Scalar_ , int Dim_, typename _Object >

const Volume& Eigen::KdBVH< Scalar_, Dim_, _Object >::getVolume ( Index index ) const

inline

Returns: the bounding box of the node at index

Definition at line 167 of file KdBVH.h.

   {
     return boxes[index];
   }

◆ init() [1/2]

template<typename Scalar_ , int Dim_, typename _Object >

template<typename Iter >

void Eigen::KdBVH< Scalar_, Dim_, _Object >::init	(	Iter	begin,
		Iter	end
	)

inline

Given an iterator range over Object references, constructs the BVH, overwriting whatever is in there currently. Requires that bounding_box(Object) return a Volume.

Definition at line 93 of file KdBVH.h.

93 { init(begin, end, 0, 0); }

◆ init() [2/2]

template<typename Scalar_ , int Dim_, typename _Object >

template<typename OIter , typename BIter >

void Eigen::KdBVH< Scalar_, Dim_, _Object >::init	(	OIter	begin,
		OIter	end,
		BIter	boxBegin,
		BIter	boxEnd
	)

inline

Given an iterator range over Object references and an iterator range over their bounding boxes, constructs the BVH, overwriting whatever is in there currently.

Definition at line 97 of file KdBVH.h.

   {
     objects.clear();
     boxes.clear();
     children.clear();
  
     objects.insert(objects.end(), begin, end);
     int n = static_cast<int>(objects.size());
  
     if(n < 2)
       return; //if we have at most one object, we don't need any internal nodes
  
     VolumeList objBoxes;
     VIPairList objCenters;
  
     //compute the bounding boxes depending on BIter type
     internal::get_boxes_helper<ObjectList, VolumeList, BIter>()(objects, boxBegin, boxEnd, objBoxes);
  
     objCenters.reserve(n);
     boxes.reserve(n - 1);
     children.reserve(2 * n - 2);
  
     for(int i = 0; i < n; ++i)
       objCenters.push_back(VIPair(objBoxes[i].center(), i));
  
     build(objCenters, 0, n, objBoxes, 0); //the recursive part of the algorithm
  
     ObjectList tmp(n);
     tmp.swap(objects);
     for(int i = 0; i < n; ++i)
       objects[i] = tmp[objCenters[i].second];
   }

Member Data Documentation

◆ boxes

template<typename Scalar_ , int Dim_, typename _Object >

VolumeList Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes

private

Definition at line 219 of file KdBVH.h.

◆ children

template<typename Scalar_ , int Dim_, typename _Object >

std::vector<int> Eigen::KdBVH< Scalar_, Dim_, _Object >::children

private

Definition at line 218 of file KdBVH.h.

◆ objects

template<typename Scalar_ , int Dim_, typename _Object >

ObjectList Eigen::KdBVH< Scalar_, Dim_, _Object >::objects

private

Definition at line 220 of file KdBVH.h.

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

KdBVH.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename Scalar_, int Dim_, typename _Object> class Eigen::KdBVH< Scalar_, Dim_, _Object >

Member Typedef Documentation

◆ Index

◆ Object

◆ ObjectIterator

◆ ObjectList

◆ Scalar

◆ VectorType

◆ VIPair

◆ VIPairList

◆ Volume

◆ VolumeIterator

◆ VolumeList

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ KdBVH() [1/3]

◆ KdBVH() [2/3]

◆ KdBVH() [3/3]

Member Function Documentation

◆ build()

◆ getChildren()

◆ getRootIndex()

◆ getVolume()

◆ init() [1/2]

◆ init() [2/2]

Member Data Documentation

◆ boxes

◆ children

◆ objects

template<typename Scalar_, int Dim_, typename _Object>
class Eigen::KdBVH< Scalar_, Dim_, _Object >