Back to index

supertuxkart  0.5+dfsg1
btOptimizedBvh.h
Go to the documentation of this file.
00001 /*
00002 Bullet Continuous Collision Detection and Physics Library
00003 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
00004 
00005 This software is provided 'as-is', without any express or implied warranty.
00006 In no event will the authors be held liable for any damages arising from the use of this software.
00007 Permission is granted to anyone to use this software for any purpose, 
00008 including commercial applications, and to alter it and redistribute it freely, 
00009 subject to the following restrictions:
00010 
00011 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
00012 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
00013 3. This notice may not be removed or altered from any source distribution.
00014 */
00015 
00016 #ifndef OPTIMIZED_BVH_H
00017 #define OPTIMIZED_BVH_H
00018 
00019 //#define DEBUG_CHECK_DEQUANTIZATION 1
00020 #ifdef DEBUG_CHECK_DEQUANTIZATION
00021 #ifdef __SPU__
00022 #define printf spu_printf
00023 #endif //__SPU__
00024 
00025 #include <stdio.h>
00026 #include <stdlib.h>
00027 #endif //DEBUG_CHECK_DEQUANTIZATION
00028 
00029 #include "LinearMath/btVector3.h"
00030 #include "LinearMath/btAlignedAllocator.h"
00031 
00032 
00033 //http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/vclrf__m128.asp
00034 
00035 
00036 
00037 class btStridingMeshInterface;
00038 
00039 //Note: currently we have 16 bytes per quantized node
00040 #define MAX_SUBTREE_SIZE_IN_BYTES  2048
00041 
00042 // 10 gives the potential for 1024 parts, with at most 2^21 (2097152) (minus one
00043 // actually) triangles each (since the sign bit is reserved
00044 #define MAX_NUM_PARTS_IN_BITS 10
00045 
00048 ATTRIBUTE_ALIGNED16  (struct) btQuantizedBvhNode
00049 {
00050        BT_DECLARE_ALIGNED_ALLOCATOR();
00051 
00052        //12 bytes
00053        unsigned short int   m_quantizedAabbMin[3];
00054        unsigned short int   m_quantizedAabbMax[3];
00055        //4 bytes
00056        int    m_escapeIndexOrTriangleIndex;
00057 
00058        bool isLeafNode() const
00059        {
00060               //skipindex is negative (internal node), triangleindex >=0 (leafnode)
00061               return (m_escapeIndexOrTriangleIndex >= 0);
00062        }
00063        int getEscapeIndex() const
00064        {
00065               btAssert(!isLeafNode());
00066               return -m_escapeIndexOrTriangleIndex;
00067        }
00068        int    getTriangleIndex() const
00069        {
00070               btAssert(isLeafNode());
00071               // Get only the lower bits where the triangle index is stored
00072               return (m_escapeIndexOrTriangleIndex&~((~0)<<(31-MAX_NUM_PARTS_IN_BITS)));
00073        }
00074        int    getPartId() const
00075        {
00076               btAssert(isLeafNode());
00077               // Get only the highest bits where the part index is stored
00078               return (m_escapeIndexOrTriangleIndex>>(31-MAX_NUM_PARTS_IN_BITS));
00079        }
00080 }
00081 ;
00082 
00085 ATTRIBUTE_ALIGNED16 (struct) btOptimizedBvhNode
00086 {
00087        BT_DECLARE_ALIGNED_ALLOCATOR();
00088 
00089        //32 bytes
00090        btVector3     m_aabbMinOrg;
00091        btVector3     m_aabbMaxOrg;
00092 
00093        //4
00094        int    m_escapeIndex;
00095 
00096        //8
00097        //for child nodes
00098        int    m_subPart;
00099        int    m_triangleIndex;
00100        int    m_padding[5];//bad, due to alignment
00101 
00102 
00103 };
00104 
00105 
00107 ATTRIBUTE_ALIGNED16(class) btBvhSubtreeInfo
00108 {
00109 public:
00110        BT_DECLARE_ALIGNED_ALLOCATOR();
00111 
00112        //12 bytes
00113        unsigned short int   m_quantizedAabbMin[3];
00114        unsigned short int   m_quantizedAabbMax[3];
00115        //4 bytes, points to the root of the subtree
00116        int                  m_rootNodeIndex;
00117        //4 bytes
00118        int                  m_subtreeSize;
00119        int                  m_padding[3];
00120 
00121        btBvhSubtreeInfo()
00122        {
00123               //memset(&m_padding[0], 0, sizeof(m_padding));
00124        }
00125 
00126 
00127        void   setAabbFromQuantizeNode(const btQuantizedBvhNode& quantizedNode)
00128        {
00129               m_quantizedAabbMin[0] = quantizedNode.m_quantizedAabbMin[0];
00130               m_quantizedAabbMin[1] = quantizedNode.m_quantizedAabbMin[1];
00131               m_quantizedAabbMin[2] = quantizedNode.m_quantizedAabbMin[2];
00132               m_quantizedAabbMax[0] = quantizedNode.m_quantizedAabbMax[0];
00133               m_quantizedAabbMax[1] = quantizedNode.m_quantizedAabbMax[1];
00134               m_quantizedAabbMax[2] = quantizedNode.m_quantizedAabbMax[2];
00135        }
00136 }
00137 ;
00138 
00139 
00140 class btNodeOverlapCallback
00141 {
00142 public:
00143        virtual ~btNodeOverlapCallback() {};
00144 
00145        virtual void processNode(int subPart, int triangleIndex) = 0;
00146 };
00147 
00148 #include "LinearMath/btAlignedAllocator.h"
00149 #include "LinearMath/btAlignedObjectArray.h"
00150 
00151 
00152 
00154 typedef btAlignedObjectArray<btOptimizedBvhNode> NodeArray;
00155 typedef btAlignedObjectArray<btQuantizedBvhNode> QuantizedNodeArray;
00156 typedef btAlignedObjectArray<btBvhSubtreeInfo>          BvhSubtreeInfoArray;
00157 
00158 
00160 ATTRIBUTE_ALIGNED16(class) btOptimizedBvh
00161 {
00162        NodeArray                   m_leafNodes;
00163        NodeArray                   m_contiguousNodes;
00164 
00165        QuantizedNodeArray   m_quantizedLeafNodes;
00166        
00167        QuantizedNodeArray   m_quantizedContiguousNodes;
00168        
00169        int                                m_curNodeIndex;
00170 
00171 
00172        //quantization data
00173        bool                        m_useQuantization;
00174        btVector3                   m_bvhAabbMin;
00175        btVector3                   m_bvhAabbMax;
00176        btVector3                   m_bvhQuantization;
00177 public:
00178        BT_DECLARE_ALIGNED_ALLOCATOR();
00179 
00180        enum btTraversalMode
00181        {
00182               TRAVERSAL_STACKLESS = 0,
00183               TRAVERSAL_STACKLESS_CACHE_FRIENDLY,
00184               TRAVERSAL_RECURSIVE
00185        };
00186 protected:
00187 
00188        btTraversalMode      m_traversalMode;
00189        
00190        BvhSubtreeInfoArray         m_SubtreeHeaders;
00191 
00192        //This is only used for serialization so we don't have to add serialization directly to btAlignedObjectArray
00193        int m_subtreeHeaderCount;
00194 
00195 
00198        void   setInternalNodeAabbMin(int nodeIndex, const btVector3& aabbMin)
00199        {
00200               if (m_useQuantization)
00201               {
00202                      quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[0] ,aabbMin,0);
00203               } else
00204               {
00205                      m_contiguousNodes[nodeIndex].m_aabbMinOrg = aabbMin;
00206 
00207               }
00208        }
00209        void   setInternalNodeAabbMax(int nodeIndex,const btVector3& aabbMax)
00210        {
00211               if (m_useQuantization)
00212               {
00213                      quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[0],aabbMax,1);
00214               } else
00215               {
00216                      m_contiguousNodes[nodeIndex].m_aabbMaxOrg = aabbMax;
00217               }
00218        }
00219 
00220        btVector3 getAabbMin(int nodeIndex) const
00221        {
00222               if (m_useQuantization)
00223               {
00224                      return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMin[0]);
00225               }
00226               //non-quantized
00227               return m_leafNodes[nodeIndex].m_aabbMinOrg;
00228 
00229        }
00230        btVector3 getAabbMax(int nodeIndex) const
00231        {
00232               if (m_useQuantization)
00233               {
00234                      return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMax[0]);
00235               } 
00236               //non-quantized
00237               return m_leafNodes[nodeIndex].m_aabbMaxOrg;
00238               
00239        }
00240 
00241        
00242        void   setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
00243        {
00244               if (m_useQuantization)
00245               {
00246                      m_quantizedContiguousNodes[nodeIndex].m_escapeIndexOrTriangleIndex = -escapeIndex;
00247               } 
00248               else
00249               {
00250                      m_contiguousNodes[nodeIndex].m_escapeIndex = escapeIndex;
00251               }
00252 
00253        }
00254 
00255        void mergeInternalNodeAabb(int nodeIndex,const btVector3& newAabbMin,const btVector3& newAabbMax) 
00256        {
00257               if (m_useQuantization)
00258               {
00259                      unsigned short int quantizedAabbMin[3];
00260                      unsigned short int quantizedAabbMax[3];
00261                      quantize(quantizedAabbMin,newAabbMin,0);
00262                      quantize(quantizedAabbMax,newAabbMax,1);
00263                      for (int i=0;i<3;i++)
00264                      {
00265                             if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] > quantizedAabbMin[i])
00266                                    m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] = quantizedAabbMin[i];
00267 
00268                             if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] < quantizedAabbMax[i])
00269                                    m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] = quantizedAabbMax[i];
00270 
00271                      }
00272               } else
00273               {
00274                      //non-quantized
00275                      m_contiguousNodes[nodeIndex].m_aabbMinOrg.setMin(newAabbMin);
00276                      m_contiguousNodes[nodeIndex].m_aabbMaxOrg.setMax(newAabbMax);         
00277               }
00278        }
00279 
00280        void   swapLeafNodes(int firstIndex,int secondIndex);
00281 
00282        void   assignInternalNodeFromLeafNode(int internalNode,int leafNodeIndex);
00283 
00284 protected:
00285 
00286        
00287 
00288        void   buildTree     (int startIndex,int endIndex);
00289 
00290        int    calcSplittingAxis(int startIndex,int endIndex);
00291 
00292        int    sortAndCalcSplittingIndex(int startIndex,int endIndex,int splitAxis);
00293        
00294        void   walkStacklessTree(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;
00295 
00296        void   walkStacklessQuantizedTreeAgainstRay(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax, int startNodeIndex,int endNodeIndex) const;
00297        void   walkStacklessQuantizedTree(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax,int startNodeIndex,int endNodeIndex) const;
00298 
00300        void   walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;
00301 
00303        void   walkRecursiveQuantizedTreeAgainstQueryAabb(const btQuantizedBvhNode* currentNode,btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;
00304 
00306        void   walkRecursiveQuantizedTreeAgainstQuantizedTree(const btQuantizedBvhNode* treeNodeA,const btQuantizedBvhNode* treeNodeB,btNodeOverlapCallback* nodeCallback) const;
00307        
00308 
00309 #define USE_BANCHLESS 1
00310 #ifdef USE_BANCHLESS
00311        //This block replaces the block below and uses no branches, and replaces the 8 bit return with a 32 bit return for improved performance (~3x on XBox 360)
00312        SIMD_FORCE_INLINE unsigned testQuantizedAabbAgainstQuantizedAabb(unsigned short int* aabbMin1,unsigned short int* aabbMax1,const unsigned short int* aabbMin2,const unsigned short int* aabbMax2) const
00313        {             
00314               return btSelect((unsigned)((aabbMin1[0] <= aabbMax2[0]) & (aabbMax1[0] >= aabbMin2[0])
00315                      & (aabbMin1[2] <= aabbMax2[2]) & (aabbMax1[2] >= aabbMin2[2])
00316                      & (aabbMin1[1] <= aabbMax2[1]) & (aabbMax1[1] >= aabbMin2[1])),
00317                      1, 0);
00318        }
00319 #else
00320        SIMD_FORCE_INLINE bool testQuantizedAabbAgainstQuantizedAabb(unsigned short int* aabbMin1,unsigned short int* aabbMax1,const unsigned short int* aabbMin2,const unsigned short int* aabbMax2) const
00321        {
00322               bool overlap = true;
00323               overlap = (aabbMin1[0] > aabbMax2[0] || aabbMax1[0] < aabbMin2[0]) ? false : overlap;
00324               overlap = (aabbMin1[2] > aabbMax2[2] || aabbMax1[2] < aabbMin2[2]) ? false : overlap;
00325               overlap = (aabbMin1[1] > aabbMax2[1] || aabbMax1[1] < aabbMin2[1]) ? false : overlap;
00326               return overlap;
00327        }
00328 #endif //USE_BANCHLESS
00329 
00330        void   updateSubtreeHeaders(int leftChildNodexIndex,int rightChildNodexIndex);
00331 
00332 public:
00333        btOptimizedBvh();
00334 
00335        virtual ~btOptimizedBvh();
00336 
00337        void   build(btStridingMeshInterface* triangles,bool useQuantizedAabbCompression, const btVector3& bvhAabbMin, const btVector3& bvhAabbMax);
00338 
00340        void   setQuantizationValues(const btVector3& bvhAabbMin,const btVector3& bvhAabbMax,btScalar quantizationMargin=btScalar(1.0));
00341        QuantizedNodeArray&  getLeafNodeArray() {               return m_quantizedLeafNodes;       }
00343        void   buildInternal();
00345 
00346        void   reportAabbOverlappingNodex(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;
00347        void   reportRayOverlappingNodex (btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget) const;
00348        void   reportBoxCastOverlappingNodex(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin,const btVector3& aabbMax) const;
00349 
00350               SIMD_FORCE_INLINE void quantize(unsigned short* out, const btVector3& point,int isMax) const
00351        {
00352 
00353               btAssert(m_useQuantization);
00354 
00355               btAssert(point.getX() <= m_bvhAabbMax.getX());
00356               btAssert(point.getY() <= m_bvhAabbMax.getY());
00357               btAssert(point.getZ() <= m_bvhAabbMax.getZ());
00358 
00359               btAssert(point.getX() >= m_bvhAabbMin.getX());
00360               btAssert(point.getY() >= m_bvhAabbMin.getY());
00361               btAssert(point.getZ() >= m_bvhAabbMin.getZ());
00362 
00363               btVector3 v = (point - m_bvhAabbMin) * m_bvhQuantization;
00367               if (isMax)
00368               {
00369                      out[0] = (unsigned short) (((unsigned short)(v.getX()+btScalar(1.)) | 1));
00370                      out[1] = (unsigned short) (((unsigned short)(v.getY()+btScalar(1.)) | 1));
00371                      out[2] = (unsigned short) (((unsigned short)(v.getZ()+btScalar(1.)) | 1));
00372               } else
00373               {
00374                      out[0] = (unsigned short) (((unsigned short)(v.getX()) & 0xfffe));
00375                      out[1] = (unsigned short) (((unsigned short)(v.getY()) & 0xfffe));
00376                      out[2] = (unsigned short) (((unsigned short)(v.getZ()) & 0xfffe));
00377               }
00378 
00379 
00380 #ifdef DEBUG_CHECK_DEQUANTIZATION
00381               btVector3 newPoint = unQuantize(out);
00382               if (isMax)
00383               {
00384                      if (newPoint.getX() < point.getX())
00385                      {
00386                             printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
00387                      }
00388                      if (newPoint.getY() < point.getY())
00389                      {
00390                             printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
00391                      }
00392                      if (newPoint.getZ() < point.getZ())
00393                      {
00394 
00395                             printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
00396                      }
00397               } else
00398               {
00399                      if (newPoint.getX() > point.getX())
00400                      {
00401                             printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
00402                      }
00403                      if (newPoint.getY() > point.getY())
00404                      {
00405                             printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
00406                      }
00407                      if (newPoint.getZ() > point.getZ())
00408                      {
00409                             printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
00410                      }
00411               }
00412 #endif //DEBUG_CHECK_DEQUANTIZATION
00413 
00414        }
00415 
00416 
00417        SIMD_FORCE_INLINE void quantizeWithClamp(unsigned short* out, const btVector3& point2,int isMax) const
00418        {
00419 
00420               btAssert(m_useQuantization);
00421 
00422               btVector3 clampedPoint(point2);
00423               clampedPoint.setMax(m_bvhAabbMin);
00424               clampedPoint.setMin(m_bvhAabbMax);
00425 
00426               quantize(out,clampedPoint,isMax);
00427 
00428        }
00429        
00430        SIMD_FORCE_INLINE btVector3 unQuantize(const unsigned short* vecIn) const
00431        {
00432                      btVector3     vecOut;
00433                      vecOut.setValue(
00434                      (btScalar)(vecIn[0]) / (m_bvhQuantization.getX()),
00435                      (btScalar)(vecIn[1]) / (m_bvhQuantization.getY()),
00436                      (btScalar)(vecIn[2]) / (m_bvhQuantization.getZ()));
00437                      vecOut += m_bvhAabbMin;
00438                      return vecOut;
00439        }
00440 
00442        void   setTraversalMode(btTraversalMode   traversalMode)
00443        {
00444               m_traversalMode = traversalMode;
00445        }
00446 
00447        void   refit(btStridingMeshInterface* triangles,const btVector3& aabbMin,const btVector3& aabbMax);
00448 
00449        void   refitPartial(btStridingMeshInterface* triangles,const btVector3& aabbMin, const btVector3& aabbMax);
00450 
00451        void   updateBvhNodes(btStridingMeshInterface* meshInterface,int firstNode,int endNode,int index);
00452 
00453 
00454        SIMD_FORCE_INLINE QuantizedNodeArray&     getQuantizedNodeArray()
00455        {      
00456               return m_quantizedContiguousNodes;
00457        }
00458 
00459 
00460        SIMD_FORCE_INLINE BvhSubtreeInfoArray&    getSubtreeInfoArray()
00461        {
00462               return m_SubtreeHeaders;
00463        }
00464 
00465 
00467        unsigned calculateSerializeBufferSize();
00468 
00470        bool serialize(void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian);
00471 
00473        static btOptimizedBvh *deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian);
00474 
00475        static unsigned int getAlignmentSerializationPadding();
00476 
00477        SIMD_FORCE_INLINE bool isQuantized()
00478        {
00479               return m_useQuantization;
00480        }
00481 
00482 private:
00483        // Special "copy" constructor that allows for in-place deserialization
00484        // Prevents btVector3's default constructor from being called, but doesn't inialize much else
00485        // ownsMemory should most likely be false if deserializing, and if you are not, don't call this (it also changes the function signature, which we need)
00486        btOptimizedBvh(btOptimizedBvh &other, bool ownsMemory);
00487 
00488 }
00489 ;
00490 
00491 
00492 #endif //OPTIMIZED_BVH_H
00493 
00494