Generic multi-dimensional kd-tree data structure for point data. More...

#include <mitsuba/core/kdtree.h>

Classes
struct	CoordinateOrdering

struct	LessThanOrEqual

struct	SearchResult
	Result data type for k-nn queries. More...

struct	SearchResultComparator
	Comparison functor for nearest-neighbor search queries. More...

Public Types
enum	EHeuristic { EBalanced = 0, ELeftBalanced, ESlidingMidpoint, EVoxelVolume }
	Supported tree construction heuristics. More...

typedef _NodeType	NodeType

typedef NodeType::PointType	PointType

typedef NodeType::IndexType	IndexType

typedef PointType::Scalar	Scalar

typedef PointType::VectorType	VectorType

typedef TAABB< PointType >	AABBType

Public Member Functions
	PointKDTree (size_t nodes=0, EHeuristic heuristic=ESlidingMidpoint)
	Create an empty KD-tree that can hold the specified number of points. More...

void	setAABB (const AABBType &aabb)
	Set the AABB of the underlying point data. More...

const AABBType &	getAABB () const
	Return the AABB of the underlying point data. More...

size_t	getDepth () const
	Return the depth of the constructed KD-tree. More...

void	setDepth (size_t depth)
	Set the depth of the constructed KD-tree (be careful with this) More...

void	build (bool recomputeAABB=false)
	Construct the KD-tree hierarchy. More...

size_t	nnSearch (const PointType &p, Float &_sqrSearchRadius, size_t k, SearchResult *results) const
	Run a k-nearest-neighbor search query. More...

size_t	nnSearchCollectStatistics (const PointType &p, Float &sqrSearchRadius, size_t k, SearchResult *results, size_t &traversalSteps) const
	Run a k-nearest-neighbor search query and record statistics. More...

size_t	nnSearch (const PointType &p, size_t k, SearchResult *results) const
	Run a k-nearest-neighbor search query without any search radius threshold. More...

template<typename Functor >
size_t	executeModifier (const PointType &p, Float searchRadius, Functor &functor)
	Execute a search query and run the specified functor on them, which potentially modifies the nodes themselves. More...

template<typename Functor >
size_t	executeQuery (const PointType &p, Float searchRadius, Functor &functor) const
	Execute a search query and run the specified functor on them. More...

size_t	search (const PointType &p, Float searchRadius, std::vector< IndexType > &results) const
	Run a search query. More...

bool	hasRightChild (IndexType index) const
	Return whether or not the inner node of the specified index has a right child node. More...

\c stl::vector-like interface
void	clear ()
	Clear the kd-tree array. More...

void	resize (size_t size)
	Resize the kd-tree array. More...

void	reserve (size_t size)
	Reserve a certain amount of memory for the kd-tree array. More...

size_t	size () const
	Return the size of the kd-tree. More...

size_t	capacity () const
	Return the capacity of the kd-tree. More...

void	push_back (const NodeType &node)
	Append a kd-tree node to the node array. More...

NodeType &	operator[] (size_t idx)
	Return one of the KD-tree nodes by index. More...

const NodeType &	operator[] (size_t idx) const
	Return one of the KD-tree nodes by index (const version) More...

Protected Member Functions
IndexType	leftSubtreeSize (IndexType count) const

void	buildLB (IndexType idx, size_t depth, typename std::vector< IndexType >::iterator base, typename std::vector< IndexType >::iterator rangeStart, typename std::vector< IndexType >::iterator rangeEnd, typename std::vector< IndexType > &permutation)
	Left-balanced tree construction routine. More...

void	build (size_t depth, typename std::vector< IndexType >::iterator base, typename std::vector< IndexType >::iterator rangeStart, typename std::vector< IndexType >::iterator rangeEnd)
	Default tree construction routine. More...

Protected Attributes
std::vector< NodeType >	m_nodes

AABBType	m_aabb

EHeuristic	m_heuristic

size_t	m_depth

Detailed Description

template<typename _NodeType>
class mitsuba::PointKDTree< _NodeType >

Generic multi-dimensional kd-tree data structure for point data.

This class organizes point data in a hierarchical manner so various types of queries can be performed efficiently. It supports several heuristics for building ``good'' trees, and it is oblivious to the data layout of the nodes themselves.

