3D Kdtree with reentrant queries More...

#include <kdtree.h>

+ Inheritance diagram for gr::KdTree< _Scalar, _Index >:
+ Collaboration diagram for gr::KdTree< _Scalar, _Index >:

Classes

struct  KdNode
 
struct  QueryNode
 element of the stack More...
 
struct  RangeQuery
 

Public Types

typedef Eigen::AlignedBox< _Scalar, 3 > AxisAlignedBoxType
 
typedef _Index Index
 
typedef std::vector< IndexIndexList
 
typedef std::vector< KdNodeNodeList
 
typedef std::vector< VectorTypePointList
 
typedef _Scalar Scalar
 
typedef Eigen::Matrix< Scalar, 3, 1 > VectorType
 

Public Member Functions

const PointList_getIndices (void)
 
const NodeList_getNodes (void)
 
const PointList_getPoints (void)
 
const AxisAlignedBoxTypeaabb () const
 
template<class VectorDerived >
void add (const VectorDerived &p)
 Add a new vertex in the KdTree. More...
 
void add (Scalar *position)
 
template<int stackSize, typename Container = std::vector<VectorType>>
void doQueryDist (RangeQuery< stackSize > &query, Container &result) const
 Performs distance query and return vector coordinates. More...
 
template<int stackSize, typename IndexContainer = std::vector<Index>>
void doQueryDistIndices (RangeQuery< stackSize > &query, IndexContainer &result) const
 Performs distance query and return indices. More...
 
template<int stackSize, typename Functor >
void doQueryDistProcessIndices (RangeQuery< stackSize > &query, Functor f) const
 Performs distance query and return indices. More...
 
template<int stackSize>
std::pair< Index, ScalardoQueryRestrictedClosestIndex (RangeQuery< stackSize > &query, int currentId=-1) const
 Finds the closest element index within the range [0:sqrt(sqdist)]. More...
 
void finalize ()
 Finalize the creation of the KdTree. More...
 
 KdTree (const PointList &points, unsigned int nofPointsPerCell=KD_POINT_PER_CELL, unsigned int maxDepth=KD_MAX_DEPTH)
 Create the Kd-Tree using memory copy. More...
 
 KdTree (unsigned int size=0, unsigned int nofPointsPerCell=KD_POINT_PER_CELL, unsigned int maxDepth=KD_MAX_DEPTH)
 Create a void KdTree. More...
 
 ~KdTree ()
 

Static Public Member Functions

static constexpr Index invalidIndex ()
 

Protected Member Functions

template<int stackSize, typename Functor >
void _doQueryDistIndicesWithFunctor (RangeQuery< stackSize > &query, Functor f) const
 Performs distance query and pass the internal id to a functor. More...
 
void createTree (unsigned int nodeId, unsigned int start, unsigned int end, unsigned int level, unsigned int targetCellsize, unsigned int targetMaxDepth)
 Recursively builds the kdtree. More...
 
