Eigen::KdBVH< Scalar_, Dim_, _Object > Class Template Reference

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

#include <KdBVH.h>

Classes
struct	VectorComparator

Public Types
enum	{ Dim = Dim_ }
typedef _Object	Object
typedef std::vector< Object, aligned_allocator< Object > >	ObjectList
typedef Scalar_	Scalar
typedef AlignedBox< Scalar, Dim >	Volume
typedef std::vector< Volume, aligned_allocator< Volume > >	VolumeList
typedef int	Index
typedef const int *	VolumeIterator
typedef const Object *	ObjectIterator

Public Member Functions
	KdBVH ()
template<typename Iter >
	KdBVH (Iter begin, Iter end)
template<typename OIter , typename BIter >
	KdBVH (OIter begin, OIter end, BIter boxBegin, BIter boxEnd)
template<typename Iter >
void	init (Iter begin, Iter end)
template<typename OIter , typename BIter >
void	init (OIter begin, OIter end, BIter boxBegin, BIter boxEnd)
Index	getRootIndex () const
EIGEN_STRONG_INLINE void	getChildren (Index index, VolumeIterator &outVBegin, VolumeIterator &outVEnd, ObjectIterator &outOBegin, ObjectIterator &outOEnd) const
const Volume &	getVolume (Index index) const

Private Types
typedef internal::vector_int_pair< Scalar, Dim >	VIPair
typedef std::vector< VIPair, aligned_allocator< VIPair > >	VIPairList
typedef Matrix< Scalar, Dim, 1 >	VectorType

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

Private Attributes
std::vector< int >	children
VolumeList	boxes
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.

Member Typedef Documentation

Index

template<typename Scalar_ , int Dim_, typename _Object >

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

Object

template<typename Scalar_ , int Dim_, typename _Object >

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

ObjectIterator

template<typename Scalar_ , int Dim_, typename _Object >

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

ObjectList

template<typename Scalar_ , int Dim_, typename _Object >

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

Scalar

template<typename Scalar_ , int Dim_, typename _Object >

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

VectorType

template<typename Scalar_ , int Dim_, typename _Object >

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

private

VIPair

template<typename Scalar_ , int Dim_, typename _Object >

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

private

VIPairList

template<typename Scalar_ , int Dim_, typename _Object >

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

private

Volume

template<typename Scalar_ , int Dim_, typename _Object >

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

VolumeIterator

template<typename Scalar_ , int Dim_, typename _Object >

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

VolumeList

template<typename Scalar_ , int Dim_, typename _Object >

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

Member Enumeration Documentation

anonymous enum

template<typename Scalar_ , int Dim_, typename _Object >

anonymous enum

Enumerator
Dim

{ Dim = Dim_ };

Constructor & Destructor Documentation

KdBVH() [1/3]

template<typename Scalar_ , int Dim_, typename _Object >

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

inline

{}

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.

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

References Eigen::placeholders::end, and Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

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

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

References Eigen::placeholders::end, and Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

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

                                                                                            {
    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);
    }
  }

References Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes, Eigen::KdBVH< Scalar_, Dim_, _Object >::children, Eigen::KdBVH< Scalar_, Dim_, _Object >::Dim, eigen_assert, int(), and Eigen::KdBVH< Scalar_, Dim_, _Object >::objects.

Referenced by Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

getChildren()

template<typename Scalar_ , int Dim_, typename _Object >

EIGEN_STRONG_INLINE 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

            {  // 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;
    }
  }

References Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes, Eigen::KdBVH< Scalar_, Dim_, _Object >::children, and Eigen::KdBVH< Scalar_, Dim_, _Object >::objects.

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

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

References Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes.

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

{ return boxes[index]; }

References Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes.

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.

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

References Eigen::placeholders::end.

Referenced by Eigen::KdBVH< Scalar_, Dim_, _Object >::KdBVH().

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.

                                                                  {
    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];
  }

References Eigen::KdBVH< Scalar_, Dim_, _Object >::boxes, Eigen::KdBVH< Scalar_, Dim_, _Object >::build(), Eigen::KdBVH< Scalar_, Dim_, _Object >::children, Eigen::placeholders::end, i, n, Eigen::KdBVH< Scalar_, Dim_, _Object >::objects, Eigen::PlainObjectBase< Derived >::swap(), and tmp.

Member Data Documentation

boxes

template<typename Scalar_ , int Dim_, typename _Object >

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

private

Referenced by Eigen::KdBVH< Scalar_, Dim_, _Object >::build(), Eigen::KdBVH< Scalar_, Dim_, _Object >::getChildren(), Eigen::KdBVH< Scalar_, Dim_, _Object >::getRootIndex(), Eigen::KdBVH< Scalar_, Dim_, _Object >::getVolume(), and Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

children

template<typename Scalar_ , int Dim_, typename _Object >

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

private

Referenced by Eigen::KdBVH< Scalar_, Dim_, _Object >::build(), Eigen::KdBVH< Scalar_, Dim_, _Object >::getChildren(), and Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

objects

template<typename Scalar_ , int Dim_, typename _Object >

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

private

Referenced by Eigen::KdBVH< Scalar_, Dim_, _Object >::build(), Eigen::KdBVH< Scalar_, Dim_, _Object >::getChildren(), and Eigen::KdBVH< Scalar_, Dim_, _Object >::init().

---

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

• KdBVH.h