Note that this class is meant for point data only — for things that have some kind of spatial extent, the classes GenericKDTree and ShapeKDTree will be more appropriate.

Template Parameters

_NodeType Underlying node data structure. See SimpleKDNode as an example for the required public interface

See Also: SimpleKDNode

Member Typedef Documentation

template<typename _NodeType>

typedef TAABB<PointType> mitsuba::PointKDTree< _NodeType >::AABBType

template<typename _NodeType>

typedef NodeType::IndexType mitsuba::PointKDTree< _NodeType >::IndexType

template<typename _NodeType>

typedef _NodeType mitsuba::PointKDTree< _NodeType >::NodeType

template<typename _NodeType>

typedef NodeType::PointType mitsuba::PointKDTree< _NodeType >::PointType

template<typename _NodeType>

typedef PointType::Scalar mitsuba::PointKDTree< _NodeType >::Scalar

template<typename _NodeType>

typedef PointType::VectorType mitsuba::PointKDTree< _NodeType >::VectorType

Member Enumeration Documentation

template<typename _NodeType>

enum mitsuba::PointKDTree::EHeuristic

Supported tree construction heuristics.

Enumerator
EBalanced	Create a balanced tree by splitting along the median.
ELeftBalanced	Create a left-balanced tree.
ESlidingMidpoint	Use the sliding midpoint tree construction rule. This ensures that cells do not become overly elongated.
EVoxelVolume	Choose the split plane by optimizing a cost heuristic based on the ratio of voxel volumes. Note that Mitsuba's implementation of this heuristic is not particularly optimized — the tree construction construction runs time O(n (log n)^2) instead of O(n log n).

Constructor & Destructor Documentation

template<typename _NodeType>

mitsuba::PointKDTree< _NodeType >::PointKDTree	(	size_t	nodes = `0`,
		EHeuristic	heuristic = `ESlidingMidpoint`
	)

inline

Create an empty KD-tree that can hold the specified number of points.

Member Function Documentation

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::build ( bool recomputeAABB = false )

inline

Construct the KD-tree hierarchy.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::build	(	size_t	depth,
		typename std::vector< IndexType >::iterator	base,
		typename std::vector< IndexType >::iterator	rangeStart,
		typename std::vector< IndexType >::iterator	rangeEnd
	)

inlineprotected

Default tree construction routine.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::buildLB	(	IndexType	idx,
		size_t	depth,
		typename std::vector< IndexType >::iterator	base,
		typename std::vector< IndexType >::iterator	rangeStart,
		typename std::vector< IndexType >::iterator	rangeEnd,
		typename std::vector< IndexType > &	permutation
	)

inlineprotected

Left-balanced tree construction routine.

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::capacity ( ) const

inline

Return the capacity of the kd-tree.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::clear ( )

inline

Clear the kd-tree array.

template<typename _NodeType>

template<typename Functor >

size_t mitsuba::PointKDTree< _NodeType >::executeModifier	(	const PointType &	p,
		Float	searchRadius,
		Functor &	functor
	)

inline

Execute a search query and run the specified functor on them, which potentially modifies the nodes themselves.

The functor must have an operator() implementation, which accepts a NodeType as its argument.

Parameters

p	Search position
functor	Functor to be called on each search result
searchRadius	Search radius

Returns: The number of functor invocations

template<typename _NodeType>

template<typename Functor >

size_t mitsuba::PointKDTree< _NodeType >::executeQuery	(	const PointType &	p,
		Float	searchRadius,
		Functor &	functor
	)		const

inline

Execute a search query and run the specified functor on them.

The functor must have an operator() implementation, which accepts a constant reference to a NodeType as its argument.

Parameters

p	Search position
functor	Functor to be called on each search result
searchRadius	Search radius

Returns: The number of functor invocations

template<typename _NodeType>

const AABBType& mitsuba::PointKDTree< _NodeType >::getAABB ( ) const

inline

Return the AABB of the underlying point data.

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::getDepth ( ) const

inline

Return the depth of the constructed KD-tree.

template<typename _NodeType>

bool mitsuba::PointKDTree< _NodeType >::hasRightChild ( IndexType index ) const

inline

Return whether or not the inner node of the specified index has a right child node.

