BV_OBBTree Class Reference

#include <BV_OBBTree.h>

Inheritance diagram for BV_OBBTree:

List of all members.

Classes

class bvLeaf

Public Types

typedef BV_Tree BaseClass

Public Member Functions

BV_OBBTree ()

BV_OBBTree (const BV_OBBTree &)

virtual ~BV_OBBTree ()

BV_OBBTree & operator= (const BV_OBBTree &)

virtual const char * getType () const

virtual const BV_Tree * castTo (const char *type) const

virtual BV_Tree * castTo (const char *type)

void buildLazy (BV_LeafIterator &leafIt)

void getRootOBB (UT_Matrix4 &xform, UT_Vector3 &radii) const

void setUseConvexHull (bool bValue)

bool getUseConvexHull (void)

Protected Member Functions

virtual BV_Tree * cloneSubclass () const

virtual int64 getMemoryUsageSubclass () const

virtual int getNumLeavesSubclass () const

virtual void buildSubclass (BV_LeafIterator &leafIt)

virtual void updateExtentsSubclass (BV_LeafIterator &leafIt)

virtual Status intersectSubclass (BV_Callback &callback, const BV_Tree &treeb, const UT_DMatrix4 &startxforma, const UT_DMatrix4 &startxformb, const UT_DMatrix4 &endxforma, const UT_DMatrix4 &endxformb, fpreal tol) const

WARNING: not thread-safe if tree was lazily built!

BV_OBB * getRoot ()

void buildInternal (BV_LeafIterator &leafIt, bool lazy)

BV_OBB * createTree (int startprim, int numleaves, const UT_Matrix3 &rootBasis, const UT_Vector3 &rootPos, int depth=-1)

void createChildren (BV_OBB &root, int depth=-1)

bool updateExtentsRecurse (BV_OBB &node, const UT_Matrix3 &parentBasis, const UT_Vector3 &parentPos)

void getBounds (const UT_Matrix3 &basis, UT_BoundingBox &bbox, bool &firstPrim)

void calcOBB (BV_OBB &node)

void calcSize (BV_OBB &node)

bool computeConvexHull (const TPointArray &source_points_in, TSimpleTriangleArray &final_triangles_out)

bool doConvexHullIteration (BV_CHDataManager &data_manager, TTriArray &working_triangles)

bool intersectRecurse (BV_Callback &callback, const BV_OBBTree &treeb, const BV_OBB &a, const BV_OBB &b, const bvTransform &t1, const bvTransform &t2, const bvTransform &t3, const bvTransform &t4, fpreal tol, int identities) const

void calculateSortKeys (bvLeaf *prims, int numleaves, UT_Matrix3 &basis, int axis) const

virtual void saveSubclass (ostream &os, bool onlyStructure) const

Saving and loading only works for non-lazy building.

virtual bool loadSubclass (UT_IStream &is, bool onlyStructure)

Saving and loading only works for non-lazy building.

Static Protected Member Functions

static int compareLeaves (const void *t1, const void *t2)

Protected Attributes

BV_OBB * myRoot

UT_RefArray< bvLeaf > myLeaves

BV_LeafIterator * myLeafIt

bool myUseConvexHullForBBoxes

Detailed Description

Bounding volume hierarchy based on Oriented Bounding Boxes (OBBs).

Build: O(n^2) Update extents: O(n^2)

Source: Gottschalk, Lin and Manocha, "OBB-Tree: A Hierarchical Structure for Rapid Interference Detection," Proceedings of ACM SIGGRAPH 1996, pages 171-180. ACM Press, 1996. ftp://ftp.cs.unc.edu/pub/users/gottscha/obbt.ps.gz

Definition at line 273 of file BV_OBBTree.h.

Member Typedef Documentation

typedef BV_Tree BV_OBBTree::BaseClass

Reimplemented in GU_OBBTree.

Definition at line 276 of file BV_OBBTree.h.

Constructor & Destructor Documentation

BV_OBBTree::BV_OBBTree ( )

BV_OBBTree::BV_OBBTree ( const BV_OBBTree & )

virtual BV_OBBTree::~BV_OBBTree ( ) [virtual]

Member Function Documentation

void BV_OBBTree::buildInternal	(	BV_LeafIterator &	leafIt,
		bool	lazy
	)			`[protected]`

void BV_OBBTree::buildLazy ( BV_LeafIterator & leafIt ) [inline]

Alternative lazy building: sections of the tree are only built when a query needs them. In this case, the leaf iterator *must* not be destroyed until the tree is destroyed, or until a fresh call to buildLazy.

