Bullet Collision Detection & Physics Library
btQuantizedBvh.h
Go to the documentation of this file.
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2006 Erwin Coumans http://continuousphysics.com/Bullet/
4 
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages arising from the use of this software.
7 Permission is granted to anyone to use this software for any purpose,
8 including commercial applications, and to alter it and redistribute it freely,
9 subject to the following restrictions:
10 
11 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.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15 
16 #ifndef BT_QUANTIZED_BVH_H
17 #define BT_QUANTIZED_BVH_H
18 
19 class btSerializer;
20 
21 //#define DEBUG_CHECK_DEQUANTIZATION 1
22 #ifdef DEBUG_CHECK_DEQUANTIZATION
23 #ifdef __SPU__
24 #define printf spu_printf
25 #endif //__SPU__
26 
27 #include <stdio.h>
28 #include <stdlib.h>
29 #endif //DEBUG_CHECK_DEQUANTIZATION
30 
31 #include "LinearMath/btVector3.h"
33 
34 #ifdef BT_USE_DOUBLE_PRECISION
35 #define btQuantizedBvhData btQuantizedBvhDoubleData
36 #define btOptimizedBvhNodeData btOptimizedBvhNodeDoubleData
37 #define btQuantizedBvhDataName "btQuantizedBvhDoubleData"
38 #else
39 #define btQuantizedBvhData btQuantizedBvhFloatData
40 #define btOptimizedBvhNodeData btOptimizedBvhNodeFloatData
41 #define btQuantizedBvhDataName "btQuantizedBvhFloatData"
42 #endif
43 
44 
45 
46 //http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/vclrf__m128.asp
47 
48 
49 //Note: currently we have 16 bytes per quantized node
50 #define MAX_SUBTREE_SIZE_IN_BYTES 2048
51 
52 // 10 gives the potential for 1024 parts, with at most 2^21 (2097152) (minus one
53 // actually) triangles each (since the sign bit is reserved
54 #define MAX_NUM_PARTS_IN_BITS 10
55 
59 {
61 
62  //12 bytes
63  unsigned short int m_quantizedAabbMin[3];
64  unsigned short int m_quantizedAabbMax[3];
65  //4 bytes
67 
68  bool isLeafNode() const
69  {
70  //skipindex is negative (internal node), triangleindex >=0 (leafnode)
71  return (m_escapeIndexOrTriangleIndex >= 0);
72  }
73  int getEscapeIndex() const
74  {
75  btAssert(!isLeafNode());
76  return -m_escapeIndexOrTriangleIndex;
77  }
78  int getTriangleIndex() const
79  {
80  btAssert(isLeafNode());
81  unsigned int x=0;
82  unsigned int y = (~(x&0))<<(31-MAX_NUM_PARTS_IN_BITS);
83  // Get only the lower bits where the triangle index is stored
84  return (m_escapeIndexOrTriangleIndex&~(y));
85  }
86  int getPartId() const
87  {
88  btAssert(isLeafNode());
89  // Get only the highest bits where the part index is stored
90  return (m_escapeIndexOrTriangleIndex>>(31-MAX_NUM_PARTS_IN_BITS));
91  }
92 }
93 ;
94 
98 {
100 
101  //32 bytes
104 
105  //4
107 
108  //8
109  //for child nodes
112 
113 //pad the size to 64 bytes
114  char m_padding[20];
115 };
116 
117 
120 {
121 public:
123 
124  //12 bytes
125  unsigned short int m_quantizedAabbMin[3];
126  unsigned short int m_quantizedAabbMax[3];
127  //4 bytes, points to the root of the subtree
129  //4 bytes
131  int m_padding[3];
132 
134  {
135  //memset(&m_padding[0], 0, sizeof(m_padding));
136  }
137 
138 
139  void setAabbFromQuantizeNode(const btQuantizedBvhNode& quantizedNode)
140  {
141  m_quantizedAabbMin[0] = quantizedNode.m_quantizedAabbMin[0];
142  m_quantizedAabbMin[1] = quantizedNode.m_quantizedAabbMin[1];
143  m_quantizedAabbMin[2] = quantizedNode.m_quantizedAabbMin[2];
144  m_quantizedAabbMax[0] = quantizedNode.m_quantizedAabbMax[0];
145  m_quantizedAabbMax[1] = quantizedNode.m_quantizedAabbMax[1];
146  m_quantizedAabbMax[2] = quantizedNode.m_quantizedAabbMax[2];
147  }
148 }
149 ;
150 
151 
153 {
154 public:
156 
157  virtual void processNode(int subPart, int triangleIndex) = 0;
158 };
159 
162 
163 
164 
169 
170 
175 {
176 public:
178  {
179  TRAVERSAL_STACKLESS = 0,
181  TRAVERSAL_RECURSIVE
182  };
183 
184 protected:
185 
186 
190 
191  int m_bulletVersion; //for serialization versioning. It could also be used to detect endianess.
192 
194  //quantization data
196 
197 
198 
203 
206 
207  //This is only used for serialization so we don't have to add serialization directly to btAlignedObjectArray
208  mutable int m_subtreeHeaderCount;
209 
210 
211 
212 
213 
216  void setInternalNodeAabbMin(int nodeIndex, const btVector3& aabbMin)
217  {
218  if (m_useQuantization)
219  {
220  quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[0] ,aabbMin,0);
221  } else
222  {
223  m_contiguousNodes[nodeIndex].m_aabbMinOrg = aabbMin;
224 
225  }
226  }
227  void setInternalNodeAabbMax(int nodeIndex,const btVector3& aabbMax)
228  {
229  if (m_useQuantization)
230  {
231  quantize(&m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[0],aabbMax,1);
232  } else
233  {
234  m_contiguousNodes[nodeIndex].m_aabbMaxOrg = aabbMax;
235  }
236  }
237 
238  btVector3 getAabbMin(int nodeIndex) const
239  {
240  if (m_useQuantization)
241  {
242  return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMin[0]);
243  }
244  //non-quantized
245  return m_leafNodes[nodeIndex].m_aabbMinOrg;
246 
247  }
248  btVector3 getAabbMax(int nodeIndex) const
249  {
250  if (m_useQuantization)
251  {
252  return unQuantize(&m_quantizedLeafNodes[nodeIndex].m_quantizedAabbMax[0]);
253  }
254  //non-quantized
255  return m_leafNodes[nodeIndex].m_aabbMaxOrg;
256 
257  }
258 
259 
260  void setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
261  {
262  if (m_useQuantization)
263  {
264  m_quantizedContiguousNodes[nodeIndex].m_escapeIndexOrTriangleIndex = -escapeIndex;
265  }
266  else
267  {
268  m_contiguousNodes[nodeIndex].m_escapeIndex = escapeIndex;
269  }
270 
271  }
272 
273  void mergeInternalNodeAabb(int nodeIndex,const btVector3& newAabbMin,const btVector3& newAabbMax)
274  {
275  if (m_useQuantization)
276  {
277  unsigned short int quantizedAabbMin[3];
278  unsigned short int quantizedAabbMax[3];
279  quantize(quantizedAabbMin,newAabbMin,0);
280  quantize(quantizedAabbMax,newAabbMax,1);
281  for (int i=0;i<3;i++)
282  {
283  if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] > quantizedAabbMin[i])
284  m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMin[i] = quantizedAabbMin[i];
285 
286  if (m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] < quantizedAabbMax[i])
287  m_quantizedContiguousNodes[nodeIndex].m_quantizedAabbMax[i] = quantizedAabbMax[i];
288 
289  }
290  } else
291  {
292  //non-quantized
293  m_contiguousNodes[nodeIndex].m_aabbMinOrg.setMin(newAabbMin);
294  m_contiguousNodes[nodeIndex].m_aabbMaxOrg.setMax(newAabbMax);
295  }
296  }
297 
298  void swapLeafNodes(int firstIndex,int secondIndex);
299 
300  void assignInternalNodeFromLeafNode(int internalNode,int leafNodeIndex);
301 
302 protected:
303 
304 
305 
306  void buildTree (int startIndex,int endIndex);
307 
308  int calcSplittingAxis(int startIndex,int endIndex);
309 
310  int sortAndCalcSplittingIndex(int startIndex,int endIndex,int splitAxis);
311 
312  void walkStacklessTree(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;
313 
314  void walkStacklessQuantizedTreeAgainstRay(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax, int startNodeIndex,int endNodeIndex) const;
315  void walkStacklessQuantizedTree(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax,int startNodeIndex,int endNodeIndex) const;
316  void walkStacklessTreeAgainstRay(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin, const btVector3& aabbMax, int startNodeIndex,int endNodeIndex) const;
317 
319  void walkStacklessQuantizedTreeCacheFriendly(btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;
320 
322  void walkRecursiveQuantizedTreeAgainstQueryAabb(const btQuantizedBvhNode* currentNode,btNodeOverlapCallback* nodeCallback,unsigned short int* quantizedQueryAabbMin,unsigned short int* quantizedQueryAabbMax) const;
323 
325  void walkRecursiveQuantizedTreeAgainstQuantizedTree(const btQuantizedBvhNode* treeNodeA,const btQuantizedBvhNode* treeNodeB,btNodeOverlapCallback* nodeCallback) const;
326 
327 
328 
329 
330  void updateSubtreeHeaders(int leftChildNodexIndex,int rightChildNodexIndex);
331 
332 public:
333 
335 
336  btQuantizedBvh();
337 
338  virtual ~btQuantizedBvh();
339 
340 
342  void setQuantizationValues(const btVector3& bvhAabbMin,const btVector3& bvhAabbMax,btScalar quantizationMargin=btScalar(1.0));
343  QuantizedNodeArray& getLeafNodeArray() { return m_quantizedLeafNodes; }
345  void buildInternal();
347 
348  void reportAabbOverlappingNodex(btNodeOverlapCallback* nodeCallback,const btVector3& aabbMin,const btVector3& aabbMax) const;
349  void reportRayOverlappingNodex (btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget) const;
350  void reportBoxCastOverlappingNodex(btNodeOverlapCallback* nodeCallback, const btVector3& raySource, const btVector3& rayTarget, const btVector3& aabbMin,const btVector3& aabbMax) const;
351 
352  SIMD_FORCE_INLINE void quantize(unsigned short* out, const btVector3& point,int isMax) const
353  {
354 
355  btAssert(m_useQuantization);
356 
357  btAssert(point.getX() <= m_bvhAabbMax.getX());
358  btAssert(point.getY() <= m_bvhAabbMax.getY());
359  btAssert(point.getZ() <= m_bvhAabbMax.getZ());
360 
361  btAssert(point.getX() >= m_bvhAabbMin.getX());
362  btAssert(point.getY() >= m_bvhAabbMin.getY());
363  btAssert(point.getZ() >= m_bvhAabbMin.getZ());
364 
365  btVector3 v = (point - m_bvhAabbMin) * m_bvhQuantization;
369  if (isMax)
370  {
371  out[0] = (unsigned short) (((unsigned short)(v.getX()+btScalar(1.)) | 1));
372  out[1] = (unsigned short) (((unsigned short)(v.getY()+btScalar(1.)) | 1));
373  out[2] = (unsigned short) (((unsigned short)(v.getZ()+btScalar(1.)) | 1));
374  } else
375  {
376  out[0] = (unsigned short) (((unsigned short)(v.getX()) & 0xfffe));
377  out[1] = (unsigned short) (((unsigned short)(v.getY()) & 0xfffe));
378  out[2] = (unsigned short) (((unsigned short)(v.getZ()) & 0xfffe));
379  }
380 
381 
382 #ifdef DEBUG_CHECK_DEQUANTIZATION
383  btVector3 newPoint = unQuantize(out);
384  if (isMax)
385  {
386  if (newPoint.getX() < point.getX())
387  {
388  printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
389  }
390  if (newPoint.getY() < point.getY())
391  {
392  printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
393  }
394  if (newPoint.getZ() < point.getZ())
395  {
396 
397  printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
398  }
399  } else
400  {
401  if (newPoint.getX() > point.getX())
402  {
403  printf("unconservative X, diffX = %f, oldX=%f,newX=%f\n",newPoint.getX()-point.getX(), newPoint.getX(),point.getX());
404  }
405  if (newPoint.getY() > point.getY())
406  {
407  printf("unconservative Y, diffY = %f, oldY=%f,newY=%f\n",newPoint.getY()-point.getY(), newPoint.getY(),point.getY());
408  }
409  if (newPoint.getZ() > point.getZ())
410  {
411  printf("unconservative Z, diffZ = %f, oldZ=%f,newZ=%f\n",newPoint.getZ()-point.getZ(), newPoint.getZ(),point.getZ());
412  }
413  }
414 #endif //DEBUG_CHECK_DEQUANTIZATION
415 
416  }
417 
418 
419  SIMD_FORCE_INLINE void quantizeWithClamp(unsigned short* out, const btVector3& point2,int isMax) const
420  {
421 
422  btAssert(m_useQuantization);
423 
424  btVector3 clampedPoint(point2);
425  clampedPoint.setMax(m_bvhAabbMin);
426  clampedPoint.setMin(m_bvhAabbMax);
427 
428  quantize(out,clampedPoint,isMax);
429 
430  }
431 
432  SIMD_FORCE_INLINE btVector3 unQuantize(const unsigned short* vecIn) const
433  {
434  btVector3 vecOut;
435  vecOut.setValue(
436  (btScalar)(vecIn[0]) / (m_bvhQuantization.getX()),
437  (btScalar)(vecIn[1]) / (m_bvhQuantization.getY()),
438  (btScalar)(vecIn[2]) / (m_bvhQuantization.getZ()));
439  vecOut += m_bvhAabbMin;
440  return vecOut;
441  }
442 
444  void setTraversalMode(btTraversalMode traversalMode)
445  {
446  m_traversalMode = traversalMode;
447  }
448 
449 
451  {
452  return m_quantizedContiguousNodes;
453  }
454 
455 
457  {
458  return m_SubtreeHeaders;
459  }
460 
462 
464  unsigned calculateSerializeBufferSize() const;
465 
467  virtual bool serialize(void *o_alignedDataBuffer, unsigned i_dataBufferSize, bool i_swapEndian) const;
468 
470  static btQuantizedBvh *deSerializeInPlace(void *i_alignedDataBuffer, unsigned int i_dataBufferSize, bool i_swapEndian);
471 
472  static unsigned int getAlignmentSerializationPadding();
474 
475 
476  virtual int calculateSerializeBufferSizeNew() const;
477 
479  virtual const char* serialize(void* dataBuffer, btSerializer* serializer) const;
480 
481  virtual void deSerializeFloat(struct btQuantizedBvhFloatData& quantizedBvhFloatData);
482 
483  virtual void deSerializeDouble(struct btQuantizedBvhDoubleData& quantizedBvhDoubleData);
484 
485 
487 
489  {
490  return m_useQuantization;
491  }
492 
493 private:
494  // Special "copy" constructor that allows for in-place deserialization
495  // Prevents btVector3's default constructor from being called, but doesn't inialize much else
496  // 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)
497  btQuantizedBvh(btQuantizedBvh &other, bool ownsMemory);
498 
499 }
500 ;
501 
502 
504 {
507  unsigned short m_quantizedAabbMin[3];
508  unsigned short m_quantizedAabbMax[3];
509 };
510 
512 {
518  char m_pad[4];
519 };
520 
522 {
528  char m_pad[4];
529 };
530 
531 
533 {
534  unsigned short m_quantizedAabbMin[3];
535  unsigned short m_quantizedAabbMax[3];
537 };
538 
540 {
553 
554 };
555 
557 {
567 
571 };
572 
573 
575 {
576  return sizeof(btQuantizedBvhData);
577 }
578 
579 
580 
581 #endif //BT_QUANTIZED_BVH_H
btAlignedObjectArray< btQuantizedBvhNode > QuantizedNodeArray
QuantizedNodeArray & getLeafNodeArray()
void quantizeWithClamp(unsigned short *out, const btVector3 &point2, int isMax) const
btTraversalMode m_traversalMode
btVector3DoubleData m_bvhAabbMax
void setValue(const btScalar &_x, const btScalar &_y, const btScalar &_z)
Definition: btVector3.h:640
bool isLeafNode() const
btVector3FloatData m_bvhQuantization
btOptimizedBvhNodeFloatData * m_contiguousNodesPtr
btVector3DoubleData m_bvhAabbMin
btVector3 m_bvhAabbMax
unsigned short m_quantizedAabbMax[3]
btVector3 m_bvhQuantization
#define btAssert(x)
Definition: btScalar.h:101
#define SIMD_FORCE_INLINE
Definition: btScalar.h:58
btAlignedObjectArray< btBvhSubtreeInfo > BvhSubtreeInfoArray
unsigned short m_quantizedAabbMin[3]
void setInternalNodeEscapeIndex(int nodeIndex, int escapeIndex)
btVector3FloatData m_bvhAabbMin
btVector3DoubleData m_bvhQuantization
const btScalar & getZ() const
Return the z value.
Definition: btVector3.h:565
btBvhSubtreeInfo provides info to gather a subtree of limited size
#define MAX_NUM_PARTS_IN_BITS
NodeArray m_contiguousNodes
NodeArray m_leafNodes
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)
virtual void processNode(int subPart, int triangleIndex)=0
btOptimizedBvhNode contains both internal and leaf node information.
const btScalar & getY() const
Return the y value.
Definition: btVector3.h:563
btVector3 getAabbMin(int nodeIndex) const
const btScalar & getX() const
Return the x value.
Definition: btVector3.h:561
void quantize(unsigned short *out, const btVector3 &point, int isMax) const
btVector3 unQuantize(const unsigned short *vecIn) const
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
btQuantizedBvhNode is a compressed aabb node, 16 bytes.
virtual ~btNodeOverlapCallback()
BvhSubtreeInfoArray m_SubtreeHeaders
btVector3 m_bvhAabbMin
void setTraversalMode(btTraversalMode traversalMode)
setTraversalMode let's you choose between stackless, recursive or stackless cache friendly tree trave...
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:83
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:59
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
int getTriangleIndex() const
BvhSubtreeInfoArray & getSubtreeInfoArray()
btVector3FloatData m_bvhAabbMax
btVector3 getAabbMax(int nodeIndex) const
btBvhSubtreeInfoData * m_subTreeInfoPtr
#define BT_DECLARE_ALIGNED_ALLOCATOR()
Definition: btScalar.h:357
The btQuantizedBvh class stores an AABB tree that can be quickly traversed on CPU and Cell SPU...
unsigned short int m_quantizedAabbMin[3]
unsigned short int m_quantizedAabbMax[3]
void setMax(const btVector3 &other)
Set each element to the max of the current values and the values of another btVector3.
Definition: btVector3.h:609
QuantizedNodeArray m_quantizedLeafNodes
unsigned short m_quantizedAabbMax[3]
btAlignedObjectArray< btOptimizedBvhNode > NodeArray
for code readability:
btQuantizedBvhNodeData * m_quantizedContiguousNodesPtr
QuantizedNodeArray & getQuantizedNodeArray()
int getPartId() const
btOptimizedBvhNodeDoubleData * m_contiguousNodesPtr
btVector3DoubleData m_aabbMinOrg
void setMin(const btVector3 &other)
Set each element to the min of the current values and the values of another btVector3.
Definition: btVector3.h:626
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:266
int getEscapeIndex() const
#define btQuantizedBvhData
virtual int calculateSerializeBufferSizeNew() const
QuantizedNodeArray m_quantizedContiguousNodes
btVector3DoubleData m_aabbMaxOrg