GEO_PointTree Class Reference

#include <GEO_PointTree.h>

Inheritance diagram for GEO_PointTree:

List of all members.

Public Member Functions

GEO_PointTree ()

virtual ~GEO_PointTree ()

void build (const GEO_Detail *gdp, const GB_PointGroup *ptgroup)

void build (const GEO_Detail *gdp, const UT_PtrArray< GEO_Point * > &ptlist)

void build (const UT_Vector3Array &pts)

void build (const UT_Vector3Array &pts, const UT_IntArray &idx)

void append (const GEO_Detail *gdp, const GEO_Point *pt, bool auto_rebalance=false)

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

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

void appendPtRadius (const GEO_Detail *gdp, const GEO_Point *pt, fpreal radius)

void appendPtRadius (const UT_Vector3 &pt, fpreal radius, int idx)

void appendPtRadius (const UT_Vector3 &pt, fpreal radius)

void harden ()

void soften (const GEO_Detail *gdp)

void clear ()

Clears out the tree, leaving it with no entries and no bound gdp.

int entries () const

Returns the number of actual points in the tree.

int64 getMemoryUsage () const

Returns the amount of memory used by this tree.

void setValidCallback (UT_PointTreeValidNearestFunc, void *user_data)

GEO_Point * findNearestPt (const UT_Vector3 &pt)

int findNearestIdx (const UT_Vector3 &pt)

GEO_Point * findNearestPt (const UT_Vector3 &pt, fpreal maxdist)

int findNearestIdx (const UT_Vector3 &pt, fpreal maxdist)

ut_KDPQueue * createFindNearestQueue (fpreal maxdist=1e18f) const

GEO_Point * findNearestPtQueue (const UT_Vector3 &pt, ut_KDPQueue &q)

int findNearestIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &q)

int findNearestGroupPt (const UT_Vector3 &pt, fpreal maxdist, int groupsize, UT_PtrArray< GEO_Point * > &group, UT_FloatArray &groupdist)

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

int findAllClosePt (const UT_Vector3 &pt, float maxdist, UT_PtrArray< GEO_Point * > &list)

int findAllCloseIdx (const UT_Vector3 &pt, float maxdist, UT_IntArray &list)

ut_KDPQueue * createFindAllQueue (fpreal maxdist) const

int findAllCloseIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &queue, UT_IntArray &list)

int findAllInTubePt (const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal radius, UT_PtrArray< GEO_Point * > &list)

int findAllInTubeIdx (const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal radius, UT_IntArray &list)

GEO_Point * convertIdxToPoint (int idx) const

void setPointTransform (const UT_DMatrix4 &xform)

void ensureTreeBuilt ()

Protected Member Functions

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

These are used by KDTree:.

virtual const fpreal * getP (int idx) const

Return the position associated with the given point.

virtual bool isValid (int idx) const

Returns whether the given index should be considered in searches.

virtual bool pointsHaveRadius () const

These are used if the user adds points with radii.

virtual fpreal getRadius (int idx) const

Return the radius associated with the point in question.

void updateKDTree ()

void dirtyKDTree ()

Marks the kd tree as out of date.

void clearPointTransform ()

Clears the myPointTransform member data.

Protected Attributes

GEO_Detail * myGdp

This is the gdp we were built from. 0 if we are hardened.

UT_DMatrix4 * myPointTransform

UT_IntArray myIndexList

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

UT_Vector3Array myPointList

The list of all the points.

UT_FloatArray myRadii

List of radii for each pont.

bool myIsKDTreeDirty

UT_PointTreeValidNearestFunc myValidNearestFunc

This tracks the callback for the valid nearest function.

void * myValidNearestData

Detailed Description

Definition at line 34 of file GEO_PointTree.h.

Constructor & Destructor Documentation

GEO_PointTree::GEO_PointTree ( )

virtual GEO_PointTree::~GEO_PointTree ( ) [virtual]

Member Function Documentation

