btQuantizedBvh Class Reference

The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU. More...

#include <btQuantizedBvh.h>

Inheritance diagram for btQuantizedBvh:

[legend]

Collaboration diagram for btQuantizedBvh:

[legend]

List of all members.

Public Types
enum	btTraversalMode { TRAVERSAL_STACKLESS = 0, TRAVERSAL_STACKLESS_CACHE_FRIENDLY, TRAVERSAL_RECURSIVE }
Public Member Functions
	BT_DECLARE_ALIGNED_ALLOCATOR ()
	btQuantizedBvh ()
virtual	~btQuantizedBvh ()
void	setQuantizationValues (const btVector3 &bvhAabbMin, const btVector3 &bvhAabbMax, btScalar quantizationMargin=btScalar(1.0))
	*************************************** expert/internal use only ***********************
QuantizedNodeArray &	getLeafNodeArray ()
void	buildInternal ()
	buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialized
void	reportAabbOverlappingNodex (btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
	*************************************** expert/internal use only ***********************
void	reportRayOverlappingNodex (btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget) const
void	reportBoxCastOverlappingNodex (btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax) const
SIMD_FORCE_INLINE void	quantize (unsigned short *out, const btVector3 &point, int isMax) const
SIMD_FORCE_INLINE void	quantizeWithClamp (unsigned short *out, const btVector3 &point2, int isMax) const
SIMD_FORCE_INLINE btVector3	unQuantize (const unsigned short *vecIn) const
void	setTraversalMode (btTraversalMode traversalMode)
	setTraversalMode let's you choose between stackless, recursive or stackless cache friendly tree traversal. Note this is only implemented for quantized trees.
SIMD_FORCE_INLINE QuantizedNodeArray &	getQuantizedNodeArray ()
SIMD_FORCE_INLINE BvhSubtreeInfoArray &	getSubtreeInfoArray ()
unsigned	calculateSerializeBufferSize () const
virtual bool	serialize (void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian) const
	Data buffer MUST be 16 byte aligned.
SIMD_FORCE_INLINE bool	isQuantized ()
Static Public Member Functions
static btQuantizedBvh *	deSerializeInPlace (void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian)
	deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'
static unsigned int	getAlignmentSerializationPadding ()
Protected Member Functions
void	setInternalNodeAabbMin (int nodeIndex, const btVector3 &aabbMin)
	two versions, one for quantized and normal nodes.
void	setInternalNodeAabbMax (int nodeIndex, const btVector3 &aabbMax)
btVector3	getAabbMin (int nodeIndex) const
btVector3	getAabbMax (int nodeIndex) const
void	setInternalNodeEscapeIndex (int nodeIndex, int escapeIndex)
void	mergeInternalNodeAabb (int nodeIndex, const btVector3 &newAabbMin, const btVector3 &newAabbMax)
void	swapLeafNodes (int firstIndex, int secondIndex)
void	assignInternalNodeFromLeafNode (int internalNode, int leafNodeIndex)
void	buildTree (int startIndex, int endIndex)
int	calcSplittingAxis (int startIndex, int endIndex)
int	sortAndCalcSplittingIndex (int startIndex, int endIndex, int splitAxis)
void	walkStacklessTree (btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
void	walkStacklessQuantizedTreeAgainstRay (btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
void	walkStacklessQuantizedTree (btNodeOverlapCallback nodeCallback, unsigned short int quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax, int startNodeIndex, int endNodeIndex) const
void	walkStacklessTreeAgainstRay (btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
void	walkStacklessQuantizedTreeCacheFriendly (btNodeOverlapCallback nodeCallback, unsigned short int quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax) const
	tree traversal designed for small-memory processors like PS3 SPU
void	walkRecursiveQuantizedTreeAgainstQueryAabb (const btQuantizedBvhNode currentNode, btNodeOverlapCallback nodeCallback, unsigned short int quantizedQueryAabbMin, unsigned short int quantizedQueryAabbMax) const
	use the 16-byte stackless 'skipindex' node tree to do a recursive traversal
void	walkRecursiveQuantizedTreeAgainstQuantizedTree (const btQuantizedBvhNode treeNodeA, const btQuantizedBvhNode treeNodeB, btNodeOverlapCallback *nodeCallback) const
	use the 16-byte stackless 'skipindex' node tree to do a recursive traversal
void	updateSubtreeHeaders (int leftChildNodexIndex, int rightChildNodexIndex)
Protected Attributes
btVector3	m_bvhAabbMin
btVector3	m_bvhAabbMax
btVector3	m_bvhQuantization
int	m_bulletVersion
int	m_curNodeIndex
bool	m_useQuantization
NodeArray	m_leafNodes
NodeArray	m_contiguousNodes
QuantizedNodeArray	m_quantizedLeafNodes
QuantizedNodeArray	m_quantizedContiguousNodes
btTraversalMode	m_traversalMode
BvhSubtreeInfoArray	m_SubtreeHeaders
int	m_subtreeHeaderCount
Private Member Functions
	btQuantizedBvh (btQuantizedBvh &other, bool ownsMemory)

Detailed Description

The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU.

It is used by the btBvhTriangleMeshShape as midphase, and by the btMultiSapBroadphase. It is recommended to use quantization for better performance and lower memory requirements.

Definition at line 159 of file btQuantizedBvh.h.

Member Enumeration Documentation

enum btQuantizedBvh::btTraversalMode

Enumerator:

TRAVERSAL_STACKLESS
TRAVERSAL_STACKLESS_CACHE_FRIENDLY
TRAVERSAL_RECURSIVE

Definition at line 162 of file btQuantizedBvh.h.

Constructor & Destructor Documentation

btQuantizedBvh::btQuantizedBvh ( )

Definition at line 23 of file btQuantizedBvh.cpp.

btQuantizedBvh::~btQuantizedBvh ( ) [virtual]

Definition at line 104 of file btQuantizedBvh.cpp.

btQuantizedBvh::btQuantizedBvh	(	btQuantizedBvh &	other,
		bool	ownsMemory
	)			`[private]`

Definition at line 1137 of file btQuantizedBvh.cpp.

Member Function Documentation

void btQuantizedBvh::assignInternalNodeFromLeafNode	(	int	internalNode,
		int	leafNodeIndex
	)			`[protected]`

Definition at line 804 of file btQuantizedBvh.cpp.

btQuantizedBvh::BT_DECLARE_ALIGNED_ALLOCATOR ( )

Reimplemented in btOptimizedBvh.

void btQuantizedBvh::buildInternal ( )

buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialized

assumes that caller filled in the m_quantizedLeafNodes

if the entire tree is small then subtree size, we need to create a header info for the tree

Definition at line 39 of file btQuantizedBvh.cpp.

void btQuantizedBvh::buildTree	(	int	startIndex,
		int	endIndex
	)			`[protected]`

Definition at line 113 of file btQuantizedBvh.cpp.

int btQuantizedBvh::calcSplittingAxis	(	int	startIndex,
		int	endIndex
	)			`[protected]`

Definition at line 283 of file btQuantizedBvh.cpp.

unsigned btQuantizedBvh::calculateSerializeBufferSize ( ) const

Definition at line 833 of file btQuantizedBvh.cpp.

btQuantizedBvh * btQuantizedBvh::deSerializeInPlace	(	void *	i_alignedDataBuffer,
		unsigned int	i_dataBufferSize,
		bool	i_swapEndian
	)			`[static]`

deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place'

Reimplemented in btOptimizedBvh.

Definition at line 1030 of file btQuantizedBvh.cpp.

btVector3 btQuantizedBvh::getAabbMax ( int nodeIndex ) const [inline, protected]

Definition at line 233 of file btQuantizedBvh.h.

btVector3 btQuantizedBvh::getAabbMin ( int nodeIndex ) const [inline, protected]

Definition at line 223 of file btQuantizedBvh.h.

unsigned int btQuantizedBvh::getAlignmentSerializationPadding ( ) [static]

Definition at line 827 of file btQuantizedBvh.cpp.

QuantizedNodeArray& btQuantizedBvh::getLeafNodeArray ( ) [inline]

Definition at line 328 of file btQuantizedBvh.h.

SIMD_FORCE_INLINE QuantizedNodeArray& btQuantizedBvh::getQuantizedNodeArray ( ) [inline]

Definition at line 435 of file btQuantizedBvh.h.

SIMD_FORCE_INLINE BvhSubtreeInfoArray& btQuantizedBvh::getSubtreeInfoArray ( ) [inline]

Definition at line 441 of file btQuantizedBvh.h.

SIMD_FORCE_INLINE bool btQuantizedBvh::isQuantized ( ) [inline]

Definition at line 458 of file btQuantizedBvh.h.

void btQuantizedBvh::mergeInternalNodeAabb	(	int	nodeIndex,
		const btVector3 &	newAabbMin,
		const btVector3 &	newAabbMax
	)			`[inline, protected]`

Definition at line 258 of file btQuantizedBvh.h.

SIMD_FORCE_INLINE void btQuantizedBvh::quantize	(	unsigned short *	out,
		const btVector3 &	point,
		int	isMax
	)			const `[inline]`

Make sure rounding is done in a way that unQuantize(quantizeWithClamp(...)) is conservative end-points always set the first bit, so that they are sorted properly (so that neighbouring AABBs overlap properly)

Definition at line 337 of file btQuantizedBvh.h.

SIMD_FORCE_INLINE void btQuantizedBvh::quantizeWithClamp	(	unsigned short *	out,
		const btVector3 &	point2,
		int	isMax
	)			const `[inline]`

Definition at line 404 of file btQuantizedBvh.h.

void btQuantizedBvh::reportAabbOverlappingNodex	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax
	)			const

***************************************** expert/internal use only *************************

quantize query AABB

Definition at line 312 of file btQuantizedBvh.cpp.

void btQuantizedBvh::reportBoxCastOverlappingNodex	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	raySource,
		const btVector3 &	rayTarget,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax
	)			const

Definition at line 761 of file btQuantizedBvh.cpp.

void btQuantizedBvh::reportRayOverlappingNodex	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	raySource,
		const btVector3 &	rayTarget
	)			const

Definition at line 755 of file btQuantizedBvh.cpp.

bool btQuantizedBvh::serialize	(	void *	o_alignedDataBuffer,
		unsigned	i_dataBufferSize,
		bool	i_swapEndian
	)			const `[virtual]`

Data buffer MUST be 16 byte aligned.

Reimplemented in btOptimizedBvh.

Definition at line 844 of file btQuantizedBvh.cpp.

void btQuantizedBvh::setInternalNodeAabbMax	(	int	nodeIndex,
		const btVector3 &	aabbMax
	)			`[inline, protected]`

Definition at line 212 of file btQuantizedBvh.h.

void btQuantizedBvh::setInternalNodeAabbMin	(	int	nodeIndex,
		const btVector3 &	aabbMin
	)			`[inline, protected]`

two versions, one for quantized and normal nodes.

This allows code-reuse while maintaining readability (no template/macro!) this might be refactored into a virtual, it is usually not calculated at run-time

Definition at line 201 of file btQuantizedBvh.h.

void btQuantizedBvh::setInternalNodeEscapeIndex	(	int	nodeIndex,
		int	escapeIndex
	)			`[inline, protected]`

Definition at line 245 of file btQuantizedBvh.h.

void btQuantizedBvh::setQuantizationValues	(	const btVector3 &	bvhAabbMin,
		const btVector3 &	bvhAabbMax,
		btScalar	quantizationMargin = `btScalar(1.0)`
	)

***************************************** expert/internal use only *************************

just for debugging, to visualize the individual patches/subtrees

Definition at line 90 of file btQuantizedBvh.cpp.

void btQuantizedBvh::setTraversalMode ( btTraversalMode traversalMode ) [inline]

setTraversalMode let's you choose between stackless, recursive or stackless cache friendly tree traversal. Note this is only implemented for quantized trees.

Definition at line 429 of file btQuantizedBvh.h.

int btQuantizedBvh::sortAndCalcSplittingIndex	(	int	startIndex,
		int	endIndex,
		int	splitAxis
	)			`[protected]`

Definition at line 229 of file btQuantizedBvh.cpp.

void btQuantizedBvh::swapLeafNodes	(	int	firstIndex,
		int	secondIndex
	)			`[protected]`

Definition at line 789 of file btQuantizedBvh.cpp.

SIMD_FORCE_INLINE btVector3 btQuantizedBvh::unQuantize ( const unsigned short * vecIn ) const [inline]

Definition at line 417 of file btQuantizedBvh.h.

void btQuantizedBvh::updateSubtreeHeaders	(	int	leftChildNodexIndex,
		int	rightChildNodexIndex
	)			`[protected]`

Definition at line 196 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkRecursiveQuantizedTreeAgainstQuantizedTree	(	const btQuantizedBvhNode *	treeNodeA,
		const btQuantizedBvhNode *	treeNodeB,
		btNodeOverlapCallback *	nodeCallback
	)			const `[protected]`

use the 16-byte stackless 'skipindex' node tree to do a recursive traversal

void btQuantizedBvh::walkRecursiveQuantizedTreeAgainstQueryAabb	(	const btQuantizedBvhNode *	currentNode,
		btNodeOverlapCallback *	nodeCallback,
		unsigned short int *	quantizedQueryAabbMin,
		unsigned short int *	quantizedQueryAabbMax
	)			const `[protected]`

use the 16-byte stackless 'skipindex' node tree to do a recursive traversal

Definition at line 416 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkStacklessQuantizedTree	(	btNodeOverlapCallback *	nodeCallback,
		unsigned short int *	quantizedQueryAabbMin,
		unsigned short int *	quantizedQueryAabbMax,
		int	startNodeIndex,
		int	endNodeIndex
	)			const `[protected]`

Definition at line 666 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkStacklessQuantizedTreeAgainstRay	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	raySource,
		const btVector3 &	rayTarget,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax,
		int	startNodeIndex,
		int	endNodeIndex
	)			const `[protected]`

what about division by zero? --> just set rayDirection[i] to 1.0

careful with this check: need to check division by zero (above) and fix the unQuantize method thanks Joerg/hiker for the reproduction case! http://www.bulletphysics.com/Bullet/phpBB3/viewtopic.php?f=9&t=1858

Definition at line 540 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkStacklessQuantizedTreeCacheFriendly	(	btNodeOverlapCallback *	nodeCallback,
		unsigned short int *	quantizedQueryAabbMin,
		unsigned short int *	quantizedQueryAabbMax
	)			const `[protected]`

tree traversal designed for small-memory processors like PS3 SPU

Definition at line 732 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkStacklessTree	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax
	)			const `[protected]`

Definition at line 352 of file btQuantizedBvh.cpp.

void btQuantizedBvh::walkStacklessTreeAgainstRay	(	btNodeOverlapCallback *	nodeCallback,
		const btVector3 &	raySource,
		const btVector3 &	rayTarget,
		const btVector3 &	aabbMin,
		const btVector3 &	aabbMax,
		int	startNodeIndex,
		int	endNodeIndex
	)			const `[protected]`