Definition at line 293 of file BV_OBBTree.h.

virtual void BV_OBBTree::buildSubclass ( BV_LeafIterator & leafIt ) [inline, protected, virtual]

Implements BV_Tree.

Definition at line 329 of file BV_OBBTree.h.

void BV_OBBTree::calcOBB ( BV_OBB & node ) [protected]

Calculate the OBB associated with the given node. Stores orientation in node->myRot, and calls calcSize to calculate the extents. May disable the node if it contains no enabled leaves.

void BV_OBBTree::calcSize ( BV_OBB & node ) [protected]

Given the input OBB orientation, calculate the OBB extents. Stores extents (radii) and position in node.

void BV_OBBTree::calculateSortKeys	(	bvLeaf *	prims,
		int	numleaves,
		UT_Matrix3 &	basis,
		int	axis
	)			const `[protected]`

virtual BV_Tree* BV_OBBTree::castTo ( const char * type ) [virtual]

Reimplemented from BV_Tree.

virtual const BV_Tree* BV_OBBTree::castTo ( const char * type ) const [virtual]

Reimplemented from BV_Tree.

virtual BV_Tree* BV_OBBTree::cloneSubclass ( ) const [protected, virtual]

Implements BV_Tree.

static int BV_OBBTree::compareLeaves	(	const void *	t1,
		const void *	t2
	)			`[static, protected]`

bool BV_OBBTree::computeConvexHull	(	const TPointArray &	source_points_in,
		TSimpleTriangleArray &	final_triangles_out
	)			`[protected]`

Compute a convex hull around the points provided, output result as a series of triangles to the array provided. This is currently slower than it should be. Also, note that if coplanar points are present, the convex hull constructed might be around jiggled versions of those points.

void BV_OBBTree::createChildren	(	BV_OBB &	root,
		int	depth = `-1`
	)			`[protected]`

BV_OBB* BV_OBBTree::createTree	(	int	startprim,
		int	numleaves,
		const UT_Matrix3 &	rootBasis,
		const UT_Vector3 &	rootPos,
		int	depth = `-1`
	)			`[protected]`

Build the tree. If depth is non-negative, the algorithm is lazy and stops after depth levels.

bool BV_OBBTree::doConvexHullIteration	(	BV_CHDataManager &	data_manager,
		TTriArray &	working_triangles
	)			`[protected]`

void BV_OBBTree::getBounds	(	const UT_Matrix3 &	basis,
		UT_BoundingBox &	bbox,
		bool &	firstPrim
	)			`[protected]`

virtual int64 BV_OBBTree::getMemoryUsageSubclass ( ) const [protected, virtual]

Implements BV_Tree.

virtual int BV_OBBTree::getNumLeavesSubclass ( ) const [protected, virtual]

Implements BV_Tree.

BV_OBB* BV_OBBTree::getRoot ( ) [inline, protected]

Definition at line 343 of file BV_OBBTree.h.

void BV_OBBTree::getRootOBB	(	UT_Matrix4 &	xform,
		UT_Vector3 &	radii
	)			const

virtual const char* BV_OBBTree::getType ( ) const [virtual]

Implements BV_Tree.

bool BV_OBBTree::getUseConvexHull ( void )

bool BV_OBBTree::intersectRecurse	(	BV_Callback &	callback,
		const BV_OBBTree &	treeb,
		const BV_OBB &	a,
		const BV_OBB &	b,
		const bvTransform &	t1,
		const bvTransform &	t2,
		const bvTransform &	t3,
		const bvTransform &	t4,
		fpreal	tol,
		int	identities
	)			const `[protected]`

virtual Status BV_OBBTree::intersectSubclass	(	BV_Callback &	callback,
		const BV_Tree &	treeb,
		const UT_DMatrix4 &	startxforma,
		const UT_DMatrix4 &	startxformb,
		const UT_DMatrix4 &	endxforma,
		const UT_DMatrix4 &	endxformb,
		fpreal	tol
	)			const `[protected, virtual]`

WARNING: not thread-safe if tree was lazily built!

Implements BV_Tree.

virtual bool BV_OBBTree::loadSubclass	(	UT_IStream &	is,
		bool	onlyStructure
	)			`[protected, virtual]`

Saving and loading only works for non-lazy building.

Implements BV_Tree.

BV_OBBTree& BV_OBBTree::operator= ( const BV_OBBTree & )

virtual void BV_OBBTree::saveSubclass	(	ostream &	os,
		bool	onlyStructure
	)			const `[protected, virtual]`