void GEO_PointTree::append	(	const UT_Vector3 &	pt,
		bool	auto_rebalance = `false`
	)

void GEO_PointTree::append	(	const UT_Vector3 &	pt,
		int	idx,
		bool	auto_rebalance = `false`
	)

void GEO_PointTree::append	(	const GEO_Detail *	gdp,
		const GEO_Point *	pt,
		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.

void GEO_PointTree::appendPtRadius	(	const UT_Vector3 &	pt,
		fpreal	radius
	)

void GEO_PointTree::appendPtRadius	(	const UT_Vector3 &	pt,
		fpreal	radius,
		int	idx
	)

void GEO_PointTree::appendPtRadius	(	const GEO_Detail *	gdp,
		const GEO_Point *	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.

void GEO_PointTree::build	(	const UT_Vector3Array &	pts,
		const UT_IntArray &	idx
	)

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

void GEO_PointTree::build ( const UT_Vector3Array & pts )

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

void GEO_PointTree::build	(	const GEO_Detail *	gdp,
		const UT_PtrArray< GEO_Point * > &	ptlist
	)

Rebuilds the PointTree given a list of GEO_Points. It will make its own internal vector3 array of the points and original indices.

void GEO_PointTree::build	(	const GEO_Detail *	gdp,
		const GB_PointGroup *	ptgroup
	)

Rebuilds the PointTree with the given detail and values. It will make its own internal vector3 array of the points and original indices.

void GEO_PointTree::clear ( )

Clears out the tree, leaving it with no entries and no bound gdp.

void GEO_PointTree::clearPointTransform ( ) [protected]

Clears the myPointTransform member data.

virtual int GEO_PointTree::comparePosition	(	int	idx0,
		int	idx1,
		int	dim
	)			const `[protected, virtual]`

These are used by KDTree:.

Implements UT_KDTree.

GEO_Point* GEO_PointTree::convertIdxToPoint ( int idx ) const

Takes an index and returns the corresponding point. Only valid if it was built with a gdp and harden() has not been called. Otherwise, it will always return NULL.

ut_KDPQueue* GEO_PointTree::createFindAllQueue ( fpreal maxdist ) const

Creates a search queue useful for findAll queries. You must destroy it with UT_KDTree::destroyQueue(q) when done.

ut_KDPQueue* GEO_PointTree::createFindNearestQueue ( fpreal maxdist = 1e18f ) const

These use a pre-built queue to reduce memory allocation You must call UT_KDTree::destroyQueue() when you are done with the queue.

void GEO_PointTree::dirtyKDTree ( ) [inline, protected]

Marks the kd tree as out of date.

Definition at line 207 of file GEO_PointTree.h.

void GEO_PointTree::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 188 of file GEO_PointTree.h.

int GEO_PointTree::entries ( ) const

Returns the number of actual points in the tree.

int GEO_PointTree::findAllCloseIdx	(	const UT_Vector3 &	pt,
		float	maxdist,
		UT_IntArray &	list
	)

int GEO_PointTree::findAllCloseIdxQueue	(	const UT_Vector3 &	pt,
		ut_KDPQueue &	queue,
		UT_IntArray &	list
	)

int GEO_PointTree::findAllClosePt	(	const UT_Vector3 &	pt,
		float	maxdist,
		UT_PtrArray< GEO_Point * > &	list
	)

Finds all the points within the given radius of a point. The resulting points will *not* be sorted. NOTE: findAllClosePt() will fail if it has not been built with a gdp

int GEO_PointTree::findAllInTubeIdx	(	const UT_Vector3 &	orig,
		const UT_Vector3 &	dir,
		fpreal	radius,
		UT_IntArray &	list
	)

int GEO_PointTree::findAllInTubePt	(	const UT_Vector3 &	orig,
		const UT_Vector3 &	dir,
		fpreal	radius,
		UT_PtrArray< GEO_Point * > &	list
	)

Find all of the points inside the given tube. NOTE: findAllInTubePt() will fail if it has not been built with a gdp

int GEO_PointTree::findNearestGroupIdx	(	const UT_Vector3 &	pt,
		fpreal	maxdist,
		int	groupsize,
		UT_IntArray &	group,
		UT_FloatArray &	groupdist
	)

int GEO_PointTree::findNearestGroupPt	(	const UT_Vector3 &	pt,
		fpreal	maxdist,
		int	groupsize,
		UT_PtrArray< GEO_Point * > &	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. NOTE: findNearestGroupPt() will fail if it has not been built with a gdp

int GEO_PointTree::findNearestIdx	(	const UT_Vector3 &	pt,
		fpreal	maxdist
	)

int GEO_PointTree::findNearestIdx ( const UT_Vector3 & pt )

int GEO_PointTree::findNearestIdxQueue	(	const UT_Vector3 &	pt,
		ut_KDPQueue &	q
	)

GEO_Point* GEO_PointTree::findNearestPt	(	const UT_Vector3 &	pt,
		fpreal	maxdist
	)

Finds the nearest point or index to the given value. Returns 0 or -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

GEO_Point* GEO_PointTree::findNearestPt ( const UT_Vector3 & pt )

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

GEO_Point* GEO_PointTree::findNearestPtQueue	(	const UT_Vector3 &	pt,
		ut_KDPQueue &	q
	)

int64 GEO_PointTree::getMemoryUsage ( ) const

Returns the amount of memory used by this tree.

virtual const fpreal* GEO_PointTree::getP ( int idx ) const [protected, virtual]

Return the position associated with the given point.

Implements UT_KDTree.

virtual fpreal GEO_PointTree::getRadius ( int ) const [protected, virtual]

Return the radius associated with the point in question.

Reimplemented from UT_KDTree.

void GEO_PointTree::harden ( )

This makes the tree hard. This makes any attempt to do a GEO_Point look up illegal - one must instead fetch by index.

virtual bool GEO_PointTree::isValid ( int ) const [protected, virtual]

Returns whether the given index should be considered in searches.

Reimplemented from UT_KDTree.

virtual bool GEO_PointTree::pointsHaveRadius ( ) const [protected, virtual]

These are used if the user adds points with radii.

Reimplemented from UT_KDTree.

void GEO_PointTree::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.

void GEO_PointTree::setValidCallback	(	UT_PointTreeValidNearestFunc	,
		void *	user_data
	)

This sets the valid function method. This call back will be called for each point to see if it should be included in the search. This only works for non-hard trees!

void GEO_PointTree::soften ( const GEO_Detail * gdp )

This makes the tree soft. The given GEO_Detail becomes the relevant GEO_Detail for all look ups involving GEO_Points.

void GEO_PointTree::updateKDTree ( ) [protected]

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

Member Data Documentation

GEO_Detail* GEO_PointTree::myGdp [protected]

This is the gdp we were built from. 0 if we are hardened.

Definition at line 214 of file GEO_PointTree.h.

UT_IntArray GEO_PointTree::myIndexList [protected]

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

Definition at line 221 of file GEO_PointTree.h.

bool GEO_PointTree::myIsKDTreeDirty [protected]

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

Definition at line 231 of file GEO_PointTree.h.

UT_Vector3Array GEO_PointTree::myPointList [protected]

The list of all the points.

Definition at line 224 of file GEO_PointTree.h.

UT_DMatrix4* GEO_PointTree::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 218 of file GEO_PointTree.h.

UT_FloatArray GEO_PointTree::myRadii [protected]

List of radii for each pont.

Definition at line 227 of file GEO_PointTree.h.

void* GEO_PointTree::myValidNearestData [protected]

Definition at line 235 of file GEO_PointTree.h.

UT_PointTreeValidNearestFunc GEO_PointTree::myValidNearestFunc [protected]

This tracks the callback for the valid nearest function.

Definition at line 234 of file GEO_PointTree.h.

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

GEO/GEO_PointTree.h


Public Member Functions
	GEO_PointTree ()
virtual	~GEO_PointTree ()
void	build (const GEO_Detail gdp, const GB_PointGroup ptgroup)
void	build (const GEO_Detail gdp, const UT_PtrArray< GEO_Point > &ptlist)
void	build (const UT_Vector3Array &pts)
void	build (const UT_Vector3Array &pts, const UT_IntArray &idx)
void	append (const GEO_Detail gdp, const GEO_Point pt, bool auto_rebalance=false)
void	append (const UT_Vector3 &pt, int idx, bool auto_rebalance=false)
void	append (const UT_Vector3 &pt, bool auto_rebalance=false)
void	appendPtRadius (const GEO_Detail gdp, const GEO_Point pt, fpreal radius)
void	appendPtRadius (const UT_Vector3 &pt, fpreal radius, int idx)
void	appendPtRadius (const UT_Vector3 &pt, fpreal radius)
void	harden ()
void	soften (const GEO_Detail *gdp)
void	clear ()
	Clears out the tree, leaving it with no entries and no bound gdp.
int	entries () const
	Returns the number of actual points in the tree.
int64	getMemoryUsage () const
	Returns the amount of memory used by this tree.
void	setValidCallback (UT_PointTreeValidNearestFunc, void *user_data)
GEO_Point *	findNearestPt (const UT_Vector3 &pt)
int	findNearestIdx (const UT_Vector3 &pt)
GEO_Point *	findNearestPt (const UT_Vector3 &pt, fpreal maxdist)
int	findNearestIdx (const UT_Vector3 &pt, fpreal maxdist)
ut_KDPQueue *	createFindNearestQueue (fpreal maxdist=1e18f) const
GEO_Point *	findNearestPtQueue (const UT_Vector3 &pt, ut_KDPQueue &q)
int	findNearestIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &q)
int	findNearestGroupPt (const UT_Vector3 &pt, fpreal maxdist, int groupsize, UT_PtrArray< GEO_Point * > &group, UT_FloatArray &groupdist)
int	findNearestGroupIdx (const UT_Vector3 &pt, fpreal maxdist, int groupsize, UT_IntArray &group, UT_FloatArray &groupdist)
int	findAllClosePt (const UT_Vector3 &pt, float maxdist, UT_PtrArray< GEO_Point * > &list)
int	findAllCloseIdx (const UT_Vector3 &pt, float maxdist, UT_IntArray &list)
ut_KDPQueue *	createFindAllQueue (fpreal maxdist) const
int	findAllCloseIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &queue, UT_IntArray &list)
int	findAllInTubePt (const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal radius, UT_PtrArray< GEO_Point * > &list)
int	findAllInTubeIdx (const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal radius, UT_IntArray &list)
GEO_Point *	convertIdxToPoint (int idx) const
void	setPointTransform (const UT_DMatrix4 &xform)
void	ensureTreeBuilt ()
Protected Member Functions
virtual int	comparePosition (int idx0, int idx1, int dim) const
	These are used by KDTree:.
virtual const fpreal *	getP (int idx) const
	Return the position associated with the given point.
virtual bool	isValid (int idx) const
	Returns whether the given index should be considered in searches.
virtual bool	pointsHaveRadius () const
	These are used if the user adds points with radii.
virtual fpreal	getRadius (int idx) const
	Return the radius associated with the point in question.
void	updateKDTree ()
void	dirtyKDTree ()
	Marks the kd tree as out of date.
void	clearPointTransform ()
	Clears the myPointTransform member data.
Protected Attributes
GEO_Detail *	myGdp
	This is the gdp we were built from. 0 if we are hardened.
UT_DMatrix4 *	myPointTransform
UT_IntArray	myIndexList
	This is the mapping from the KD entries into the GDP numbers.
UT_Vector3Array	myPointList
	The list of all the points.
UT_FloatArray	myRadii
	List of radii for each pont.
bool	myIsKDTreeDirty
UT_PointTreeValidNearestFunc	myValidNearestFunc
	This tracks the callback for the valid nearest function.
void *	myValidNearestData