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< Index >	IndexList

typedef std::vector< KdNode >	NodeList

typedef std::vector< VectorType >	PointList

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 AxisAlignedBoxType &	aabb () 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, Scalar >	doQueryRestrictedClosestIndex (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

currentId Index 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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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