#include <UT_KDTree.h>

Inheritance diagram for UT_KDTree:

Classes
class	AggregateVolume

class	KDSplit

class	Visitor
	Interface for tree traversals. More...

class	VolumeData
	Interface for aggregate data used by volume filtering. More...

Public Types
enum	ut_KDBalancer { UT_KD_MEDIAN, UT_KD_SAH, UT_KD_CENTROID }
	KD Tree balancing algorithms. See setBalancer. More...

Public Member Functions
	UT_KDTree (int dim=3, size_t size=0)

virtual	~UT_KDTree ()

virtual void	buildIfNeeded (bool enable_multithreading=true)
	This must be called before querying, to build and balance the tree. More...

int64	getMemoryUsage (bool inclusive) const

void	setEntries (size_t size)

size_t	getEntries () const

void	growEntries (size_t amount)

size_t	getRebalanceCount () const

void	setRebalanceCount (size_t count)

void	setBalancer (ut_KDBalancer balance)

void	setMaxLeafNodes (int max_leaf_nodes)

void	flagDirty ()

virtual int	comparePosition (int idx0, int idx1, int dim) const =0

virtual const float *	getP (int idx) const =0
	Return the position associated with the given point. More...

virtual bool	pointsHaveRadius () const

virtual fpreal	getRadius (int) const
	Return the radius associated with the point in question. More...

virtual bool	isValid (int) const
	Returns whether the given index should be considered in searches. More...

virtual bool	isValid (int idx, const UT_KDQueryPt &) const

virtual int	getInvalidLimit (int maxn) const

template<typename QueryPoint >
int	findClosest (const QueryPoint &pt, fpreal max_distance_squared)

template<typename QueryPoint >
int	findClosestQueue (const QueryPoint &pt, ut_KDPQueue &queue, fpreal max_distance_squared)

template<typename QueryPoint >
int	findClosest (UT_IntArray &list, const QueryPoint &pt, fpreal max_distance_squared, int max_nodes, bool sorted=true)

template<typename QueryPoint >
int	findClosestQueue (UT_IntArray &list, const QueryPoint &pt, ut_KDPQueue &q, fpreal max_distance_squared, int max_nodes, bool sorted=true)

template<typename QueryPoint >
int	findClosest (UT_IntArray &list, UT_FloatArray &dist, const QueryPoint &pt, fpreal max_distance_squared, int max_nodes, bool sorted=true)

template<typename QueryPoint >
int	findClosestQueue (UT_IntArray &list, UT_FloatArray &dist, const QueryPoint &pt, ut_KDPQueue &q, fpreal max_distance_squared, int max_nodes, bool sorted=true)

template<typename QueryPoint >
int	findNClosest (UT_IntArray &list, const QueryPoint &pt, int max_nodes)

template<typename QueryPoint >
int	findAllClosest (UT_IntArray &list, const QueryPoint &pt, fpreal max_distance_squared)

void	traverse (Visitor &visitor)

void	filterVolume (VolumeData &data, const UT_Vector3 &pos, const UT_Filter &filter, const AggregateVolume &aggdata, int max_nodes)

const fpreal *	getBoxMin ()

const fpreal *	getBoxMax ()

Static Public Member Functions
static ut_KDPQueuePtr	createQueue ()

Protected Member Functions
int	getHead () const

bool	isValid (int node, const UT_KDTubeQuery &) const

bool	isValid (int node, const UT_KDLineQuery &) const

bool	isValid (int node, const UT_KDTriQuery &) const

bool	isValid (int node, const UT_KDTetQuery &) const

bool	isValid (int node, const UT_KDQueryPtUnitWrap &) const

template<typename QueryPoint >
int	findClosest (ut_KDPQueue &list, const QueryPoint &pt)

