#include <btDbvt.h>

Classes
struct	IClone
struct	ICollide
struct	IWriter
struct	sStkCLN
struct	sStkNN
struct	sStkNP
struct	sStkNPS
Public Types
enum	{ SIMPLE_STACKSIZE = 64, DOUBLE_STACKSIZE = SIMPLE_STACKSIZE*2 }
Public Member Functions
	btDbvt ()
	~btDbvt ()
void	clear ()
bool	empty () const
void	optimizeBottomUp ()
void	optimizeTopDown (int bu_treshold=128)
void	optimizeIncremental (int passes)
btDbvtNode *	insert (const btDbvtVolume &box, void *data)
void	update (btDbvtNode *leaf, int lookahead=-1)
void	update (btDbvtNode *leaf, btDbvtVolume &volume)
bool	update (btDbvtNode *leaf, btDbvtVolume &volume, const btVector3 &velocity, btScalar margin)
bool	update (btDbvtNode *leaf, btDbvtVolume &volume, const btVector3 &velocity)
bool	update (btDbvtNode *leaf, btDbvtVolume &volume, btScalar margin)
void	remove (btDbvtNode *leaf)
void	write (IWriter *iwriter) const
void	clone (btDbvt &dest, IClone *iclone=0) const
DBVT_PREFIX void	collideTT (const btDbvtNode root0, const btDbvtNode root1, DBVT_IPOLICY)
DBVT_PREFIX void	collideTTpersistentStack (const btDbvtNode root0, const btDbvtNode root1, DBVT_IPOLICY)
DBVT_PREFIX void	collideTV (const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY)
DBVT_PREFIX void	rayTestInternal (const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &rayDirectionInverse, unsigned int signs[3], btScalar lambda_max, const btVector3 &aabbMin, const btVector3 &aabbMax, DBVT_IPOLICY) const
Static Public Member Functions
static int	maxdepth (const btDbvtNode *node)
static int	countLeaves (const btDbvtNode *node)
static void	extractLeaves (const btDbvtNode node, btAlignedObjectArray< const btDbvtNode > &leaves)
static void	benchmark ()
static DBVT_PREFIX void	enumNodes (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_PREFIX void	enumLeaves (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_PREFIX void	rayTest (const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, DBVT_IPOLICY)
static DBVT_PREFIX void	collideKDOP (const btDbvtNode root, const btVector3 normals, const btScalar *offsets, int count, DBVT_IPOLICY)
static DBVT_PREFIX void	collideOCL (const btDbvtNode root, const btVector3 normals, const btScalar *offsets, const btVector3 &sortaxis, int count, DBVT_IPOLICY, bool fullsort=true)
static DBVT_PREFIX void	collideTU (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_INLINE int	nearest (const int i, const btDbvt::sStkNPS a, btScalar v, int l, int h)
static DBVT_INLINE int	allocate (btAlignedObjectArray< int > &ifree, btAlignedObjectArray< sStkNPS > &stock, const sStkNPS &value)
Public Attributes
btDbvtNode *	m_root
btDbvtNode *	m_free
int	m_lkhd
int	m_leaves
unsigned	m_opath
btAlignedObjectArray< sStkNN >	m_stkStack

Detailed Description

The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes (aabb tree). This btDbvt is used for soft body collision detection and for the btDbvtBroadphase. It has a fast insert, remove and update of nodes. Unlike the btQuantizedBvh, nodes can be dynamically moved around, which allows for change in topology of the underlying data structure.

Definition at line 190 of file btDbvt.h.

Member Enumeration Documentation

anonymous enum

Enumerator:

SIMPLE_STACKSIZE
DOUBLE_STACKSIZE

Definition at line 248 of file btDbvt.h.

Constructor & Destructor Documentation

btDbvt::btDbvt ( )

Definition at line 409 of file btDbvt.cpp.

References m_free, m_leaves, m_lkhd, m_opath, and m_root.

btDbvt::~btDbvt ( )

Definition at line 419 of file btDbvt.cpp.

References clear().

Member Function Documentation

static DBVT_INLINE int btDbvt::allocate	(	btAlignedObjectArray< int > &	ifree,
		btAlignedObjectArray< sStkNPS > &	stock,
		const sStkNPS &	value
	)		`[inline, static]`

Definition at line 371 of file btDbvt.h.

References i, btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), and btAlignedObjectArray< T >::size().

Referenced by collideOCL().

static void btDbvt::benchmark ( ) [inline, static]

Definition at line 287 of file btDbvt.h.

void btDbvt::clear ( )

Definition at line 425 of file btDbvt.cpp.

References btAlignedFree, btAlignedObjectArray< T >::clear(), m_free, m_lkhd, m_opath, m_root, m_stkStack, and recursedeletenode().

Referenced by clone(), btSoftBody::initializeFaceTree(), btSoftBody::predictMotion(), btDbvtBroadphase::resetPool(), and ~btDbvt().

void btDbvt::clone	(	btDbvt &	dest,
		IClone *	iclone = `0`
	)		const

DBVT_PREFIX void btDbvt::collideKDOP	(	const btDbvtNode *	root,
		const btVector3 *	normals,
		const btScalar *	offsets,
		int	count,
		DBVT_IPOLICY
	)		`[inline, static]`

Definition at line 1062 of file btDbvt.h.

References btAssert, btDbvtNode::childs, btDbvtAabbMm::Classify(), DBVT_CHECKTYPE, enumLeaves(), i, btDbvtNode::isinternal(), btDbvt::sStkNP::mask, btDbvt::sStkNP::node, btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), stack, and btDbvtNode::volume.

Referenced by CcdPhysicsEnvironment::cullingTest().

DBVT_PREFIX void btDbvt::collideOCL	(	const btDbvtNode *	root,
		const btVector3 *	normals,
		const btScalar *	offsets,
		const btVector3 &	sortaxis,
		int	count,
		DBVT_IPOLICY	,
		bool	fullsort = `true`
	)		`[inline, static]`

DBVT_PREFIX void btDbvt::collideTT	(	const btDbvtNode *	root0,
		const btDbvtNode *	root1,
		DBVT_IPOLICY
	)		`[inline]`

Definition at line 710 of file btDbvt.h.

References btDbvt::sStkNN::a, btDbvt::sStkNN::b, btDbvtNode::childs, DBVT_CHECKTYPE, DOUBLE_STACKSIZE, Intersect(), btDbvtNode::isinternal(), p, btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

Referenced by btSoftBody::defaultCollisionHandler(), and btSoftColliders::CollideCL_SS::Process().

DBVT_PREFIX void btDbvt::collideTTpersistentStack	(	const btDbvtNode *	root0,
		const btDbvtNode *	root1,
		DBVT_IPOLICY
	)		`[inline]`

Definition at line 775 of file btDbvt.h.

References btDbvt::sStkNN::a, btDbvt::sStkNN::b, btDbvtNode::childs, DBVT_CHECKTYPE, DOUBLE_STACKSIZE, Intersect(), btDbvtNode::isinternal(), m_stkStack, p, btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

Referenced by btDbvtBroadphase::collide(), btDbvtBroadphase::setAabb(), and btDbvtBroadphase::setAabbForceUpdate().

DBVT_PREFIX void btDbvt::collideTU	(	const btDbvtNode *	root,
		DBVT_IPOLICY
	)		`[inline, static]`

Definition at line 1215 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, btDbvtNode::isinternal(), btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), and stack.