Saving and loading only works for non-lazy building.

Implements BV_Tree.

void BV_OBBTree::setUseConvexHull ( bool bValue )

If true, a somewhat different version of the algorithm is used to compute OBBs around nodes, which uses a convex hull around the points instead of the points themselves. While slower, it results in a consistent bbox that is not influenced by the density/inner points on the mesh. False by default.

bool BV_OBBTree::updateExtentsRecurse	(	BV_OBB &	node,
		const UT_Matrix3 &	parentBasis,
		const UT_Vector3 &	parentPos
	)			`[protected]`

virtual void BV_OBBTree::updateExtentsSubclass ( BV_LeafIterator & leafIt ) [protected, virtual]

Implements BV_Tree.

Member Data Documentation

BV_LeafIterator* BV_OBBTree::myLeafIt [protected]

Definition at line 390 of file BV_OBBTree.h.

UT_RefArray<bvLeaf> BV_OBBTree::myLeaves [protected]

Definition at line 389 of file BV_OBBTree.h.

BV_OBB* BV_OBBTree::myRoot [protected]

Definition at line 388 of file BV_OBBTree.h.

bool BV_OBBTree::myUseConvexHullForBBoxes [protected]

Definition at line 392 of file BV_OBBTree.h.

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

BV/BV_OBBTree.h


Classes
class	bvLeaf
Public Types
typedef BV_Tree	BaseClass
Public Member Functions
	BV_OBBTree ()
	BV_OBBTree (const BV_OBBTree &)
virtual	~BV_OBBTree ()
BV_OBBTree &	operator= (const BV_OBBTree &)
virtual const char *	getType () const
virtual const BV_Tree *	castTo (const char *type) const
virtual BV_Tree *	castTo (const char *type)
void	buildLazy (BV_LeafIterator &leafIt)
void	getRootOBB (UT_Matrix4 &xform, UT_Vector3 &radii) const
void	setUseConvexHull (bool bValue)
bool	getUseConvexHull (void)
Protected Member Functions
virtual BV_Tree *	cloneSubclass () const
virtual int64	getMemoryUsageSubclass () const
virtual int	getNumLeavesSubclass () const
virtual void	buildSubclass (BV_LeafIterator &leafIt)
virtual void	updateExtentsSubclass (BV_LeafIterator &leafIt)
virtual Status	intersectSubclass (BV_Callback &callback, const BV_Tree &treeb, const UT_DMatrix4 &startxforma, const UT_DMatrix4 &startxformb, const UT_DMatrix4 &endxforma, const UT_DMatrix4 &endxformb, fpreal tol) const
	WARNING: not thread-safe if tree was lazily built!
BV_OBB *	getRoot ()
void	buildInternal (BV_LeafIterator &leafIt, bool lazy)
BV_OBB *	createTree (int startprim, int numleaves, const UT_Matrix3 &rootBasis, const UT_Vector3 &rootPos, int depth=-1)
void	createChildren (BV_OBB &root, int depth=-1)
bool	updateExtentsRecurse (BV_OBB &node, const UT_Matrix3 &parentBasis, const UT_Vector3 &parentPos)
void	getBounds (const UT_Matrix3 &basis, UT_BoundingBox &bbox, bool &firstPrim)
void	calcOBB (BV_OBB &node)
void	calcSize (BV_OBB &node)
bool	computeConvexHull (const TPointArray &source_points_in, TSimpleTriangleArray &final_triangles_out)
bool	doConvexHullIteration (BV_CHDataManager &data_manager, TTriArray &working_triangles)
bool	intersectRecurse (BV_Callback &callback, const BV_OBBTree &treeb, const BV_OBB &a, const BV_OBB &b, const bvTransform &t1, const bvTransform &t2, const bvTransform &t3, const bvTransform &t4, fpreal tol, int identities) const
void	calculateSortKeys (bvLeaf *prims, int numleaves, UT_Matrix3 &basis, int axis) const

virtual void	saveSubclass (ostream &os, bool onlyStructure) const
	Saving and loading only works for non-lazy building.
virtual bool	loadSubclass (UT_IStream &is, bool onlyStructure)
	Saving and loading only works for non-lazy building.
Static Protected Member Functions
static int	compareLeaves (const void t1, const void t2)
Protected Attributes
BV_OBB *	myRoot
UT_RefArray< bvLeaf >	myLeaves
BV_LeafIterator *	myLeafIt
bool	myUseConvexHullForBBoxes