template<typename QueryPoint >
void	recurseFind (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const

template<typename QueryPoint >
void	recurseFindTube (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const

template<typename QueryPoint >
void	recurseFindTri (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const

template<typename QueryPoint >
void	findInLeaf (ut_KDPQueue &list, const QueryPoint &pt, int lo, int hi, int invalid_limit, int &invalid) const

bool	isBalanced () const

void	traverseRecursive (Visitor &visitor, int split, int nodeid, UT_BoundingBox &box, int lo, int hi)

void	computeBox (int start_index=0)

bool	isBoxClose (const fpreal *P, fpreal qd, fpreal r) const

void	balance (bool enable_multithreading=true)

void	balanceSet (int &split, fpreal &radius, int list, int entries, fpreal boxmin, fpreal boxmax, UT_Lock splitlock)

Protected Attributes
fpreal	myBMin [UT_KD_MAXDIM]

fpreal	myBMax [UT_KD_MAXDIM]

int *	myList

UT_Array< KDSplit >	mySplits

UT_Lock	myLock
	For protecting tree balancing and bounding box computation. More...

size_t	myEntries
	This marks the number of entries that have been added to our tree. More...

size_t	myFullEntries

size_t	myRebalanceCount

int	myDim

int	myMaxLeafNodes

bool	myBalanced

bool	myBoxComputed

bool	myHasRadius
	A faster way to evaluate pointsHaveRadius() at runtime. More...

ut_KDBalancer	myBalancer

Friends
class	ut_KDPQueueDeleter

Detailed Description

Definition at line 465 of file UT_KDTree.h.

Member Enumeration Documentation

enum UT_KDTree::ut_KDBalancer

KD Tree balancing algorithms. See setBalancer.

Enumerator
UT_KD_MEDIAN
UT_KD_SAH
UT_KD_CENTROID

Definition at line 469 of file UT_KDTree.h.

Constructor & Destructor Documentation

UT_KDTree::UT_KDTree	(	int	dim = `3`,
		size_t	size = `0`
	)

inline

Definition at line 476 of file UT_KDTree.h.

virtual UT_KDTree::~UT_KDTree ( )

virtual

Member Function Documentation

void UT_KDTree::balance ( bool enable_multithreading = true )

protected

Creates a KD tree from an unsorted set of points. Given a list of points, we: 1) Find the dimension in which there is most change. 2) Use the balancing algorithm to choose a splitting plane and partition myList into left and right portions. 3) Store the splitting information in mySplits 4) Recurse on the two halves. This is repeated until myMaxLeafNodes is reached where we just leave it as a linear list.

void UT_KDTree::balanceSet	(	int &	split,
		fpreal &	radius,
		int *	list,
		int	entries,
		fpreal *	boxmin,
		fpreal *	boxmax,
		UT_Lock *	splitlock
	)

protected

Balances a subset, returning the maximum radius of that subset. If splitlock is NULL, the balancing will all be done serially instead of in parallel.

virtual void UT_KDTree::buildIfNeeded ( bool enable_multithreading = true )

inlinevirtual

This must be called before querying, to build and balance the tree.

Reimplemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GEO_2DTree.

Definition at line 489 of file UT_KDTree.h.

virtual int UT_KDTree::comparePosition	(	int	idx0,
		int	idx1,
		int	dim
	)		const

pure virtual

The compare function should compare the distance between two points (given by idx0 and idx1) in the dimension specified. The dimension will be between 0 and 3. For example, comparePosition(...) { fpreal delta = myP[idx0](dim) - myP[idx1](dim); return delta < 0 ? -1 : (delta > 0 ? 1 : 0); }

Implemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GU_SortKDTree.

void UT_KDTree::computeBox ( int start_index = 0 )

protected

static ut_KDPQueuePtr UT_KDTree::createQueue ( )

static

This allows you to create a search queue so you can maintain it over time, avoiding the cost of reallocing for each search. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

void UT_KDTree::filterVolume	(	VolumeData &	data,
		const UT_Vector3 &	pos,
		const UT_Filter &	filter,
		const AggregateVolume &	aggdata,
		int	max_nodes
	)