DBVT_PREFIX void btDbvt::collideTV	(	const btDbvtNode *	root,
		const btDbvtVolume &	volume,
		DBVT_IPOLICY
	)		`[inline]`

int btDbvt::countLeaves ( const btDbvtNode * node ) [static]

Definition at line 627 of file btDbvt.cpp.

References btDbvtNode::childs, and btDbvtNode::isinternal().

bool btDbvt::empty ( ) const [inline]

Definition at line 268 of file btDbvt.h.

References m_root.

Referenced by btSoftBody::predictMotion(), and btSoftBody::rayTest().

DBVT_PREFIX void btDbvt::enumLeaves	(	const btDbvtNode *	root,
		DBVT_IPOLICY
	)		`[inline, static]`

Definition at line 693 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, and btDbvtNode::isinternal().

Referenced by collideKDOP().

DBVT_PREFIX void btDbvt::enumNodes	(	const btDbvtNode *	root,
		DBVT_IPOLICY
	)		`[inline, static]`

Definition at line 679 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, and btDbvtNode::isinternal().

Referenced by write().

void btDbvt::extractLeaves	(	const btDbvtNode *	node,
		btAlignedObjectArray< const btDbvtNode * > &	leaves
	)		`[static]`

Definition at line 636 of file btDbvt.cpp.