unsigned int split (int start, int end, unsigned int dim, Scalar splitValue)
 Used to build the tree: split the subset [start..end[ according to dim and splitValue, and returns the index of the first element of the second subset. More...
 

Protected Attributes

unsigned int _maxDepth
 
unsigned int _nofPointsPerCell
 
AxisAlignedBoxType mAABB
 
IndexList mIndices
 
NodeList mNodes
 
PointList mPoints
 

Detailed Description

template<typename _Scalar, typename _Index = int>
class gr::KdTree< _Scalar, _Index >

3D Kdtree with reentrant queries

Member Typedef Documentation

template<typename _Scalar, typename _Index = int>
typedef Eigen::AlignedBox<_Scalar, 3> gr::KdTree< _Scalar, _Index >::AxisAlignedBoxType
template<typename _Scalar, typename _Index = int>
typedef _Index gr::KdTree< _Scalar, _Index >::Index
template<typename _Scalar, typename _Index = int>
typedef std::vector<Index> gr::KdTree< _Scalar, _Index >::IndexList
template<typename _Scalar, typename _Index = int>
typedef std::vector<KdNode> gr::KdTree< _Scalar, _Index >::NodeList
template<typename _Scalar, typename _Index = int>
typedef std::vector<VectorType> gr::KdTree< _Scalar, _Index >::PointList
template<typename _Scalar, typename _Index = int>
typedef _Scalar gr::KdTree< _Scalar, _Index >::Scalar
template<typename _Scalar, typename _Index = int>
typedef Eigen::Matrix<Scalar,3,1> gr::KdTree< _Scalar, _Index >::VectorType

Constructor & Destructor Documentation

template<typename Scalar , typename Index >
gr::KdTree< Scalar, Index >::KdTree ( const PointList points,
unsigned int  nofPointsPerCell = KD_POINT_PER_CELL,
unsigned int  maxDepth = KD_MAX_DEPTH 
)

Create the Kd-Tree using memory copy.

See also
KdTree(unsigned int size, unsigned int nofPointsPerCell, unsigned int maxDepth)

+ Here is the call graph for this function:

template<typename Scalar , typename Index >
gr::KdTree< Scalar, Index >::KdTree ( unsigned int  size = 0,
unsigned int  nofPointsPerCell = KD_POINT_PER_CELL,
unsigned int  maxDepth = KD_MAX_DEPTH 
)

Create a void KdTree.

Second way to create the KdTree, in two time.

You must call finalize() before requesting for closest points.

See also
finalize()
template<typename Scalar , typename Index >
gr::KdTree< Scalar, Index >::~KdTree ( )

Member Function Documentation

template<typename Scalar , typename Index >
template<int stackSize, typename Functor >
void gr::KdTree< Scalar, Index >::_doQueryDistIndicesWithFunctor ( RangeQuery< stackSize > &  query,
Functor  f 
) const
inlineprotected

Performs distance query and pass the internal id to a functor.

See also
doQueryRestrictedClosestIndex For more information about the algorithm.

This function is an alternative to doQueryDist(const VectorType& queryPoint) that allow to perform the query by requesting a maximum distance instead of neighborhood size.

template<typename _Scalar, typename _Index = int>
const PointList& gr::KdTree< _Scalar, _Index >::_getIndices ( void  )
inline
template<typename _Scalar, typename _Index = int>
const NodeList& gr::KdTree< _Scalar, _Index >::_getNodes ( void  )
inline
template<typename _Scalar, typename _Index = int>
const PointList& gr::KdTree< _Scalar, _Index >::_getPoints ( void  )
inline
template<typename _Scalar, typename _Index = int>
const AxisAlignedBoxType& gr::KdTree< _Scalar, _Index >::aabb ( ) const
inline
template<typename _Scalar, typename _Index = int>
template<class VectorDerived >
void gr::KdTree< _Scalar, _Index >::add ( const VectorDerived &  p)
inline

Add a new vertex in the KdTree.

template<typename _Scalar, typename _Index = int>
void gr::KdTree< _Scalar, _Index >::add ( Scalar position)
inline
template<typename Scalar , typename Index >
void gr::KdTree< Scalar, Index >::createTree ( unsigned int  nodeId,
unsigned int  start,
unsigned int  end,
unsigned int  level,
unsigned int  targetCellSize,
unsigned int  targetMaxDepth 
)
protected

Recursively builds the kdtree.

The heuristic is the following:

  • if the number of points in the node is lower than targetCellsize then make a leaf
  • else compute the AABB of the points of the node and split it at the middle of the largest AABB dimension.

This strategy might look not optimal because it does not explicitly prune empty space, unlike more advanced SAH-like techniques used for RT. On the other hand it leads to a shorter tree, faster to traverse and our experience shown that in the special case of kNN queries, this strategy is indeed more efficient (and much faster to build). Moreover, for volume data (e.g., fluid simulation) pruning the empty space is useless.

Actually, storing at each node the exact AABB (we therefore have a binary BVH) allows to prune only about 10% of the leaves, but the overhead of this pruning (ball/ABBB intersection) is more expensive than the gain it provides and the memory consumption is x4 higher !

+ Here is the call graph for this function:

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename Container = std::vector<VectorType>>
void gr::KdTree< _Scalar, _Index >::doQueryDist ( RangeQuery< stackSize > &  query,
Container &  result 
) const
inline

Performs distance query and return vector coordinates.

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename IndexContainer = std::vector<Index>>
void gr::KdTree< _Scalar, _Index >::doQueryDistIndices ( RangeQuery< stackSize > &  query,
IndexContainer &  result 
) const
inline

Performs distance query and return indices.

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename Functor >
void gr::KdTree< _Scalar, _Index >::doQueryDistProcessIndices ( RangeQuery< stackSize > &  query,
Functor  f 
) const
inline

Performs distance query and return indices.

template<typename Scalar , typename Index >
template<int stackSize>
std::pair< Index, Scalar > gr::KdTree< Scalar, Index >::doQueryRestrictedClosestIndex ( RangeQuery< stackSize > &  query,
int  currentId = -1 
) const
inline

Finds the closest element index within the range [0:sqrt(sqdist)].

This algorithm uses the simple distance to the split plane to prune nodes.

Parameters
currentIdIndex of the querypoint if it belongs to the tree

A more elaborated approach consists to track the closest corner of the cell relatively to the current query point. This strategy allows to save about 5% of the leaves. However, in practice the slight overhead due to this tracking reduces the overall performance.

This algorithm also use a simple stack while a priority queue using the squared distances to the cells as a priority values allows to save about 10% of the leaves. But, again, priority queue insertions and deletions are quite involved, and therefore a simple stack is by far much faster.

The optionnal parameter currentId is used when the query point is stored in the tree, and must thus be avoided during the query

template<typename Scalar , typename Index >
void gr::KdTree< Scalar, Index >::finalize ( )
inline

Finalize the creation of the KdTree.

template<typename _Scalar, typename _Index = int>
static constexpr Index gr::KdTree< _Scalar, _Index >::invalidIndex ( )
inlinestatic
template<typename Scalar , typename Index >
unsigned int gr::KdTree< Scalar, Index >::split ( int  start,
int  end,
unsigned int  dim,
Scalar  splitValue 
)
inlineprotected

Used to build the tree: split the subset [start..end[ according to dim and splitValue, and returns the index of the first element of the second subset.

Member Data Documentation

template<typename _Scalar, typename _Index = int>
unsigned int gr::KdTree< _Scalar, _Index >::_maxDepth
protected
template<typename _Scalar, typename _Index = int>
unsigned int gr::KdTree< _Scalar, _Index >::_nofPointsPerCell
protected
template<typename _Scalar, typename _Index = int>
AxisAlignedBoxType gr::KdTree< _Scalar, _Index >::mAABB
protected
template<typename _Scalar, typename _Index = int>
IndexList gr::KdTree< _Scalar, _Index >::mIndices
protected
template<typename _Scalar, typename _Index = int>
NodeList gr::KdTree< _Scalar, _Index >::mNodes
protected
template<typename _Scalar, typename _Index = int>
PointList gr::KdTree< _Scalar, _Index >::mPoints
protected

The documentation for this class was generated from the following file:
  • /home/travis/build/STORM-IRIT/OpenGR/src/gr/accelerators/kdtree.h