KDTree Class Reference

#include <kdtree.h>

Detailed Description

class to find closest points in space for a given point cloud

Public Member Functions
	KDTree ()
	KDTree (KDTree &&src)
	MAXON_OPERATOR_MOVE_ASSIGNMENT (KDTree)
Result< void >	Init (Int maxThreads)
void	Free ()
Result< void >	Insert (const Vector &point, Int idValue)
void	Balance ()
Int	FindNearest (Int threadIndex, const Vector &point, KDTreeNearest *nearest)
Int	FindNearest (Int threadIndex, const Vector &point, Float maxDistance, BaseArray< KDTreeNearest > &list, Int maxElements, Bool sortResults)
Int	FindRange (Int threadIndex, const Vector &point, Float maxDistance, BaseArray< KDTreeNearest > &list, Bool sortResults)

Private Member Functions
	MAXON_DISALLOW_COPY_AND_ASSIGN (KDTree)
KDTreeNode *	Balance (Int index, Int count)
void	InsertElement (BaseArray< KDTreeNearest > &list, Int &count, Float &maxRangeSquare, Int maxElements, KDTreeNode *node, Float distanceSquare)
Bool	AppendElement (BaseArray< KDTreeNearest > &list, KDTreeNode *node, Float distance)

Private Attributes
KDTreeNode *	_root
BaseArray< KDTreeNode >	_nodelist
PointerArray< KDStackArray >	_stack

Constructor & Destructor Documentation

KDTree() [1/2]

KDTree

(

)

KDTree() [2/2]

KDTree

(

KDTree &&

src

)

Member Function Documentation

MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( KDTree  )

private

MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT

(

KDTree

)

Init()

Result<void> Init

(

Int

maxThreads

)

Initialize the kd-tree.

Parameters

[in]

maxThreads

Maximum number of threads using the tree at the same time. set to 1 if no MP is used.

Returns

OK on success.

Free()

void Free

(

)

free the kd-tree and helper arrays

Insert()

Result<void> Insert	(	const Vector &	point,
		Int	idValue
	)

Insert a node into the kd-tree.

Returns

OK on success.

Balance() [1/2]

void Balance

(

)

balance the kd-tree. This needs to be done once after all nodes have been inserted calling 'Insert'

FindNearest() [1/2]

Int FindNearest	(	Int	threadIndex,
		const Vector &	point,
		KDTreeNearest *	nearest
	)

Find the nearest node in the kd-tree.

Parameters

[in]	threadIndex	Index of thread using the tree, set to 0 if no MP is used.
[in]	point	Point in space that is searched for.
[out]	nearest	Optional, can be nullptr. If provided the structure will be filled with information about the nearest node.

Returns

Returns the index of the nearest node or NOTOK if there is no nearest node.

FindNearest() [2/2]

Int FindNearest	(	Int	threadIndex,
		const Vector &	point,
		Float	maxDistance,
		BaseArray< KDTreeNearest > &	list,
		Int	maxElements,
		Bool	sortResults
	)

Find the nearest nodes in the kd-tree note: for performance reasons this routine should only be called if the maximum number of searched nodes is sufficiently small (<100), otherwise FindRange is the better choice.

Parameters

[in]	threadIndex	Index of thread using the tree, set to 0 if no MP is used.
[in]	point	Point in space that is searched for.
[in]	maxDistance	Optional, can be MAXVALUE_FLOAT. If provided only nodes within this distance are searched.
[out]	list	Array that will be filled with search results. the array doesn't have to be initialized before, this will be done inside the routine. for performance reasons try to re-use the array, so that memory doesn't have to be allocated each time.
[in]	maxElements	Maximum number of elements that shall be searched for.
[in]	sortResults	If true the resulting array will be sorted by distance, starting with the closest point.

Returns

Returns the number of found nodes or 0 if there was not enough memory.

FindRange()

Int FindRange	(	Int	threadIndex,
		const Vector &	point,
		Float	maxDistance,
		BaseArray< KDTreeNearest > &	list,
		Bool	sortResults
	)

Find all nodes within a radius in the kd-tree note depending on the structure of the tree there can be a lot of search results (in an extreme case as many as there are nodes in the tree, which costs SIZEOF(KDTreeNearest)*nodes bytes memory.

Parameters

[in]	threadIndex	Index of thread using the tree, set to 0 if no MP is used.
[in]	point	Point in space that is searched for.
[in]	maxDistance	Distance that nodes are searched within.
[out]	list	Array that will be filled with search results. the array doesn't have to be initialized before, this will be done inside the routine. for performance reasons try to re-use the array, so that memory doesn't have to be allocated each time.
[in]	sortResults	If true the resulting array will be sorted by distance, starting with the closest point.

Returns

Returns the number of found nodes or 0 if there was not enough memory.

Balance() [2/2]

KDTreeNode* Balance ( Int  index, Int  count  )

private

InsertElement()

void InsertElement ( BaseArray< KDTreeNearest > &  list, Int &  count, Float &  maxRangeSquare, Int  maxElements, KDTreeNode *  node, Float  distanceSquare  )

private

AppendElement()

Bool AppendElement ( BaseArray< KDTreeNearest > &  list, KDTreeNode *  node, Float  distance  )

private

Member Data Documentation

_root

KDTreeNode* _root

private

_nodelist

BaseArray<KDTreeNode> _nodelist

private

_stack

PointerArray<KDStackArray> _stack

private