Bullet Collision Detection & Physics Library: 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:

Collaboration diagram for btQuantizedBvh:

[legend]

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 *********************** More...

QuantizedNodeArray &	getLeafNodeArray ()

void	buildInternal ()
	buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialized More...

void	reportAabbOverlappingNodex (btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
	‍*************************************** expert/internal use only *********************** More...

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

void	quantize (unsigned short *out, const btVector3 &point, int isMax) const

void	quantizeWithClamp (unsigned short *out, const btVector3 &point2, int isMax) const

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. More...

QuantizedNodeArray &	getQuantizedNodeArray ()

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. More...

virtual int	calculateSerializeBufferSizeNew () const

virtual const char *	serialize (void dataBuffer, btSerializer serializer) const
	fills the dataBuffer and returns the struct name (and 0 on failure) More...

virtual void	deSerializeFloat (struct btQuantizedBvhFloatData &quantizedBvhFloatData)

virtual void	deSerializeDouble (struct btQuantizedBvhDoubleData &quantizedBvhDoubleData)

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' More...

static unsigned int	getAlignmentSerializationPadding ()

Protected Member Functions
void	setInternalNodeAabbMin (int nodeIndex, const btVector3 &aabbMin)
	two versions, one for quantized and normal nodes. More...

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 More...

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 More...

void	walkRecursiveQuantizedTreeAgainstQuantizedTree (const btQuantizedBvhNode treeNodeA, const btQuantizedBvhNode treeNodeB, btNodeOverlapCallback *nodeCallback) const
	use the 16-byte stackless 'skipindex' node tree to do a recursive traversal More...

void	updateSubtreeHeaders (int leftChildNodexIndex, int rightChildNodexIndex)

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. It is recommended to use quantization for better performance and lower memory requirements.

Definition at line 166 of file btQuantizedBvh.h.

Member Enumeration Documentation

◆ btTraversalMode

enum btQuantizedBvh::btTraversalMode

Enumerator
TRAVERSAL_STACKLESS
TRAVERSAL_STACKLESS_CACHE_FRIENDLY
TRAVERSAL_RECURSIVE

Definition at line 170 of file btQuantizedBvh.h.

Constructor & Destructor Documentation

◆ btQuantizedBvh() [1/2]

btQuantizedBvh::btQuantizedBvh ( )

Definition at line 24 of file btQuantizedBvh.cpp.

◆ ~btQuantizedBvh()

btQuantizedBvh::~btQuantizedBvh ( )

virtual

Definition at line 112 of file btQuantizedBvh.cpp.

◆ btQuantizedBvh() [2/2]

btQuantizedBvh::btQuantizedBvh	(	btQuantizedBvh &	other,
		bool	ownsMemory
	)

private

Definition at line 1112 of file btQuantizedBvh.cpp.

Member Function Documentation

◆ assignInternalNodeFromLeafNode()

void btQuantizedBvh::assignInternalNodeFromLeafNode	(	int	internalNode,
		int	leafNodeIndex
	)

protected

Definition at line 784 of file btQuantizedBvh.cpp.

◆ BT_DECLARE_ALIGNED_ALLOCATOR()

btQuantizedBvh::BT_DECLARE_ALIGNED_ALLOCATOR ( )

◆ buildInternal()

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 36 of file btQuantizedBvh.cpp.

◆ buildTree()

void btQuantizedBvh::buildTree	(	int	startIndex,
		int	endIndex
	)

protected

Definition at line 121 of file btQuantizedBvh.cpp.

◆ calcSplittingAxis()

int btQuantizedBvh::calcSplittingAxis	(	int	startIndex,
		int	endIndex
	)

protected

Definition at line 285 of file btQuantizedBvh.cpp.

◆ calculateSerializeBufferSize()

unsigned btQuantizedBvh::calculateSerializeBufferSize ( ) const

Definition at line 813 of file btQuantizedBvh.cpp.

◆ calculateSerializeBufferSizeNew()

int btQuantizedBvh::calculateSerializeBufferSizeNew ( ) const

inlinevirtual

Definition at line 538 of file btQuantizedBvh.h.

◆ deSerializeDouble()

void btQuantizedBvh::deSerializeDouble ( struct btQuantizedBvhDoubleData & quantizedBvhDoubleData )

virtual

Definition at line 1190 of file btQuantizedBvh.cpp.

◆ deSerializeFloat()

void btQuantizedBvh::deSerializeFloat ( struct btQuantizedBvhFloatData & quantizedBvhFloatData )

virtual

Definition at line 1119 of file btQuantizedBvh.cpp.

◆ deSerializeInPlace()

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'

Definition at line 1006 of file btQuantizedBvh.cpp.

◆ getAabbMax()

btVector3 btQuantizedBvh::getAabbMax ( int nodeIndex ) const

inlineprotected

Definition at line 233 of file btQuantizedBvh.h.

◆ getAabbMin()

btVector3 btQuantizedBvh::getAabbMin ( int nodeIndex ) const

inlineprotected

Definition at line 224 of file btQuantizedBvh.h.

◆ getAlignmentSerializationPadding()

unsigned int btQuantizedBvh::getAlignmentSerializationPadding ( )

static

Definition at line 807 of file btQuantizedBvh.cpp.

◆ getLeafNodeArray()

QuantizedNodeArray & btQuantizedBvh::getLeafNodeArray ( )

inline

Definition at line 317 of file btQuantizedBvh.h.

◆ getQuantizedNodeArray()

QuantizedNodeArray & btQuantizedBvh::getQuantizedNodeArray ( )

inline

Definition at line 418 of file btQuantizedBvh.h.

◆ getSubtreeInfoArray()

BvhSubtreeInfoArray & btQuantizedBvh::getSubtreeInfoArray ( )

inline

Definition at line 423 of file btQuantizedBvh.h.

◆ isQuantized()

bool btQuantizedBvh::isQuantized ( )

inline

Definition at line 453 of file btQuantizedBvh.h.

◆ mergeInternalNodeAabb()

void btQuantizedBvh::mergeInternalNodeAabb	(	int	nodeIndex,
		const btVector3 &	newAabbMin,
		const btVector3 &	newAabbMax
	)

inlineprotected

Definition at line 255 of file btQuantizedBvh.h.

◆ quantize()

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 326 of file btQuantizedBvh.h.

◆ quantizeWithClamp()

void btQuantizedBvh::quantizeWithClamp	(	unsigned short *	out,
		const btVector3 &	point2,
		int	isMax
	)		const

inline

Definition at line 390 of file btQuantizedBvh.h.

◆ reportAabbOverlappingNodex()

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.

◆ reportBoxCastOverlappingNodex()

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

Definition at line 742 of file btQuantizedBvh.cpp.

◆ reportRayOverlappingNodex()

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

Definition at line 737 of file btQuantizedBvh.cpp.

◆ serialize() [1/2]

const char * btQuantizedBvh::serialize	(	void *	dataBuffer,
		btSerializer *	serializer
	)		const

virtual

fills the dataBuffer and returns the struct name (and 0 on failure)

Definition at line 1262 of file btQuantizedBvh.cpp.

◆ serialize() [2/2]

bool btQuantizedBvh::serialize	(	void *	o_alignedDataBuffer,
		unsigned	i_dataBufferSize,
		bool	i_swapEndian
	)		const

virtual

Data buffer MUST be 16 byte aligned.

Definition at line 824 of file btQuantizedBvh.cpp.

◆ setInternalNodeAabbMax()

void btQuantizedBvh::setInternalNodeAabbMax	(	int	nodeIndex,
		const btVector3 &	aabbMax
	)

inlineprotected

Definition at line 212 of file btQuantizedBvh.h.

◆ setInternalNodeAabbMin()

void btQuantizedBvh::setInternalNodeAabbMin	(	int	nodeIndex,
		const btVector3 &	aabbMin
	)

inlineprotected

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.

◆ setInternalNodeEscapeIndex()

void btQuantizedBvh::setInternalNodeEscapeIndex	(	int	nodeIndex,
		int	escapeIndex
	)

inlineprotected

Definition at line 243 of file btQuantizedBvh.h.

◆ setQuantizationValues()

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 81 of file btQuantizedBvh.cpp.

◆ setTraversalMode()

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 413 of file btQuantizedBvh.h.

◆ sortAndCalcSplittingIndex()

int btQuantizedBvh::sortAndCalcSplittingIndex	(	int	startIndex,
		int	endIndex,
		int	splitAxis
	)

protected

Definition at line 232 of file btQuantizedBvh.cpp.

◆ swapLeafNodes()

void btQuantizedBvh::swapLeafNodes	(	int	firstIndex,
		int	secondIndex
	)

protected

Definition at line 768 of file btQuantizedBvh.cpp.

◆ unQuantize()

btVector3 btQuantizedBvh::unQuantize ( const unsigned short * vecIn ) const

inline

Definition at line 401 of file btQuantizedBvh.h.

◆ updateSubtreeHeaders()

void btQuantizedBvh::updateSubtreeHeaders	(	int	leftChildNodexIndex,
		int	rightChildNodexIndex
	)

protected

Definition at line 200 of file btQuantizedBvh.cpp.

◆ walkRecursiveQuantizedTreeAgainstQuantizedTree()

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

◆ walkRecursiveQuantizedTreeAgainstQueryAabb()

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 411 of file btQuantizedBvh.cpp.

◆ walkStacklessQuantizedTree()

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

protected

Definition at line 653 of file btQuantizedBvh.cpp.

◆ walkStacklessQuantizedTreeAgainstRay()

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 530 of file btQuantizedBvh.cpp.

◆ walkStacklessQuantizedTreeCacheFriendly()

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 716 of file btQuantizedBvh.cpp.

◆ walkStacklessTree()

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

protected

Definition at line 349 of file btQuantizedBvh.cpp.

◆ walkStacklessTreeAgainstRay()

void btQuantizedBvh::walkStacklessTreeAgainstRay	(	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

Definition at line 442 of file btQuantizedBvh.cpp.

Member Data Documentation

◆ m_bulletVersion

int btQuantizedBvh::m_bulletVersion

protected

Definition at line 182 of file btQuantizedBvh.h.

◆ m_bvhAabbMax

btVector3 btQuantizedBvh::m_bvhAabbMax

protected

Definition at line 179 of file btQuantizedBvh.h.

◆ m_bvhAabbMin

btVector3 btQuantizedBvh::m_bvhAabbMin

protected

Definition at line 178 of file btQuantizedBvh.h.

◆ m_bvhQuantization

btVector3 btQuantizedBvh::m_bvhQuantization

protected

Definition at line 180 of file btQuantizedBvh.h.

◆ m_contiguousNodes

NodeArray btQuantizedBvh::m_contiguousNodes

protected

Definition at line 189 of file btQuantizedBvh.h.

◆ m_curNodeIndex

int btQuantizedBvh::m_curNodeIndex

protected

Definition at line 184 of file btQuantizedBvh.h.

◆ m_leafNodes

NodeArray btQuantizedBvh::m_leafNodes

protected

Definition at line 188 of file btQuantizedBvh.h.

◆ m_quantizedContiguousNodes

QuantizedNodeArray btQuantizedBvh::m_quantizedContiguousNodes

protected

Definition at line 191 of file btQuantizedBvh.h.

◆ m_quantizedLeafNodes

QuantizedNodeArray btQuantizedBvh::m_quantizedLeafNodes

protected

Definition at line 190 of file btQuantizedBvh.h.

◆ m_subtreeHeaderCount

int btQuantizedBvh::m_subtreeHeaderCount

mutableprotected

Definition at line 197 of file btQuantizedBvh.h.

◆ m_SubtreeHeaders

BvhSubtreeInfoArray btQuantizedBvh::m_SubtreeHeaders

protected

Definition at line 194 of file btQuantizedBvh.h.

◆ m_traversalMode

btTraversalMode btQuantizedBvh::m_traversalMode

protected

Definition at line 193 of file btQuantizedBvh.h.

◆ m_useQuantization

bool btQuantizedBvh::m_useQuantization

protected

Definition at line 186 of file btQuantizedBvh.h.

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

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

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Enumeration Documentation

◆ btTraversalMode

Constructor & Destructor Documentation

◆ btQuantizedBvh() [1/2]

◆ ~btQuantizedBvh()

◆ btQuantizedBvh() [2/2]

Member Function Documentation

◆ assignInternalNodeFromLeafNode()

◆ BT_DECLARE_ALIGNED_ALLOCATOR()

◆ buildInternal()

◆ buildTree()

◆ calcSplittingAxis()

◆ calculateSerializeBufferSize()

◆ calculateSerializeBufferSizeNew()

◆ deSerializeDouble()

◆ deSerializeFloat()

◆ deSerializeInPlace()

◆ getAabbMax()

◆ getAabbMin()

◆ getAlignmentSerializationPadding()

◆ getLeafNodeArray()

◆ getQuantizedNodeArray()

◆ getSubtreeInfoArray()

◆ isQuantized()

◆ mergeInternalNodeAabb()

◆ quantize()

◆ quantizeWithClamp()

◆ reportAabbOverlappingNodex()

◆ reportBoxCastOverlappingNodex()

◆ reportRayOverlappingNodex()

◆ serialize() [1/2]

◆ serialize() [2/2]

◆ setInternalNodeAabbMax()

◆ setInternalNodeAabbMin()

◆ setInternalNodeEscapeIndex()

◆ setQuantizationValues()

◆ setTraversalMode()

◆ sortAndCalcSplittingIndex()

◆ swapLeafNodes()

◆ unQuantize()

◆ updateSubtreeHeaders()

◆ walkRecursiveQuantizedTreeAgainstQuantizedTree()

◆ walkRecursiveQuantizedTreeAgainstQueryAabb()

◆ walkStacklessQuantizedTree()

◆ walkStacklessQuantizedTreeAgainstRay()

◆ walkStacklessQuantizedTreeCacheFriendly()

◆ walkStacklessTree()

◆ walkStacklessTreeAgainstRay()

Member Data Documentation

◆ m_bulletVersion

◆ m_bvhAabbMax

◆ m_bvhAabbMin

◆ m_bvhQuantization

◆ m_contiguousNodes

◆ m_curNodeIndex

◆ m_leafNodes

◆ m_quantizedContiguousNodes

◆ m_quantizedLeafNodes

◆ m_subtreeHeaderCount

◆ m_SubtreeHeaders

◆ m_traversalMode

◆ m_useQuantization