40 #if (DBVT_MERGE_IMPL==DBVT_IMPL_SSE) 55 return( edges.
x()*edges.
y()*edges.
z()+
56 edges.
x()+edges.
y()+edges.
z());
66 }
else maxdepth=
btMax(maxdepth,depth);
162 }
while(0!=(prev=node->
parent));
201 return(prev?prev:pdbvt->
m_root);
240 for(
int i=0,ni=leaves.
size();i<ni;++i)
242 if(
btDot(axis,leaves[i]->volume.Center()-org)<0)
252 #if DBVT_MERGE_IMPL==DBVT_IMPL_SSE 256 volume=leaves[0]->volume;
260 for(
int i=1,ni=leaves.
size();i<ni;++i)
262 Merge(volume,leaves[i]->volume,volume);
271 while(leaves.
size()>1)
274 int minidx[2]={-1,-1};
275 for(
int i=0;i<leaves.
size();++i)
277 for(
int j=i+1;j<leaves.
size();++j)
288 btDbvtNode* n[] = {leaves[minidx[0]],leaves[minidx[1]]};
294 leaves[minidx[0]] = p;
295 leaves.
swap(minidx[1],leaves.
size()-1);
310 if(leaves.
size()>bu_treshold)
316 int bestmidp=leaves.
size();
317 int splitcount[3][2]={{0,0},{0,0},{0,0}};
319 for( i=0;i<leaves.
size();++i)
321 const btVector3 x=leaves[i]->volume.Center()-org;
324 ++splitcount[j][
btDot(x,axis[j])>0?1:0];
329 if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
331 const int midp=(int)
btFabs(
btScalar(splitcount[i][0]-splitcount[i][1]));
341 sets[0].
reserve(splitcount[bestaxis][0]);
342 sets[1].
reserve(splitcount[bestaxis][1]);
343 split(leaves,sets[0],sets[1],org,axis[bestaxis]);
349 for(
int i=0,ni=leaves.
size();i<ni;++i)
401 while(n&&(count--)) n=n->
parent;
460 m_root=
topdown(
this,leaves,bu_treshold);
467 if(passes<0) passes=m_leaves;
468 if(m_root&&(passes>0))
475 node=
sort(node,m_root)->
childs[(m_opath>>bit)&1];
476 bit=(bit+1)&(
sizeof(
unsigned)*8-1);
501 for(
int i=0;(i<lookahead)&&root->
parent;++i)
518 for(
int i=0;(i<m_lkhd)&&root->
parent;++i)
569 enumNodes(m_root,nodes);
599 const int i=stack.
size()-1;
616 }
while(stack.
size()>0);
632 return(countLeaves(node->
childs[0])+countLeaves(node->
childs[1]));
642 extractLeaves(node->
childs[0],leaves);
643 extractLeaves(node->
childs[1],leaves);
652 #if DBVT_ENABLE_BENCHMARK 656 #include "LinearMath/btQuickProf.h" 693 struct btDbvtBenchmark
697 NilPolicy() : m_pcount(0),m_depth(-
SIMD_INFINITY),m_checksort(
true) {}
704 {
if(depth>=m_depth) m_depth=depth;
else printf(
"wrong depth: %f (should be >= %f)\r\n",depth,m_depth); }
723 static int sortfnc(
const Node& a,
const Node& b)
725 if(a.depth<b.depth)
return(+1);
726 if(a.depth>b.depth)
return(-1);
744 static int sortfnc(
const Node& a,
const Node& b)
746 if(a.depth<b.depth)
return(+1);
747 if(a.depth>b.depth)
return(-1);
759 return(
btVector3(RandUnit(),RandUnit(),RandUnit()));
763 return(RandVector3()*cs-
btVector3(cs,cs,cs)/2);
779 for(
int i=0;i<leaves;++i)
781 dbvt.
insert(RandVolume(cs,eb,es),0);
788 static const btScalar cfgVolumeCenterScale = 100;
789 static const btScalar cfgVolumeExentsBase = 1;
790 static const btScalar cfgVolumeExentsScale = 4;
791 static const int cfgLeaves = 8192;
792 static const bool cfgEnable =
true;
795 bool cfgBenchmark1_Enable = cfgEnable;
796 static const int cfgBenchmark1_Iterations = 8;
797 static const int cfgBenchmark1_Reference = 3499;
799 bool cfgBenchmark2_Enable = cfgEnable;
800 static const int cfgBenchmark2_Iterations = 4;
801 static const int cfgBenchmark2_Reference = 1945;
803 bool cfgBenchmark3_Enable = cfgEnable;
804 static const int cfgBenchmark3_Iterations = 512;
805 static const int cfgBenchmark3_Reference = 5485;
807 bool cfgBenchmark4_Enable = cfgEnable;
808 static const int cfgBenchmark4_Iterations = 512;
809 static const int cfgBenchmark4_Reference = 2814;
811 bool cfgBenchmark5_Enable = cfgEnable;
812 static const int cfgBenchmark5_Iterations = 512;
813 static const btScalar cfgBenchmark5_OffsetScale = 2;
814 static const int cfgBenchmark5_Reference = 7379;
816 bool cfgBenchmark6_Enable = cfgEnable;
817 static const int cfgBenchmark6_Iterations = 512;
818 static const btScalar cfgBenchmark6_OffsetScale = 2;
819 static const int cfgBenchmark6_Reference = 7270;
821 bool cfgBenchmark7_Enable = cfgEnable;
822 static const int cfgBenchmark7_Passes = 32;
823 static const int cfgBenchmark7_Iterations = 65536;
824 static const int cfgBenchmark7_Reference = 6307;
826 bool cfgBenchmark8_Enable = cfgEnable;
827 static const int cfgBenchmark8_Passes = 32;
828 static const int cfgBenchmark8_Iterations = 65536;
829 static const int cfgBenchmark8_Reference = 2105;
831 bool cfgBenchmark9_Enable = cfgEnable;
832 static const int cfgBenchmark9_Passes = 32;
833 static const int cfgBenchmark9_Iterations = 65536;
834 static const int cfgBenchmark9_Reference = 1879;
836 bool cfgBenchmark10_Enable = cfgEnable;
837 static const btScalar cfgBenchmark10_Scale = cfgVolumeCenterScale/10000;
838 static const int cfgBenchmark10_Passes = 32;
839 static const int cfgBenchmark10_Iterations = 65536;
840 static const int cfgBenchmark10_Reference = 1244;
842 bool cfgBenchmark11_Enable = cfgEnable;
843 static const int cfgBenchmark11_Passes = 64;
844 static const int cfgBenchmark11_Iterations = 65536;
845 static const int cfgBenchmark11_Reference = 2510;
847 bool cfgBenchmark12_Enable = cfgEnable;
848 static const int cfgBenchmark12_Iterations = 32;
849 static const int cfgBenchmark12_Reference = 3677;
851 bool cfgBenchmark13_Enable = cfgEnable;
852 static const int cfgBenchmark13_Iterations = 1024;
853 static const int cfgBenchmark13_Reference = 2231;
855 bool cfgBenchmark14_Enable = cfgEnable;
856 static const int cfgBenchmark14_Iterations = 8192;
857 static const int cfgBenchmark14_Reference = 3500;
859 bool cfgBenchmark15_Enable = cfgEnable;
860 static const int cfgBenchmark15_Iterations = 8192;
861 static const int cfgBenchmark15_Reference = 1151;
863 bool cfgBenchmark16_Enable = cfgEnable;
864 static const int cfgBenchmark16_BatchCount = 256;
865 static const int cfgBenchmark16_Passes = 16384;
866 static const int cfgBenchmark16_Reference = 5138;
868 bool cfgBenchmark17_Enable = cfgEnable;
869 static const int cfgBenchmark17_Iterations = 4;
870 static const int cfgBenchmark17_Reference = 3390;
873 printf(
"Benchmarking dbvt...\r\n");
874 printf(
"\tWorld scale: %f\r\n",cfgVolumeCenterScale);
875 printf(
"\tExtents base: %f\r\n",cfgVolumeExentsBase);
876 printf(
"\tExtents range: %f\r\n",cfgVolumeExentsScale);
877 printf(
"\tLeaves: %u\r\n",cfgLeaves);
878 printf(
"\tsizeof(btDbvtVolume): %u bytes\r\n",
sizeof(
btDbvtVolume));
879 printf(
"\tsizeof(btDbvtNode): %u bytes\r\n",
sizeof(
btDbvtNode));
880 if(cfgBenchmark1_Enable)
885 volumes.
resize(cfgLeaves);
886 results.
resize(cfgLeaves);
887 for(
int i=0;i<cfgLeaves;++i)
889 volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
891 printf(
"[1] btDbvtVolume intersections: ");
893 for(
int i=0;i<cfgBenchmark1_Iterations;++i)
895 for(
int j=0;j<cfgLeaves;++j)
897 for(
int k=0;k<cfgLeaves;++k)
899 results[k]=
Intersect(volumes[j],volumes[k]);
904 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark1_Reference)*100/time);
906 if(cfgBenchmark2_Enable)
911 volumes.
resize(cfgLeaves);
912 results.
resize(cfgLeaves);
913 for(
int i=0;i<cfgLeaves;++i)
915 volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
917 printf(
"[2] btDbvtVolume merges: ");
919 for(
int i=0;i<cfgBenchmark2_Iterations;++i)
921 for(
int j=0;j<cfgLeaves;++j)
923 for(
int k=0;k<cfgLeaves;++k)
925 Merge(volumes[j],volumes[k],results[k]);
930 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark2_Reference)*100/time);
932 if(cfgBenchmark3_Enable)
936 btDbvtBenchmark::NilPolicy policy;
937 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
938 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
941 printf(
"[3] btDbvt::collideTT: ");
943 for(
int i=0;i<cfgBenchmark3_Iterations;++i)
948 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark3_Reference)*100/time);
950 if(cfgBenchmark4_Enable)
954 btDbvtBenchmark::NilPolicy policy;
955 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
957 printf(
"[4] btDbvt::collideTT self: ");
959 for(
int i=0;i<cfgBenchmark4_Iterations;++i)
964 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark4_Reference)*100/time);
966 if(cfgBenchmark5_Enable)
971 btDbvtBenchmark::NilPolicy policy;
972 transforms.
resize(cfgBenchmark5_Iterations);
973 for(
int i=0;i<transforms.
size();++i)
975 transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale);
977 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
978 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
981 printf(
"[5] btDbvt::collideTT xform: ");
983 for(
int i=0;i<cfgBenchmark5_Iterations;++i)
988 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark5_Reference)*100/time);
990 if(cfgBenchmark6_Enable)
995 btDbvtBenchmark::NilPolicy policy;
996 transforms.
resize(cfgBenchmark6_Iterations);
997 for(
int i=0;i<transforms.
size();++i)
999 transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale);
1001 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1003 printf(
"[6] btDbvt::collideTT xform,self: ");
1005 for(
int i=0;i<cfgBenchmark6_Iterations;++i)
1010 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark6_Reference)*100/time);
1012 if(cfgBenchmark7_Enable)
1018 btDbvtBenchmark::NilPolicy policy;
1019 rayorg.
resize(cfgBenchmark7_Iterations);
1020 raydir.
resize(cfgBenchmark7_Iterations);
1021 for(
int i=0;i<rayorg.
size();++i)
1023 rayorg[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1024 raydir[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1026 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1028 printf(
"[7] btDbvt::rayTest: ");
1030 for(
int i=0;i<cfgBenchmark7_Passes;++i)
1032 for(
int j=0;j<cfgBenchmark7_Iterations;++j)
1038 unsigned rays=cfgBenchmark7_Passes*cfgBenchmark7_Iterations;
1039 printf(
"%u ms (%i%%),(%u r/s)\r\n",time,(time-cfgBenchmark7_Reference)*100/time,(rays*1000)/time);
1041 if(cfgBenchmark8_Enable)
1045 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1047 printf(
"[8] insert/remove: ");
1049 for(
int i=0;i<cfgBenchmark8_Passes;++i)
1051 for(
int j=0;j<cfgBenchmark8_Iterations;++j)
1053 dbvt.
remove(dbvt.
insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1057 const int ir=cfgBenchmark8_Passes*cfgBenchmark8_Iterations;
1058 printf(
"%u ms (%i%%),(%u ir/s)\r\n",time,(time-cfgBenchmark8_Reference)*100/time,ir*1000/time);
1060 if(cfgBenchmark9_Enable)
1065 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1068 printf(
"[9] updates (teleport): ");
1070 for(
int i=0;i<cfgBenchmark9_Passes;++i)
1072 for(
int j=0;j<cfgBenchmark9_Iterations;++j)
1074 dbvt.
update(const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]),
1075 btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale));
1079 const int up=cfgBenchmark9_Passes*cfgBenchmark9_Iterations;
1080 printf(
"%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark9_Reference)*100/time,up*1000/time);
1082 if(cfgBenchmark10_Enable)
1088 vectors.
resize(cfgBenchmark10_Iterations);
1089 for(
int i=0;i<vectors.
size();++i)
1091 vectors[i]=(btDbvtBenchmark::RandVector3()*2-
btVector3(1,1,1))*cfgBenchmark10_Scale;
1093 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1096 printf(
"[10] updates (jitter): ");
1099 for(
int i=0;i<cfgBenchmark10_Passes;++i)
1101 for(
int j=0;j<cfgBenchmark10_Iterations;++j)
1110 const int up=cfgBenchmark10_Passes*cfgBenchmark10_Iterations;
1111 printf(
"%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark10_Reference)*100/time,up*1000/time);
1113 if(cfgBenchmark11_Enable)
1117 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1119 printf(
"[11] optimize (incremental): ");
1121 for(
int i=0;i<cfgBenchmark11_Passes;++i)
1126 const int op=cfgBenchmark11_Passes*cfgBenchmark11_Iterations;
1127 printf(
"%u ms (%i%%),(%u o/s)\r\n",time,(time-cfgBenchmark11_Reference)*100/time,op/time*1000);
1129 if(cfgBenchmark12_Enable)
1134 volumes.
resize(cfgLeaves);
1135 results.
resize(cfgLeaves);
1136 for(
int i=0;i<cfgLeaves;++i)
1138 volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1140 printf(
"[12] btDbvtVolume notequal: ");
1142 for(
int i=0;i<cfgBenchmark12_Iterations;++i)
1144 for(
int j=0;j<cfgLeaves;++j)
1146 for(
int k=0;k<cfgLeaves;++k)
1148 results[k]=
NotEqual(volumes[j],volumes[k]);
1153 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark12_Reference)*100/time);
1155 if(cfgBenchmark13_Enable)
1160 btDbvtBenchmark::NilPolicy policy;
1161 vectors.
resize(cfgBenchmark13_Iterations);
1162 for(
int i=0;i<vectors.
size();++i)
1164 vectors[i]=(btDbvtBenchmark::RandVector3()*2-
btVector3(1,1,1)).normalized();
1166 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1168 printf(
"[13] culling(OCL+fullsort): ");
1170 for(
int i=0;i<cfgBenchmark13_Iterations;++i)
1177 const int t=cfgBenchmark13_Iterations;
1178 printf(
"%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark13_Reference)*100/time,(t*1000)/time);
1180 if(cfgBenchmark14_Enable)
1185 btDbvtBenchmark::P14 policy;
1186 vectors.
resize(cfgBenchmark14_Iterations);
1187 for(
int i=0;i<vectors.
size();++i)
1189 vectors[i]=(btDbvtBenchmark::RandVector3()*2-
btVector3(1,1,1)).normalized();
1191 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1193 policy.m_nodes.reserve(cfgLeaves);
1194 printf(
"[14] culling(OCL+qsort): ");
1196 for(
int i=0;i<cfgBenchmark14_Iterations;++i)
1199 policy.m_nodes.resize(0);
1200 dbvt.
collideOCL(dbvt.
m_root,&vectors[i],&offset,vectors[i],1,policy,
false);
1201 policy.m_nodes.quickSort(btDbvtBenchmark::P14::sortfnc);
1204 const int t=cfgBenchmark14_Iterations;
1205 printf(
"%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark14_Reference)*100/time,(t*1000)/time);
1207 if(cfgBenchmark15_Enable)
1212 btDbvtBenchmark::P15 policy;
1213 vectors.
resize(cfgBenchmark15_Iterations);
1214 for(
int i=0;i<vectors.
size();++i)
1216 vectors[i]=(btDbvtBenchmark::RandVector3()*2-
btVector3(1,1,1)).normalized();
1218 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1220 policy.m_nodes.reserve(cfgLeaves);
1221 printf(
"[15] culling(KDOP+qsort): ");
1223 for(
int i=0;i<cfgBenchmark15_Iterations;++i)
1226 policy.m_nodes.resize(0);
1227 policy.m_axis=vectors[i];
1229 policy.m_nodes.quickSort(btDbvtBenchmark::P15::sortfnc);
1232 const int t=cfgBenchmark15_Iterations;
1233 printf(
"%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark15_Reference)*100/time,(t*1000)/time);
1235 if(cfgBenchmark16_Enable)
1240 btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1242 batch.
reserve(cfgBenchmark16_BatchCount);
1243 printf(
"[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount);
1245 for(
int i=0;i<cfgBenchmark16_Passes;++i)
1247 for(
int j=0;j<cfgBenchmark16_BatchCount;++j)
1249 batch.
push_back(dbvt.
insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1251 for(
int j=0;j<cfgBenchmark16_BatchCount;++j)
1258 const int ir=cfgBenchmark16_Passes*cfgBenchmark16_BatchCount;
1259 printf(
"%u ms (%i%%),(%u bir/s)\r\n",time,(time-cfgBenchmark16_Reference)*100/time,
int(ir*1000.0/time));
1261 if(cfgBenchmark17_Enable)
1267 volumes.
resize(cfgLeaves);
1268 results.
resize(cfgLeaves);
1269 indices.
resize(cfgLeaves);
1270 for(
int i=0;i<cfgLeaves;++i)
1273 volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1275 for(
int i=0;i<cfgLeaves;++i)
1277 btSwap(indices[i],indices[rand()%cfgLeaves]);
1279 printf(
"[17] btDbvtVolume select: ");
1281 for(
int i=0;i<cfgBenchmark17_Iterations;++i)
1283 for(
int j=0;j<cfgLeaves;++j)
1285 for(
int k=0;k<cfgLeaves;++k)
1287 const int idx=indices[k];
1288 results[idx]=
Select(volumes[idx],volumes[j],volumes[k]);
1293 printf(
"%u ms (%i%%)\r\n",time,(time-cfgBenchmark17_Reference)*100/time);
static DBVT_PREFIX void collideKDOP(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
DBVT_INLINE void Merge(const btDbvtAabbMm &a, const btDbvtAabbMm &b, btDbvtAabbMm &r)
void push_back(const T &_Val)
static void bottomup(btDbvt *pdbvt, tNodeArray &leaves)
DBVT_INLINE bool isleaf() const
static DBVT_PREFIX void collideOCL(const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, const btVector3 &sortaxis, int count, DBVT_IPOLICY, bool fullsort=true)
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
static void fetchleaves(btDbvt *pdbvt, btDbvtNode *root, tNodeArray &leaves, int depth=-1)
static void getmaxdepth(const btDbvtNode *node, int depth, int &maxdepth)
static void recursedeletenode(btDbvt *pdbvt, btDbvtNode *node)
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes ...
btDbvtNode * insert(const btDbvtVolume &box, void *data)
The btClock is a portable basic clock that measures accurate time in seconds, use for profiling...
virtual void WriteNode(const btDbvtNode *, int index, int parent, int child0, int child1)=0
void reset()
Resets the initial reference time.
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...
DBVT_INLINE int Select(const btDbvtAabbMm &o, const btDbvtAabbMm &a, const btDbvtAabbMm &b)
DBVT_INLINE bool isinternal() const
void swap(int index0, int index1)
void Process(const btDbvtNode *n)
const btScalar & x() const
Return the x value.
unsigned long int getTimeMilliseconds()
Returns the time in ms since the last call to reset or since the btClock was created.
void update(btDbvtNode *leaf, int lookahead=-1)
btAlignedObjectArray< const btDbvtNode * > tConstNodeArray
static int countLeaves(const btDbvtNode *node)
int size() const
return the number of elements in the array
void optimizeIncremental(int passes)
static DBVT_INLINE btDbvtNode * createnode(btDbvt *pdbvt, btDbvtNode *parent, void *data)
static btDbvtAabbMm FromCE(const btVector3 &c, const btVector3 &e)
static DBVT_INLINE btDbvtVolume merge(const btDbvtVolume &a, const btDbvtVolume &b)
static int maxdepth(const btDbvtNode *node)
static btDbvtAabbMm FromMM(const btVector3 &mi, const btVector3 &mx)
DBVT_INLINE btVector3 Lengths() const
static void insertleaf(btDbvt *pdbvt, btDbvtNode *root, btDbvtNode *leaf)
#define btAlignedFree(ptr)
DBVT_INLINE btVector3 Center() const
DBVT_INLINE void Expand(const btVector3 &e)
void optimizeTopDown(int bu_treshold=128)
const btScalar & y() const
Return the y value.
btVector3 can be used to represent 3D points and vectors.
#define ATTRIBUTE_ALIGNED16(a)
DBVT_INLINE const btVector3 & Maxs() const
void write(IWriter *iwriter) const
virtual void Prepare(const btDbvtNode *root, int numnodes)=0
static void clear(T &value)
static void split(const tNodeArray &leaves, tNodeArray &left, tNodeArray &right, const btVector3 &org, const btVector3 &axis)
void resize(int newsize, const T &fillData=T())
int findLinearSearch(const T &key) const
virtual void WriteLeaf(const btDbvtNode *, int index, int parent)=0
static btDbvtNode * removeleaf(btDbvt *pdbvt, btDbvtNode *leaf)
const T & btMax(const T &a, const T &b)
static void extractLeaves(const btDbvtNode *node, btAlignedObjectArray< const btDbvtNode * > &leaves)
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
static btDbvtNode * topdown(btDbvt *pdbvt, tNodeArray &leaves, int bu_treshold)
#define btAlignedAlloc(size, alignment)
static DBVT_INLINE int indexof(const btDbvtNode *node)
btScalar dot(const btQuaternion &q1, const btQuaternion &q2)
Calculate the dot product between two quaternions.
btAlignedObjectArray< btDbvtNode * > tNodeArray
btDbvt implementation by Nathanael Presson
DBVT_PREFIX void collideTT(const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
The btQuaternion implements quaternion to perform linear algebra rotations in combination with btMatr...
btScalar btDot(const btVector3 &v1, const btVector3 &v2)
Return the dot product between two vectors.
static DBVT_INLINE void deletenode(btDbvt *pdbvt, btDbvtNode *node)
DBVT_INLINE bool Contain(const btDbvtAabbMm &a) const
DBVT_INLINE const btVector3 & Mins() const
DBVT_INLINE void SignedExpand(const btVector3 &e)
static DBVT_INLINE btDbvtNode * sort(btDbvtNode *n, btDbvtNode *&r)
void clone(btDbvt &dest, IClone *iclone=0) const
void remove(btDbvtNode *leaf)
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
virtual void CloneLeaf(btDbvtNode *)
static btDbvtVolume bounds(const tNodeArray &leaves)
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
btScalar btFabs(btScalar x)
const btScalar & z() const
Return the z value.