diff options
Diffstat (limited to 'extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp')
| -rw-r--r-- | extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp | 657 |
1 files changed, 101 insertions, 556 deletions
diff --git a/extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp b/extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp index 44438a24455..a248c55b571 100644 --- a/extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp +++ b/extern/bullet2/src/BulletCollision/CollisionShapes/btOptimizedBvh.cpp @@ -19,13 +19,12 @@ subject to the following restrictions: #include "LinearMath/btIDebugDraw.h" - -btOptimizedBvh::btOptimizedBvh() : m_useQuantization(false), - m_traversalMode(TRAVERSAL_STACKLESS_CACHE_FRIENDLY) - //m_traversalMode(TRAVERSAL_STACKLESS) - //m_traversalMode(TRAVERSAL_RECURSIVE) +btOptimizedBvh::btOptimizedBvh() { +} +btOptimizedBvh::~btOptimizedBvh() +{ } @@ -80,7 +79,7 @@ void btOptimizedBvh::build(btStridingMeshInterface* triangles, bool useQuantized struct QuantizedNodeTriangleCallback : public btInternalTriangleIndexCallback { QuantizedNodeArray& m_triangleNodes; - const btOptimizedBvh* m_optimizedTree; // for quantization + const btQuantizedBvh* m_optimizedTree; // for quantization QuantizedNodeTriangleCallback& operator=(QuantizedNodeTriangleCallback& other) { @@ -89,14 +88,16 @@ void btOptimizedBvh::build(btStridingMeshInterface* triangles, bool useQuantized return *this; } - QuantizedNodeTriangleCallback(QuantizedNodeArray& triangleNodes,const btOptimizedBvh* tree) + QuantizedNodeTriangleCallback(QuantizedNodeArray& triangleNodes,const btQuantizedBvh* tree) :m_triangleNodes(triangleNodes),m_optimizedTree(tree) { } virtual void internalProcessTriangleIndex(btVector3* triangle,int partId,int triangleIndex) { - btAssert(partId==0); + // The partId and triangle index must fit in the same (positive) integer + btAssert(partId < (1<<MAX_NUM_PARTS_IN_BITS)); + btAssert(triangleIndex < (1<<(31-MAX_NUM_PARTS_IN_BITS))); //negative indices are reserved for escapeIndex btAssert(triangleIndex>=0); @@ -111,10 +112,29 @@ void btOptimizedBvh::build(btStridingMeshInterface* triangles, bool useQuantized aabbMin.setMin(triangle[2]); aabbMax.setMax(triangle[2]); - m_optimizedTree->quantizeWithClamp(&node.m_quantizedAabbMin[0],aabbMin); - m_optimizedTree->quantizeWithClamp(&node.m_quantizedAabbMax[0],aabbMax); + //PCK: add these checks for zero dimensions of aabb + const btScalar MIN_AABB_DIMENSION = btScalar(0.002); + const btScalar MIN_AABB_HALF_DIMENSION = btScalar(0.001); + if (aabbMax.x() - aabbMin.x() < MIN_AABB_DIMENSION) + { + aabbMax.setX(aabbMax.x() + MIN_AABB_HALF_DIMENSION); + aabbMin.setX(aabbMin.x() - MIN_AABB_HALF_DIMENSION); + } + if (aabbMax.y() - aabbMin.y() < MIN_AABB_DIMENSION) + { + aabbMax.setY(aabbMax.y() + MIN_AABB_HALF_DIMENSION); + aabbMin.setY(aabbMin.y() - MIN_AABB_HALF_DIMENSION); + } + if (aabbMax.z() - aabbMin.z() < MIN_AABB_DIMENSION) + { + aabbMax.setZ(aabbMax.z() + MIN_AABB_HALF_DIMENSION); + aabbMin.setZ(aabbMin.z() - MIN_AABB_HALF_DIMENSION); + } - node.m_escapeIndexOrTriangleIndex = triangleIndex; + m_optimizedTree->quantize(&node.m_quantizedAabbMin[0],aabbMin,0); + m_optimizedTree->quantize(&node.m_quantizedAabbMax[0],aabbMax,1); + + node.m_escapeIndexOrTriangleIndex = (partId<<(31-MAX_NUM_PARTS_IN_BITS)) | triangleIndex; m_triangleNodes.push_back(node); } @@ -170,10 +190,45 @@ void btOptimizedBvh::build(btStridingMeshInterface* triangles, bool useQuantized subtree.m_rootNodeIndex = 0; subtree.m_subtreeSize = m_quantizedContiguousNodes[0].isLeafNode() ? 1 : m_quantizedContiguousNodes[0].getEscapeIndex(); } + + //PCK: update the copy of the size + m_subtreeHeaderCount = m_SubtreeHeaders.size(); + + //PCK: clear m_quantizedLeafNodes and m_leafNodes, they are temporary + m_quantizedLeafNodes.clear(); + m_leafNodes.clear(); +} + + + + +void btOptimizedBvh::refit(btStridingMeshInterface* meshInterface,const btVector3& aabbMin,const btVector3& aabbMax) +{ + if (m_useQuantization) + { + + setQuantizationValues(aabbMin,aabbMax); + + updateBvhNodes(meshInterface,0,m_curNodeIndex,0); + + ///now update all subtree headers + + int i; + for (i=0;i<m_SubtreeHeaders.size();i++) + { + btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i]; + subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]); + } + + } else + { + + } } + void btOptimizedBvh::refitPartial(btStridingMeshInterface* meshInterface,const btVector3& aabbMin,const btVector3& aabbMax) { //incrementally initialize quantization values @@ -193,16 +248,17 @@ void btOptimizedBvh::refitPartial(btStridingMeshInterface* meshInterface,const b unsigned short quantizedQueryAabbMin[3]; unsigned short quantizedQueryAabbMax[3]; - quantizeWithClamp(&quantizedQueryAabbMin[0],aabbMin); - quantizeWithClamp(&quantizedQueryAabbMax[0],aabbMax); + quantize(&quantizedQueryAabbMin[0],aabbMin,0); + quantize(&quantizedQueryAabbMax[0],aabbMax,1); int i; for (i=0;i<this->m_SubtreeHeaders.size();i++) { btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i]; - bool overlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,subtree.m_quantizedAabbMin,subtree.m_quantizedAabbMax); - if (overlap) + //PCK: unsigned instead of bool + unsigned overlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,subtree.m_quantizedAabbMin,subtree.m_quantizedAabbMax); + if (overlap != 0) { updateBvhNodes(meshInterface,subtree.m_rootNodeIndex,subtree.m_rootNodeIndex+subtree.m_subtreeSize,i); @@ -212,36 +268,23 @@ void btOptimizedBvh::refitPartial(btStridingMeshInterface* meshInterface,const b } -///just for debugging, to visualize the individual patches/subtrees -#ifdef DEBUG_PATCH_COLORS -btVector3 color[4]= -{ - btVector3(255,0,0), - btVector3(0,255,0), - btVector3(0,0,255), - btVector3(0,255,255) -}; -#endif //DEBUG_PATCH_COLORS - - void btOptimizedBvh::updateBvhNodes(btStridingMeshInterface* meshInterface,int firstNode,int endNode,int index) { (void)index; btAssert(m_useQuantization); - int nodeSubPart=0; + int curNodeSubPart=-1; //get access info to trianglemesh data - const unsigned char *vertexbase; - int numverts; - PHY_ScalarType type; - int stride; - const unsigned char *indexbase; - int indexstride; - int numfaces; - PHY_ScalarType indicestype; - meshInterface->getLockedReadOnlyVertexIndexBase(&vertexbase,numverts, type,stride,&indexbase,indexstride,numfaces,indicestype,nodeSubPart); + const unsigned char *vertexbase = 0; + int numverts = 0; + PHY_ScalarType type = PHY_INTEGER; + int stride = 0; + const unsigned char *indexbase = 0; + int indexstride = 0; + int numfaces = 0; + PHY_ScalarType indicestype = PHY_INTEGER; btVector3 triangleVerts[3]; btVector3 aabbMin,aabbMax; @@ -256,16 +299,26 @@ void btOptimizedBvh::updateBvhNodes(btStridingMeshInterface* meshInterface,int f if (curNode.isLeafNode()) { //recalc aabb from triangle data + int nodeSubPart = curNode.getPartId(); int nodeTriangleIndex = curNode.getTriangleIndex(); + if (nodeSubPart != curNodeSubPart) + { + if (curNodeSubPart >= 0) + meshInterface->unLockReadOnlyVertexBase(curNodeSubPart); + meshInterface->getLockedReadOnlyVertexIndexBase(&vertexbase,numverts, type,stride,&indexbase,indexstride,numfaces,indicestype,nodeSubPart); + + curNodeSubPart = nodeSubPart; + btAssert(indicestype==PHY_INTEGER||indicestype==PHY_SHORT); + } //triangles->getLockedReadOnlyVertexIndexBase(vertexBase,numVerts, - int* gfxbase = (int*)(indexbase+nodeTriangleIndex*indexstride); + unsigned int* gfxbase = (unsigned int*)(indexbase+nodeTriangleIndex*indexstride); for (int j=2;j>=0;j--) { - int graphicsindex = gfxbase[j]; + int graphicsindex = indicestype==PHY_SHORT?((unsigned short*)gfxbase)[j]:gfxbase[j]; btScalar* graphicsbase = (btScalar*)(vertexbase+graphicsindex*stride); #ifdef DEBUG_PATCH_COLORS btVector3 mycolor = color[index&3]; @@ -292,8 +345,8 @@ void btOptimizedBvh::updateBvhNodes(btStridingMeshInterface* meshInterface,int f aabbMin.setMin(triangleVerts[2]); aabbMax.setMax(triangleVerts[2]); - quantizeWithClamp(&curNode.m_quantizedAabbMin[0],aabbMin); - quantizeWithClamp(&curNode.m_quantizedAabbMax[0],aabbMax); + quantize(&curNode.m_quantizedAabbMin[0],aabbMin,0); + quantize(&curNode.m_quantizedAabbMax[0],aabbMax,1); } else { @@ -321,525 +374,17 @@ void btOptimizedBvh::updateBvhNodes(btStridingMeshInterface* meshInterface,int f } - meshInterface->unLockReadOnlyVertexBase(nodeSubPart); - - -} - -void btOptimizedBvh::setQuantizationValues(const btVector3& bvhAabbMin,const btVector3& bvhAabbMax,btScalar quantizationMargin) -{ - //enlarge the AABB to avoid division by zero when initializing the quantization values - btVector3 clampValue(quantizationMargin,quantizationMargin,quantizationMargin); - m_bvhAabbMin = bvhAabbMin - clampValue; - m_bvhAabbMax = bvhAabbMax + clampValue; - btVector3 aabbSize = m_bvhAabbMax - m_bvhAabbMin; - m_bvhQuantization = btVector3(btScalar(65535.0),btScalar(65535.0),btScalar(65535.0)) / aabbSize; -} - - -void btOptimizedBvh::refit(btStridingMeshInterface* meshInterface) -{ - if (m_useQuantization) - { - //calculate new aabb - btVector3 aabbMin,aabbMax; - meshInterface->calculateAabbBruteForce(aabbMin,aabbMax); - - setQuantizationValues(aabbMin,aabbMax); - - updateBvhNodes(meshInterface,0,m_curNodeIndex,0); - - ///now update all subtree headers - - int i; - for (i=0;i<m_SubtreeHeaders.size();i++) - { - btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i]; - subtree.setAabbFromQuantizeNode(m_quantizedContiguousNodes[subtree.m_rootNodeIndex]); - } - - } else - { - - } -} - - - -btOptimizedBvh::~btOptimizedBvh() -{ -} - -#ifdef DEBUG_TREE_BUILDING -int gStackDepth = 0; -int gMaxStackDepth = 0; -#endif //DEBUG_TREE_BUILDING - -void btOptimizedBvh::buildTree (int startIndex,int endIndex) -{ -#ifdef DEBUG_TREE_BUILDING - gStackDepth++; - if (gStackDepth > gMaxStackDepth) - gMaxStackDepth = gStackDepth; -#endif //DEBUG_TREE_BUILDING - - - int splitAxis, splitIndex, i; - int numIndices =endIndex-startIndex; - int curIndex = m_curNodeIndex; - - assert(numIndices>0); - - if (numIndices==1) - { -#ifdef DEBUG_TREE_BUILDING - gStackDepth--; -#endif //DEBUG_TREE_BUILDING - - assignInternalNodeFromLeafNode(m_curNodeIndex,startIndex); - - m_curNodeIndex++; - return; - } - //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'. - - splitAxis = calcSplittingAxis(startIndex,endIndex); - - splitIndex = sortAndCalcSplittingIndex(startIndex,endIndex,splitAxis); - - int internalNodeIndex = m_curNodeIndex; - - setInternalNodeAabbMax(m_curNodeIndex,btVector3(btScalar(-1e30),btScalar(-1e30),btScalar(-1e30))); - setInternalNodeAabbMin(m_curNodeIndex,btVector3(btScalar(1e30),btScalar(1e30),btScalar(1e30))); - - for (i=startIndex;i<endIndex;i++) - { - mergeInternalNodeAabb(m_curNodeIndex,getAabbMin(i),getAabbMax(i)); - } - - m_curNodeIndex++; - - - //internalNode->m_escapeIndex; - - int leftChildNodexIndex = m_curNodeIndex; - - //build left child tree - buildTree(startIndex,splitIndex); - - int rightChildNodexIndex = m_curNodeIndex; - //build right child tree - buildTree(splitIndex,endIndex); - -#ifdef DEBUG_TREE_BUILDING - gStackDepth--; -#endif //DEBUG_TREE_BUILDING - - int escapeIndex = m_curNodeIndex - curIndex; - - if (m_useQuantization) - { - //escapeIndex is the number of nodes of this subtree - const int sizeQuantizedNode =sizeof(btQuantizedBvhNode); - const int treeSizeInBytes = escapeIndex * sizeQuantizedNode; - if (treeSizeInBytes > MAX_SUBTREE_SIZE_IN_BYTES) - { - updateSubtreeHeaders(leftChildNodexIndex,rightChildNodexIndex); - } - } - - setInternalNodeEscapeIndex(internalNodeIndex,escapeIndex); - -} - -void btOptimizedBvh::updateSubtreeHeaders(int leftChildNodexIndex,int rightChildNodexIndex) -{ - btAssert(m_useQuantization); - - btQuantizedBvhNode& leftChildNode = m_quantizedContiguousNodes[leftChildNodexIndex]; - int leftSubTreeSize = leftChildNode.isLeafNode() ? 1 : leftChildNode.getEscapeIndex(); - int leftSubTreeSizeInBytes = leftSubTreeSize * sizeof(btQuantizedBvhNode); - - btQuantizedBvhNode& rightChildNode = m_quantizedContiguousNodes[rightChildNodexIndex]; - int rightSubTreeSize = rightChildNode.isLeafNode() ? 1 : rightChildNode.getEscapeIndex(); - int rightSubTreeSizeInBytes = rightSubTreeSize * sizeof(btQuantizedBvhNode); - - if(leftSubTreeSizeInBytes <= MAX_SUBTREE_SIZE_IN_BYTES) - { - btBvhSubtreeInfo& subtree = m_SubtreeHeaders.expand(); - subtree.setAabbFromQuantizeNode(leftChildNode); - subtree.m_rootNodeIndex = leftChildNodexIndex; - subtree.m_subtreeSize = leftSubTreeSize; - } - - if(rightSubTreeSizeInBytes <= MAX_SUBTREE_SIZE_IN_BYTES) - { - btBvhSubtreeInfo& subtree = m_SubtreeHeaders.expand(); - subtree.setAabbFromQuantizeNode(rightChildNode); - subtree.m_rootNodeIndex = rightChildNodexIndex; - subtree.m_subtreeSize = rightSubTreeSize; - } -} - - -int btOptimizedBvh::sortAndCalcSplittingIndex(int startIndex,int endIndex,int splitAxis) -{ - int i; - int splitIndex =startIndex; - int numIndices = endIndex - startIndex; - btScalar splitValue; - - btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.)); - for (i=startIndex;i<endIndex;i++) - { - btVector3 center = btScalar(0.5)*(getAabbMax(i)+getAabbMin(i)); - means+=center; - } - means *= (btScalar(1.)/(btScalar)numIndices); - - splitValue = means[splitAxis]; - - //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'. - for (i=startIndex;i<endIndex;i++) - { - btVector3 center = btScalar(0.5)*(getAabbMax(i)+getAabbMin(i)); - if (center[splitAxis] > splitValue) - { - //swap - swapLeafNodes(i,splitIndex); - splitIndex++; - } - } - - //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex - //otherwise the tree-building might fail due to stack-overflows in certain cases. - //unbalanced1 is unsafe: it can cause stack overflows - //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1))); - - //unbalanced2 should work too: always use center (perfect balanced trees) - //bool unbalanced2 = true; - - //this should be safe too: - int rangeBalancedIndices = numIndices/3; - bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices))); - - if (unbalanced) - { - splitIndex = startIndex+ (numIndices>>1); - } - - bool unbal = (splitIndex==startIndex) || (splitIndex == (endIndex)); - btAssert(!unbal); - - return splitIndex; -} - - -int btOptimizedBvh::calcSplittingAxis(int startIndex,int endIndex) -{ - int i; - - btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.)); - btVector3 variance(btScalar(0.),btScalar(0.),btScalar(0.)); - int numIndices = endIndex-startIndex; - - for (i=startIndex;i<endIndex;i++) - { - btVector3 center = btScalar(0.5)*(getAabbMax(i)+getAabbMin(i)); - means+=center; - } - means *= (btScalar(1.)/(btScalar)numIndices); - - for (i=startIndex;i<endIndex;i++) - { - btVector3 center = btScalar(0.5)*(getAabbMax(i)+getAabbMin(i)); - btVector3 diff2 = center-means; - diff2 = diff2 * diff2; - variance += diff2; - } - variance *= (btScalar(1.)/ ((btScalar)numIndices-1) ); - - return variance.maxAxis(); -} - - - -void btOptimizedBvh::reportAabbOverlappingNodex(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const -{ - //either choose recursive traversal (walkTree) or stackless (walkStacklessTree) - - - if (m_useQuantization) - { - ///quantize query AABB - unsigned short int quantizedQueryAabbMin[3]; - unsigned short int quantizedQueryAabbMax[3]; - quantizeWithClamp(quantizedQueryAabbMin,aabbMin); - quantizeWithClamp(quantizedQueryAabbMax,aabbMax); - - switch (m_traversalMode) - { - case TRAVERSAL_STACKLESS: - walkStacklessQuantizedTree(nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax,0,m_curNodeIndex); - break; - case TRAVERSAL_STACKLESS_CACHE_FRIENDLY: - walkStacklessQuantizedTreeCacheFriendly(nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax); - break; - case TRAVERSAL_RECURSIVE: - { - const btQuantizedBvhNode* rootNode = &m_quantizedContiguousNodes[0]; - walkRecursiveQuantizedTreeAgainstQueryAabb(rootNode,nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax); - } - break; - default: - //unsupported - btAssert(0); - } - } else - { - walkStacklessTree(nodeCallback,aabbMin,aabbMax); - } -} - - -int maxIterations = 0; - -void btOptimizedBvh::walkStacklessTree(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const -{ - btAssert(!m_useQuantization); - - const btOptimizedBvhNode* rootNode = &m_contiguousNodes[0]; - int escapeIndex, curIndex = 0; - int walkIterations = 0; - bool aabbOverlap, isLeafNode; - - while (curIndex < m_curNodeIndex) - { - //catch bugs in tree data - assert (walkIterations < m_curNodeIndex); - - walkIterations++; - aabbOverlap = TestAabbAgainstAabb2(aabbMin,aabbMax,rootNode->m_aabbMinOrg,rootNode->m_aabbMaxOrg); - isLeafNode = rootNode->m_escapeIndex == -1; - - if (isLeafNode && aabbOverlap) - { - nodeCallback->processNode(rootNode->m_subPart,rootNode->m_triangleIndex); - } - - if (aabbOverlap || isLeafNode) - { - rootNode++; - curIndex++; - } else - { - escapeIndex = rootNode->m_escapeIndex; - rootNode += escapeIndex; - curIndex += escapeIndex; - } - } - if (maxIterations < walkIterations) - maxIterations = walkIterations; - -} + if (curNodeSubPart >= 0) + meshInterface->unLockReadOnlyVertexBase(curNodeSubPart); -/* -///this was the original recursive traversal, before we optimized towards stackless traversal -void btOptimizedBvh::walkTree(btOptimizedBvhNode* rootNode,btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const -{ - bool isLeafNode, aabbOverlap = TestAabbAgainstAabb2(aabbMin,aabbMax,rootNode->m_aabbMin,rootNode->m_aabbMax); - if (aabbOverlap) - { - isLeafNode = (!rootNode->m_leftChild && !rootNode->m_rightChild); - if (isLeafNode) - { - nodeCallback->processNode(rootNode); - } else - { - walkTree(rootNode->m_leftChild,nodeCallback,aabbMin,aabbMax); - walkTree(rootNode->m_rightChild,nodeCallback,aabbMin,aabbMax); - } - } - -} -*/ - -void btOptimizedBvh::walkRecursiveQuantizedTreeAgainstQueryAabb(const btQuantizedBvhNode* currentNode,btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const -{ - btAssert(m_useQuantization); - - bool aabbOverlap, isLeafNode; - - aabbOverlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,currentNode->m_quantizedAabbMin,currentNode->m_quantizedAabbMax); - isLeafNode = currentNode->isLeafNode(); - if (aabbOverlap) - { - if (isLeafNode) - { - nodeCallback->processNode(0,currentNode->getTriangleIndex()); - } else - { - //process left and right children - const btQuantizedBvhNode* leftChildNode = currentNode+1; - walkRecursiveQuantizedTreeAgainstQueryAabb(leftChildNode,nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax); - - const btQuantizedBvhNode* rightChildNode = leftChildNode->isLeafNode() ? leftChildNode+1:leftChildNode+leftChildNode->getEscapeIndex(); - walkRecursiveQuantizedTreeAgainstQueryAabb(rightChildNode,nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax); - } - } } - - - - - - -void btOptimizedBvh::walkStacklessQuantizedTree(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax,int startNodeIndex,int endNodeIndex) const +///deSerializeInPlace loads and initializes a BVH from a buffer in memory 'in place' +btOptimizedBvh* btOptimizedBvh::deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian) { - btAssert(m_useQuantization); - - int curIndex = startNodeIndex; - int walkIterations = 0; - int subTreeSize = endNodeIndex - startNodeIndex; - - const btQuantizedBvhNode* rootNode = &m_quantizedContiguousNodes[startNodeIndex]; - int escapeIndex; + btQuantizedBvh* bvh = btQuantizedBvh::deSerializeInPlace(i_alignedDataBuffer,i_dataBufferSize,i_swapEndian); - bool aabbOverlap, isLeafNode; - - while (curIndex < endNodeIndex) - { - -//#define VISUALLY_ANALYZE_BVH 1 -#ifdef VISUALLY_ANALYZE_BVH - //some code snippet to debugDraw aabb, to visually analyze bvh structure - static int drawPatch = 0; - //need some global access to a debugDrawer - extern btIDebugDraw* debugDrawerPtr; - if (curIndex==drawPatch) - { - btVector3 aabbMin,aabbMax; - aabbMin = unQuantize(rootNode->m_quantizedAabbMin); - aabbMax = unQuantize(rootNode->m_quantizedAabbMax); - btVector3 color(1,0,0); - debugDrawerPtr->drawAabb(aabbMin,aabbMax,color); - } -#endif//VISUALLY_ANALYZE_BVH - - //catch bugs in tree data - assert (walkIterations < subTreeSize); - - walkIterations++; - aabbOverlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,rootNode->m_quantizedAabbMin,rootNode->m_quantizedAabbMax); - isLeafNode = rootNode->isLeafNode(); - - if (isLeafNode && aabbOverlap) - { - nodeCallback->processNode(0,rootNode->getTriangleIndex()); - } - - if (aabbOverlap || isLeafNode) - { - rootNode++; - curIndex++; - } else - { - escapeIndex = rootNode->getEscapeIndex(); - rootNode += escapeIndex; - curIndex += escapeIndex; - } - } - if (maxIterations < walkIterations) - maxIterations = walkIterations; - -} - -//This traversal can be called from Playstation 3 SPU -void btOptimizedBvh::walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const -{ - btAssert(m_useQuantization); - - int i; - - - for (i=0;i<this->m_SubtreeHeaders.size();i++) - { - const btBvhSubtreeInfo& subtree = m_SubtreeHeaders[i]; - - bool overlap = testQuantizedAabbAgainstQuantizedAabb(quantizedQueryAabbMin,quantizedQueryAabbMax,subtree.m_quantizedAabbMin,subtree.m_quantizedAabbMax); - if (overlap) - { - walkStacklessQuantizedTree(nodeCallback,quantizedQueryAabbMin,quantizedQueryAabbMax, - subtree.m_rootNodeIndex, - subtree.m_rootNodeIndex+subtree.m_subtreeSize); - } - } -} - - - - -void btOptimizedBvh::reportSphereOverlappingNodex(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const -{ - (void)nodeCallback; - (void)aabbMin; - (void)aabbMax; - //not yet, please use aabb - btAssert(0); -} - - -void btOptimizedBvh::quantizeWithClamp(unsigned short* out, const btVector3& point) const -{ - - btAssert(m_useQuantization); - - btVector3 clampedPoint(point); - clampedPoint.setMax(m_bvhAabbMin); - clampedPoint.setMin(m_bvhAabbMax); - - btVector3 v = (clampedPoint - m_bvhAabbMin) * m_bvhQuantization; - out[0] = (unsigned short)(v.getX()+0.5f); - out[1] = (unsigned short)(v.getY()+0.5f); - out[2] = (unsigned short)(v.getZ()+0.5f); -} - -btVector3 btOptimizedBvh::unQuantize(const unsigned short* vecIn) const -{ - btVector3 vecOut; - vecOut.setValue( - (btScalar)(vecIn[0]) / (m_bvhQuantization.getX()), - (btScalar)(vecIn[1]) / (m_bvhQuantization.getY()), - (btScalar)(vecIn[2]) / (m_bvhQuantization.getZ())); - vecOut += m_bvhAabbMin; - return vecOut; -} - - -void btOptimizedBvh::swapLeafNodes(int i,int splitIndex) -{ - if (m_useQuantization) - { - btQuantizedBvhNode tmp = m_quantizedLeafNodes[i]; - m_quantizedLeafNodes[i] = m_quantizedLeafNodes[splitIndex]; - m_quantizedLeafNodes[splitIndex] = tmp; - } else - { - btOptimizedBvhNode tmp = m_leafNodes[i]; - m_leafNodes[i] = m_leafNodes[splitIndex]; - m_leafNodes[splitIndex] = tmp; - } -} - -void btOptimizedBvh::assignInternalNodeFromLeafNode(int internalNode,int leafNodeIndex) -{ - if (m_useQuantization) - { - m_quantizedContiguousNodes[internalNode] = m_quantizedLeafNodes[leafNodeIndex]; - } else - { - m_contiguousNodes[internalNode] = m_leafNodes[leafNodeIndex]; - } + //we don't add additional data so just do a static upcast + return static_cast<btOptimizedBvh*>(bvh); } |