Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/physics/src/bullet/BulletCollision/BroadphaseCollision/btDbvt.cpp @ 2305

Last change on this file since 2305 was 2192, checked in by rgrieder, 16 years ago

Reverted all changes of attempt to update physics branch.
  • Property svn:eol-style set to native
File size: 34.7 KB
Line 
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 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*/
15///btDbvt implementation by Nathanael Presson
16
17#include "btDbvt.h"
18
19//
20typedef btAlignedObjectArray<btDbvtNode*>                       tNodeArray;
21typedef btAlignedObjectArray<const btDbvtNode*> tConstNodeArray;
22
23//
24struct btDbvtNodeEnumerator : btDbvt::ICollide
25{
26tConstNodeArray nodes;
27void Process(const btDbvtNode* n) { nodes.push_back(n); }
28};
29
30//
31static DBVT_INLINE int                  indexof(const btDbvtNode* node)
32{
33return(node->parent->childs[1]==node);
34}
35
36//
37static DBVT_INLINE btDbvtVolume merge(  const btDbvtVolume& a,
38                                                                                const btDbvtVolume& b)
39{
40#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
41DBVT_ALIGN char locals[sizeof(btDbvtAabbMm)];
42btDbvtVolume&   res=*(btDbvtVolume*)locals;
43#else
44btDbvtVolume    res;
45#endif
46Merge(a,b,res);
47return(res);
48}
49
50// volume+edge lengths
51static DBVT_INLINE btScalar             size(const btDbvtVolume& a)
52{
53const btVector3 edges=a.Lengths();
54return( edges.x()*edges.y()*edges.z()+
55                edges.x()+edges.y()+edges.z());
56}
57
58//
59static void                                             getmaxdepth(const btDbvtNode* node,int depth,int& maxdepth)
60{
61if(node->isinternal())
62        {
63        getmaxdepth(node->childs[0],depth+1,maxdepth);
64        getmaxdepth(node->childs[0],depth+1,maxdepth);
65        } else maxdepth=btMax(maxdepth,depth);
66}
67
68//
69static DBVT_INLINE void                 deletenode(     btDbvt* pdbvt,
70                                                                                        btDbvtNode* node)
71{
72btAlignedFree(pdbvt->m_free);
73pdbvt->m_free=node;
74}
75       
76//
77static void                                             recursedeletenode(      btDbvt* pdbvt,
78                                                                                                        btDbvtNode* node)
79{
80if(!node->isleaf())
81        {
82        recursedeletenode(pdbvt,node->childs[0]);
83        recursedeletenode(pdbvt,node->childs[1]);
84        }
85if(node==pdbvt->m_root) pdbvt->m_root=0;
86deletenode(pdbvt,node);
87}
88
89//
90static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
91                                                                                        btDbvtNode* parent,
92                                                                                        void* data)
93{
94btDbvtNode*     node;
95if(pdbvt->m_free)
96        { node=pdbvt->m_free;pdbvt->m_free=0; }
97        else
98        { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
99node->parent    =       parent;
100node->data              =       data;
101node->childs[1] =       0;
102return(node);
103}
104
105//
106static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
107                                                                                        btDbvtNode* parent,
108                                                                                        const btDbvtVolume& volume,
109                                                                                        void* data)
110{
111btDbvtNode*     node=createnode(pdbvt,parent,data);
112node->volume=volume;
113return(node);
114}
115
116//
117static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
118                                                                                        btDbvtNode* parent,
119                                                                                        const btDbvtVolume& volume0,
120                                                                                        const btDbvtVolume& volume1,
121                                                                                        void* data)
122{
123btDbvtNode*     node=createnode(pdbvt,parent,data);
124Merge(volume0,volume1,node->volume);
125return(node);
126}
127
128//
129static void                                             insertleaf(     btDbvt* pdbvt,
130                                                                                        btDbvtNode* root,
131                                                                                        btDbvtNode* leaf)
132{
133if(!pdbvt->m_root)
134        {
135        pdbvt->m_root   =       leaf;
136        leaf->parent    =       0;
137        }
138        else
139        {
140        if(!root->isleaf())
141                {
142                do      {
143                        root=root->childs[Select(       leaf->volume,
144                                                                                root->childs[0]->volume,
145                                                                                root->childs[1]->volume)];
146                        } while(!root->isleaf());
147                }
148        btDbvtNode*     prev=root->parent;
149        btDbvtNode*     node=createnode(pdbvt,prev,leaf->volume,root->volume,0);
150        if(prev)
151                {
152                prev->childs[indexof(root)]     =       node;
153                node->childs[0]                         =       root;root->parent=node;
154                node->childs[1]                         =       leaf;leaf->parent=node;
155                do      {
156                        if(!prev->volume.Contain(node->volume))
157                                Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
158                                else
159                                break;
160                        node=prev;
161                        } while(0!=(prev=node->parent));
162                }
163                else
164                {
165                node->childs[0] =       root;root->parent=node;
166                node->childs[1] =       leaf;leaf->parent=node;
167                pdbvt->m_root   =       node;
168                }
169        }
170}
171       
172//
173static btDbvtNode*                              removeleaf(     btDbvt* pdbvt,
174                                                                                        btDbvtNode* leaf)
175{
176if(leaf==pdbvt->m_root)
177        {
178        pdbvt->m_root=0;
179        return(0);
180        }
181        else
182        {
183        btDbvtNode*     parent=leaf->parent;
184        btDbvtNode*     prev=parent->parent;
185        btDbvtNode*     sibling=parent->childs[1-indexof(leaf)];                       
186        if(prev)
187                {
188                prev->childs[indexof(parent)]=sibling;
189                sibling->parent=prev;
190                deletenode(pdbvt,parent);
191                while(prev)
192                        {
193                        const btDbvtVolume      pb=prev->volume;
194                        Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
195                        if(NotEqual(pb,prev->volume))
196                                {
197                                prev=prev->parent;
198                                } else break;
199                        }
200                return(prev?prev:pdbvt->m_root);
201                }
202                else
203                {                                                               
204                pdbvt->m_root=sibling;
205                sibling->parent=0;
206                deletenode(pdbvt,parent);
207                return(pdbvt->m_root);
208                }                       
209        }
210}
211
212//
213static void                                             fetchleaves(btDbvt* pdbvt,
214                                                                                        btDbvtNode* root,
215                                                                                        tNodeArray& leaves,
216                                                                                        int depth=-1)
217{
218if(root->isinternal()&&depth)
219        {
220        fetchleaves(pdbvt,root->childs[0],leaves,depth-1);
221        fetchleaves(pdbvt,root->childs[1],leaves,depth-1);
222        deletenode(pdbvt,root);
223        }
224        else
225        {
226        leaves.push_back(root);
227        }
228}
229
230//
231static void                                             split(  const tNodeArray& leaves,
232                                                                                tNodeArray& left,
233                                                                                tNodeArray& right,
234                                                                                const btVector3& org,
235                                                                                const btVector3& axis)
236{
237left.resize(0);
238right.resize(0);
239for(int i=0,ni=leaves.size();i<ni;++i)
240        {
241        if(dot(axis,leaves[i]->volume.Center()-org)<0)
242                left.push_back(leaves[i]);
243                else
244                right.push_back(leaves[i]);
245        }
246}
247
248//
249static btDbvtVolume                             bounds( const tNodeArray& leaves)
250{
251#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
252DBVT_ALIGN char locals[sizeof(btDbvtVolume)];
253btDbvtVolume&   volume=*(btDbvtVolume*)locals;
254volume=leaves[0]->volume;
255#else
256btDbvtVolume volume=leaves[0]->volume;
257#endif
258for(int i=1,ni=leaves.size();i<ni;++i)
259        {
260        Merge(volume,leaves[i]->volume,volume);
261        }
262return(volume);
263}
264
265//
266static void                                             bottomup(       btDbvt* pdbvt,
267                                                                                        tNodeArray& leaves)
268{
269while(leaves.size()>1)
270        {
271        btScalar        minsize=SIMD_INFINITY;
272        int                     minidx[2]={-1,-1};
273        for(int i=0;i<leaves.size();++i)
274                {
275                for(int j=i+1;j<leaves.size();++j)
276                        {
277                        const btScalar  sz=size(merge(leaves[i]->volume,leaves[j]->volume));
278                        if(sz<minsize)
279                                {
280                                minsize         =       sz;
281                                minidx[0]       =       i;
282                                minidx[1]       =       j;
283                                }
284                        }
285                }
286        btDbvtNode*     n[]     =       {leaves[minidx[0]],leaves[minidx[1]]};
287        btDbvtNode*     p       =       createnode(pdbvt,0,n[0]->volume,n[1]->volume,0);
288        p->childs[0]            =       n[0];
289        p->childs[1]            =       n[1];
290        n[0]->parent            =       p;
291        n[1]->parent            =       p;
292        leaves[minidx[0]]       =       p;
293        leaves.swap(minidx[1],leaves.size()-1);
294        leaves.pop_back();
295        }
296}
297
298//
299static btDbvtNode*                      topdown(btDbvt* pdbvt,
300                                                                        tNodeArray& leaves,
301                                                                        int bu_treshold)
302{
303static const btVector3  axis[]={btVector3(1,0,0),
304                                                                btVector3(0,1,0),
305                                                                btVector3(0,0,1)};
306if(leaves.size()>1)
307        {
308        if(leaves.size()>bu_treshold)
309                {
310                const btDbvtVolume      vol=bounds(leaves);
311                const btVector3                 org=vol.Center();
312                tNodeArray                              sets[2];
313                int                                             bestaxis=-1;
314                int                                             bestmidp=leaves.size();
315                int                                             splitcount[3][2]={{0,0},{0,0},{0,0}};
316                int i;
317                for( i=0;i<leaves.size();++i)
318                        {
319                        const btVector3 x=leaves[i]->volume.Center()-org;
320                        for(int j=0;j<3;++j)
321                                {
322                                ++splitcount[j][dot(x,axis[j])>0?1:0];
323                                }
324                        }
325                for( i=0;i<3;++i)
326                        {
327                        if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
328                                {
329                                const int       midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
330                                if(midp<bestmidp)
331                                        {
332                                        bestaxis=i;
333                                        bestmidp=midp;
334                                        }
335                                }
336                        }
337                if(bestaxis>=0)
338                        {
339                        sets[0].reserve(splitcount[bestaxis][0]);
340                        sets[1].reserve(splitcount[bestaxis][1]);
341                        split(leaves,sets[0],sets[1],org,axis[bestaxis]);
342                        }
343                        else
344                        {
345                        sets[0].reserve(leaves.size()/2+1);
346                        sets[1].reserve(leaves.size()/2);
347                        for(int i=0,ni=leaves.size();i<ni;++i)
348                                {
349                                sets[i&1].push_back(leaves[i]);
350                                }
351                        }
352                btDbvtNode*     node=createnode(pdbvt,0,vol,0);
353                node->childs[0]=topdown(pdbvt,sets[0],bu_treshold);
354                node->childs[1]=topdown(pdbvt,sets[1],bu_treshold);
355                node->childs[0]->parent=node;
356                node->childs[1]->parent=node;
357                return(node);
358                }
359                else
360                {
361                bottomup(pdbvt,leaves);
362                return(leaves[0]);
363                }
364        }
365return(leaves[0]);
366}
367
368//
369static DBVT_INLINE btDbvtNode*  sort(btDbvtNode* n,btDbvtNode*& r)
370{
371btDbvtNode*     p=n->parent;
372btAssert(n->isinternal());
373if(p>n)
374        {
375        const int               i=indexof(n);
376        const int               j=1-i;
377        btDbvtNode*     s=p->childs[j];
378        btDbvtNode*     q=p->parent;
379        btAssert(n==p->childs[i]);
380        if(q) q->childs[indexof(p)]=n; else r=n;
381        s->parent=n;
382        p->parent=n;
383        n->parent=q;
384        p->childs[0]=n->childs[0];
385        p->childs[1]=n->childs[1];
386        n->childs[0]->parent=p;
387        n->childs[1]->parent=p;
388        n->childs[i]=p;
389        n->childs[j]=s;
390        btSwap(p->volume,n->volume);
391        return(p);
392        }
393return(n);
394}
395
396//
397static DBVT_INLINE btDbvtNode*  walkup(btDbvtNode* n,int count)
398{
399while(n&&(count--)) n=n->parent;
400return(n);
401}
402
403//
404// Api
405//
406
407//
408                                btDbvt::btDbvt()
409{
410m_root          =       0;
411m_free          =       0;
412m_lkhd          =       -1;
413m_leaves        =       0;
414m_opath         =       0;
415}
416
417//
418                                btDbvt::~btDbvt()
419{
420clear();
421}
422
423//
424void                    btDbvt::clear()
425{
426if(m_root)      recursedeletenode(this,m_root);
427btAlignedFree(m_free);
428m_free=0;
429}
430
431//
432void                    btDbvt::optimizeBottomUp()
433{
434if(m_root)
435        {
436        tNodeArray leaves;
437        leaves.reserve(m_leaves);
438        fetchleaves(this,m_root,leaves);
439        bottomup(this,leaves);
440        m_root=leaves[0];
441        }
442}
443
444//
445void                    btDbvt::optimizeTopDown(int bu_treshold)
446{
447if(m_root)
448        {
449        tNodeArray      leaves;
450        leaves.reserve(m_leaves);
451        fetchleaves(this,m_root,leaves);
452        m_root=topdown(this,leaves,bu_treshold);
453        }
454}
455
456//
457void                    btDbvt::optimizeIncremental(int passes)
458{
459if(passes<0) passes=m_leaves;
460if(m_root&&(passes>0))
461        {
462        do      {
463                btDbvtNode*             node=m_root;
464                unsigned        bit=0;
465                while(node->isinternal())
466                        {
467                        node=sort(node,m_root)->childs[(m_opath>>bit)&1];
468                        bit=(bit+1)&(sizeof(unsigned)*8-1);
469                        }
470                update(node);
471                ++m_opath;
472                } while(--passes);
473        }
474}
475
476//
477btDbvtNode*     btDbvt::insert(const btDbvtVolume& volume,void* data)
478{
479btDbvtNode*     leaf=createnode(this,0,volume,data);
480insertleaf(this,m_root,leaf);
481++m_leaves;
482return(leaf);
483}
484
485//
486void                    btDbvt::update(btDbvtNode* leaf,int lookahead)
487{
488btDbvtNode*     root=removeleaf(this,leaf);
489if(root)
490        {
491        if(lookahead>=0)
492                {
493                for(int i=0;(i<lookahead)&&root->parent;++i)
494                        {
495                        root=root->parent;
496                        }
497                } else root=m_root;
498        }
499insertleaf(this,root,leaf);
500}
501
502//
503void                    btDbvt::update(btDbvtNode* leaf,const btDbvtVolume& volume)
504{
505btDbvtNode*     root=removeleaf(this,leaf);
506if(root)
507        {
508        if(m_lkhd>=0)
509                {
510                for(int i=0;(i<m_lkhd)&&root->parent;++i)
511                        {
512                        root=root->parent;
513                        }
514                } else root=m_root;
515        }
516leaf->volume=volume;
517insertleaf(this,root,leaf);
518}
519
520//
521bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume volume,const btVector3& velocity,btScalar margin)
522{
523if(leaf->volume.Contain(volume)) return(false);
524volume.Expand(btVector3(margin,margin,margin));
525volume.SignedExpand(velocity);
526update(leaf,volume);
527return(true);
528}
529
530//
531bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume volume,const btVector3& velocity)
532{
533if(leaf->volume.Contain(volume)) return(false);
534volume.SignedExpand(velocity);
535update(leaf,volume);
536return(true);
537}
538
539//
540bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume volume,btScalar margin)
541{
542if(leaf->volume.Contain(volume)) return(false);
543volume.Expand(btVector3(margin,margin,margin));
544update(leaf,volume);
545return(true);
546}
547
548//
549void                    btDbvt::remove(btDbvtNode* leaf)
550{
551removeleaf(this,leaf);
552deletenode(this,leaf);
553--m_leaves;
554}
555
556//
557void                    btDbvt::write(IWriter* iwriter) const
558{
559btDbvtNodeEnumerator    nodes;
560nodes.nodes.reserve(m_leaves*2);
561enumNodes(m_root,nodes);
562iwriter->Prepare(m_root,nodes.nodes.size());
563for(int i=0;i<nodes.nodes.size();++i)
564        {
565        const btDbvtNode* n=nodes.nodes[i];
566        int                     p=-1;
567        if(n->parent) p=nodes.nodes.findLinearSearch(n->parent);
568        if(n->isinternal())
569                {
570                const int       c0=nodes.nodes.findLinearSearch(n->childs[0]);
571                const int       c1=nodes.nodes.findLinearSearch(n->childs[1]);
572                iwriter->WriteNode(n,i,p,c0,c1);
573                }
574                else
575                {
576                iwriter->WriteLeaf(n,i,p);
577                }       
578        }
579}
580
581//
582void                    btDbvt::clone(btDbvt& dest,IClone* iclone) const
583{
584dest.clear();
585if(m_root!=0)
586        {       
587        btAlignedObjectArray<sStkCLN>   stack;
588        stack.reserve(m_leaves);
589        stack.push_back(sStkCLN(m_root,0));
590        do      {
591                const int               i=stack.size()-1;
592                const sStkCLN   e=stack[i];
593                btDbvtNode*                     n=createnode(&dest,e.parent,e.node->volume,e.node->data);
594                stack.pop_back();
595                if(e.parent!=0)
596                        e.parent->childs[i&1]=n;
597                        else
598                        dest.m_root=n;
599                if(e.node->isinternal())
600                        {
601                        stack.push_back(sStkCLN(e.node->childs[0],n));
602                        stack.push_back(sStkCLN(e.node->childs[1],n));
603                        }
604                        else
605                        {
606                        iclone->CloneLeaf(n);
607                        }
608                } while(stack.size()>0);
609        }
610}
611
612//
613int                             btDbvt::maxdepth(const btDbvtNode* node)
614{
615int     depth=0;
616if(node) getmaxdepth(node,1,depth);
617return(depth);
618}
619
620//
621int                             btDbvt::countLeaves(const btDbvtNode* node)
622{
623if(node->isinternal())
624        return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
625        else
626        return(1);
627}
628
629//
630void                    btDbvt::extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves)
631{
632if(node->isinternal())
633        {
634        extractLeaves(node->childs[0],leaves);
635        extractLeaves(node->childs[1],leaves);
636        }
637        else
638        {
639        leaves.push_back(node);
640        }       
641}
642
643//
644#if DBVT_ENABLE_BENCHMARK
645
646#include <stdio.h>
647#include <stdlib.h>
648#include "LinearMath/btQuickProf.h"
649
650/*
651q6600,2.4ghz
652
653/Ox /Ob2 /Oi /Ot /I "." /I "..\.." /I "..\..\src" /D "NDEBUG" /D "_LIB" /D "_WINDOWS" /D "_CRT_SECURE_NO_DEPRECATE" /D "_CRT_NONSTDC_NO_DEPRECATE" /D "WIN32"
654/GF /FD /MT /GS- /Gy /arch:SSE2 /Zc:wchar_t- /Fp"..\..\out\release8\build\libbulletcollision\libbulletcollision.pch"
655/Fo"..\..\out\release8\build\libbulletcollision\\"
656/Fd"..\..\out\release8\build\libbulletcollision\bulletcollision.pdb"
657/W3 /nologo /c /Wp64 /Zi /errorReport:prompt
658
659Benchmarking dbvt...
660        World scale: 100.000000
661        Extents base: 1.000000
662        Extents range: 4.000000
663        Leaves: 8192
664        sizeof(btDbvtVolume): 32 bytes
665        sizeof(btDbvtNode):   44 bytes
666[1] btDbvtVolume intersections: 3499 ms (-1%)
667[2] btDbvtVolume merges: 1934 ms (0%)
668[3] btDbvt::collideTT: 5485 ms (-21%)
669[4] btDbvt::collideTT self: 2814 ms (-20%)
670[5] btDbvt::collideTT xform: 7379 ms (-1%)
671[6] btDbvt::collideTT xform,self: 7270 ms (-2%)
672[7] btDbvt::collideRAY: 6314 ms (0%),(332143 r/s)
673[8] insert/remove: 2093 ms (0%),(1001983 ir/s)
674[9] updates (teleport): 1879 ms (-3%),(1116100 u/s)
675[10] updates (jitter): 1244 ms (-4%),(1685813 u/s)
676[11] optimize (incremental): 2514 ms (0%),(1668000 o/s)
677[12] btDbvtVolume notequal: 3659 ms (0%)
678[13] culling(OCL+fullsort): 2218 ms (0%),(461 t/s)
679[14] culling(OCL+qsort): 3688 ms (5%),(2221 t/s)
680[15] culling(KDOP+qsort): 1139 ms (-1%),(7192 t/s)
681[16] insert/remove batch(256): 5092 ms (0%),(823704 bir/s)
682[17] btDbvtVolume select: 3419 ms (0%)
683*/
684
685struct btDbvtBenchmark
686{
687struct NilPolicy : btDbvt::ICollide
688        {
689        NilPolicy() : m_pcount(0),m_depth(-SIMD_INFINITY),m_checksort(true)             {}
690        void    Process(const btDbvtNode*,const btDbvtNode*)                            { ++m_pcount; }
691        void    Process(const btDbvtNode*)                                                                      { ++m_pcount; }
692        void    Process(const btDbvtNode*,btScalar depth)
693                {
694                ++m_pcount;
695                if(m_checksort)
696                        { if(depth>=m_depth) m_depth=depth; else printf("wrong depth: %f (should be >= %f)\r\n",depth,m_depth); }
697                }
698        int                     m_pcount;
699        btScalar        m_depth;
700        bool            m_checksort;
701        };
702struct P14 : btDbvt::ICollide
703        {
704        struct Node
705                {
706                const btDbvtNode*       leaf;
707                btScalar                        depth;
708                };
709        void Process(const btDbvtNode* leaf,btScalar depth)
710                {
711                Node    n;
712                n.leaf  =       leaf;
713                n.depth =       depth;
714                }
715        static int sortfnc(const Node& a,const Node& b)
716                {
717                if(a.depth<b.depth) return(+1);
718                if(a.depth>b.depth) return(-1);
719                return(0);
720                }
721        btAlignedObjectArray<Node>              m_nodes;
722        };
723struct P15 : btDbvt::ICollide
724        {
725        struct Node
726                {
727                const btDbvtNode*       leaf;
728                btScalar                        depth;
729                };
730        void Process(const btDbvtNode* leaf)
731                {
732                Node    n;
733                n.leaf  =       leaf;
734                n.depth =       dot(leaf->volume.Center(),m_axis);
735                }
736        static int sortfnc(const Node& a,const Node& b)
737                {
738                if(a.depth<b.depth) return(+1);
739                if(a.depth>b.depth) return(-1);
740                return(0);
741                }
742        btAlignedObjectArray<Node>              m_nodes;
743        btVector3                                               m_axis;
744        };
745static btScalar                 RandUnit()
746        {
747        return(rand()/(btScalar)RAND_MAX);
748        }
749static btVector3                RandVector3()
750        {
751        return(btVector3(RandUnit(),RandUnit(),RandUnit()));
752        }
753static btVector3                RandVector3(btScalar cs)
754        {
755        return(RandVector3()*cs-btVector3(cs,cs,cs)/2);
756        }
757static btDbvtVolume     RandVolume(btScalar cs,btScalar eb,btScalar es)
758        {
759        return(btDbvtVolume::FromCE(RandVector3(cs),btVector3(eb,eb,eb)+RandVector3()*es));
760        }
761static btTransform              RandTransform(btScalar cs)
762        {
763        btTransform     t;
764        t.setOrigin(RandVector3(cs));
765        t.setRotation(btQuaternion(RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2).normalized());
766        return(t);
767        }
768static void                             RandTree(btScalar cs,btScalar eb,btScalar es,int leaves,btDbvt& dbvt)
769        {
770        dbvt.clear();
771        for(int i=0;i<leaves;++i)
772                {
773                dbvt.insert(RandVolume(cs,eb,es),0);
774                }
775        }
776};
777
778void                    btDbvt::benchmark()
779{
780static const btScalar   cfgVolumeCenterScale            =       100;
781static const btScalar   cfgVolumeExentsBase                     =       1;
782static const btScalar   cfgVolumeExentsScale            =       4;
783static const int                cfgLeaves                                       =       8192;
784static const bool               cfgEnable                                       =       true;
785
786//[1] btDbvtVolume intersections
787bool                                    cfgBenchmark1_Enable            =       cfgEnable;
788static const int                cfgBenchmark1_Iterations        =       8;
789static const int                cfgBenchmark1_Reference         =       3499;
790//[2] btDbvtVolume merges
791bool                                    cfgBenchmark2_Enable            =       cfgEnable;
792static const int                cfgBenchmark2_Iterations        =       4;
793static const int                cfgBenchmark2_Reference         =       1945;
794//[3] btDbvt::collideTT
795bool                                    cfgBenchmark3_Enable            =       cfgEnable;
796static const int                cfgBenchmark3_Iterations        =       512;
797static const int                cfgBenchmark3_Reference         =       5485;
798//[4] btDbvt::collideTT self
799bool                                    cfgBenchmark4_Enable            =       cfgEnable;
800static const int                cfgBenchmark4_Iterations        =       512;
801static const int                cfgBenchmark4_Reference         =       2814;
802//[5] btDbvt::collideTT xform
803bool                                    cfgBenchmark5_Enable            =       cfgEnable;
804static const int                cfgBenchmark5_Iterations        =       512;
805static const btScalar   cfgBenchmark5_OffsetScale       =       2;
806static const int                cfgBenchmark5_Reference         =       7379;
807//[6] btDbvt::collideTT xform,self
808bool                                    cfgBenchmark6_Enable            =       cfgEnable;
809static const int                cfgBenchmark6_Iterations        =       512;
810static const btScalar   cfgBenchmark6_OffsetScale       =       2;
811static const int                cfgBenchmark6_Reference         =       7270;
812//[7] btDbvt::collideRAY
813bool                                    cfgBenchmark7_Enable            =       cfgEnable;
814static const int                cfgBenchmark7_Passes            =       32;
815static const int                cfgBenchmark7_Iterations        =       65536;
816static const int                cfgBenchmark7_Reference         =       6307;
817//[8] insert/remove
818bool                                    cfgBenchmark8_Enable            =       cfgEnable;
819static const int                cfgBenchmark8_Passes            =       32;
820static const int                cfgBenchmark8_Iterations        =       65536;
821static const int                cfgBenchmark8_Reference         =       2105;
822//[9] updates (teleport)
823bool                                    cfgBenchmark9_Enable            =       cfgEnable;
824static const int                cfgBenchmark9_Passes            =       32;
825static const int                cfgBenchmark9_Iterations        =       65536;
826static const int                cfgBenchmark9_Reference         =       1879;
827//[10] updates (jitter)
828bool                                    cfgBenchmark10_Enable           =       cfgEnable;
829static const btScalar   cfgBenchmark10_Scale            =       cfgVolumeCenterScale/10000;
830static const int                cfgBenchmark10_Passes           =       32;
831static const int                cfgBenchmark10_Iterations       =       65536;
832static const int                cfgBenchmark10_Reference        =       1244;
833//[11] optimize (incremental)
834bool                                    cfgBenchmark11_Enable           =       cfgEnable;
835static const int                cfgBenchmark11_Passes           =       64;
836static const int                cfgBenchmark11_Iterations       =       65536;
837static const int                cfgBenchmark11_Reference        =       2510;
838//[12] btDbvtVolume notequal
839bool                                    cfgBenchmark12_Enable           =       cfgEnable;
840static const int                cfgBenchmark12_Iterations       =       32;
841static const int                cfgBenchmark12_Reference        =       3677;
842//[13] culling(OCL+fullsort)
843bool                                    cfgBenchmark13_Enable           =       cfgEnable;
844static const int                cfgBenchmark13_Iterations       =       1024;
845static const int                cfgBenchmark13_Reference        =       2231;
846//[14] culling(OCL+qsort)
847bool                                    cfgBenchmark14_Enable           =       cfgEnable;
848static const int                cfgBenchmark14_Iterations       =       8192;
849static const int                cfgBenchmark14_Reference        =       3500;
850//[15] culling(KDOP+qsort)
851bool                                    cfgBenchmark15_Enable           =       cfgEnable;
852static const int                cfgBenchmark15_Iterations       =       8192;
853static const int                cfgBenchmark15_Reference        =       1151;
854//[16] insert/remove batch
855bool                                    cfgBenchmark16_Enable           =       cfgEnable;
856static const int                cfgBenchmark16_BatchCount       =       256;
857static const int                cfgBenchmark16_Passes           =       16384;
858static const int                cfgBenchmark16_Reference        =       5138;
859//[17] select
860bool                                    cfgBenchmark17_Enable           =       cfgEnable;
861static const int                cfgBenchmark17_Iterations       =       4;
862static const int                cfgBenchmark17_Reference        =       3390;
863
864btClock                                 wallclock;
865printf("Benchmarking dbvt...\r\n");
866printf("\tWorld scale: %f\r\n",cfgVolumeCenterScale);
867printf("\tExtents base: %f\r\n",cfgVolumeExentsBase);
868printf("\tExtents range: %f\r\n",cfgVolumeExentsScale);
869printf("\tLeaves: %u\r\n",cfgLeaves);
870printf("\tsizeof(btDbvtVolume): %u bytes\r\n",sizeof(btDbvtVolume));
871printf("\tsizeof(btDbvtNode):   %u bytes\r\n",sizeof(btDbvtNode));
872if(cfgBenchmark1_Enable)
873        {// Benchmark 1
874        srand(380843);
875        btAlignedObjectArray<btDbvtVolume>      volumes;
876        btAlignedObjectArray<bool>                      results;
877        volumes.resize(cfgLeaves);
878        results.resize(cfgLeaves);
879        for(int i=0;i<cfgLeaves;++i)
880                {
881                volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
882                }
883        printf("[1] btDbvtVolume intersections: ");
884        wallclock.reset();
885        for(int i=0;i<cfgBenchmark1_Iterations;++i)
886                {
887                for(int j=0;j<cfgLeaves;++j)
888                        {
889                        for(int k=0;k<cfgLeaves;++k)
890                                {
891                                results[k]=Intersect(volumes[j],volumes[k]);
892                                }
893                        }
894                }
895        const int time=(int)wallclock.getTimeMilliseconds();
896        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark1_Reference)*100/time);
897        }
898if(cfgBenchmark2_Enable)
899        {// Benchmark 2
900        srand(380843);
901        btAlignedObjectArray<btDbvtVolume>      volumes;
902        btAlignedObjectArray<btDbvtVolume>      results;
903        volumes.resize(cfgLeaves);
904        results.resize(cfgLeaves);
905        for(int i=0;i<cfgLeaves;++i)
906                {
907                volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
908                }
909        printf("[2] btDbvtVolume merges: ");
910        wallclock.reset();
911        for(int i=0;i<cfgBenchmark2_Iterations;++i)
912                {
913                for(int j=0;j<cfgLeaves;++j)
914                        {
915                        for(int k=0;k<cfgLeaves;++k)
916                                {
917                                Merge(volumes[j],volumes[k],results[k]);
918                                }
919                        }
920                }
921        const int time=(int)wallclock.getTimeMilliseconds();
922        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark2_Reference)*100/time);
923        }
924if(cfgBenchmark3_Enable)
925        {// Benchmark 3
926        srand(380843);
927        btDbvt                                          dbvt[2];
928        btDbvtBenchmark::NilPolicy      policy;
929        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
930        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
931        dbvt[0].optimizeTopDown();
932        dbvt[1].optimizeTopDown();
933        printf("[3] btDbvt::collideTT: ");
934        wallclock.reset();
935        for(int i=0;i<cfgBenchmark3_Iterations;++i)
936                {
937                btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,policy);
938                }
939        const int time=(int)wallclock.getTimeMilliseconds();
940        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark3_Reference)*100/time);
941        }
942if(cfgBenchmark4_Enable)
943        {// Benchmark 4
944        srand(380843);
945        btDbvt                                          dbvt;
946        btDbvtBenchmark::NilPolicy      policy;
947        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
948        dbvt.optimizeTopDown();
949        printf("[4] btDbvt::collideTT self: ");
950        wallclock.reset();
951        for(int i=0;i<cfgBenchmark4_Iterations;++i)
952                {
953                btDbvt::collideTT(dbvt.m_root,dbvt.m_root,policy);
954                }
955        const int time=(int)wallclock.getTimeMilliseconds();
956        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark4_Reference)*100/time);
957        }
958if(cfgBenchmark5_Enable)
959        {// Benchmark 5
960        srand(380843);
961        btDbvt                                                          dbvt[2];
962        btAlignedObjectArray<btTransform>       transforms;
963        btDbvtBenchmark::NilPolicy                      policy;
964        transforms.resize(cfgBenchmark5_Iterations);
965        for(int i=0;i<transforms.size();++i)
966                {
967                transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale);
968                }
969        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
970        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
971        dbvt[0].optimizeTopDown();
972        dbvt[1].optimizeTopDown();
973        printf("[5] btDbvt::collideTT xform: ");
974        wallclock.reset();
975        for(int i=0;i<cfgBenchmark5_Iterations;++i)
976                {
977                btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,transforms[i],policy);
978                }
979        const int time=(int)wallclock.getTimeMilliseconds();
980        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark5_Reference)*100/time);
981        }
982if(cfgBenchmark6_Enable)
983        {// Benchmark 6
984        srand(380843);
985        btDbvt                                                          dbvt;
986        btAlignedObjectArray<btTransform>       transforms;
987        btDbvtBenchmark::NilPolicy                      policy;
988        transforms.resize(cfgBenchmark6_Iterations);
989        for(int i=0;i<transforms.size();++i)
990                {
991                transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale);
992                }
993        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
994        dbvt.optimizeTopDown();
995        printf("[6] btDbvt::collideTT xform,self: ");
996        wallclock.reset();
997        for(int i=0;i<cfgBenchmark6_Iterations;++i)
998                {
999                btDbvt::collideTT(dbvt.m_root,dbvt.m_root,transforms[i],policy);               
1000                }
1001        const int time=(int)wallclock.getTimeMilliseconds();
1002        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark6_Reference)*100/time);
1003        }
1004if(cfgBenchmark7_Enable)
1005        {// Benchmark 7
1006        srand(380843);
1007        btDbvt                                                          dbvt;
1008        btAlignedObjectArray<btVector3>         rayorg;
1009        btAlignedObjectArray<btVector3>         raydir;
1010        btDbvtBenchmark::NilPolicy                      policy;
1011        rayorg.resize(cfgBenchmark7_Iterations);
1012        raydir.resize(cfgBenchmark7_Iterations);
1013        for(int i=0;i<rayorg.size();++i)
1014                {
1015                rayorg[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1016                raydir[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
1017                }
1018        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1019        dbvt.optimizeTopDown();
1020        printf("[7] btDbvt::collideRAY: ");
1021        wallclock.reset();
1022        for(int i=0;i<cfgBenchmark7_Passes;++i)
1023                {
1024                for(int j=0;j<cfgBenchmark7_Iterations;++j)
1025                        {
1026                        btDbvt::collideRAY(dbvt.m_root,rayorg[j],raydir[j],policy);
1027                        }
1028                }
1029        const int       time=(int)wallclock.getTimeMilliseconds();
1030        unsigned        rays=cfgBenchmark7_Passes*cfgBenchmark7_Iterations;
1031        printf("%u ms (%i%%),(%u r/s)\r\n",time,(time-cfgBenchmark7_Reference)*100/time,(rays*1000)/time);
1032        }
1033if(cfgBenchmark8_Enable)
1034        {// Benchmark 8
1035        srand(380843);
1036        btDbvt                                                          dbvt;
1037        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1038        dbvt.optimizeTopDown();
1039        printf("[8] insert/remove: ");
1040        wallclock.reset();
1041        for(int i=0;i<cfgBenchmark8_Passes;++i)
1042                {
1043                for(int j=0;j<cfgBenchmark8_Iterations;++j)
1044                        {
1045                        dbvt.remove(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1046                        }
1047                }
1048        const int       time=(int)wallclock.getTimeMilliseconds();
1049        const int       ir=cfgBenchmark8_Passes*cfgBenchmark8_Iterations;
1050        printf("%u ms (%i%%),(%u ir/s)\r\n",time,(time-cfgBenchmark8_Reference)*100/time,ir*1000/time);
1051        }
1052if(cfgBenchmark9_Enable)
1053        {// Benchmark 9
1054        srand(380843);
1055        btDbvt                                                                          dbvt;
1056        btAlignedObjectArray<const btDbvtNode*> leaves;
1057        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1058        dbvt.optimizeTopDown();
1059        dbvt.extractLeaves(dbvt.m_root,leaves);
1060        printf("[9] updates (teleport): ");
1061        wallclock.reset();
1062        for(int i=0;i<cfgBenchmark9_Passes;++i)
1063                {
1064                for(int j=0;j<cfgBenchmark9_Iterations;++j)
1065                        {
1066                        dbvt.update(const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]),
1067                                                btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale));
1068                        }
1069                }
1070        const int       time=(int)wallclock.getTimeMilliseconds();
1071        const int       up=cfgBenchmark9_Passes*cfgBenchmark9_Iterations;
1072        printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark9_Reference)*100/time,up*1000/time);
1073        }
1074if(cfgBenchmark10_Enable)
1075        {// Benchmark 10       
1076        srand(380843);
1077        btDbvt                                                                          dbvt;
1078        btAlignedObjectArray<const btDbvtNode*> leaves;
1079        btAlignedObjectArray<btVector3>                         vectors;
1080        vectors.resize(cfgBenchmark10_Iterations);
1081        for(int i=0;i<vectors.size();++i)
1082                {
1083                vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1))*cfgBenchmark10_Scale;
1084                }
1085        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1086        dbvt.optimizeTopDown();
1087        dbvt.extractLeaves(dbvt.m_root,leaves);
1088        printf("[10] updates (jitter): ");
1089        wallclock.reset();
1090       
1091        for(int i=0;i<cfgBenchmark10_Passes;++i)
1092                {
1093                for(int j=0;j<cfgBenchmark10_Iterations;++j)
1094                        {                       
1095                        const btVector3&        d=vectors[j];
1096                        btDbvtNode*             l=const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]);
1097                        btDbvtVolume            v=btDbvtVolume::FromMM(l->volume.Mins()+d,l->volume.Maxs()+d);
1098                        dbvt.update(l,v);
1099                        }
1100                }
1101        const int       time=(int)wallclock.getTimeMilliseconds();
1102        const int       up=cfgBenchmark10_Passes*cfgBenchmark10_Iterations;
1103        printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark10_Reference)*100/time,up*1000/time);
1104        }
1105if(cfgBenchmark11_Enable)
1106        {// Benchmark 11       
1107        srand(380843);
1108        btDbvt                                                                          dbvt;
1109        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1110        dbvt.optimizeTopDown();
1111        printf("[11] optimize (incremental): ");
1112        wallclock.reset();     
1113        for(int i=0;i<cfgBenchmark11_Passes;++i)
1114                {
1115                dbvt.optimizeIncremental(cfgBenchmark11_Iterations);
1116                }
1117        const int       time=(int)wallclock.getTimeMilliseconds();
1118        const int       op=cfgBenchmark11_Passes*cfgBenchmark11_Iterations;
1119        printf("%u ms (%i%%),(%u o/s)\r\n",time,(time-cfgBenchmark11_Reference)*100/time,op/time*1000);
1120        }
1121if(cfgBenchmark12_Enable)
1122        {// Benchmark 12       
1123        srand(380843);
1124        btAlignedObjectArray<btDbvtVolume>      volumes;
1125        btAlignedObjectArray<bool>                              results;
1126        volumes.resize(cfgLeaves);
1127        results.resize(cfgLeaves);
1128        for(int i=0;i<cfgLeaves;++i)
1129                {
1130                volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1131                }
1132        printf("[12] btDbvtVolume notequal: ");
1133        wallclock.reset();
1134        for(int i=0;i<cfgBenchmark12_Iterations;++i)
1135                {
1136                for(int j=0;j<cfgLeaves;++j)
1137                        {
1138                        for(int k=0;k<cfgLeaves;++k)
1139                                {
1140                                results[k]=NotEqual(volumes[j],volumes[k]);
1141                                }
1142                        }
1143                }
1144        const int time=(int)wallclock.getTimeMilliseconds();
1145        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark12_Reference)*100/time);
1146        }
1147if(cfgBenchmark13_Enable)
1148        {// Benchmark 13       
1149        srand(380843);
1150        btDbvt                                                          dbvt;
1151        btAlignedObjectArray<btVector3>         vectors;
1152        btDbvtBenchmark::NilPolicy                      policy;
1153        vectors.resize(cfgBenchmark13_Iterations);
1154        for(int i=0;i<vectors.size();++i)
1155                {
1156                vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1157                }
1158        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1159        dbvt.optimizeTopDown();
1160        printf("[13] culling(OCL+fullsort): ");
1161        wallclock.reset();     
1162        for(int i=0;i<cfgBenchmark13_Iterations;++i)
1163                {
1164                static const btScalar   offset=0;
1165                policy.m_depth=-SIMD_INFINITY;
1166                dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy);
1167                }
1168        const int       time=(int)wallclock.getTimeMilliseconds();
1169        const int       t=cfgBenchmark13_Iterations;
1170        printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark13_Reference)*100/time,(t*1000)/time);
1171        }
1172if(cfgBenchmark14_Enable)
1173        {// Benchmark 14       
1174        srand(380843);
1175        btDbvt                                                          dbvt;
1176        btAlignedObjectArray<btVector3>         vectors;
1177        btDbvtBenchmark::P14                            policy;
1178        vectors.resize(cfgBenchmark14_Iterations);
1179        for(int i=0;i<vectors.size();++i)
1180                {
1181                vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1182                }
1183        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1184        dbvt.optimizeTopDown();
1185        policy.m_nodes.reserve(cfgLeaves);
1186        printf("[14] culling(OCL+qsort): ");
1187        wallclock.reset();     
1188        for(int i=0;i<cfgBenchmark14_Iterations;++i)
1189                {
1190                static const btScalar   offset=0;
1191                policy.m_nodes.resize(0);
1192                dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy,false);
1193                policy.m_nodes.quickSort(btDbvtBenchmark::P14::sortfnc);
1194                }
1195        const int       time=(int)wallclock.getTimeMilliseconds();
1196        const int       t=cfgBenchmark14_Iterations;
1197        printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark14_Reference)*100/time,(t*1000)/time);
1198        }
1199if(cfgBenchmark15_Enable)
1200        {// Benchmark 15       
1201        srand(380843);
1202        btDbvt                                                          dbvt;
1203        btAlignedObjectArray<btVector3>         vectors;
1204        btDbvtBenchmark::P15                            policy;
1205        vectors.resize(cfgBenchmark15_Iterations);
1206        for(int i=0;i<vectors.size();++i)
1207                {
1208                vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized();
1209                }
1210        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1211        dbvt.optimizeTopDown();
1212        policy.m_nodes.reserve(cfgLeaves);
1213        printf("[15] culling(KDOP+qsort): ");
1214        wallclock.reset();     
1215        for(int i=0;i<cfgBenchmark15_Iterations;++i)
1216                {
1217                static const btScalar   offset=0;
1218                policy.m_nodes.resize(0);
1219                policy.m_axis=vectors[i];
1220                dbvt.collideKDOP(dbvt.m_root,&vectors[i],&offset,1,policy);
1221                policy.m_nodes.quickSort(btDbvtBenchmark::P15::sortfnc);
1222                }
1223        const int       time=(int)wallclock.getTimeMilliseconds();
1224        const int       t=cfgBenchmark15_Iterations;
1225        printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark15_Reference)*100/time,(t*1000)/time);
1226        }
1227if(cfgBenchmark16_Enable)
1228        {// Benchmark 16       
1229        srand(380843);
1230        btDbvt                                                          dbvt;
1231        btAlignedObjectArray<btDbvtNode*>       batch;
1232        btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
1233        dbvt.optimizeTopDown();
1234        batch.reserve(cfgBenchmark16_BatchCount);
1235        printf("[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount);
1236        wallclock.reset();
1237        for(int i=0;i<cfgBenchmark16_Passes;++i)
1238                {
1239                for(int j=0;j<cfgBenchmark16_BatchCount;++j)
1240                        {
1241                        batch.push_back(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
1242                        }
1243                for(int j=0;j<cfgBenchmark16_BatchCount;++j)
1244                        {
1245                        dbvt.remove(batch[j]);
1246                        }
1247                batch.resize(0);
1248                }
1249        const int       time=(int)wallclock.getTimeMilliseconds();
1250        const int       ir=cfgBenchmark16_Passes*cfgBenchmark16_BatchCount;
1251        printf("%u ms (%i%%),(%u bir/s)\r\n",time,(time-cfgBenchmark16_Reference)*100/time,int(ir*1000.0/time));
1252        }
1253if(cfgBenchmark17_Enable)
1254        {// Benchmark 17
1255        srand(380843);
1256        btAlignedObjectArray<btDbvtVolume>      volumes;
1257        btAlignedObjectArray<int>                       results;
1258        btAlignedObjectArray<int>                       indices;
1259        volumes.resize(cfgLeaves);
1260        results.resize(cfgLeaves);
1261        indices.resize(cfgLeaves);
1262        for(int i=0;i<cfgLeaves;++i)
1263                {
1264                indices[i]=i;
1265                volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
1266                }
1267        for(int i=0;i<cfgLeaves;++i)
1268                {
1269                btSwap(indices[i],indices[rand()%cfgLeaves]);
1270                }
1271        printf("[17] btDbvtVolume select: ");
1272        wallclock.reset();
1273        for(int i=0;i<cfgBenchmark17_Iterations;++i)
1274                {
1275                for(int j=0;j<cfgLeaves;++j)
1276                        {
1277                        for(int k=0;k<cfgLeaves;++k)
1278                                {
1279                                const int idx=indices[k];
1280                                results[idx]=Select(volumes[idx],volumes[j],volumes[k]);
1281                                }
1282                        }
1283                }
1284        const int time=(int)wallclock.getTimeMilliseconds();
1285        printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark17_Reference)*100/time);
1286        }
1287printf("\r\n\r\n");
1288}
1289#endif
Note: See TracBrowser for help on using the repository browser.