Filtered evaluation for 3D volumes. This method interprets the KD-Tree as a volume, and filters aggregate point data using the volumetric coverage for aggregate nodes in the tree. The max_nodes parameter controls the approximate number of points that should be averaged to produce the filtered result. The actual filter radius used will depend on max_nodes and on the size of KD-Tree nodes close to the query point. Since this is an approximate query, the actual number of points that contribute to the result may be larger than max_nodes.

This method relies on implemented subclasses for AggregateVolume and for VolumeData. You must compute aggregate volume data before calling this method.

UT_KDTree tree; AggregateVolumeSubclass aggdata; VolumeDataSubclass data;

// Store aggregate values (do this once) kdtree.traverse(aggdata);

// Filter aggregate data (do this many times) kdtree.filterVolume(data, pos, filter, aggdata, max_nodes);

template<typename QueryPoint >

int UT_KDTree::findAllClosest	(	UT_IntArray &	list,
		const QueryPoint &	pt,
		fpreal	max_distance_squared
	)

inline

Definition at line 646 of file UT_KDTree.h.

template<typename QueryPoint >

int UT_KDTree::findClosest	(	const QueryPoint &	pt,
		fpreal	max_distance_squared
	)

Find the closest node to the position specified. This method returns -1 if no photon is found. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >

int UT_KDTree::findClosest	(	UT_IntArray &	list,
		const QueryPoint &	pt,
		fpreal	max_distance_squared,
		int	max_nodes,
		bool	sorted = `true`
	)

Find the closest N (max_nodes) nodes to the position given. Only points within the sphere defined by max_distance_squared will be considered. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >

int UT_KDTree::findClosest	(	UT_IntArray &	list,
		UT_FloatArray &	dist,
		const QueryPoint &	pt,
		fpreal	max_distance_squared,
		int	max_nodes,
		bool	sorted = `true`
	)

Find the closest N (max_nodes) nodes to the position given. Only points within the sphere defined by max_distance_squared will be considered. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >

int UT_KDTree::findClosest	(	ut_KDPQueue &	list,
		const QueryPoint &	pt
	)

protected

template<typename QueryPoint >

int UT_KDTree::findClosestQueue	(	const QueryPoint &	pt,
		ut_KDPQueue &	queue,
		fpreal	max_distance_squared
	)

template<typename QueryPoint >

int UT_KDTree::findClosestQueue	(	UT_IntArray &	list,
		const QueryPoint &	pt,
		ut_KDPQueue &	q,
		fpreal	max_distance_squared,
		int	max_nodes,
		bool	sorted = `true`
	)

template<typename QueryPoint >

int UT_KDTree::findClosestQueue	(	UT_IntArray &	list,
		UT_FloatArray &	dist,
		const QueryPoint &	pt,
		ut_KDPQueue &	q,
		fpreal	max_distance_squared,
		int	max_nodes,
		bool	sorted = `true`
	)

template<typename QueryPoint >

void UT_KDTree::findInLeaf	(	ut_KDPQueue &	list,
		const QueryPoint &	pt,
		int	lo,
		int	hi,
		int	invalid_limit,
		int &	invalid
	)		const

protected

template<typename QueryPoint >

int UT_KDTree::findNClosest	(	UT_IntArray &	list,
		const QueryPoint &	pt,
		int	max_nodes
	)

inline

Definition at line 639 of file UT_KDTree.h.

void UT_KDTree::flagDirty ( )

inline

Marks the tree as dirty. Note, however, that this has O(size) time cost.

Definition at line 556 of file UT_KDTree.h.

const fpreal* UT_KDTree::getBoxMax ( )

const fpreal* UT_KDTree::getBoxMin ( )

size_t UT_KDTree::getEntries ( ) const

inline

Definition at line 513 of file UT_KDTree.h.

int UT_KDTree::getHead ( ) const

inlineprotected

Definition at line 790 of file UT_KDTree.h.

virtual int UT_KDTree::getInvalidLimit ( int maxn ) const

