IECore::BoundedKDTree< BoundIterator > Class Template Reference

Builds a KDTree of bounded volumes to permit fast intersection/overlap tests. More...

#include <BoundedKDTree.h>

List of all members.

Classes
class	Node
Public Types
typedef BoundIterator	Iterator
typedef std::iterator_traits < BoundIterator >::value_type	Bound
typedef BoxTraits< Bound > ::BaseType	BaseType
typedef std::vector< Node >	NodeVector
typedef NodeVector::size_type	NodeIndex
Public Member Functions
	BoundedKDTree ()
	BoundedKDTree (BoundIterator first, BoundIterator last, int maxLeafSize=4)
void	init (BoundIterator first, BoundIterator last, int maxLeafSize=4)
template<typename S >
unsigned int	intersectingBounds (const S &b, std::vector< BoundIterator > &bounds) const
NodeIndex	numNodes () const
	Returns the number of nodes in the tree.
const Node &	node (NodeIndex idx) const
	Retrieve the node associated with a given index.
NodeIndex	rootIndex () const
	Returns the index for the root node.
Static Public Member Functions
static NodeIndex	lowChildIndex (NodeIndex index)
	Retrieve the index of the "low" child node.
static NodeIndex	highChildIndex (NodeIndex index)
	Retrieve the index of the "high" child node.

---

Detailed Description

template<class BoundIterator>
class IECore::BoundedKDTree< BoundIterator >

Builds a KDTree of bounded volumes to permit fast intersection/overlap tests.

---

Member Typedef Documentation

template<class BoundIterator>

typedef BoxTraits<Bound>::BaseType IECore::BoundedKDTree< BoundIterator >::BaseType

template<class BoundIterator>

typedef std::iterator_traits<BoundIterator>::value_type IECore::BoundedKDTree< BoundIterator >::Bound

template<class BoundIterator>

typedef BoundIterator IECore::BoundedKDTree< BoundIterator >::Iterator

template<class BoundIterator>

typedef NodeVector::size_type IECore::BoundedKDTree< BoundIterator >::NodeIndex

template<class BoundIterator>

typedef std::vector<Node> IECore::BoundedKDTree< BoundIterator >::NodeVector

---

Constructor & Destructor Documentation

template<class BoundIterator>

IECore::BoundedKDTree< BoundIterator >::BoundedKDTree

(

)

Construncts an uninitialised tree - you must call init() before using it.

template<class BoundIterator>

IECore::BoundedKDTree< BoundIterator >::BoundedKDTree	(	BoundIterator	first,
		BoundIterator	last,
		int	maxLeafSize = 4
	)

Creates a tree for the fast searching of bounds. Note that the tree does not own the passed bounds - it is up to you to ensure that they remain valid and unchanged as long as the BoundedKDTree is in use.

---

Member Function Documentation

template<class BoundIterator>

static NodeIndex IECore::BoundedKDTree< BoundIterator >::highChildIndex

(

NodeIndex

index

)

[static]

Retrieve the index of the "high" child node.

Referenced by IECore::MeshPrimitiveEvaluator::intersectionPointsWalk(), IECore::MeshPrimitiveEvaluator::intersectionPointWalk(), and IECore::MeshPrimitiveEvaluator::pointAtUVWalk().

template<class BoundIterator>

void IECore::BoundedKDTree< BoundIterator >::init	(	BoundIterator	first,
		BoundIterator	last,
		int	maxLeafSize = 4
	)

Builds the tree for the specified bounds - the iterator range must remain valid and unchanged as long as the tree is in use. This method can be called again to rebuild the tree at any time.

Threading:

This can't be called while other threads are making queries.

template<class BoundIterator>

template<typename S >

unsigned int IECore::BoundedKDTree< BoundIterator >::intersectingBounds	(	const S &	b,
		std::vector< BoundIterator > &	bounds
	)			const [inline]

Populates the passed vector of iterators with the bounds which intersect "b". Returns the number of bounds found.

Threading:

May be called by multiple concurrent threads provided they each use a different vector for the result.

Todo:

There should be a form where nearNeighbours is an output iterator, to allow any container to be filled.

template<class BoundIterator>

static NodeIndex IECore::BoundedKDTree< BoundIterator >::lowChildIndex

(

NodeIndex

index

)

[static]

Retrieve the index of the "low" child node.

Referenced by IECore::MeshPrimitiveEvaluator::intersectionPointsWalk(), IECore::MeshPrimitiveEvaluator::intersectionPointWalk(), and IECore::MeshPrimitiveEvaluator::pointAtUVWalk().

template<class BoundIterator>

const Node& IECore::BoundedKDTree< BoundIterator >::node

(

NodeIndex

idx

)

const

Retrieve the node associated with a given index.

Referenced by IECore::MeshPrimitiveEvaluator::intersectionPointsWalk(), IECore::MeshPrimitiveEvaluator::intersectionPointWalk(), IECore::MeshPrimitiveEvaluator::pointAtUVWalk(), and IECore::MeshPrimitiveEvaluator::uvBound().

template<class BoundIterator>

NodeIndex IECore::BoundedKDTree< BoundIterator >::numNodes

(

)

const [inline]

Returns the number of nodes in the tree.

template<class BoundIterator>

NodeIndex IECore::BoundedKDTree< BoundIterator >::rootIndex

(

)

const

Returns the index for the root node.

Referenced by IECore::CurvesPrimitiveEvaluator::closestPoint(), IECore::MeshPrimitiveEvaluator::intersectionPoint(), IECore::MeshPrimitiveEvaluator::intersectionPoints(), IECore::MeshPrimitiveEvaluator::pointAtUV(), and IECore::MeshPrimitiveEvaluator::uvBound().

---

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

• include/IECore/BoundedKDTree.h