This function is available for convenience and abstracts away some details about the underlying node representation.

template<typename _NodeType>

IndexType mitsuba::PointKDTree< _NodeType >::leftSubtreeSize ( IndexType count ) const

inlineprotected

Given a number of entries, this method calculates the number of nodes nodes on the left subtree of a left-balanced tree. There are two main cases here:

1) It is possible to completely fill the left subtree 2) It doesn't work - the last level contains too few nodes, e.g : O / \ O O / O

The function assumes that "count" > 1.

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::nnSearch	(	const PointType &	p,
		Float &	_sqrSearchRadius,
		size_t	k,
		SearchResult *	results
	)		const

inline

Run a k-nearest-neighbor search query.

Parameters

p	Search position
sqrSearchRadius	Specifies the squared maximum search radius. This parameter can be used to restrict the k-nn query to a subset of the data – it that is not desired, simply set it to positive infinity. After the query finishes, the parameter value will correspond to the (potentially lower) maximum query radius that was necessary to ensure that the number of results did not exceed `k`.
k	Maximum number of search results
results	Target array for search results. Must contain storage for at least `k+1` entries! (one extra entry is needed for shuffling data around)

Returns: The number of search results (equal to k or less)

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::nnSearch	(	const PointType &	p,
		size_t	k,
		SearchResult *	results
	)		const

inline

Run a k-nearest-neighbor search query without any search radius threshold.

Parameters

p	Search position
k	Maximum number of search results
results	Target array for search results. Must contain storage for at least `k+1` entries! (one extra entry is needed for shuffling data around)

Returns: The number of used traversal steps

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::nnSearchCollectStatistics	(	const PointType &	p,
		Float &	sqrSearchRadius,
		size_t	k,
		SearchResult *	results,
		size_t &	traversalSteps
	)		const

inline

Run a k-nearest-neighbor search query and record statistics.

Parameters

p	Search position
sqrSearchRadius	Specifies the squared maximum search radius. This parameter can be used to restrict the k-nn query to a subset of the data – it that is not desired, simply set it to positive infinity. After the query finishes, the parameter value will correspond to the (potentially lower) maximum query radius that was necessary to ensure that the number of results did not exceed `k`.
k	Maximum number of search results
results	Target array for search results. Must contain storage for at least `k+1` entries! (one extra entry is needed for shuffling data around)

Returns: The number of used traversal steps

template<typename _NodeType>

NodeType& mitsuba::PointKDTree< _NodeType >::operator[] ( size_t idx )

inline

Return one of the KD-tree nodes by index.

template<typename _NodeType>

const NodeType& mitsuba::PointKDTree< _NodeType >::operator[] ( size_t idx ) const

inline

Return one of the KD-tree nodes by index (const version)

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::push_back ( const NodeType & node )

inline

Append a kd-tree node to the node array.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::reserve ( size_t size )

inline

Reserve a certain amount of memory for the kd-tree array.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::resize ( size_t size )

inline

Resize the kd-tree array.

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::search	(	const PointType &	p,
		Float	searchRadius,
		std::vector< IndexType > &	results
	)		const

inline

Run a search query.

Parameters

p	Search position
results	Index list of search results
searchRadius	Search radius

Returns: The number of functor invocations

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::setAABB ( const AABBType & aabb )

inline

Set the AABB of the underlying point data.

template<typename _NodeType>

void mitsuba::PointKDTree< _NodeType >::setDepth ( size_t depth )

inline

Set the depth of the constructed KD-tree (be careful with this)

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::size ( ) const

inline

Return the size of the kd-tree.

Member Data Documentation

template<typename _NodeType>

AABBType mitsuba::PointKDTree< _NodeType >::m_aabb

protected

template<typename _NodeType>

size_t mitsuba::PointKDTree< _NodeType >::m_depth

protected

template<typename _NodeType>

EHeuristic mitsuba::PointKDTree< _NodeType >::m_heuristic

protected

template<typename _NodeType>

std::vector<NodeType> mitsuba::PointKDTree< _NodeType >::m_nodes

protected

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

include/mitsuba/core/kdtree.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<typename _NodeType> class mitsuba::PointKDTree< _NodeType >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename _NodeType>
class mitsuba::PointKDTree< _NodeType >