26 m_useQuantization(false),
28 m_traversalMode(TRAVERSAL_STACKLESS)
30 ,m_subtreeHeaderCount(0)
79 #ifdef DEBUG_PATCH_COLORS 87 #endif //DEBUG_PATCH_COLORS 94 btVector3 clampValue(quantizationMargin,quantizationMargin,quantizationMargin);
103 unsigned short vecIn[3];
108 m_bvhAabbMin.setMin(v-clampValue);
129 #ifdef DEBUG_TREE_BUILDING 131 int gMaxStackDepth = 0;
132 #endif //DEBUG_TREE_BUILDING 136 #ifdef DEBUG_TREE_BUILDING 138 if (gStackDepth > gMaxStackDepth)
139 gMaxStackDepth = gStackDepth;
140 #endif //DEBUG_TREE_BUILDING 143 int splitAxis, splitIndex, i;
144 int numIndices =endIndex-startIndex;
151 #ifdef DEBUG_TREE_BUILDING 153 #endif //DEBUG_TREE_BUILDING 174 for (i=startIndex;i<endIndex;i++)
193 #ifdef DEBUG_TREE_BUILDING 195 #endif //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};
517 bounds[0] -= aabbMax;
518 bounds[1] -= aabbMin;
524 rayBoxOverlap = aabbOverlap ?
btRayAabb2 (raySource, rayDirectionInverse, sign, bounds, param, 0.0f, lambda_max) :
false;
531 rayBoxOverlap =
btRayAabb(raySource, rayTarget,bounds[0],bounds[1],param, normal);
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);
623 #endif//VISUALLY_ANALYZE_BVH 626 btAssert (walkIterations < subTreeSize);
641 bounds[0] -= aabbMax;
642 bounds[1] -= aabbMin;
645 bool ra2 =
btRayAabb2 (raySource, rayDirection, sign, bounds, param, 0.0, lambda_max);
646 bool ra =
btRayAabb (raySource, rayTarget, bounds[0], bounds[1], param, normal);
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);
720 #endif//VISUALLY_ANALYZE_BVH 723 btAssert (walkIterations < subTreeSize);
730 if (isLeafNode && aabbOverlap)
736 if ((aabbOverlap != 0) || isLeafNode)
743 rootNode += escapeIndex;
744 curIndex += escapeIndex;
841 static const unsigned BVH_ALIGNMENT = 16;
842 static const unsigned BVH_ALIGNMENT_MASK = BVH_ALIGNMENT-1;
844 static 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;
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++)
void walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback *nodeCallback, unsigned short int *quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax) const
tree traversal designed for small-memory processors like PS3 SPU
void walkStacklessTreeAgainstRay(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
void quantizeWithClamp(unsigned short *out, const btVector3 &point2, int isMax) const
btTraversalMode m_traversalMode
void setQuantizationValues(const btVector3 &bvhAabbMin, const btVector3 &bvhAabbMax, btScalar quantizationMargin=btScalar(1.0))
***************************************** expert/internal use only ************************* ...
void walkStacklessTree(btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
void deSerializeDouble(const struct btVector3DoubleData &dataIn)
btVector3DoubleData m_bvhAabbMax
virtual bool serialize(void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian) const
Data buffer MUST be 16 byte aligned.
void setValue(const btScalar &_x, const btScalar &_y, const btScalar &_z)
void assignInternalNodeFromLeafNode(int internalNode, int leafNodeIndex)
btVector3FloatData m_bvhQuantization
void buildInternal()
buildInternal is expert use only: assumes that setQuantizationValues and LeafNodeArray are initialize...
btOptimizedBvhNodeFloatData * m_contiguousNodesPtr
btVector3DoubleData m_bvhAabbMin
int m_numContiguousLeafNodes
virtual ~btQuantizedBvh()
unsigned short m_quantizedAabbMax[3]
btVector3 m_bvhQuantization
virtual void * getUniquePointer(void *oldPtr)=0
#define btOptimizedBvhNodeData
int m_escapeIndexOrTriangleIndex
bool TestAabbAgainstAabb2(const btVector3 &aabbMin1, const btVector3 &aabbMax1, const btVector3 &aabbMin2, const btVector3 &aabbMax2)
conservative test for overlap between two aabbs
unsigned short m_quantizedAabbMin[3]
void setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
btScalar dot(const btVector3 &v) const
Return the dot product.
btVector3FloatData m_bvhAabbMin
btVector3 & normalize()
Normalize this vector x^2 + y^2 + z^2 = 1.
btVector3DoubleData m_bvhQuantization
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0), to reduce performance overhead of run-time memory (de)allocations.
btBvhSubtreeInfo provides info to gather a subtree of limited size
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)
int m_numQuantizedContiguousNodes
NodeArray m_contiguousNodes
int size() const
return the number of elements in the array
void reportRayOverlappingNodex(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget) const
virtual void deSerializeDouble(struct btQuantizedBvhDoubleData &quantizedBvhDoubleData)
void setAabbFromQuantizeNode(const btQuantizedBvhNode &quantizedNode)
void setInternalNodeAabbMax(int nodeIndex, const btVector3 &aabbMax)
btVector3FloatData m_aabbMaxOrg
void mergeInternalNodeAabb(int nodeIndex, const btVector3 &newAabbMin, const btVector3 &newAabbMax)
unsigned testQuantizedAabbAgainstQuantizedAabb(const unsigned short int *aabbMin1, const unsigned short int *aabbMax1, const unsigned short int *aabbMin2, const unsigned short int *aabbMax2)
virtual void processNode(int subPart, int triangleIndex)=0
btOptimizedBvhNode contains both internal and leaf node information.
void serialize(struct btVector3Data &dataOut) const
btVector3 getAabbMin(int nodeIndex) const
void initializeFromBuffer(void *buffer, int size, int capacity)
static unsigned int getAlignmentSerializationPadding()
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)
void btUnSwapVector3Endian(btVector3 &vector)
btUnSwapVector3Endian swaps vector endianness, useful for network and cross-platform serialization ...
void quantize(unsigned short *out, const btVector3 &point, int isMax) const
btVector3 unQuantize(const unsigned short *vecIn) const
void walkStacklessQuantizedTree(btNodeOverlapCallback *nodeCallback, unsigned short int *quantizedQueryAabbMin, unsigned short int *quantizedQueryAabbMax, int startNodeIndex, int endNodeIndex) const
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
btQuantizedBvhNode is a compressed aabb node, 16 bytes.
BvhSubtreeInfoArray m_SubtreeHeaders
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' ...
btVector3 can be used to represent 3D points and vectors.
#define btQuantizedBvhDataName
unsigned short m_quantizedAabbMin[3]
btBvhSubtreeInfoData * m_subTreeInfoPtr
void setInternalNodeAabbMin(int nodeIndex, const btVector3 &aabbMin)
two versions, one for quantized and normal nodes.
btVector3FloatData m_aabbMinOrg
virtual void finalizeChunk(btChunk *chunk, const char *structType, int chunkCode, void *oldPtr)=0
unsigned short int m_quantizedAabbMax[3]
int getTriangleIndex() const
btVector3FloatData m_bvhAabbMax
btVector3 getAabbMax(int nodeIndex) const
int sortAndCalcSplittingIndex(int startIndex, int endIndex, int splitAxis)
virtual void deSerializeFloat(struct btQuantizedBvhFloatData &quantizedBvhFloatData)
void resize(int newsize, const T &fillData=T())
#define BT_BULLET_VERSION
btBvhSubtreeInfoData * m_subTreeInfoPtr
#define MAX_SUBTREE_SIZE_IN_BYTES
The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU...
void swapLeafNodes(int firstIndex, int secondIndex)
unsigned short int m_quantizedAabbMin[3]
unsigned btSwapEndian(unsigned val)
T & expand(const T &fillValue=T())
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
unsigned calculateSerializeBufferSize() const
int m_numQuantizedContiguousNodes
void walkStacklessQuantizedTreeAgainstRay(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax, int startNodeIndex, int endNodeIndex) const
unsigned short int m_quantizedAabbMax[3]
void buildTree(int startIndex, int endIndex)
void reportBoxCastOverlappingNodex(btNodeOverlapCallback *nodeCallback, const btVector3 &raySource, const btVector3 &rayTarget, const btVector3 &aabbMin, const btVector3 &aabbMax) const
void setMax(const btVector3 &other)
Set each element to the max of the current values and the values of another btVector3.
QuantizedNodeArray m_quantizedLeafNodes
void deSerializeFloat(const struct btVector3FloatData &dataIn)
unsigned short m_quantizedAabbMax[3]
unsigned short int m_quantizedAabbMin[3]
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
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)
void reportAabbOverlappingNodex(btNodeOverlapCallback *nodeCallback, const btVector3 &aabbMin, const btVector3 &aabbMax) const
***************************************** expert/internal use only ************************* ...
bool btRayAabb(const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &aabbMin, const btVector3 &aabbMax, btScalar ¶m, btVector3 &normal)
void btSwapVector3Endian(const btVector3 &sourceVec, btVector3 &destVec)
btSwapVector3Endian swaps vector endianness, useful for network and cross-platform serialization ...
virtual btChunk * allocate(size_t size, int numElements)=0
btOptimizedBvhNodeDoubleData * m_contiguousNodesPtr
btVector3DoubleData m_aabbMinOrg
int calcSplittingAxis(int startIndex, int endIndex)
void setMin(const btVector3 &other)
Set each element to the min of the current values and the values of another btVector3.
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
int getEscapeIndex() const
#define btQuantizedBvhData
int m_numContiguousLeafNodes
int maxAxis() const
Return the axis with the largest value Note return values are 0,1,2 for x, y, or z.
QuantizedNodeArray m_quantizedContiguousNodes
btVector3DoubleData m_aabbMaxOrg