inlinevirtual

Return the maximum number of invalid indices that should be considered before bailing. Return -1 for no limit. maxn - the search limit

Definition at line 590 of file UT_KDTree.h.

int64 UT_KDTree::getMemoryUsage ( bool inclusive ) const

inline

Definition at line 494 of file UT_KDTree.h.

virtual const float* UT_KDTree::getP ( int idx ) const

pure virtual

Return the position associated with the given point.

Implemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GU_SortKDTree.

virtual fpreal UT_KDTree::getRadius ( int ) const

inlinevirtual

Return the radius associated with the point in question.

Reimplemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, and GEO_PointTreeT< GA_Offset >.

Definition at line 579 of file UT_KDTree.h.

size_t UT_KDTree::getRebalanceCount ( ) const

inline

Definition at line 529 of file UT_KDTree.h.

void UT_KDTree::growEntries ( size_t amount )

Sometimes, a tree might have new points added since it's construction. Rather than re-balancing the tree (which can be relatively expensive), we have allow N points to be added to the tree without re-balancing. To add entries to the tree, simply call "growEntries" with the number of points being added. If the size of the unsorted pool exceeds the re-balance count, then the tree will be re-balanced.

The rebalance count is automatically scaled as the tree is constructed, so it shouldn't be required to set the count (unless you know what you're doing).

To force a re-build of the tree, simply call setEntries(), or flag the tree as dirty.

bool UT_KDTree::isBalanced ( ) const

inlineprotected

Definition at line 836 of file UT_KDTree.h.

bool UT_KDTree::isBoxClose	(	const fpreal *	P,
		fpreal	qd,
		fpreal	r
	)		const

protected

virtual bool UT_KDTree::isValid ( int ) const

inlinevirtual

Returns whether the given index should be considered in searches.

Definition at line 582 of file UT_KDTree.h.

virtual bool UT_KDTree::isValid	(	int	idx,
		const UT_KDQueryPt &
	)		const

inlinevirtual

Definition at line 584 of file UT_KDTree.h.

bool UT_KDTree::isValid	(	int	node,
		const UT_KDTubeQuery &
	)		const

inlineprotected

Definition at line 793 of file UT_KDTree.h.

bool UT_KDTree::isValid	(	int	node,
		const UT_KDLineQuery &
	)		const

inlineprotected

Definition at line 795 of file UT_KDTree.h.

bool UT_KDTree::isValid	(	int	node,
		const UT_KDTriQuery &
	)		const

inlineprotected

Definition at line 797 of file UT_KDTree.h.

bool UT_KDTree::isValid	(	int	node,
		const UT_KDTetQuery &
	)		const

inlineprotected

Definition at line 799 of file UT_KDTree.h.

bool UT_KDTree::isValid	(	int	node,
		const UT_KDQueryPtUnitWrap &
	)		const

inlineprotected

Definition at line 801 of file UT_KDTree.h.

virtual bool UT_KDTree::pointsHaveRadius ( ) const

inlinevirtual

If each point in the KD Tree has a radius associated with it, then this method should return true. Adding a per-point radius can affect performance adversely.

Reimplemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, and GEO_PointTreeT< GA_Offset >.

Definition at line 577 of file UT_KDTree.h.

template<typename QueryPoint >

void UT_KDTree::recurseFind	(	ut_KDPQueue &	list,
		const QueryPoint &	pt,
		int	split,
		int	lo,
		int	hi
	)		const

protected

template<typename QueryPoint >

void UT_KDTree::recurseFindTri	(	ut_KDPQueue &	list,
		const QueryPoint &	pt,
		int	split,
		int	lo,
		int	hi
	)		const

protected

template<typename QueryPoint >

void UT_KDTree::recurseFindTube	(	ut_KDPQueue &	list,
		const QueryPoint &	pt,
		int	split,
		int	lo,
		int	hi
	)		const

protected

void UT_KDTree::setBalancer ( ut_KDBalancer balance )

inline

