26 m_useQuantization(false),
28 m_traversalMode(TRAVERSAL_STACKLESS)
30 ,m_subtreeHeaderCount(0)
79#ifdef DEBUG_PATCH_COLORS
94 btVector3 clampValue(quantizationMargin,quantizationMargin,quantizationMargin);
103 unsigned short vecIn[3];
129#ifdef DEBUG_TREE_BUILDING
131int gMaxStackDepth = 0;
136#ifdef DEBUG_TREE_BUILDING
138 if (gStackDepth > gMaxStackDepth)
139 gMaxStackDepth = gStackDepth;
143 int splitAxis, splitIndex, i;
144 int numIndices =endIndex-startIndex;
151#ifdef DEBUG_TREE_BUILDING
174 for (i=startIndex;i<endIndex;i++)
193#ifdef DEBUG_TREE_BUILDING
203 const int treeSizeInBytes = escapeIndex * sizeQuantizedNode;
223 int leftSubTreeSizeInBytes = leftSubTreeSize *
static_cast<int>(
sizeof(
btQuantizedBvhNode));
227 int rightSubTreeSizeInBytes = rightSubTreeSize *
static_cast<int>(
sizeof(
btQuantizedBvhNode));
253 int splitIndex =startIndex;
254 int numIndices = endIndex - startIndex;
258 for (i=startIndex;i<endIndex;i++)
265 splitValue = means[splitAxis];
268 for (i=startIndex;i<endIndex;i++)
271 if (center[splitAxis] > splitValue)
288 int rangeBalancedIndices = numIndices/3;
289 bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices)));
293 splitIndex = startIndex+ (numIndices>>1);
296 bool unbal = (splitIndex==startIndex) || (splitIndex == (endIndex));
310 int numIndices = endIndex-startIndex;
312 for (i=startIndex;i<endIndex;i++)
319 for (i=startIndex;i<endIndex;i++)
323 diff2 = diff2 * diff2;
340 unsigned short int quantizedQueryAabbMin[3];
341 unsigned short int quantizedQueryAabbMax[3];
378 int escapeIndex, curIndex = 0;
379 int walkIterations = 0;
382 unsigned aabbOverlap;
394 if (isLeafNode && (aabbOverlap != 0))
400 if ((aabbOverlap != 0) || isLeafNode)
407 rootNode += escapeIndex;
408 curIndex += escapeIndex;
443 unsigned aabbOverlap;
450 if (aabbOverlap != 0)
474 int escapeIndex, curIndex = 0;
475 int walkIterations = 0;
478 unsigned aabbOverlap=0;
479 unsigned rayBoxOverlap=0;
485 rayAabbMin.
setMin(rayTarget);
486 rayAabbMax.
setMax(rayTarget);
489 rayAabbMin += aabbMin;
490 rayAabbMax += aabbMax;
493 btVector3 rayDir = (rayTarget-raySource);
495 lambda_max = rayDir.
dot(rayTarget-raySource);
501 unsigned int sign[3] = { rayDirectionInverse[0] < 0.0, rayDirectionInverse[1] < 0.0, rayDirectionInverse[2] < 0.0};
527 rayBoxOverlap = aabbOverlap ?
btRayAabb2 (raySource, rayDirectionInverse, sign,
bounds, param, 0.0f, lambda_max) :
false;
537 if (isLeafNode && (rayBoxOverlap != 0))
543 if ((rayBoxOverlap != 0) || isLeafNode)
550 rootNode += escapeIndex;
551 curIndex += escapeIndex;
565 int curIndex = startNodeIndex;
566 int walkIterations = 0;
567 int subTreeSize = endNodeIndex - startNodeIndex;
575 unsigned boxBoxOverlap = 0;
576 unsigned rayBoxOverlap = 0;
581 btVector3 rayDirection = (rayTarget-raySource);
583 lambda_max = rayDirection.
dot(rayTarget-raySource);
588 unsigned int sign[3] = { rayDirection[0] < 0.0, rayDirection[1] < 0.0, rayDirection[2] < 0.0};
594 rayAabbMin.
setMin(rayTarget);
595 rayAabbMax.
setMax(rayTarget);
598 rayAabbMin += aabbMin;
599 rayAabbMax += aabbMax;
601 unsigned short int quantizedQueryAabbMin[3];
602 unsigned short int quantizedQueryAabbMax[3];
606 while (curIndex < endNodeIndex)
610#ifdef VISUALLY_ANALYZE_BVH
612 static int drawPatch = 0;
615 if (curIndex==drawPatch)
621 debugDrawerPtr->
drawAabb(aabbMin,aabbMax,color);
626 btAssert (walkIterations < subTreeSize);
645 bool ra2 =
btRayAabb2 (raySource, rayDirection, sign,
bounds, param, 0.0, lambda_max);
649 printf(
"functions don't match\n");
658 rayBoxOverlap =
btRayAabb2 (raySource, rayDirection, sign,
bounds, param, 0.0f, lambda_max);
661 rayBoxOverlap =
true;
665 if (isLeafNode && rayBoxOverlap)
671 if ((rayBoxOverlap != 0) || isLeafNode)
678 rootNode += escapeIndex;
679 curIndex += escapeIndex;
691 int curIndex = startNodeIndex;
692 int walkIterations = 0;
693 int subTreeSize = endNodeIndex - startNodeIndex;
701 unsigned aabbOverlap;
703 while (curIndex < endNodeIndex)
707#ifdef VISUALLY_ANALYZE_BVH
709 static int drawPatch = 0;
712 if (curIndex==drawPatch)
718 debugDrawerPtr->
drawAabb(aabbMin,aabbMax,color);
723 btAssert (walkIterations < subTreeSize);
730 if (isLeafNode && aabbOverlap)
736 if ((aabbOverlap != 0) || isLeafNode)
743 rootNode += escapeIndex;
744 curIndex += escapeIndex;
841static const unsigned BVH_ALIGNMENT = 16;
842static const unsigned BVH_ALIGNMENT_MASK = BVH_ALIGNMENT-1;
844static const unsigned BVH_ALIGNMENT_BLOCKS = 2;
908 unsigned char *nodeData = (
unsigned char *)targetBvh;
911 unsigned sizeToAdd = 0;
912 nodeData += sizeToAdd;
922 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
937 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
966 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
978 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
997 nodeData += sizeToAdd;
1046 *((
void**)o_alignedDataBuffer) = NULL;
1054 if (i_alignedDataBuffer == NULL)
1073 btAssert(calculatedBufSize <= i_dataBufferSize);
1075 if (calculatedBufSize > i_dataBufferSize)
1080 unsigned char *nodeData = (
unsigned char *)bvh;
1083 unsigned sizeToAdd = 0;
1084 nodeData += sizeToAdd;
1098 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
1119 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
1133 nodeData += sizeToAdd;
1159m_bvhAabbMin(self.m_bvhAabbMin),
1160m_bvhAabbMax(self.m_bvhAabbMax),
1161m_bvhQuantization(self.m_bvhQuantization),
1184 for (
int i=0;i<numElem;i++,memPtr++)
1202 for (
int i=0;i<numElem;i++,memPtr++)
1223 for (
int i=0;i<numElem;i++,memPtr++)
1255 for (
int i=0;i<numElem;i++,memPtr++)
1273 for (
int i=0;i<numElem;i++,memPtr++)
1294 for (
int i=0;i<numElem;i++,memPtr++)
1326 if (quantizedData->m_contiguousNodesPtr)
1332 for (
int i=0;i<numElem;i++,memPtr++)
1340 memset(memPtr->m_pad, 0,
sizeof(memPtr->m_pad));
1348 if (quantizedData->m_quantizedContiguousNodesPtr)
1354 for (
int i=0;i<numElem;i++,memPtr++)
1371 if (quantizedData->m_subTreeInfoPtr)
1377 for (
int i=0;i<numElem;i++,memPtr++)
bool btRayAabb(const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &aabbMin, const btVector3 &aabbMax, btScalar ¶m, btVector3 &normal)
bool TestAabbAgainstAabb2(const btVector3 &aabbMin1, const btVector3 &aabbMax1, const btVector3 &aabbMin2, const btVector3 &aabbMax2)
conservative test for overlap between two aabbs
bool btRayAabb2(const btVector3 &rayFrom, const btVector3 &rayInvDirection, const unsigned int raySign[3], const btVector3 bounds[2], btScalar &tmin, btScalar lambda_min, btScalar lambda_max)
unsigned testQuantizedAabbAgainstQuantizedAabb(const unsigned short int *aabbMin1, const unsigned short int *aabbMax1, const unsigned short int *aabbMin2, const unsigned short int *aabbMax2)
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
#define btOptimizedBvhNodeData
#define MAX_SUBTREE_SIZE_IN_BYTES
#define btQuantizedBvhDataName
#define btQuantizedBvhData
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
unsigned btSwapEndian(unsigned val)
#define BT_BULLET_VERSION
void btSwapVector3Endian(const btVector3 &sourceVec, btVector3 &destVec)
btSwapVector3Endian swaps vector endianness, useful for network and cross-platform serialization
void btUnSwapVector3Endian(btVector3 &vector)
btUnSwapVector3Endian swaps vector endianness, useful for network and cross-platform serialization
int size() const
return the number of elements in the array
void resize(int newsize, const T &fillData=T())
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
T & expand(const T &fillValue=T())
void initializeFromBuffer(void *buffer, int size, int capacity)
btBvhSubtreeInfo provides info to gather a subtree of limited size
unsigned short int m_quantizedAabbMax[3]
unsigned short int m_quantizedAabbMin[3]
void setAabbFromQuantizeNode(const btQuantizedBvhNode &quantizedNode)
The btIDebugDraw interface class allows hooking up a debug renderer to visually debug simulations.
virtual void drawAabb(const btVector3 &from, const btVector3 &to, const btVector3 &color)
virtual void processNode(int subPart, int triangleIndex)=0
The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU.
void reportAabbOverlappingNodex(btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
***************************************** expert/internal use only *************************
void setInternalNodeAabbMax(int nodeIndex, const btVector3 &aabbMax)
void setQuantizationValues(const btVector3 &bvhAabbMin, const btVector3 &bvhAabbMax, btScalar quantizationMargin=btScalar(1.0))
***************************************** expert/internal use only *************************
void swapLeafNodes(int firstIndex, int secondIndex)
unsigned calculateSerializeBufferSize() const
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 updateSubtreeHeaders(int leftChildNodexIndex, int rightChildNodexIndex)
void buildTree(int startIndex, int endIndex)
QuantizedNodeArray m_quantizedLeafNodes
btTraversalMode m_traversalMode
void quantize(unsigned short *out, const btVector3 &point, int isMax) const
btVector3 m_bvhQuantization
void setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
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'
@ TRAVERSAL_STACKLESS_CACHE_FRIENDLY
virtual void deSerializeFloat(struct btQuantizedBvhFloatData &quantizedBvhFloatData)
void walkStacklessQuantizedTreeAgainstRay(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
BvhSubtreeInfoArray m_SubtreeHeaders
NodeArray m_contiguousNodes
virtual ~btQuantizedBvh()
static unsigned int getAlignmentSerializationPadding()
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 walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback *nodeCallback, unsigned short int *quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax) const
tree traversal designed for small-memory processors like PS3 SPU
void walkStacklessTree(btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
void walkStacklessTreeAgainstRay(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
void setInternalNodeAabbMin(int nodeIndex, const btVector3 &aabbMin)
two versions, one for quantized and normal nodes.
void mergeInternalNodeAabb(int nodeIndex, const btVector3 &newAabbMin, const btVector3 &newAabbMax)
void walkStacklessQuantizedTree(btNodeOverlapCallback *nodeCallback, unsigned short int *quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax, int startNodeIndex, int endNodeIndex) const
void quantizeWithClamp(unsigned short *out, const btVector3 &point2, int isMax) const
void assignInternalNodeFromLeafNode(int internalNode, int leafNodeIndex)
int sortAndCalcSplittingIndex(int startIndex, int endIndex, int splitAxis)
btVector3 getAabbMax(int nodeIndex) const
btVector3 getAabbMin(int nodeIndex) const
int calcSplittingAxis(int startIndex, int endIndex)
QuantizedNodeArray m_quantizedContiguousNodes
void buildInternal()
buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialize...
btVector3 unQuantize(const unsigned short *vecIn) const
virtual bool serialize(void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian) const
Data buffer MUST be 16 byte aligned.
virtual void deSerializeDouble(struct btQuantizedBvhDoubleData &quantizedBvhDoubleData)
virtual btChunk * allocate(size_t size, int numElements)=0
virtual void * getUniquePointer(void *oldPtr)=0
virtual void finalizeChunk(btChunk *chunk, const char *structType, int chunkCode, void *oldPtr)=0
btVector3 can be used to represent 3D points and vectors.
void setMax(const btVector3 &other)
Set each element to the max of the current values and the values of another btVector3.
btScalar dot(const btVector3 &v) const
Return the dot product.
void deSerializeFloat(const struct btVector3FloatData &dataIn)
void setValue(const btScalar &_x, const btScalar &_y, const btScalar &_z)
void deSerializeDouble(const struct btVector3DoubleData &dataIn)
int maxAxis() const
Return the axis with the largest value Note return values are 0,1,2 for x, y, or z.
void serialize(struct btVector3Data &dataOut) const
void setMin(const btVector3 &other)
Set each element to the min of the current values and the values of another btVector3.
btVector3 & normalize()
Normalize this vector x^2 + y^2 + z^2 = 1.
unsigned short m_quantizedAabbMin[3]
unsigned short m_quantizedAabbMax[3]
btVector3DoubleData m_aabbMaxOrg
btVector3DoubleData m_aabbMinOrg
btVector3FloatData m_aabbMaxOrg
btVector3FloatData m_aabbMinOrg
btOptimizedBvhNode contains both internal and leaf node information.
btBvhSubtreeInfoData * m_subTreeInfoPtr
int m_numContiguousLeafNodes
btVector3DoubleData m_bvhAabbMin
btVector3DoubleData m_bvhAabbMax
int m_numQuantizedContiguousNodes
btVector3DoubleData m_bvhQuantization
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
btOptimizedBvhNodeDoubleData * m_contiguousNodesPtr
btOptimizedBvhNodeFloatData * m_contiguousNodesPtr
btVector3FloatData m_bvhAabbMin
int m_numQuantizedContiguousNodes
btBvhSubtreeInfoData * m_subTreeInfoPtr
int m_numContiguousLeafNodes
btVector3FloatData m_bvhQuantization
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
btVector3FloatData m_bvhAabbMax
int m_escapeIndexOrTriangleIndex
unsigned short m_quantizedAabbMax[3]
unsigned short m_quantizedAabbMin[3]
btQuantizedBvhNode is a compressed aabb node, 16 bytes.
unsigned short int m_quantizedAabbMin[3]
unsigned short int m_quantizedAabbMax[3]
int getEscapeIndex() const
int getTriangleIndex() const