25 m_useQuantization(false),
27 m_traversalMode(TRAVERSAL_STACKLESS)
30 m_subtreeHeaderCount(0)
72 #ifdef DEBUG_PATCH_COLORS
84 btVector3 clampValue(quantizationMargin, quantizationMargin, quantizationMargin);
93 unsigned short vecIn[3];
116 #ifdef DEBUG_TREE_BUILDING
118 int gMaxStackDepth = 0;
123 #ifdef DEBUG_TREE_BUILDING
125 if (gStackDepth > gMaxStackDepth)
126 gMaxStackDepth = gStackDepth;
129 int splitAxis, splitIndex, i;
130 int numIndices = endIndex - startIndex;
137 #ifdef DEBUG_TREE_BUILDING
159 for (i = startIndex; i < endIndex; i++)
177 #ifdef DEBUG_TREE_BUILDING
187 const int treeSizeInBytes = escapeIndex * sizeQuantizedNode;
206 int leftSubTreeSizeInBytes = leftSubTreeSize *
static_cast<int>(
sizeof(
btQuantizedBvhNode));
210 int rightSubTreeSizeInBytes = rightSubTreeSize *
static_cast<int>(
sizeof(
btQuantizedBvhNode));
235 int splitIndex = startIndex;
236 int numIndices = endIndex - startIndex;
240 for (i = startIndex; i < endIndex; i++)
247 splitValue = means[splitAxis];
250 for (i = startIndex; i < endIndex; i++)
253 if (center[splitAxis] > splitValue)
270 int rangeBalancedIndices = numIndices / 3;
271 bool unbalanced = ((splitIndex <= (startIndex + rangeBalancedIndices)) || (splitIndex >= (endIndex - 1 - rangeBalancedIndices)));
275 splitIndex = startIndex + (numIndices >> 1);
278 bool unbal = (splitIndex == startIndex) || (splitIndex == (endIndex));
291 int numIndices = endIndex - startIndex;
293 for (i = startIndex; i < endIndex; i++)
300 for (i = startIndex; i < endIndex; i++)
304 diff2 = diff2 * diff2;
319 unsigned short int quantizedQueryAabbMin[3];
320 unsigned short int quantizedQueryAabbMax[3];
356 int escapeIndex, curIndex = 0;
357 int walkIterations = 0;
360 unsigned aabbOverlap;
372 if (isLeafNode && (aabbOverlap != 0))
378 if ((aabbOverlap != 0) || isLeafNode)
386 rootNode += escapeIndex;
387 curIndex += escapeIndex;
421 unsigned aabbOverlap;
428 if (aabbOverlap != 0)
451 int escapeIndex, curIndex = 0;
452 int walkIterations = 0;
455 unsigned aabbOverlap = 0;
456 unsigned rayBoxOverlap = 0;
462 rayAabbMin.
setMin(rayTarget);
463 rayAabbMax.
setMax(rayTarget);
466 rayAabbMin += aabbMin;
467 rayAabbMax += aabbMax;
470 btVector3 rayDir = (rayTarget - raySource);
472 lambda_max = rayDir.
dot(rayTarget - raySource);
478 unsigned int sign[3] = {rayDirectionInverse[0] < 0.0, rayDirectionInverse[1] < 0.0, rayDirectionInverse[2] < 0.0};
504 rayBoxOverlap = aabbOverlap ?
btRayAabb2(raySource, rayDirectionInverse, sign,
bounds, param, 0.0f, lambda_max) :
false;
514 if (isLeafNode && (rayBoxOverlap != 0))
520 if ((rayBoxOverlap != 0) || isLeafNode)
528 rootNode += escapeIndex;
529 curIndex += escapeIndex;
540 int curIndex = startNodeIndex;
541 int walkIterations = 0;
542 int subTreeSize = endNodeIndex - startNodeIndex;
550 unsigned boxBoxOverlap = 0;
551 unsigned rayBoxOverlap = 0;
556 btVector3 rayDirection = (rayTarget - raySource);
558 lambda_max = rayDirection.
dot(rayTarget - raySource);
563 unsigned int sign[3] = {rayDirection[0] < 0.0, rayDirection[1] < 0.0, rayDirection[2] < 0.0};
569 rayAabbMin.
setMin(rayTarget);
570 rayAabbMax.
setMax(rayTarget);
573 rayAabbMin += aabbMin;
574 rayAabbMax += aabbMax;
576 unsigned short int quantizedQueryAabbMin[3];
577 unsigned short int quantizedQueryAabbMax[3];
581 while (curIndex < endNodeIndex)
584 #ifdef VISUALLY_ANALYZE_BVH
586 static int drawPatch = 0;
589 if (curIndex == drawPatch)
595 debugDrawerPtr->
drawAabb(aabbMin, aabbMax, color);
600 btAssert(walkIterations < subTreeSize);
619 bool ra2 =
btRayAabb2 (raySource, rayDirection, sign,
bounds, param, 0.0, lambda_max);
623 printf(
"functions don't match\n");
632 rayBoxOverlap =
btRayAabb2(raySource, rayDirection, sign,
bounds, param, 0.0f, lambda_max);
635 rayBoxOverlap =
true;
639 if (isLeafNode && rayBoxOverlap)
645 if ((rayBoxOverlap != 0) || isLeafNode)
653 rootNode += escapeIndex;
654 curIndex += escapeIndex;
665 int curIndex = startNodeIndex;
666 int walkIterations = 0;
667 int subTreeSize = endNodeIndex - startNodeIndex;
675 unsigned aabbOverlap;
677 while (curIndex < endNodeIndex)
680 #ifdef VISUALLY_ANALYZE_BVH
682 static int drawPatch = 0;
685 if (curIndex == drawPatch)
691 debugDrawerPtr->
drawAabb(aabbMin, aabbMax, color);
696 btAssert(walkIterations < subTreeSize);
703 if (isLeafNode && aabbOverlap)
709 if ((aabbOverlap != 0) || isLeafNode)
717 rootNode += escapeIndex;
718 curIndex += escapeIndex;
811 static const unsigned BVH_ALIGNMENT = 16;
812 static const unsigned BVH_ALIGNMENT_MASK = BVH_ALIGNMENT-1;
814 static const unsigned BVH_ALIGNMENT_BLOCKS = 2;
876 unsigned char* nodeData = (
unsigned char*)targetBvh;
879 unsigned sizeToAdd = 0;
880 nodeData += sizeToAdd;
890 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
905 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
931 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
943 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
962 nodeData += sizeToAdd;
1011 *((
void**)o_alignedDataBuffer) = NULL;
1018 if (i_alignedDataBuffer == NULL)
1037 btAssert(calculatedBufSize <= i_dataBufferSize);
1039 if (calculatedBufSize > i_dataBufferSize)
1044 unsigned char* nodeData = (
unsigned char*)bvh;
1047 unsigned sizeToAdd = 0;
1048 nodeData += sizeToAdd;
1062 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
1083 for (
int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
1097 nodeData += sizeToAdd;
1123 m_bvhAabbMax(self.m_bvhAabbMax),
1124 m_bvhQuantization(self.m_bvhQuantization),
1146 for (
int i = 0; i < numElem; i++, memPtr++)
1164 for (
int i = 0; i < numElem; i++, memPtr++)
1185 for (
int i = 0; i < numElem; i++, memPtr++)
1217 for (
int i = 0; i < numElem; i++, memPtr++)
1235 for (
int i = 0; i < numElem; i++, memPtr++)
1256 for (
int i = 0; i < numElem; i++, memPtr++)
1285 if (quantizedData->m_contiguousNodesPtr)
1291 for (
int i = 0; i < numElem; i++, memPtr++)
1299 memset(memPtr->m_pad, 0,
sizeof(memPtr->m_pad));
1307 if (quantizedData->m_quantizedContiguousNodesPtr)
1313 for (
int i = 0; i < numElem; i++, memPtr++)
1330 if (quantizedData->m_subTreeInfoPtr)
1336 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
T & expand(const T &fillValue=T())
void resize(int newsize, const T &fillData=T())
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
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.
btVector3 & normalize()
Normalize this vector x^2 + y^2 + z^2 = 1.
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.
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