References btDbvtNode::childs, btDbvtNode::isinternal(), and btAlignedObjectArray< T >::push_back().

btDbvtNode * btDbvt::insert	(	const btDbvtVolume &	box,
		void *	data
	)

Definition at line 483 of file btDbvt.cpp.

References createnode(), insertleaf(), m_leaves, and m_root.

Referenced by btSoftBody::appendNode(), btSoftBody::btSoftBody(), btDbvtBroadphase::collide(), btDbvtBroadphase::createProxy(), btSoftBody::initializeFaceTree(), btDbvtBroadphase::setAabb(), btDbvtBroadphase::setAabbForceUpdate(), and btSoftBody::updateClusters().

int btDbvt::maxdepth ( const btDbvtNode * node ) [static]

Definition at line 619 of file btDbvt.cpp.

References getmaxdepth().

static DBVT_INLINE int btDbvt::nearest	(	const int *	i,
		const btDbvt::sStkNPS *	a,
		btScalar	v,
		int	l,
		int	h
	)		`[inline, static]`

Definition at line 361 of file btDbvt.h.

Referenced by collideOCL().

void btDbvt::optimizeBottomUp ( )

Definition at line 438 of file btDbvt.cpp.

References bottomup(), fetchleaves(), m_leaves, m_root, and btAlignedObjectArray< T >::reserve().

void btDbvt::optimizeIncremental ( int passes )

Definition at line 463 of file btDbvt.cpp.

References btDbvtNode::childs, btDbvtNode::isinternal(), m_leaves, m_opath, m_root, sort(), and update().

Referenced by btDbvtBroadphase::collide(), and btSoftBody::predictMotion().

void btDbvt::optimizeTopDown ( int bu_treshold = 128 )

Definition at line 451 of file btDbvt.cpp.

References fetchleaves(), m_leaves, m_root, btAlignedObjectArray< T >::reserve(), and topdown().

Referenced by btDbvtBroadphase::optimize().

DBVT_PREFIX void btDbvt::rayTest	(	const btDbvtNode *	root,
		const btVector3 &	rayFrom,
		const btVector3 &	rayTo,
		DBVT_IPOLICY
	)		`[inline, static]`

rayTest is a re-entrant ray test, and can be called in parallel as long as the btAlignedAlloc is thread-safe (uses locking etc) rayTest is slower than rayTestInternal, because it builds a local stack, using memory allocations, and it recomputes signs/rayDirectionInverses each time

what about division by zero? --> just set rayDirection[i] to INF/BT_LARGE_FLOAT

Definition at line 993 of file btDbvt.h.

References bounds(), BT_LARGE_FLOAT, btAssert, btRayAabb(), btRayAabb2(), btDbvtNode::childs, DBVT_CHECKTYPE, DOUBLE_STACKSIZE, btDbvtNode::isinternal(), btDbvtAabbMm::Maxs(), btDbvtAabbMm::Mins(), btAlignedObjectArray< T >::resize(), MakeCursor::root, btAlignedObjectArray< T >::size(), stack, and btDbvtNode::volume.

DBVT_PREFIX void btDbvt::rayTestInternal	(	const btDbvtNode *	root,
		const btVector3 &	rayFrom,
		const btVector3 &	rayTo,
		const btVector3 &	rayDirectionInverse,
		unsigned int	signs[3],
		btScalar	lambda_max,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax,
		DBVT_IPOLICY
	)		const `[inline]`

rayTestInternal is faster than rayTest, because it uses a persistent stack (to reduce dynamic memory allocations to a minimum) and it uses precomputed signs/rayInverseDirections rayTestInternal is used by btDbvtBroadphase to accelerate world ray casts

Definition at line 940 of file btDbvt.h.

References bounds(), btRayAabb2(), btDbvtNode::childs, DBVT_CHECKTYPE, DOUBLE_STACKSIZE, btDbvtNode::isinternal(), btDbvtAabbMm::Maxs(), btDbvtAabbMm::Mins(), btAlignedObjectArray< T >::resize(), MakeCursor::root, btAlignedObjectArray< T >::size(), stack, and btDbvtNode::volume.