Bullet Collision Detection & Physics Library
btDbvt.h
Go to the documentation of this file.
1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2007 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 */
16 
17 #ifndef BT_DYNAMIC_BOUNDING_VOLUME_TREE_H
18 #define BT_DYNAMIC_BOUNDING_VOLUME_TREE_H
19 
21 #include "LinearMath/btVector3.h"
22 #include "LinearMath/btTransform.h"
23 #include "LinearMath/btAabbUtil2.h"
24 
25 //
26 // Compile time configuration
27 //
28 
29 
30 // Implementation profiles
31 #define DBVT_IMPL_GENERIC 0 // Generic implementation
32 #define DBVT_IMPL_SSE 1 // SSE
33 
34 // Template implementation of ICollide
35 #ifdef _WIN32
36 #if (defined (_MSC_VER) && _MSC_VER >= 1400)
37 #define DBVT_USE_TEMPLATE 1
38 #else
39 #define DBVT_USE_TEMPLATE 0
40 #endif
41 #else
42 #define DBVT_USE_TEMPLATE 0
43 #endif
44 
45 // Use only intrinsics instead of inline asm
46 #define DBVT_USE_INTRINSIC_SSE 1
47 
48 // Using memmov for collideOCL
49 #define DBVT_USE_MEMMOVE 1
50 
51 // Enable benchmarking code
52 #define DBVT_ENABLE_BENCHMARK 0
53 
54 // Inlining
55 #define DBVT_INLINE SIMD_FORCE_INLINE
56 
57 // Specific methods implementation
58 
59 //SSE gives errors on a MSVC 7.1
60 #if defined (BT_USE_SSE) //&& defined (_WIN32)
61 #define DBVT_SELECT_IMPL DBVT_IMPL_SSE
62 #define DBVT_MERGE_IMPL DBVT_IMPL_SSE
63 #define DBVT_INT0_IMPL DBVT_IMPL_SSE
64 #else
65 #define DBVT_SELECT_IMPL DBVT_IMPL_GENERIC
66 #define DBVT_MERGE_IMPL DBVT_IMPL_GENERIC
67 #define DBVT_INT0_IMPL DBVT_IMPL_GENERIC
68 #endif
69 
70 #if (DBVT_SELECT_IMPL==DBVT_IMPL_SSE)|| \
71  (DBVT_MERGE_IMPL==DBVT_IMPL_SSE)|| \
72  (DBVT_INT0_IMPL==DBVT_IMPL_SSE)
73 #include <emmintrin.h>
74 #endif
75 
76 //
77 // Auto config and checks
78 //
79 
80 #if DBVT_USE_TEMPLATE
81 #define DBVT_VIRTUAL
82 #define DBVT_VIRTUAL_DTOR(a)
83 #define DBVT_PREFIX template <typename T>
84 #define DBVT_IPOLICY T& policy
85 #define DBVT_CHECKTYPE static const ICollide& typechecker=*(T*)1;(void)typechecker;
86 #else
87 #define DBVT_VIRTUAL_DTOR(a) virtual ~a() {}
88 #define DBVT_VIRTUAL virtual
89 #define DBVT_PREFIX
90 #define DBVT_IPOLICY ICollide& policy
91 #define DBVT_CHECKTYPE
92 #endif
93 
94 #if DBVT_USE_MEMMOVE
95 #if !defined( __CELLOS_LV2__) && !defined(__MWERKS__)
96 #include <memory.h>
97 #endif
98 #include <string.h>
99 #endif
100 
101 #ifndef DBVT_USE_TEMPLATE
102 #error "DBVT_USE_TEMPLATE undefined"
103 #endif
104 
105 #ifndef DBVT_USE_MEMMOVE
106 #error "DBVT_USE_MEMMOVE undefined"
107 #endif
108 
109 #ifndef DBVT_ENABLE_BENCHMARK
110 #error "DBVT_ENABLE_BENCHMARK undefined"
111 #endif
112 
113 #ifndef DBVT_SELECT_IMPL
114 #error "DBVT_SELECT_IMPL undefined"
115 #endif
116 
117 #ifndef DBVT_MERGE_IMPL
118 #error "DBVT_MERGE_IMPL undefined"
119 #endif
120 
121 #ifndef DBVT_INT0_IMPL
122 #error "DBVT_INT0_IMPL undefined"
123 #endif
124 
125 
126 //
127 // Defaults volumes
128 //
129 
130 /* btDbvtAabbMm */
132 {
133  DBVT_INLINE btVector3 Center() const { return((mi+mx)/2); }
134  DBVT_INLINE btVector3 Lengths() const { return(mx-mi); }
135  DBVT_INLINE btVector3 Extents() const { return((mx-mi)/2); }
136  DBVT_INLINE const btVector3& Mins() const { return(mi); }
137  DBVT_INLINE const btVector3& Maxs() const { return(mx); }
138  static inline btDbvtAabbMm FromCE(const btVector3& c,const btVector3& e);
139  static inline btDbvtAabbMm FromCR(const btVector3& c,btScalar r);
140  static inline btDbvtAabbMm FromMM(const btVector3& mi,const btVector3& mx);
141  static inline btDbvtAabbMm FromPoints(const btVector3* pts,int n);
142  static inline btDbvtAabbMm FromPoints(const btVector3** ppts,int n);
143  DBVT_INLINE void Expand(const btVector3& e);
144  DBVT_INLINE void SignedExpand(const btVector3& e);
145  DBVT_INLINE bool Contain(const btDbvtAabbMm& a) const;
146  DBVT_INLINE int Classify(const btVector3& n,btScalar o,int s) const;
147  DBVT_INLINE btScalar ProjectMinimum(const btVector3& v,unsigned signs) const;
148  DBVT_INLINE friend bool Intersect( const btDbvtAabbMm& a,
149  const btDbvtAabbMm& b);
150 
151  DBVT_INLINE friend bool Intersect( const btDbvtAabbMm& a,
152  const btVector3& b);
153 
154  DBVT_INLINE friend btScalar Proximity( const btDbvtAabbMm& a,
155  const btDbvtAabbMm& b);
156  DBVT_INLINE friend int Select( const btDbvtAabbMm& o,
157  const btDbvtAabbMm& a,
158  const btDbvtAabbMm& b);
159  DBVT_INLINE friend void Merge( const btDbvtAabbMm& a,
160  const btDbvtAabbMm& b,
161  btDbvtAabbMm& r);
162  DBVT_INLINE friend bool NotEqual( const btDbvtAabbMm& a,
163  const btDbvtAabbMm& b);
164 
165  DBVT_INLINE btVector3& tMins() { return(mi); }
166  DBVT_INLINE btVector3& tMaxs() { return(mx); }
167 
168 private:
169  DBVT_INLINE void AddSpan(const btVector3& d,btScalar& smi,btScalar& smx) const;
170 private:
172 };
173 
174 // Types
176 
177 /* btDbvtNode */
179 {
182  DBVT_INLINE bool isleaf() const { return(childs[1]==0); }
183  DBVT_INLINE bool isinternal() const { return(!isleaf()); }
184  union
185  {
186  btDbvtNode* childs[2];
187  void* data;
189  };
190 };
191 
193 
194 
198 struct btDbvt
199 {
200  /* Stack element */
201  struct sStkNN
202  {
203  const btDbvtNode* a;
204  const btDbvtNode* b;
205  sStkNN() {}
206  sStkNN(const btDbvtNode* na,const btDbvtNode* nb) : a(na),b(nb) {}
207  };
208  struct sStkNP
209  {
210  const btDbvtNode* node;
211  int mask;
212  sStkNP(const btDbvtNode* n,unsigned m) : node(n),mask(m) {}
213  };
214  struct sStkNPS
215  {
216  const btDbvtNode* node;
217  int mask;
219  sStkNPS() {}
220  sStkNPS(const btDbvtNode* n,unsigned m,btScalar v) : node(n),mask(m),value(v) {}
221  };
222  struct sStkCLN
223  {
224  const btDbvtNode* node;
226  sStkCLN(const btDbvtNode* n,btDbvtNode* p) : node(n),parent(p) {}
227  };
228  // Policies/Interfaces
229 
230  /* ICollide */
231  struct ICollide
232  {
234  DBVT_VIRTUAL void Process(const btDbvtNode*,const btDbvtNode*) {}
237  DBVT_VIRTUAL bool Descent(const btDbvtNode*) { return(true); }
238  DBVT_VIRTUAL bool AllLeaves(const btDbvtNode*) { return(true); }
239  };
240  /* IWriter */
241  struct IWriter
242  {
243  virtual ~IWriter() {}
244  virtual void Prepare(const btDbvtNode* root,int numnodes)=0;
245  virtual void WriteNode(const btDbvtNode*,int index,int parent,int child0,int child1)=0;
246  virtual void WriteLeaf(const btDbvtNode*,int index,int parent)=0;
247  };
248  /* IClone */
249  struct IClone
250  {
251  virtual ~IClone() {}
252  virtual void CloneLeaf(btDbvtNode*) {}
253  };
254 
255  // Constants
256  enum {
257  SIMPLE_STACKSIZE = 64,
258  DOUBLE_STACKSIZE = SIMPLE_STACKSIZE*2
259  };
260 
261  // Fields
264  int m_lkhd;
265  int m_leaves;
266  unsigned m_opath;
267 
268 
270 
271 
272  // Methods
273  btDbvt();
274  ~btDbvt();
275  void clear();
276  bool empty() const { return(0==m_root); }
277  void optimizeBottomUp();
278  void optimizeTopDown(int bu_treshold=128);
279  void optimizeIncremental(int passes);
280  btDbvtNode* insert(const btDbvtVolume& box,void* data);
281  void update(btDbvtNode* leaf,int lookahead=-1);
282  void update(btDbvtNode* leaf,btDbvtVolume& volume);
283  bool update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin);
284  bool update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity);
285  bool update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin);
286  void remove(btDbvtNode* leaf);
287  void write(IWriter* iwriter) const;
288  void clone(btDbvt& dest,IClone* iclone=0) const;
289  static int maxdepth(const btDbvtNode* node);
290  static int countLeaves(const btDbvtNode* node);
291  static void extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves);
292 #if DBVT_ENABLE_BENCHMARK
293  static void benchmark();
294 #else
295  static void benchmark(){}
296 #endif
297  // DBVT_IPOLICY must support ICollide policy/interface
299  static void enumNodes( const btDbvtNode* root,
300  DBVT_IPOLICY);
302  static void enumLeaves( const btDbvtNode* root,
303  DBVT_IPOLICY);
305  void collideTT( const btDbvtNode* root0,
306  const btDbvtNode* root1,
307  DBVT_IPOLICY);
308 
310  void collideTTpersistentStack( const btDbvtNode* root0,
311  const btDbvtNode* root1,
312  DBVT_IPOLICY);
313 #if 0
315  void collideTT( const btDbvtNode* root0,
316  const btDbvtNode* root1,
317  const btTransform& xform,
318  DBVT_IPOLICY);
320  void collideTT( const btDbvtNode* root0,
321  const btTransform& xform0,
322  const btDbvtNode* root1,
323  const btTransform& xform1,
324  DBVT_IPOLICY);
325 #endif
326 
328  void collideTV( const btDbvtNode* root,
329  const btDbvtVolume& volume,
330  DBVT_IPOLICY) const;
331 
333  void collideTVNoStackAlloc( const btDbvtNode* root,
334  const btDbvtVolume& volume,
335  btNodeStack& stack,
336  DBVT_IPOLICY) const;
337 
338 
339 
340 
344  static void rayTest( const btDbvtNode* root,
345  const btVector3& rayFrom,
346  const btVector3& rayTo,
347  DBVT_IPOLICY);
351  void rayTestInternal( const btDbvtNode* root,
352  const btVector3& rayFrom,
353  const btVector3& rayTo,
354  const btVector3& rayDirectionInverse,
355  unsigned int signs[3],
356  btScalar lambda_max,
357  const btVector3& aabbMin,
358  const btVector3& aabbMax,
360  DBVT_IPOLICY) const;
361 
363  static void collideKDOP(const btDbvtNode* root,
364  const btVector3* normals,
365  const btScalar* offsets,
366  int count,
367  DBVT_IPOLICY);
369  static void collideOCL( const btDbvtNode* root,
370  const btVector3* normals,
371  const btScalar* offsets,
372  const btVector3& sortaxis,
373  int count,
374  DBVT_IPOLICY,
375  bool fullsort=true);
377  static void collideTU( const btDbvtNode* root,
378  DBVT_IPOLICY);
379  // Helpers
380  static DBVT_INLINE int nearest(const int* i,const btDbvt::sStkNPS* a,btScalar v,int l,int h)
381  {
382  int m=0;
383  while(l<h)
384  {
385  m=(l+h)>>1;
386  if(a[i[m]].value>=v) l=m+1; else h=m;
387  }
388  return(h);
389  }
392  const sStkNPS& value)
393  {
394  int i;
395  if(ifree.size()>0)
396  { i=ifree[ifree.size()-1];ifree.pop_back();stock[i]=value; }
397  else
398  { i=stock.size();stock.push_back(value); }
399  return(i);
400  }
401  //
402 private:
403  btDbvt(const btDbvt&) {}
404 };
405 
406 //
407 // Inline's
408 //
409 
410 //
412 {
413  btDbvtAabbMm box;
414  box.mi=c-e;box.mx=c+e;
415  return(box);
416 }
417 
418 //
420 {
421  return(FromCE(c,btVector3(r,r,r)));
422 }
423 
424 //
426 {
427  btDbvtAabbMm box;
428  box.mi=mi;box.mx=mx;
429  return(box);
430 }
431 
432 //
434 {
435  btDbvtAabbMm box;
436  box.mi=box.mx=pts[0];
437  for(int i=1;i<n;++i)
438  {
439  box.mi.setMin(pts[i]);
440  box.mx.setMax(pts[i]);
441  }
442  return(box);
443 }
444 
445 //
447 {
448  btDbvtAabbMm box;
449  box.mi=box.mx=*ppts[0];
450  for(int i=1;i<n;++i)
451  {
452  box.mi.setMin(*ppts[i]);
453  box.mx.setMax(*ppts[i]);
454  }
455  return(box);
456 }
457 
458 //
460 {
461  mi-=e;mx+=e;
462 }
463 
464 //
466 {
467  if(e.x()>0) mx.setX(mx.x()+e[0]); else mi.setX(mi.x()+e[0]);
468  if(e.y()>0) mx.setY(mx.y()+e[1]); else mi.setY(mi.y()+e[1]);
469  if(e.z()>0) mx.setZ(mx.z()+e[2]); else mi.setZ(mi.z()+e[2]);
470 }
471 
472 //
474 {
475  return( (mi.x()<=a.mi.x())&&
476  (mi.y()<=a.mi.y())&&
477  (mi.z()<=a.mi.z())&&
478  (mx.x()>=a.mx.x())&&
479  (mx.y()>=a.mx.y())&&
480  (mx.z()>=a.mx.z()));
481 }
482 
483 //
485 {
486  btVector3 pi,px;
487  switch(s)
488  {
489  case (0+0+0): px=btVector3(mi.x(),mi.y(),mi.z());
490  pi=btVector3(mx.x(),mx.y(),mx.z());break;
491  case (1+0+0): px=btVector3(mx.x(),mi.y(),mi.z());
492  pi=btVector3(mi.x(),mx.y(),mx.z());break;
493  case (0+2+0): px=btVector3(mi.x(),mx.y(),mi.z());
494  pi=btVector3(mx.x(),mi.y(),mx.z());break;
495  case (1+2+0): px=btVector3(mx.x(),mx.y(),mi.z());
496  pi=btVector3(mi.x(),mi.y(),mx.z());break;
497  case (0+0+4): px=btVector3(mi.x(),mi.y(),mx.z());
498  pi=btVector3(mx.x(),mx.y(),mi.z());break;
499  case (1+0+4): px=btVector3(mx.x(),mi.y(),mx.z());
500  pi=btVector3(mi.x(),mx.y(),mi.z());break;
501  case (0+2+4): px=btVector3(mi.x(),mx.y(),mx.z());
502  pi=btVector3(mx.x(),mi.y(),mi.z());break;
503  case (1+2+4): px=btVector3(mx.x(),mx.y(),mx.z());
504  pi=btVector3(mi.x(),mi.y(),mi.z());break;
505  }
506  if((btDot(n,px)+o)<0) return(-1);
507  if((btDot(n,pi)+o)>=0) return(+1);
508  return(0);
509 }
510 
511 //
513 {
514  const btVector3* b[]={&mx,&mi};
515  const btVector3 p( b[(signs>>0)&1]->x(),
516  b[(signs>>1)&1]->y(),
517  b[(signs>>2)&1]->z());
518  return(btDot(p,v));
519 }
520 
521 //
523 {
524  for(int i=0;i<3;++i)
525  {
526  if(d[i]<0)
527  { smi+=mx[i]*d[i];smx+=mi[i]*d[i]; }
528  else
529  { smi+=mi[i]*d[i];smx+=mx[i]*d[i]; }
530  }
531 }
532 
533 //
535  const btDbvtAabbMm& b)
536 {
537 #if DBVT_INT0_IMPL == DBVT_IMPL_SSE
538  const __m128 rt(_mm_or_ps( _mm_cmplt_ps(_mm_load_ps(b.mx),_mm_load_ps(a.mi)),
539  _mm_cmplt_ps(_mm_load_ps(a.mx),_mm_load_ps(b.mi))));
540 #if defined (_WIN32)
541  const __int32* pu((const __int32*)&rt);
542 #else
543  const int* pu((const int*)&rt);
544 #endif
545  return((pu[0]|pu[1]|pu[2])==0);
546 #else
547  return( (a.mi.x()<=b.mx.x())&&
548  (a.mx.x()>=b.mi.x())&&
549  (a.mi.y()<=b.mx.y())&&
550  (a.mx.y()>=b.mi.y())&&
551  (a.mi.z()<=b.mx.z())&&
552  (a.mx.z()>=b.mi.z()));
553 #endif
554 }
555 
556 
557 
558 //
560  const btVector3& b)
561 {
562  return( (b.x()>=a.mi.x())&&
563  (b.y()>=a.mi.y())&&
564  (b.z()>=a.mi.z())&&
565  (b.x()<=a.mx.x())&&
566  (b.y()<=a.mx.y())&&
567  (b.z()<=a.mx.z()));
568 }
569 
570 
571 
572 
573 
575 
576 
577 //
579  const btDbvtAabbMm& b)
580 {
581  const btVector3 d=(a.mi+a.mx)-(b.mi+b.mx);
582  return(btFabs(d.x())+btFabs(d.y())+btFabs(d.z()));
583 }
584 
585 
586 
587 //
589  const btDbvtAabbMm& a,
590  const btDbvtAabbMm& b)
591 {
592 #if DBVT_SELECT_IMPL == DBVT_IMPL_SSE
593 
594 #if defined (_WIN32)
595  static ATTRIBUTE_ALIGNED16(const unsigned __int32) mask[]={0x7fffffff,0x7fffffff,0x7fffffff,0x7fffffff};
596 #else
597  static ATTRIBUTE_ALIGNED16(const unsigned int) mask[]={0x7fffffff,0x7fffffff,0x7fffffff,0x00000000 /*0x7fffffff*/};
598 #endif
599 #if DBVT_USE_INTRINSIC_SSE
601 
602  union btSSEUnion
603  {
604  __m128 ssereg;
605  float floats[4];
606  int ints[4];
607  };
608 
609  __m128 omi(_mm_load_ps(o.mi));
610  omi=_mm_add_ps(omi,_mm_load_ps(o.mx));
611  __m128 ami(_mm_load_ps(a.mi));
612  ami=_mm_add_ps(ami,_mm_load_ps(a.mx));
613  ami=_mm_sub_ps(ami,omi);
614  ami=_mm_and_ps(ami,_mm_load_ps((const float*)mask));
615  __m128 bmi(_mm_load_ps(b.mi));
616  bmi=_mm_add_ps(bmi,_mm_load_ps(b.mx));
617  bmi=_mm_sub_ps(bmi,omi);
618  bmi=_mm_and_ps(bmi,_mm_load_ps((const float*)mask));
619  __m128 t0(_mm_movehl_ps(ami,ami));
620  ami=_mm_add_ps(ami,t0);
621  ami=_mm_add_ss(ami,_mm_shuffle_ps(ami,ami,1));
622  __m128 t1(_mm_movehl_ps(bmi,bmi));
623  bmi=_mm_add_ps(bmi,t1);
624  bmi=_mm_add_ss(bmi,_mm_shuffle_ps(bmi,bmi,1));
625 
626  btSSEUnion tmp;
627  tmp.ssereg = _mm_cmple_ss(bmi,ami);
628  return tmp.ints[0]&1;
629 
630 #else
631  ATTRIBUTE_ALIGNED16(__int32 r[1]);
632  __asm
633  {
634  mov eax,o
635  mov ecx,a
636  mov edx,b
637  movaps xmm0,[eax]
638  movaps xmm5,mask
639  addps xmm0,[eax+16]
640  movaps xmm1,[ecx]
641  movaps xmm2,[edx]
642  addps xmm1,[ecx+16]
643  addps xmm2,[edx+16]
644  subps xmm1,xmm0
645  subps xmm2,xmm0
646  andps xmm1,xmm5
647  andps xmm2,xmm5
648  movhlps xmm3,xmm1
649  movhlps xmm4,xmm2
650  addps xmm1,xmm3
651  addps xmm2,xmm4
652  pshufd xmm3,xmm1,1
653  pshufd xmm4,xmm2,1
654  addss xmm1,xmm3
655  addss xmm2,xmm4
656  cmpless xmm2,xmm1
657  movss r,xmm2
658  }
659  return(r[0]&1);
660 #endif
661 #else
662  return(Proximity(o,a)<Proximity(o,b)?0:1);
663 #endif
664 }
665 
666 //
668  const btDbvtAabbMm& b,
669  btDbvtAabbMm& r)
670 {
671 #if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
672  __m128 ami(_mm_load_ps(a.mi));
673  __m128 amx(_mm_load_ps(a.mx));
674  __m128 bmi(_mm_load_ps(b.mi));
675  __m128 bmx(_mm_load_ps(b.mx));
676  ami=_mm_min_ps(ami,bmi);
677  amx=_mm_max_ps(amx,bmx);
678  _mm_store_ps(r.mi,ami);
679  _mm_store_ps(r.mx,amx);
680 #else
681  for(int i=0;i<3;++i)
682  {
683  if(a.mi[i]<b.mi[i]) r.mi[i]=a.mi[i]; else r.mi[i]=b.mi[i];
684  if(a.mx[i]>b.mx[i]) r.mx[i]=a.mx[i]; else r.mx[i]=b.mx[i];
685  }
686 #endif
687 }
688 
689 //
691  const btDbvtAabbMm& b)
692 {
693  return( (a.mi.x()!=b.mi.x())||
694  (a.mi.y()!=b.mi.y())||
695  (a.mi.z()!=b.mi.z())||
696  (a.mx.x()!=b.mx.x())||
697  (a.mx.y()!=b.mx.y())||
698  (a.mx.z()!=b.mx.z()));
699 }
700 
701 //
702 // Inline's
703 //
704 
705 //
707 inline void btDbvt::enumNodes( const btDbvtNode* root,
708  DBVT_IPOLICY)
709 {
711  policy.Process(root);
712  if(root->isinternal())
713  {
714  enumNodes(root->childs[0],policy);
715  enumNodes(root->childs[1],policy);
716  }
717 }
718 
719 //
721 inline void btDbvt::enumLeaves( const btDbvtNode* root,
722  DBVT_IPOLICY)
723 {
725  if(root->isinternal())
726  {
727  enumLeaves(root->childs[0],policy);
728  enumLeaves(root->childs[1],policy);
729  }
730  else
731  {
732  policy.Process(root);
733  }
734 }
735 
736 //
738 inline void btDbvt::collideTT( const btDbvtNode* root0,
739  const btDbvtNode* root1,
740  DBVT_IPOLICY)
741 {
743  if(root0&&root1)
744  {
745  int depth=1;
746  int treshold=DOUBLE_STACKSIZE-4;
748  stkStack.resize(DOUBLE_STACKSIZE);
749  stkStack[0]=sStkNN(root0,root1);
750  do {
751  sStkNN p=stkStack[--depth];
752  if(depth>treshold)
753  {
754  stkStack.resize(stkStack.size()*2);
755  treshold=stkStack.size()-4;
756  }
757  if(p.a==p.b)
758  {
759  if(p.a->isinternal())
760  {
761  stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[0]);
762  stkStack[depth++]=sStkNN(p.a->childs[1],p.a->childs[1]);
763  stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[1]);
764  }
765  }
766  else if(Intersect(p.a->volume,p.b->volume))
767  {
768  if(p.a->isinternal())
769  {
770  if(p.b->isinternal())
771  {
772  stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
773  stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
774  stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
775  stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
776  }
777  else
778  {
779  stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
780  stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
781  }
782  }
783  else
784  {
785  if(p.b->isinternal())
786  {
787  stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
788  stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
789  }
790  else
791  {
792  policy.Process(p.a,p.b);
793  }
794  }
795  }
796  } while(depth);
797  }
798 }
799 
800 
801 
804  const btDbvtNode* root1,
805  DBVT_IPOLICY)
806 {
808  if(root0&&root1)
809  {
810  int depth=1;
811  int treshold=DOUBLE_STACKSIZE-4;
812 
813  m_stkStack.resize(DOUBLE_STACKSIZE);
814  m_stkStack[0]=sStkNN(root0,root1);
815  do {
816  sStkNN p=m_stkStack[--depth];
817  if(depth>treshold)
818  {
819  m_stkStack.resize(m_stkStack.size()*2);
820  treshold=m_stkStack.size()-4;
821  }
822  if(p.a==p.b)
823  {
824  if(p.a->isinternal())
825  {
826  m_stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[0]);
827  m_stkStack[depth++]=sStkNN(p.a->childs[1],p.a->childs[1]);
828  m_stkStack[depth++]=sStkNN(p.a->childs[0],p.a->childs[1]);
829  }
830  }
831  else if(Intersect(p.a->volume,p.b->volume))
832  {
833  if(p.a->isinternal())
834  {
835  if(p.b->isinternal())
836  {
837  m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
838  m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
839  m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
840  m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
841  }
842  else
843  {
844  m_stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
845  m_stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
846  }
847  }
848  else
849  {
850  if(p.b->isinternal())
851  {
852  m_stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
853  m_stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
854  }
855  else
856  {
857  policy.Process(p.a,p.b);
858  }
859  }
860  }
861  } while(depth);
862  }
863 }
864 
865 #if 0
866 //
868 inline void btDbvt::collideTT( const btDbvtNode* root0,
869  const btDbvtNode* root1,
870  const btTransform& xform,
871  DBVT_IPOLICY)
872 {
874  if(root0&&root1)
875  {
876  int depth=1;
877  int treshold=DOUBLE_STACKSIZE-4;
879  stkStack.resize(DOUBLE_STACKSIZE);
880  stkStack[0]=sStkNN(root0,root1);
881  do {
882  sStkNN p=stkStack[--depth];
883  if(Intersect(p.a->volume,p.b->volume,xform))
884  {
885  if(depth>treshold)
886  {
887  stkStack.resize(stkStack.size()*2);
888  treshold=stkStack.size()-4;
889  }
890  if(p.a->isinternal())
891  {
892  if(p.b->isinternal())
893  {
894  stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[0]);
895  stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[0]);
896  stkStack[depth++]=sStkNN(p.a->childs[0],p.b->childs[1]);
897  stkStack[depth++]=sStkNN(p.a->childs[1],p.b->childs[1]);
898  }
899  else
900  {
901  stkStack[depth++]=sStkNN(p.a->childs[0],p.b);
902  stkStack[depth++]=sStkNN(p.a->childs[1],p.b);
903  }
904  }
905  else
906  {
907  if(p.b->isinternal())
908  {
909  stkStack[depth++]=sStkNN(p.a,p.b->childs[0]);
910  stkStack[depth++]=sStkNN(p.a,p.b->childs[1]);
911  }
912  else
913  {
914  policy.Process(p.a,p.b);
915  }
916  }
917  }
918  } while(depth);
919  }
920 }
921 //
923 inline void btDbvt::collideTT( const btDbvtNode* root0,
924  const btTransform& xform0,
925  const btDbvtNode* root1,
926  const btTransform& xform1,
927  DBVT_IPOLICY)
928 {
929  const btTransform xform=xform0.inverse()*xform1;
930  collideTT(root0,root1,xform,policy);
931 }
932 #endif
933 
935 inline void btDbvt::collideTV( const btDbvtNode* root,
936  const btDbvtVolume& vol,
937  DBVT_IPOLICY) const
938 {
940  if(root)
941  {
942  ATTRIBUTE_ALIGNED16(btDbvtVolume) volume(vol);
944  stack.resize(0);
945 #ifndef BT_DISABLE_STACK_TEMP_MEMORY
946  char tempmemory[SIMPLE_STACKSIZE*sizeof(const btDbvtNode*)];
947  stack.initializeFromBuffer(tempmemory, 0, SIMPLE_STACKSIZE);
948 #else
949  stack.reserve(SIMPLE_STACKSIZE);
950 #endif //BT_DISABLE_STACK_TEMP_MEMORY
951 
952  stack.push_back(root);
953  do {
954  const btDbvtNode* n=stack[stack.size()-1];
955  stack.pop_back();
956  if(Intersect(n->volume,volume))
957  {
958  if(n->isinternal())
959  {
960  stack.push_back(n->childs[0]);
961  stack.push_back(n->childs[1]);
962  }
963  else
964  {
965  policy.Process(n);
966  }
967  }
968  } while(stack.size()>0);
969  }
970 }
971 
972 //
974 inline void btDbvt::collideTVNoStackAlloc( const btDbvtNode* root,
975  const btDbvtVolume& vol,
976  btNodeStack& stack,
977  DBVT_IPOLICY) const
978 {
980  if(root)
981  {
982  ATTRIBUTE_ALIGNED16(btDbvtVolume) volume(vol);
983  stack.resize(0);
984  stack.reserve(SIMPLE_STACKSIZE);
985  stack.push_back(root);
986  do {
987  const btDbvtNode* n=stack[stack.size()-1];
988  stack.pop_back();
989  if(Intersect(n->volume,volume))
990  {
991  if(n->isinternal())
992  {
993  stack.push_back(n->childs[0]);
994  stack.push_back(n->childs[1]);
995  }
996  else
997  {
998  policy.Process(n);
999  }
1000  }
1001  } while(stack.size()>0);
1002  }
1003 }
1004 
1005 
1007 inline void btDbvt::rayTestInternal( const btDbvtNode* root,
1008  const btVector3& rayFrom,
1009  const btVector3& rayTo,
1010  const btVector3& rayDirectionInverse,
1011  unsigned int signs[3],
1012  btScalar lambda_max,
1013  const btVector3& aabbMin,
1014  const btVector3& aabbMax,
1016  DBVT_IPOLICY ) const
1017 {
1018  (void) rayTo;
1020  if(root)
1021  {
1022  btVector3 resultNormal;
1023 
1024  int depth=1;
1025  int treshold=DOUBLE_STACKSIZE-2;
1026  stack.resize(DOUBLE_STACKSIZE);
1027  stack[0]=root;
1028  btVector3 bounds[2];
1029  do
1030  {
1031  const btDbvtNode* node=stack[--depth];
1032  bounds[0] = node->volume.Mins()-aabbMax;
1033  bounds[1] = node->volume.Maxs()-aabbMin;
1034  btScalar tmin=1.f,lambda_min=0.f;
1035  unsigned int result1=false;
1036  result1 = btRayAabb2(rayFrom,rayDirectionInverse,signs,bounds,tmin,lambda_min,lambda_max);
1037  if(result1)
1038  {
1039  if(node->isinternal())
1040  {
1041  if(depth>treshold)
1042  {
1043  stack.resize(stack.size()*2);
1044  treshold=stack.size()-2;
1045  }
1046  stack[depth++]=node->childs[0];
1047  stack[depth++]=node->childs[1];
1048  }
1049  else
1050  {
1051  policy.Process(node);
1052  }
1053  }
1054  } while(depth);
1055  }
1056 }
1057 
1058 //
1060 inline void btDbvt::rayTest( const btDbvtNode* root,
1061  const btVector3& rayFrom,
1062  const btVector3& rayTo,
1063  DBVT_IPOLICY)
1064 {
1066  if(root)
1067  {
1068  btVector3 rayDir = (rayTo-rayFrom);
1069  rayDir.normalize ();
1070 
1072  btVector3 rayDirectionInverse;
1073  rayDirectionInverse[0] = rayDir[0] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[0];
1074  rayDirectionInverse[1] = rayDir[1] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[1];
1075  rayDirectionInverse[2] = rayDir[2] == btScalar(0.0) ? btScalar(BT_LARGE_FLOAT) : btScalar(1.0) / rayDir[2];
1076  unsigned int signs[3] = { rayDirectionInverse[0] < 0.0, rayDirectionInverse[1] < 0.0, rayDirectionInverse[2] < 0.0};
1077 
1078  btScalar lambda_max = rayDir.dot(rayTo-rayFrom);
1079 
1080  btVector3 resultNormal;
1081 
1083 
1084  int depth=1;
1085  int treshold=DOUBLE_STACKSIZE-2;
1086 
1087  char tempmemory[DOUBLE_STACKSIZE * sizeof(const btDbvtNode*)];
1088 #ifndef BT_DISABLE_STACK_TEMP_MEMORY
1089  stack.initializeFromBuffer(tempmemory, DOUBLE_STACKSIZE, DOUBLE_STACKSIZE);
1090 #else//BT_DISABLE_STACK_TEMP_MEMORY
1091  stack.resize(DOUBLE_STACKSIZE);
1092 #endif //BT_DISABLE_STACK_TEMP_MEMORY
1093  stack[0]=root;
1094  btVector3 bounds[2];
1095  do {
1096  const btDbvtNode* node=stack[--depth];
1097 
1098  bounds[0] = node->volume.Mins();
1099  bounds[1] = node->volume.Maxs();
1100 
1101  btScalar tmin=1.f,lambda_min=0.f;
1102  unsigned int result1 = btRayAabb2(rayFrom,rayDirectionInverse,signs,bounds,tmin,lambda_min,lambda_max);
1103 
1104 #ifdef COMPARE_BTRAY_AABB2
1105  btScalar param=1.f;
1106  bool result2 = btRayAabb(rayFrom,rayTo,node->volume.Mins(),node->volume.Maxs(),param,resultNormal);
1107  btAssert(result1 == result2);
1108 #endif //TEST_BTRAY_AABB2
1109 
1110  if(result1)
1111  {
1112  if(node->isinternal())
1113  {
1114  if(depth>treshold)
1115  {
1116  stack.resize(stack.size()*2);
1117  treshold=stack.size()-2;
1118  }
1119  stack[depth++]=node->childs[0];
1120  stack[depth++]=node->childs[1];
1121  }
1122  else
1123  {
1124  policy.Process(node);
1125  }
1126  }
1127  } while(depth);
1128 
1129  }
1130 }
1131 
1132 //
1134 inline void btDbvt::collideKDOP(const btDbvtNode* root,
1135  const btVector3* normals,
1136  const btScalar* offsets,
1137  int count,
1138  DBVT_IPOLICY)
1139 {
1141  if(root)
1142  {
1143  const int inside=(1<<count)-1;
1145  int signs[sizeof(unsigned)*8];
1146  btAssert(count<int (sizeof(signs)/sizeof(signs[0])));
1147  for(int i=0;i<count;++i)
1148  {
1149  signs[i]= ((normals[i].x()>=0)?1:0)+
1150  ((normals[i].y()>=0)?2:0)+
1151  ((normals[i].z()>=0)?4:0);
1152  }
1153  stack.reserve(SIMPLE_STACKSIZE);
1154  stack.push_back(sStkNP(root,0));
1155  do {
1156  sStkNP se=stack[stack.size()-1];
1157  bool out=false;
1158  stack.pop_back();
1159  for(int i=0,j=1;(!out)&&(i<count);++i,j<<=1)
1160  {
1161  if(0==(se.mask&j))
1162  {
1163  const int side=se.node->volume.Classify(normals[i],offsets[i],signs[i]);
1164  switch(side)
1165  {
1166  case -1: out=true;break;
1167  case +1: se.mask|=j;break;
1168  }
1169  }
1170  }
1171  if(!out)
1172  {
1173  if((se.mask!=inside)&&(se.node->isinternal()))
1174  {
1175  stack.push_back(sStkNP(se.node->childs[0],se.mask));
1176  stack.push_back(sStkNP(se.node->childs[1],se.mask));
1177  }
1178  else
1179  {
1180  if(policy.AllLeaves(se.node)) enumLeaves(se.node,policy);
1181  }
1182  }
1183  } while(stack.size());
1184  }
1185 }
1186 
1187 //
1189 inline void btDbvt::collideOCL( const btDbvtNode* root,
1190  const btVector3* normals,
1191  const btScalar* offsets,
1192  const btVector3& sortaxis,
1193  int count,
1194  DBVT_IPOLICY,
1195  bool fsort)
1196 {
1198  if(root)
1199  {
1200  const unsigned srtsgns=(sortaxis[0]>=0?1:0)+
1201  (sortaxis[1]>=0?2:0)+
1202  (sortaxis[2]>=0?4:0);
1203  const int inside=(1<<count)-1;
1207  int signs[sizeof(unsigned)*8];
1208  btAssert(count<int (sizeof(signs)/sizeof(signs[0])));
1209  for(int i=0;i<count;++i)
1210  {
1211  signs[i]= ((normals[i].x()>=0)?1:0)+
1212  ((normals[i].y()>=0)?2:0)+
1213  ((normals[i].z()>=0)?4:0);
1214  }
1215  stock.reserve(SIMPLE_STACKSIZE);
1216  stack.reserve(SIMPLE_STACKSIZE);
1217  ifree.reserve(SIMPLE_STACKSIZE);
1218  stack.push_back(allocate(ifree,stock,sStkNPS(root,0,root->volume.ProjectMinimum(sortaxis,srtsgns))));
1219  do {
1220  const int id=stack[stack.size()-1];
1221  sStkNPS se=stock[id];
1222  stack.pop_back();ifree.push_back(id);
1223  if(se.mask!=inside)
1224  {
1225  bool out=false;
1226  for(int i=0,j=1;(!out)&&(i<count);++i,j<<=1)
1227  {
1228  if(0==(se.mask&j))
1229  {
1230  const int side=se.node->volume.Classify(normals[i],offsets[i],signs[i]);
1231  switch(side)
1232  {
1233  case -1: out=true;break;
1234  case +1: se.mask|=j;break;
1235  }
1236  }
1237  }
1238  if(out) continue;
1239  }
1240  if(policy.Descent(se.node))
1241  {
1242  if(se.node->isinternal())
1243  {
1244  const btDbvtNode* pns[]={ se.node->childs[0],se.node->childs[1]};
1245  sStkNPS nes[]={ sStkNPS(pns[0],se.mask,pns[0]->volume.ProjectMinimum(sortaxis,srtsgns)),
1246  sStkNPS(pns[1],se.mask,pns[1]->volume.ProjectMinimum(sortaxis,srtsgns))};
1247  const int q=nes[0].value<nes[1].value?1:0;
1248  int j=stack.size();
1249  if(fsort&&(j>0))
1250  {
1251  /* Insert 0 */
1252  j=nearest(&stack[0],&stock[0],nes[q].value,0,stack.size());
1253  stack.push_back(0);
1254 
1255  //void * memmove ( void * destination, const void * source, size_t num );
1256 
1257 #if DBVT_USE_MEMMOVE
1258  {
1259  int num_items_to_move = stack.size()-1-j;
1260  if(num_items_to_move > 0)
1261  memmove(&stack[j+1],&stack[j],sizeof(int)*num_items_to_move);
1262  }
1263 #else
1264  for(int k=stack.size()-1;k>j;--k) {
1265  stack[k]=stack[k-1];
1266  }
1267 #endif
1268  stack[j]=allocate(ifree,stock,nes[q]);
1269  /* Insert 1 */
1270  j=nearest(&stack[0],&stock[0],nes[1-q].value,j,stack.size());
1271  stack.push_back(0);
1272 #if DBVT_USE_MEMMOVE
1273  {
1274  int num_items_to_move = stack.size()-1-j;
1275  if(num_items_to_move > 0)
1276  memmove(&stack[j+1],&stack[j],sizeof(int)*num_items_to_move);
1277  }
1278 #else
1279  for(int k=stack.size()-1;k>j;--k) {
1280  stack[k]=stack[k-1];
1281  }
1282 #endif
1283  stack[j]=allocate(ifree,stock,nes[1-q]);
1284  }
1285  else
1286  {
1287  stack.push_back(allocate(ifree,stock,nes[q]));
1288  stack.push_back(allocate(ifree,stock,nes[1-q]));
1289  }
1290  }
1291  else
1292  {
1293  policy.Process(se.node,se.value);
1294  }
1295  }
1296  } while(stack.size());
1297  }
1298 }
1299 
1300 //
1302 inline void btDbvt::collideTU( const btDbvtNode* root,
1303  DBVT_IPOLICY)
1304 {
1306  if(root)
1307  {
1309  stack.reserve(SIMPLE_STACKSIZE);
1310  stack.push_back(root);
1311  do {
1312  const btDbvtNode* n=stack[stack.size()-1];
1313  stack.pop_back();
1314  if(policy.Descent(n))
1315  {
1316  if(n->isinternal())
1317  { stack.push_back(n->childs[0]);stack.push_back(n->childs[1]); }
1318  else
1319  { policy.Process(n); }
1320  }
1321  } while(stack.size()>0);
1322  }
1323 }
1324 
1325 //
1326 // PP Cleanup
1327 //
1328 
1329 #undef DBVT_USE_MEMMOVE
1330 #undef DBVT_USE_TEMPLATE
1331 #undef DBVT_VIRTUAL_DTOR
1332 #undef DBVT_VIRTUAL
1333 #undef DBVT_PREFIX
1334 #undef DBVT_IPOLICY
1335 #undef DBVT_CHECKTYPE
1336 #undef DBVT_IMPL_GENERIC
1337 #undef DBVT_IMPL_SSE
1338 #undef DBVT_USE_INTRINSIC_SSE
1339 #undef DBVT_SELECT_IMPL
1340 #undef DBVT_MERGE_IMPL
1341 #undef DBVT_INT0_IMPL
1342 
1343 #endif
static DBVT_PREFIX void collideKDOP(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
Definition: btDbvt.h:1134
void push_back(const T &_Val)
virtual ~IClone()
Definition: btDbvt.h:251
#define BT_LARGE_FLOAT
Definition: btScalar.h:294
static void benchmark()
Definition: btDbvt.h:295
btVector3 mi
Definition: btDbvt.h:171
DBVT_INLINE int Classify(const btVector3 &n, btScalar o, int s) const
Definition: btDbvt.h:484
DBVT_INLINE bool isleaf() const
Definition: btDbvt.h:182
static DBVT_PREFIX void collideOCL(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, const btVector3 &sortaxis, int count, DBVT_IPOLICY, bool fullsort=true)
Definition: btDbvt.h:1189
sStkCLN(const btDbvtNode *n, btDbvtNode *p)
Definition: btDbvt.h:226
DBVT_VIRTUAL void Process(const btDbvtNode *)
Definition: btDbvt.h:235
void setZ(btScalar _z)
Set the z value.
Definition: btVector3.h:583
static DBVT_PREFIX void collideTU(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:1302
void * data
Definition: btDbvt.h:187
#define DBVT_VIRTUAL
Definition: btDbvt.h:88
static btDbvtAabbMm FromPoints(const btVector3 *pts, int n)
Definition: btDbvt.h:433
#define btAssert(x)
Definition: btScalar.h:131
The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes ...
Definition: btDbvt.h:198
static DBVT_INLINE int nearest(const int *i, const btDbvt::sStkNPS *a, btScalar v, int l, int h)
Definition: btDbvt.h:380
btAlignedObjectArray< const btDbvtNode * > btNodeStack
Definition: btDbvt.h:192
const btDbvtNode * b
Definition: btDbvt.h:204
btDbvtNode * m_root
Definition: btDbvt.h:262
static DBVT_PREFIX void rayTest(const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, DBVT_IPOLICY)
rayTest is a re-entrant ray test, and can be called in parallel as long as the btAlignedAlloc is thre...
Definition: btDbvt.h:1060
DBVT_INLINE friend void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
Definition: btDbvt.h:667
const btDbvtNode * node
Definition: btDbvt.h:210
#define DBVT_PREFIX
Definition: btDbvt.h:89
static DBVT_INLINE int allocate(btAlignedObjectArray< int > &ifree, btAlignedObjectArray< sStkNPS > &stock, const sStkNPS &value)
Definition: btDbvt.h:390
DBVT_INLINE bool isinternal() const
Definition: btDbvt.h:183
btScalar dot(const btVector3 &v) const
Return the dot product.
Definition: btVector3.h:235
btVector3 mx
Definition: btDbvt.h:171
btVector3 & normalize()
Normalize this vector x^2 + y^2 + z^2 = 1.
Definition: btVector3.h:309
const btScalar & x() const
Return the x value.
Definition: btVector3.h:587
const btDbvtNode * node
Definition: btDbvt.h:216
#define DBVT_CHECKTYPE
Definition: btDbvt.h:91
void setX(btScalar _x)
Set the x value.
Definition: btVector3.h:579
const btDbvtNode * node
Definition: btDbvt.h:224
btDbvt(const btDbvt &)
Definition: btDbvt.h:403
int size() const
return the number of elements in the array
static btDbvtAabbMm FromCE(const btVector3 &c, const btVector3 &e)
Definition: btDbvt.h:411
DBVT_VIRTUAL bool Descent(const btDbvtNode *)
Definition: btDbvt.h:237
unsigned m_opath
Definition: btDbvt.h:266
btDbvtNode * childs[2]
Definition: btDbvt.h:186
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
Definition: btDbvt.h:425
const btDbvtNode * a
Definition: btDbvt.h:203
DBVT_INLINE btVector3 Lengths() const
Definition: btDbvt.h:134
sStkNN(const btDbvtNode *na, const btDbvtNode *nb)
Definition: btDbvt.h:206
void setY(btScalar _y)
Set the y value.
Definition: btVector3.h:581
void initializeFromBuffer(void *buffer, int size, int capacity)
btScalar value
Definition: btDbvt.h:218
DBVT_PREFIX void collideTVNoStackAlloc(const btDbvtNode *root, const btDbvtVolume &volume, btNodeStack &stack, DBVT_IPOLICY) const
Definition: btDbvt.h:974
sStkNP(const btDbvtNode *n, unsigned m)
Definition: btDbvt.h:212
DBVT_INLINE btScalar ProjectMinimum(const btVector3 &v, unsigned signs) const
Definition: btDbvt.h:512
DBVT_INLINE btVector3 Center() const
Definition: btDbvt.h:133
DBVT_INLINE void Expand(const btVector3 &e)
Definition: btDbvt.h:459
btTransform inverse() const
Return the inverse of this transform.
Definition: btTransform.h:188
static btDbvtAabbMm FromCR(const btVector3 &c, btScalar r)
Definition: btDbvt.h:419
#define DBVT_VIRTUAL_DTOR(a)
Definition: btDbvt.h:87
btAlignedObjectArray< sStkNN > m_stkStack
Definition: btDbvt.h:269
int m_lkhd
Definition: btDbvt.h:264
const btScalar & y() const
Return the y value.
Definition: btVector3.h:589
DBVT_INLINE void AddSpan(const btVector3 &d, btScalar &smi, btScalar &smx) const
Definition: btDbvt.h:522
DBVT_INLINE btVector3 Extents() const
Definition: btDbvt.h:135
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:83
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
DBVT_PREFIX void collideTTpersistentStack(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:803
DBVT_INLINE const btVector3 & Maxs() const
Definition: btDbvt.h:137
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition: btTransform.h:34
static void clear(T &value)
void resize(int newsize, const T &fillData=T())
DBVT_INLINE friend int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:588
btDbvtVolume volume
Definition: btDbvt.h:180
DBVT_VIRTUAL void Process(const btDbvtNode *n, btScalar)
Definition: btDbvt.h:236
int dataAsInt
Definition: btDbvt.h:188
#define DBVT_INLINE
Definition: btDbvt.h:55
bool empty() const
Definition: btDbvt.h:276
DBVT_INLINE friend btScalar Proximity(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:578
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:284
static DBVT_PREFIX void enumLeaves(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:721
DBVT_PREFIX void collideTT(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:738
virtual ~IWriter()
Definition: btDbvt.h:243
btScalar btDot(const btVector3 &v1, const btVector3 &v2)
Return the dot product between two vectors.
Definition: btVector3.h:903
DBVT_INLINE btVector3 & tMaxs()
Definition: btDbvt.h:166
void setMax(const btVector3 &other)
Set each element to the max of the current values and the values of another btVector3.
Definition: btVector3.h:621
DBVT_INLINE bool Contain(const btDbvtAabbMm &a) const
Definition: btDbvt.h:473
static DBVT_PREFIX void enumNodes(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:707
DBVT_INLINE const btVector3 & Mins() const
Definition: btDbvt.h:136
DBVT_PREFIX void rayTestInternal(const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &rayDirectionInverse, unsigned int signs[3], btScalar lambda_max, const btVector3 &aabbMin, const btVector3 &aabbMax, btAlignedObjectArray< const btDbvtNode * > &stack, DBVT_IPOLICY) const
rayTestInternal is faster than rayTest, because it uses a persistent stack (to reduce dynamic memory ...
Definition: btDbvt.h:1007
DBVT_INLINE void SignedExpand(const btVector3 &e)
Definition: btDbvt.h:465
#define DBVT_IPOLICY
Definition: btDbvt.h:90
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)
Definition: btAabbUtil2.h:90
DBVT_PREFIX void collideTV(const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY) const
Definition: btDbvt.h:935
bool btRayAabb(const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &aabbMin, const btVector3 &aabbMax, btScalar &param, btVector3 &normal)
Definition: btAabbUtil2.h:125
DBVT_VIRTUAL bool AllLeaves(const btDbvtNode *)
Definition: btDbvt.h:238
btDbvtAabbMm btDbvtVolume
Definition: btDbvt.h:175
DBVT_INLINE friend bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
void setMin(const btVector3 &other)
Set each element to the min of the current values and the values of another btVector3.
Definition: btVector3.h:638
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:292
btDbvtNode * m_free
Definition: btDbvt.h:263
virtual void CloneLeaf(btDbvtNode *)
Definition: btDbvt.h:252
int m_leaves
Definition: btDbvt.h:265
DBVT_INLINE btVector3 & tMins()
Definition: btDbvt.h:165
btDbvtNode * parent
Definition: btDbvt.h:225
sStkNPS(const btDbvtNode *n, unsigned m, btScalar v)
Definition: btDbvt.h:220
btDbvtNode * parent
Definition: btDbvt.h:181
DBVT_INLINE friend bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
btScalar btFabs(btScalar x)
Definition: btScalar.h:475
const btScalar & z() const
Return the z value.
Definition: btVector3.h:591