Bullet Collision Detection & Physics Library
btDbvt.h
Go to the documentation of this file.
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2007 Erwin Coumans http://continuousphysics.com/Bullet/
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. 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
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
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
167
168private:
169 DBVT_INLINE void AddSpan(const btVector3& d,btScalar& smi,btScalar& smx) const;
170private:
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 {
187 void* data;
189 };
190};
191
193
194
198struct btDbvt
199{
200 /* Stack element */
201 struct sStkNN
202 {
203 const btDbvtNode* a;
204 const btDbvtNode* b;
206 sStkNN(const btDbvtNode* na,const btDbvtNode* nb) : a(na),b(nb) {}
207 };
208 struct sStkNP
209 {
211 int mask;
212 sStkNP(const btDbvtNode* n,unsigned m) : node(n),mask(m) {}
213 };
214 struct sStkNPS
215 {
217 int mask;
220 sStkNPS(const btDbvtNode* n,unsigned m,btScalar v) : node(n),mask(m),value(v) {}
221 };
222 struct sStkCLN
223 {
226 sStkCLN(const btDbvtNode* n,btDbvtNode* p) : node(n),parent(p) {}
227 };
228 // Policies/Interfaces
229
230 /* ICollide */
231 struct ICollide
232 {
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 {
259 };
260
261 // Fields
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);
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,
302 static void enumLeaves( const btDbvtNode* root,
305 void collideTT( const btDbvtNode* root0,
306 const btDbvtNode* root1,
308
310 void collideTTpersistentStack( const btDbvtNode* root0,
311 const btDbvtNode* root1,
313#if 0
315 void collideTT( const btDbvtNode* root0,
316 const btDbvtNode* root1,
317 const btTransform& xform,
320 void collideTT( const btDbvtNode* root0,
321 const btTransform& xform0,
322 const btDbvtNode* root1,
323 const btTransform& xform1,
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,
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,
369 static void collideOCL( const btDbvtNode* root,
370 const btVector3* normals,
371 const btScalar* offsets,
372 const btVector3& sortaxis,
373 int count,
375 bool fullsort=true);
377 static void collideTU( const btDbvtNode* root,
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 //
402private:
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
600#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//
707inline void btDbvt::enumNodes( const btDbvtNode* root,
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//
721inline void btDbvt::enumLeaves( const btDbvtNode* root,
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//
738inline void btDbvt::collideTT( const btDbvtNode* root0,
739 const btDbvtNode* root1,
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,
806{
808 if(root0&&root1)
809 {
810 int depth=1;
811 int treshold=DOUBLE_STACKSIZE-4;
812
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//
868inline void btDbvt::collideTT( const btDbvtNode* root0,
869 const btDbvtNode* root1,
870 const btTransform& xform,
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//
923inline void btDbvt::collideTT( const btDbvtNode* root0,
924 const btTransform& xform0,
925 const btDbvtNode* root1,
926 const btTransform& xform1,
928{
929 const btTransform xform=xform0.inverse()*xform1;
930 collideTT(root0,root1,xform,policy);
931}
932#endif
933
935inline void btDbvt::collideTV( const btDbvtNode* root,
936 const btDbvtVolume& vol,
937 DBVT_IPOLICY) const
938{
940 if(root)
941 {
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
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//
975 const btDbvtVolume& vol,
976 btNodeStack& stack,
977 DBVT_IPOLICY) const
978{
980 if(root)
981 {
983 stack.resize(0);
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
1007inline 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//
1060inline void btDbvt::rayTest( const btDbvtNode* root,
1061 const btVector3& rayFrom,
1062 const btVector3& rayTo,
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
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//
1134inline void btDbvt::collideKDOP(const btDbvtNode* root,
1135 const btVector3* normals,
1136 const btScalar* offsets,
1137 int count,
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 }
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//
1189inline void btDbvt::collideOCL( const btDbvtNode* root,
1190 const btVector3* normals,
1191 const btScalar* offsets,
1192 const btVector3& sortaxis,
1193 int count,
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 }
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//
1302inline void btDbvt::collideTU( const btDbvtNode* root,
1304{
1306 if(root)
1307 {
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
bool btRayAabb(const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &aabbMin, const btVector3 &aabbMax, btScalar &param, btVector3 &normal)
Definition: btAabbUtil2.h:125
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
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:284
#define DBVT_VIRTUAL_DTOR(a)
Definition: btDbvt.h:87
#define DBVT_VIRTUAL
Definition: btDbvt.h:88
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
#define DBVT_PREFIX
Definition: btDbvt.h:89
btDbvtAabbMm btDbvtVolume
Definition: btDbvt.h:175
DBVT_INLINE void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
Definition: btDbvt.h:667
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
#define DBVT_IPOLICY
Definition: btDbvt.h:90
#define DBVT_CHECKTYPE
Definition: btDbvt.h:91
DBVT_INLINE btScalar Proximity(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:578
btAlignedObjectArray< const btDbvtNode * > btNodeStack
Definition: btDbvt.h:192
#define DBVT_INLINE
Definition: btDbvt.h:55
DBVT_INLINE int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:588
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:292
#define ATTRIBUTE_ALIGNED16(a)
Definition: btScalar.h:82
#define BT_LARGE_FLOAT
Definition: btScalar.h:294
btScalar btFabs(btScalar x)
Definition: btScalar.h:475
#define btAssert(x)
Definition: btScalar.h:131
btScalar btDot(const btVector3 &v1, const btVector3 &v2)
Return the dot product between two vectors.
Definition: btVector3.h:901
int size() const
return the number of elements in the array
void resize(int newsize, const T &fillData=T())
void push_back(const T &_Val)
void initializeFromBuffer(void *buffer, int size, int capacity)
The btTransform class supports rigid transforms with only translation and rotation and no scaling/she...
Definition: btTransform.h:34
btTransform inverse() const
Return the inverse of this transform.
Definition: btTransform.h:188
btVector3 can be used to represent 3D points and vectors.
Definition: btVector3.h:84
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
void setZ(btScalar _z)
Set the z value.
Definition: btVector3.h:583
const btScalar & z() const
Return the z value.
Definition: btVector3.h:591
btScalar dot(const btVector3 &v) const
Return the dot product.
Definition: btVector3.h:235
void setY(btScalar _y)
Set the y value.
Definition: btVector3.h:581
void setX(btScalar _x)
Set the x value.
Definition: btVector3.h:579
const btScalar & x() const
Return the x value.
Definition: btVector3.h:587
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
btVector3 & normalize()
Normalize this vector x^2 + y^2 + z^2 = 1.
Definition: btVector3.h:309
const btScalar & y() const
Return the y value.
Definition: btVector3.h:589
DBVT_INLINE btScalar ProjectMinimum(const btVector3 &v, unsigned signs) const
Definition: btDbvt.h:512
DBVT_INLINE bool Contain(const btDbvtAabbMm &a) const
Definition: btDbvt.h:473
DBVT_INLINE void SignedExpand(const btVector3 &e)
Definition: btDbvt.h:465
DBVT_INLINE btVector3 & tMaxs()
Definition: btDbvt.h:166
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
Definition: btDbvt.h:425
DBVT_INLINE const btVector3 & Mins() const
Definition: btDbvt.h:136
DBVT_INLINE friend bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:690
static btDbvtAabbMm FromCE(const btVector3 &c, const btVector3 &e)
Definition: btDbvt.h:411
DBVT_INLINE friend int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:588
DBVT_INLINE friend bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:534
DBVT_INLINE btVector3 & tMins()
Definition: btDbvt.h:165
DBVT_INLINE friend void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
Definition: btDbvt.h:667
static btDbvtAabbMm FromCR(const btVector3 &c, btScalar r)
Definition: btDbvt.h:419
DBVT_INLINE const btVector3 & Maxs() const
Definition: btDbvt.h:137
DBVT_INLINE btVector3 Extents() const
Definition: btDbvt.h:135
btVector3 mi
Definition: btDbvt.h:171
static btDbvtAabbMm FromPoints(const btVector3 *pts, int n)
Definition: btDbvt.h:433
DBVT_INLINE int Classify(const btVector3 &n, btScalar o, int s) const
Definition: btDbvt.h:484
DBVT_INLINE void Expand(const btVector3 &e)
Definition: btDbvt.h:459
DBVT_INLINE btVector3 Center() const
Definition: btDbvt.h:133
DBVT_INLINE friend btScalar Proximity(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition: btDbvt.h:578
DBVT_INLINE btVector3 Lengths() const
Definition: btDbvt.h:134
btVector3 mx
Definition: btDbvt.h:171
DBVT_INLINE void AddSpan(const btVector3 &d, btScalar &smi, btScalar &smx) const
Definition: btDbvt.h:522
DBVT_INLINE bool isinternal() const
Definition: btDbvt.h:183
btDbvtNode * childs[2]
Definition: btDbvt.h:186
btDbvtNode * parent
Definition: btDbvt.h:181
void * data
Definition: btDbvt.h:187
btDbvtVolume volume
Definition: btDbvt.h:180
int dataAsInt
Definition: btDbvt.h:188
DBVT_INLINE bool isleaf() const
Definition: btDbvt.h:182
virtual void CloneLeaf(btDbvtNode *)
Definition: btDbvt.h:252
virtual ~IClone()
Definition: btDbvt.h:251
DBVT_VIRTUAL bool AllLeaves(const btDbvtNode *)
Definition: btDbvt.h:238
DBVT_VIRTUAL void Process(const btDbvtNode *)
Definition: btDbvt.h:235
DBVT_VIRTUAL void Process(const btDbvtNode *n, btScalar)
Definition: btDbvt.h:236
DBVT_VIRTUAL bool Descent(const btDbvtNode *)
Definition: btDbvt.h:237
DBVT_VIRTUAL void Process(const btDbvtNode *, const btDbvtNode *)
Definition: btDbvt.h:234
virtual void WriteLeaf(const btDbvtNode *, int index, int parent)=0
virtual ~IWriter()
Definition: btDbvt.h:243
virtual void Prepare(const btDbvtNode *root, int numnodes)=0
virtual void WriteNode(const btDbvtNode *, int index, int parent, int child0, int child1)=0
btDbvtNode * parent
Definition: btDbvt.h:225
const btDbvtNode * node
Definition: btDbvt.h:224
sStkCLN(const btDbvtNode *n, btDbvtNode *p)
Definition: btDbvt.h:226
const btDbvtNode * b
Definition: btDbvt.h:204
sStkNN(const btDbvtNode *na, const btDbvtNode *nb)
Definition: btDbvt.h:206
const btDbvtNode * a
Definition: btDbvt.h:203
const btDbvtNode * node
Definition: btDbvt.h:216
btScalar value
Definition: btDbvt.h:218
sStkNPS(const btDbvtNode *n, unsigned m, btScalar v)
Definition: btDbvt.h:220
const btDbvtNode * node
Definition: btDbvt.h:210
sStkNP(const btDbvtNode *n, unsigned m)
Definition: btDbvt.h:212
The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes ...
Definition: btDbvt.h:199
void optimizeBottomUp()
Definition: btDbvt.cpp:472
static DBVT_INLINE int nearest(const int *i, const btDbvt::sStkNPS *a, btScalar v, int l, int h)
Definition: btDbvt.h:380
btDbvtNode * insert(const btDbvtVolume &box, void *data)
Definition: btDbvt.cpp:517
static DBVT_INLINE int allocate(btAlignedObjectArray< int > &ifree, btAlignedObjectArray< sStkNPS > &stock, const sStkNPS &value)
Definition: btDbvt.h:390
void optimizeIncremental(int passes)
Definition: btDbvt.cpp:497
void optimizeTopDown(int bu_treshold=128)
Definition: btDbvt.cpp:485
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
~btDbvt()
Definition: btDbvt.cpp:453
unsigned m_opath
Definition: btDbvt.h:266
static void benchmark()
Definition: btDbvt.h:295
static DBVT_PREFIX void enumNodes(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:707
void write(IWriter *iwriter) const
Definition: btDbvt.cpp:597
static DBVT_PREFIX void collideTU(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:1302
void update(btDbvtNode *leaf, int lookahead=-1)
Definition: btDbvt.cpp:526
btAlignedObjectArray< sStkNN > m_stkStack
Definition: btDbvt.h:269
btDbvtNode * m_free
Definition: btDbvt.h:263
DBVT_PREFIX void collideTV(const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY) const
Definition: btDbvt.h:935
bool empty() const
Definition: btDbvt.h:276
void clone(btDbvt &dest, IClone *iclone=0) const
Definition: btDbvt.cpp:622
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_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
static DBVT_PREFIX void collideKDOP(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
Definition: btDbvt.h:1134
int m_leaves
Definition: btDbvt.h:265
void clear()
Definition: btDbvt.cpp:459
static void extractLeaves(const btDbvtNode *node, btAlignedObjectArray< const btDbvtNode * > &leaves)
Definition: btDbvt.cpp:670
static DBVT_PREFIX void enumLeaves(const btDbvtNode *root, DBVT_IPOLICY)
Definition: btDbvt.h:721
btDbvt()
Definition: btDbvt.cpp:443
DBVT_PREFIX void collideTVNoStackAlloc(const btDbvtNode *root, const btDbvtVolume &volume, btNodeStack &stack, DBVT_IPOLICY) const
Definition: btDbvt.h:974
btDbvt(const btDbvt &)
Definition: btDbvt.h:403
static int countLeaves(const btDbvtNode *node)
Definition: btDbvt.cpp:661
@ DOUBLE_STACKSIZE
Definition: btDbvt.h:258
@ SIMPLE_STACKSIZE
Definition: btDbvt.h:257
btDbvtNode * m_root
Definition: btDbvt.h:262
int m_lkhd
Definition: btDbvt.h:264
DBVT_PREFIX void collideTTpersistentStack(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:803
void remove(btDbvtNode *leaf)
Definition: btDbvt.cpp:589
DBVT_PREFIX void collideTT(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
Definition: btDbvt.h:738
static int maxdepth(const btDbvtNode *node)
Definition: btDbvt.cpp:653