Sets the KD-tree balancing algorithm.

UT_KD_MEDIAN: splits at the median point
UT_KD_CENTROID: splits at the spatial centroid
UT_KD_SAH: splits at SAH optimal splitting point The UT_KD_SAH (surface area heuristic) algorithm builds more efficient trees but they are slower to construct. The default is UT_KD_MEDIAN.

Definition at line 542 of file UT_KDTree.h.

void UT_KDTree::setEntries ( size_t size )

setEntries instructs the KD Tree about the number of points that it should read back from its callbacks. Note that each call to setEntries has O(size) cost! Thus, for (i = 0; i < n; i++) tree.setEntries(i); is O(n^2). There isn't a good reason for this (as one could instead just mark the tree as dirty until the next query, much like already happens with rebalancing) but it is the way things are so be

void UT_KDTree::setMaxLeafNodes ( int max_leaf_nodes )

inline

Sets the maximum number of nodes to be stored in a leaf. Smaller values will produce deeper and more memory-hungry trees.

Definition at line 548 of file UT_KDTree.h.

void UT_KDTree::setRebalanceCount ( size_t count )

void UT_KDTree::traverse ( Visitor & visitor )

Traverse the KD Tree in depth first order. This routine only works on 3D trees. NOTE: This will call balance() if the tree isn't balanced.

void UT_KDTree::traverseRecursive	(	Visitor &	visitor,
		int	split,
		int	nodeid,
		UT_BoundingBox &	box,
		int	lo,
		int	hi
	)

protected

Friends And Related Function Documentation

friend class ut_KDPQueueDeleter

friend

Definition at line 743 of file UT_KDTree.h.

Member Data Documentation

bool UT_KDTree::myBalanced

protected

Definition at line 893 of file UT_KDTree.h.

ut_KDBalancer UT_KDTree::myBalancer

protected

Definition at line 898 of file UT_KDTree.h.

fpreal UT_KDTree::myBMax[UT_KD_MAXDIM]

protected

Definition at line 867 of file UT_KDTree.h.

fpreal UT_KDTree::myBMin[UT_KD_MAXDIM]

protected

Stores the bounding box of all of the points in the KD tree, including their individual radii, in each of the possible dimensions. Note that during balanceSet these values are temporarily altered before recursion, so don't be too shocked.

Definition at line 866 of file UT_KDTree.h.

bool UT_KDTree::myBoxComputed

protected

Definition at line 894 of file UT_KDTree.h.

int UT_KDTree::myDim

protected

Definition at line 891 of file UT_KDTree.h.

size_t UT_KDTree::myEntries

protected

This marks the number of entries that have been added to our tree.

Definition at line 884 of file UT_KDTree.h.

size_t UT_KDTree::myFullEntries

protected

This marks the total number of entries in this data structure. The difference between this and myEntries is the unsorted chaff at the end.

Definition at line 889 of file UT_KDTree.h.

bool UT_KDTree::myHasRadius

protected

A faster way to evaluate pointsHaveRadius() at runtime.

Definition at line 897 of file UT_KDTree.h.

int* UT_KDTree::myList

protected

Nodes in a KD tree have two indices. One is the index that they were added in. This is the index used in getP, for example. The other is there location in the binary heap. myList takes a binary heap location and returns the index useable for getP().

Definition at line 874 of file UT_KDTree.h.

UT_Lock UT_KDTree::myLock

protected

For protecting tree balancing and bounding box computation.

Definition at line 881 of file UT_KDTree.h.

int UT_KDTree::myMaxLeafNodes

protected

Definition at line 892 of file UT_KDTree.h.

size_t UT_KDTree::myRebalanceCount

protected

Definition at line 890 of file UT_KDTree.h.

UT_Array<KDSplit> UT_KDTree::mySplits

protected

Split information stored as a tree structure. This stores the midpoints, splitting offset, axis, and max radius.

Definition at line 878 of file UT_KDTree.h.

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

UT/UT_KDTree.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation