#include <GEO_PointTree.h>

Inheritance diagram for GEO_PointTreeT< IDX_T >:

Public Types
typedef IDX_T	IdxType

typedef UT_Array< IdxType >	IdxArrayType

Public Member Functions
	GEO_PointTreeT ()

	~GEO_PointTreeT () override

void	build (const UT_Vector3Array &pts, bool enable_multithreading=true)

void	build (const UT_Vector3Array &pts, const IdxArrayType &idx, bool enable_multithreading=true)

virtual void	clear ()
	Clears out the tree, leaving it with no entries. More...

int	entries () const
	Returns the number of actual points in the tree. More...

virtual int64	getMemoryUsage (bool inclusive=true) const
	Returns the amount of memory used by this tree. More...

IdxType	findNearestIdx (const UT_Vector3 &pt)

IdxType	findNearestIdx (const UT_Vector3 &pt, fpreal maxdist)

IdxType	findNearestIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &q, fpreal maxdist=1e18f, bool wrapunitcube=false)
	This uses a pre-built queue to reduce memory allocation. More...

int	findAllCloseIdx (const UT_Vector3 &pt, fpreal maxdist, IdxArrayType &list)

int	findAllCloseIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &queue, fpreal maxdist, IdxArrayType &list)
	Creates a search queue useful for findAll queries. More...

int	findAllInTubeIdx (const UT_Vector3 &pt, const UT_Vector3 &dir, fpreal radius, IdxArrayType &list)
	Find all of the points inside the given tube. More...

void	setPointTransform (const UT_DMatrix4 &xform)

void	ensureTreeBuilt ()

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

void	setBalancer (ut_KDBalancer balance)

void	setMaxLeafNodes (int max_leaf_nodes)


void	append (const UT_Vector3 &pt, IdxType idx, bool auto_rebalance=false)

void	append (const UT_Vector3 &pt)


void	appendPtRadius (const UT_Vector3 &pt, fpreal radius, IdxType idx, bool auto_rebalance=false)

void	appendPtRadius (const UT_Vector3 &pt, fpreal radius)


int	findNearestGroupIdx (const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist)

int	findNearestGroupIdxQueue (const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist, ut_KDPQueue &q, bool wrapunitcube=false)
	This uses a pre-built queue to reduce memory allocation. More...

Protected Member Functions
int	comparePosition (int idx0, int idx1, int dim) const override
	These are used by KDTree: More...

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

bool	pointsHaveRadius () const override
	These are used if the user adds points with radii. More...

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

void	updateKDTree (bool enablemultithread=true)

void	dirtyKDTree ()
	Marks the kd tree as out of date. More...

void	clearPointTransform ()
	Clears the myPointTransform member data. More...

Protected Member Functions inherited from UT_KDTree
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)

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

virtual	~UT_KDTree ()

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 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 ()

Protected Attributes
UT_DMatrix4 *	myPointTransform

IdxArrayType	myIndexList
	This is the mapping from the KD entries into the GDP numbers. More...

UT_Vector3Array	myPointList
	The list of all the points. More...

UT_FloatArray	myRadii
	List of radii for each pont. More...

bool	myIsKDTreeDirty

Protected Attributes inherited from UT_KDTree
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

Additional Inherited Members
Protected Types inherited from UT_KDTree
enum	ut_KDBalancer { UT_KD_MEDIAN, UT_KD_SAH, UT_KD_CENTROID }
	KD Tree balancing algorithms. See setBalancer. More...

Static Protected Member Functions inherited from UT_KDTree
static ut_KDPQueuePtr	createQueue ()

Detailed Description

template<typename IDX_T>
class GEO_PointTreeT< IDX_T >

GEO_PointTreeT is a position tree used to accelerate lookups based on the index type IDX_T.

Definition at line 37 of file GEO_PointTree.h.

Member Typedef Documentation

template<typename IDX_T>

typedef UT_Array<IdxType> GEO_PointTreeT< IDX_T >::IdxArrayType

Definition at line 41 of file GEO_PointTree.h.

template<typename IDX_T>

typedef IDX_T GEO_PointTreeT< IDX_T >::IdxType

Definition at line 40 of file GEO_PointTree.h.

Constructor & Destructor Documentation

template<typename IDX_T >

GEO_PointTreeT< IDX_T >::GEO_PointTreeT ( )

Definition at line 319 of file GEO_PointTree.h.

template<typename IDX_T >

GEO_PointTreeT< IDX_T >::~GEO_PointTreeT ( )

override

Definition at line 328 of file GEO_PointTree.h.

Member Function Documentation

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::append	(	const UT_Vector3 &	pt,
		IdxType	idx,
		bool	auto_rebalance = `false`
	)

This will slowly build the tree in place. Balancing isn't done until the next lookup. Thus, it can provide a nicer way to initialize a tree. When auto_rebalance is true, the tree may choose not to rebalance on the next lookup, and will rebalance after a sufficient number of points have been added. This can be useful in cases where lookups and appends are interleaved. When it is false, the tree will be rebalanced on the next query.

Definition at line 386 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::append ( const UT_Vector3 & pt )

This will slowly build the tree in place. Balancing isn't done until the next lookup. Thus, it can provide a nicer way to initialize a tree. When auto_rebalance is true, the tree may choose not to rebalance on the next lookup, and will rebalance after a sufficient number of points have been added. This can be useful in cases where lookups and appends are interleaved. When it is false, the tree will be rebalanced on the next query.

Definition at line 413 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::appendPtRadius	(	const UT_Vector3 &	pt,
		fpreal	radius,
		IdxType	idx,
		bool	auto_rebalance = `false`
	)

This builds a tree which has a per point radius. Note that this does not work with the tube testing code. Note that there is a large performance penalty for the findNearest methods, but no real penalty for the findAllClose methods If any points are added in radius mode, ALL must be added in radius mode. NOTE: If the tree is queried or built with zero entries, it will be stuck with non-radius mode. So if you are using the auto_rebalance, make sure the first point is not auto_rebalance and you call buildIfNeeded() after adding it.

Definition at line 420 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::appendPtRadius	(	const UT_Vector3 &	pt,
		fpreal	radius
	)

This builds a tree which has a per point radius. Note that this does not work with the tube testing code. Note that there is a large performance penalty for the findNearest methods, but no real penalty for the findAllClose methods If any points are added in radius mode, ALL must be added in radius mode. NOTE: If the tree is queried or built with zero entries, it will be stuck with non-radius mode. So if you are using the auto_rebalance, make sure the first point is not auto_rebalance and you call buildIfNeeded() after adding it.

Definition at line 442 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::build	(	const UT_Vector3Array &	pts,
		bool	enable_multithreading = `true`
	)

Rebuilds the point tree as a pure index based tree using the given vectors.

Definition at line 335 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::build	(	const UT_Vector3Array &	pts,
		const IdxArrayType &	idx,
		bool	enable_multithreading = `true`
	)

Rebuilds the point tree as a pure index based tree using the given vector/index lookup.

Definition at line 361 of file GEO_PointTree.h.

template<typename IDX_T>

void GEO_PointTreeT< IDX_T >::buildIfNeeded ( bool enable_multithreading = true )

inlineoverridevirtual

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

Reimplemented from UT_KDTree.

Definition at line 178 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::clear ( )

virtual

Clears out the tree, leaving it with no entries.

Definition at line 642 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::clearPointTransform ( )

protected

Clears the myPointTransform member data.

Definition at line 677 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::comparePosition	(	int	idx0,
		int	idx1,
		int	dim
	)		const

overrideprotectedvirtual

These are used by KDTree:

Implements UT_KDTree.

Definition at line 715 of file GEO_PointTree.h.

template<typename IDX_T>

void GEO_PointTreeT< IDX_T >::dirtyKDTree ( )

inlineprotected

Marks the kd tree as out of date.

Definition at line 216 of file GEO_PointTree.h.

template<typename IDX_T>

void GEO_PointTreeT< IDX_T >::ensureTreeBuilt ( )

inline

Ensures the KD tree has been fully built. If a KD tree is being shared among multiple threads, it is important it has first been compiled on one thread to avoid race conditions (GEO_PointTree is thread safe on read provided it has been built and provided no new points are added to it)

Definition at line 175 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::entries ( ) const

Returns the number of actual points in the tree.

Definition at line 656 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::findAllCloseIdx	(	const UT_Vector3 &	pt,
		fpreal	maxdist,
		IdxArrayType &	list
	)

Finds all the points within the given radius of a point. The resulting points will not be sorted.

Definition at line 574 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::findAllCloseIdxQueue	(	const UT_Vector3 &	pt,
		ut_KDPQueue &	queue,
		fpreal	maxdist,
		IdxArrayType &	list
	)

Creates a search queue useful for findAll queries.

Definition at line 596 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::findAllInTubeIdx	(	const UT_Vector3 &	pt,
		const UT_Vector3 &	dir,
		fpreal	radius,
		IdxArrayType &	list
	)

Find all of the points inside the given tube.

Definition at line 619 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::findNearestGroupIdx	(	const UT_Vector3 &	pt,
		fpreal	maxdist,
		int	groupsize,
		IdxArrayType &	group,
		UT_FloatArray &	groupdist
	)

Find the nearest [groupsize] points not more than maxdist away. Returns the number of points found. Found points will be stored in the group array.

The resulting points will be sorted by their distance.

Definition at line 509 of file GEO_PointTree.h.

template<typename IDX_T >

int GEO_PointTreeT< IDX_T >::findNearestGroupIdxQueue	(	const UT_Vector3 &	pt,
		fpreal	maxdist,
		int	groupsize,
		IdxArrayType &	group,
		UT_FloatArray &	groupdist,
		ut_KDPQueue &	q,
		bool	wrapunitcube = `false`
	)

This uses a pre-built queue to reduce memory allocation.

Definition at line 536 of file GEO_PointTree.h.

template<typename IDX_T >

IDX_T GEO_PointTreeT< IDX_T >::findNearestIdx ( const UT_Vector3 & pt )

Finds the nearest index to the given value. Returns -1 on no such point.

Definition at line 449 of file GEO_PointTree.h.

template<typename IDX_T >

IDX_T GEO_PointTreeT< IDX_T >::findNearestIdx	(	const UT_Vector3 &	pt,
		fpreal	maxdist
	)

Finds the nearest index to the given value. Returns -1 on no such point. The point must be within the given range. NOTE: findNearestPt() will fail if it has not been built with a gdp

Definition at line 466 of file GEO_PointTree.h.

template<typename IDX_T >

IDX_T GEO_PointTreeT< IDX_T >::findNearestIdxQueue	(	const UT_Vector3 &	pt,
		ut_KDPQueue &	q,
		fpreal	maxdist = `1e18f`,
		bool	wrapunitcube = `false`
	)

This uses a pre-built queue to reduce memory allocation.

Definition at line 482 of file GEO_PointTree.h.

template<typename IDX_T >

int64 GEO_PointTreeT< IDX_T >::getMemoryUsage ( bool inclusive = true ) const

virtual

Returns the amount of memory used by this tree.

Definition at line 663 of file GEO_PointTree.h.

template<typename IDX_T >

const float * GEO_PointTreeT< IDX_T >::getP ( int idx ) const

overrideprotectedvirtual

Return the position associated with the given point.

Implements UT_KDTree.

Definition at line 728 of file GEO_PointTree.h.

template<typename IDX_T >

fpreal GEO_PointTreeT< IDX_T >::getRadius ( int ) const

overrideprotectedvirtual

Return the radius associated with the point in question.

Reimplemented from UT_KDTree.

Definition at line 745 of file GEO_PointTree.h.

template<typename IDX_T >

bool GEO_PointTreeT< IDX_T >::pointsHaveRadius ( ) const

overrideprotectedvirtual

These are used if the user adds points with radii.

Reimplemented from UT_KDTree.

Definition at line 735 of file GEO_PointTree.h.

template<typename IDX_T>

void GEO_PointTreeT< IDX_T >::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 191 of file GEO_PointTree.h.

template<typename IDX_T>

void GEO_PointTreeT< IDX_T >::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 196 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::setPointTransform ( const UT_DMatrix4 & xform )

Sets the myPointTransform member so that we can build our tree from a piece of geometry with an implicit transform on it.

Definition at line 685 of file GEO_PointTree.h.

template<typename IDX_T >

void GEO_PointTreeT< IDX_T >::updateKDTree ( bool enablemultithread = true )

protected

Should be called prior to any invocation of KD Tree methods as it ensures the KDTree knows about the current number of entries.

Definition at line 694 of file GEO_PointTree.h.

Member Data Documentation

template<typename IDX_T>

IdxArrayType GEO_PointTreeT< IDX_T >::myIndexList

protected

This is the mapping from the KD entries into the GDP numbers.

Definition at line 227 of file GEO_PointTree.h.

template<typename IDX_T>

bool GEO_PointTreeT< IDX_T >::myIsKDTreeDirty

protected

Tracks if the underlying KDtree has knowledge of our current size.

Definition at line 237 of file GEO_PointTree.h.

template<typename IDX_T>

UT_Vector3Array GEO_PointTreeT< IDX_T >::myPointList

protected

The list of all the points.

Definition at line 230 of file GEO_PointTree.h.

template<typename IDX_T>

UT_DMatrix4* GEO_PointTreeT< IDX_T >::myPointTransform

protected

If this pointer is set, then before adding any GEO_Points to our point list, we transform their position with this matrix.

Definition at line 224 of file GEO_PointTree.h.

template<typename IDX_T>

UT_FloatArray GEO_PointTreeT< IDX_T >::myRadii

protected

List of radii for each pont.

Definition at line 233 of file GEO_PointTree.h.

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

GEO/GEO_PointTree.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

template<typename IDX_T> class GEO_PointTreeT< IDX_T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename IDX_T>
class GEO_PointTreeT< IDX_T >