Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/pickups/src/bullet/BulletCollision/BroadphaseCollision/btDbvt.cpp @ 2980

Last change on this file since 2980 was 2662, checked in by rgrieder, 16 years ago

Merged presentation branch back to trunk.
  • Property svn:eol-style set to native
File size: 35.3 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{
26        tConstNodeArray nodes;
27        void Process(const btDbvtNode* n) { nodes.push_back(n); }
28};
29
30//
31static DBVT_INLINE int                  indexof(const btDbvtNode* node)
32{
33        return(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)
41        ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtAabbMm)]);
42        btDbvtVolume&   res=*(btDbvtVolume*)locals;
43#else
44                btDbvtVolume    res;
45#endif
46        Merge(a,b,res);
47        return(res);
48}
49
50// volume+edge lengths
51static DBVT_INLINE btScalar             size(const btDbvtVolume& a)
52{
53        const btVector3 edges=a.Lengths();
54        return( 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{
61        if(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{
72        btAlignedFree(pdbvt->m_free);
73        pdbvt->m_free=node;
74}
75
76//
77static void                                             recursedeletenode(      btDbvt* pdbvt,
78                                                                                                  btDbvtNode* node)
79{
80        if(!node->isleaf())
81        {
82                recursedeletenode(pdbvt,node->childs[0]);
83                recursedeletenode(pdbvt,node->childs[1]);
84        }
85        if(node==pdbvt->m_root) pdbvt->m_root=0;
86        deletenode(pdbvt,node);
87}
88
89//
90static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
91                                                                                   btDbvtNode* parent,
92                                                                                   void* data)
93{
94        btDbvtNode*     node;
95        if(pdbvt->m_free)
96        { node=pdbvt->m_free;pdbvt->m_free=0; }
97        else
98        { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
99        node->parent    =       parent;
100        node->data              =       data;
101        node->childs[1] =       0;
102        return(node);
103}
104
105//
106static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
107                                                                                   btDbvtNode* parent,
108                                                                                   const btDbvtVolume& volume,
109                                                                                   void* data)
110{
111        btDbvtNode*     node=createnode(pdbvt,parent,data);
112        node->volume=volume;
113        return(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{
123        btDbvtNode*     node=createnode(pdbvt,parent,data);
124        Merge(volume0,volume1,node->volume);
125        return(node);
126}
127
128//
129static void                                             insertleaf(     btDbvt* pdbvt,
130                                                                                   btDbvtNode* root,
131                                                                                   btDbvtNode* leaf)
132{
133        if(!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{
176        if(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{
218        if(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{
237        left.resize(0);
238        right.resize(0);
239        for(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
252        ATTRIBUTE_ALIGNED16(char        locals[sizeof(btDbvtVolume)]);
253        btDbvtVolume&   volume=*(btDbvtVolume*)locals;
254        volume=leaves[0]->volume;
255#else
256        btDbvtVolume volume=leaves[0]->volume;
257#endif
258        for(int i=1,ni=leaves.size();i<ni;++i)
259        {
260                Merge(volume,leaves[i]->volume,volume);
261        }
262        return(volume);
263}
264
265//
266static void                                             bottomup(       btDbvt* pdbvt,
267                                                                                 tNodeArray& leaves)
268{
269        while(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{
303        static const btVector3  axis[]={btVector3(1,0,0),
304                btVector3(0,1,0),
305                btVector3(0,0,1)};
306        if(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        }
365        return(leaves[0]);
366}
367
368//
369static DBVT_INLINE btDbvtNode*  sort(btDbvtNode* n,btDbvtNode*& r)
370{
371        btDbvtNode*     p=n->parent;
372        btAssert(n->isinternal());
373        if(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        }
393        return(n);
394}
395
396//
397static DBVT_INLINE btDbvtNode*  walkup(btDbvtNode* n,int count)
398{
399        while(n&&(count--)) n=n->parent;
400        return(n);
401}
402
403//
404// Api
405//
406
407//
408btDbvt::btDbvt()
409{
410        m_root          =       0;
411        m_free          =       0;
412        m_lkhd          =       -1;
413        m_leaves        =       0;
414        m_opath         =       0;
415}
416
417//
418btDbvt::~btDbvt()
419{
420        clear();
421}
422
423//
424void                    btDbvt::clear()
425{
426        if(m_root)      recursedeletenode(this,m_root);
427        btAlignedFree(m_free);
428        m_free=0;
429}
430
431//
432void                    btDbvt::optimizeBottomUp()
433{
434        if(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{
447        if(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{
459        if(passes<0) passes=m_leaves;
460        if(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{
479        btDbvtNode*     leaf=createnode(this,0,volume,data);
480        insertleaf(this,m_root,leaf);
481        ++m_leaves;
482        return(leaf);
483}
484
485//
486void                    btDbvt::update(btDbvtNode* leaf,int lookahead)
487{
488        btDbvtNode*     root=removeleaf(this,leaf);
489        if(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        }
499        insertleaf(this,root,leaf);
500}
501
502//
503void                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume)
504{
505        btDbvtNode*     root=removeleaf(this,leaf);
506        if(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        }
516        leaf->volume=volume;
517        insertleaf(this,root,leaf);
518}
519
520//
521bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin)
522{
523        if(leaf->volume.Contain(volume)) return(false);
524        volume.Expand(btVector3(margin,margin,margin));
525        volume.SignedExpand(velocity);
526        update(leaf,volume);
527        return(true);
528}
529
530//
531bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity)
532{
533        if(leaf->volume.Contain(volume)) return(false);
534        volume.SignedExpand(velocity);
535        update(leaf,volume);
536        return(true);
537}
538
539//
540bool                    btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin)
541{
542        if(leaf->volume.Contain(volume)) return(false);
543        volume.Expand(btVector3(margin,margin,margin));
544        update(leaf,volume);
545        return(true);
546}
547
548//
549void                    btDbvt::remove(btDbvtNode* leaf)
550{
551        removeleaf(this,leaf);
552        deletenode(this,leaf);
553        --m_leaves;
554}
555
556//
557void                    btDbvt::write(IWriter* iwriter) const
558{
559        btDbvtNodeEnumerator    nodes;
560        nodes.nodes.reserve(m_leaves*2);
561        enumNodes(m_root,nodes);
562        iwriter->Prepare(m_root,nodes.nodes.size());
563        for(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{
584        dest.clear();
585        if(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{
615        int     depth=0;
616        if(node) getmaxdepth(node,1,depth);
617        return(depth);
618}
619
620//
621int                             btDbvt::countLeaves(const btDbvtNode* node)
622{
623        if(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{
632        if(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...
660World scale: 100.000000
661Extents base: 1.000000
662Extents range: 4.000000
663Leaves: 8192
664sizeof(btDbvtVolume): 32 bytes
665sizeof(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::rayTest: 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{
687        struct 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        };
702        struct 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        };
723        struct 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        };
745        static btScalar                 RandUnit()
746        {
747                return(rand()/(btScalar)RAND_MAX);
748        }
749        static btVector3                RandVector3()
750        {
751                return(btVector3(RandUnit(),RandUnit(),RandUnit()));
752        }
753        static btVector3                RandVector3(btScalar cs)
754        {
755                return(RandVector3()*cs-btVector3(cs,cs,cs)/2);
756        }
757        static btDbvtVolume     RandVolume(btScalar cs,btScalar eb,btScalar es)
758        {
759                return(btDbvtVolume::FromCE(RandVector3(cs),btVector3(eb,eb,eb)+RandVector3()*es));
760        }
761        static 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        }
768        static 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{
780        static const btScalar   cfgVolumeCenterScale            =       100;
781        static const btScalar   cfgVolumeExentsBase                     =       1;
782        static const btScalar   cfgVolumeExentsScale            =       4;
783        static const int                cfgLeaves                                       =       8192;
784        static const bool               cfgEnable                                       =       true;
785
786        //[1] btDbvtVolume intersections
787        bool                                    cfgBenchmark1_Enable            =       cfgEnable;
788        static const int                cfgBenchmark1_Iterations        =       8;
789        static const int                cfgBenchmark1_Reference         =       3499;
790        //[2] btDbvtVolume merges
791        bool                                    cfgBenchmark2_Enable            =       cfgEnable;
792        static const int                cfgBenchmark2_Iterations        =       4;
793        static const int                cfgBenchmark2_Reference         =       1945;
794        //[3] btDbvt::collideTT
795        bool                                    cfgBenchmark3_Enable            =       cfgEnable;
796        static const int                cfgBenchmark3_Iterations        =       512;
797        static const int                cfgBenchmark3_Reference         =       5485;
798        //[4] btDbvt::collideTT self
799        bool                                    cfgBenchmark4_Enable            =       cfgEnable;
800        static const int                cfgBenchmark4_Iterations        =       512;
801        static const int                cfgBenchmark4_Reference         =       2814;
802        //[5] btDbvt::collideTT xform
803        bool                                    cfgBenchmark5_Enable            =       cfgEnable;
804        static const int                cfgBenchmark5_Iterations        =       512;
805        static const btScalar   cfgBenchmark5_OffsetScale       =       2;
806        static const int                cfgBenchmark5_Reference         =       7379;
807        //[6] btDbvt::collideTT xform,self
808        bool                                    cfgBenchmark6_Enable            =       cfgEnable;
809        static const int                cfgBenchmark6_Iterations        =       512;
810        static const btScalar   cfgBenchmark6_OffsetScale       =       2;
811        static const int                cfgBenchmark6_Reference         =       7270;
812        //[7] btDbvt::rayTest
813        bool                                    cfgBenchmark7_Enable            =       cfgEnable;
814        static const int                cfgBenchmark7_Passes            =       32;
815        static const int                cfgBenchmark7_Iterations        =       65536;
816        static const int                cfgBenchmark7_Reference         =       6307;
817        //[8] insert/remove
818        bool                                    cfgBenchmark8_Enable            =       cfgEnable;
819        static const int                cfgBenchmark8_Passes            =       32;
820        static const int                cfgBenchmark8_Iterations        =       65536;
821        static const int                cfgBenchmark8_Reference         =       2105;
822        //[9] updates (teleport)
823        bool                                    cfgBenchmark9_Enable            =       cfgEnable;
824        static const int                cfgBenchmark9_Passes            =       32;
825        static const int                cfgBenchmark9_Iterations        =       65536;
826        static const int                cfgBenchmark9_Reference         =       1879;
827        //[10] updates (jitter)
828        bool                                    cfgBenchmark10_Enable           =       cfgEnable;
829        static const btScalar   cfgBenchmark10_Scale            =       cfgVolumeCenterScale/10000;
830        static const int                cfgBenchmark10_Passes           =       32;
831        static const int                cfgBenchmark10_Iterations       =       65536;
832        static const int                cfgBenchmark10_Reference        =       1244;
833        //[11] optimize (incremental)
834        bool                                    cfgBenchmark11_Enable           =       cfgEnable;
835        static const int                cfgBenchmark11_Passes           =       64;
836        static const int                cfgBenchmark11_Iterations       =       65536;
837        static const int                cfgBenchmark11_Reference        =       2510;
838        //[12] btDbvtVolume notequal
839        bool                                    cfgBenchmark12_Enable           =       cfgEnable;
840        static const int                cfgBenchmark12_Iterations       =       32;
841        static const int                cfgBenchmark12_Reference        =       3677;
842        //[13] culling(OCL+fullsort)
843        bool                                    cfgBenchmark13_Enable           =       cfgEnable;
844        static const int                cfgBenchmark13_Iterations       =       1024;
845        static const int                cfgBenchmark13_Reference        =       2231;
846        //[14] culling(OCL+qsort)
847        bool                                    cfgBenchmark14_Enable           =       cfgEnable;
848        static const int                cfgBenchmark14_Iterations       =       8192;
849        static const int                cfgBenchmark14_Reference        =       3500;
850        //[15] culling(KDOP+qsort)
851        bool                                    cfgBenchmark15_Enable           =       cfgEnable;
852        static const int                cfgBenchmark15_Iterations       =       8192;
853        static const int                cfgBenchmark15_Reference        =       1151;
854        //[16] insert/remove batch
855        bool                                    cfgBenchmark16_Enable           =       cfgEnable;
856        static const int                cfgBenchmark16_BatchCount       =       256;
857        static const int                cfgBenchmark16_Passes           =       16384;
858        static const int                cfgBenchmark16_Reference        =       5138;
859        //[17] select
860        bool                                    cfgBenchmark17_Enable           =       cfgEnable;
861        static const int                cfgBenchmark17_Iterations       =       4;
862        static const int                cfgBenchmark17_Reference        =       3390;
863
864        btClock                                 wallclock;
865        printf("Benchmarking dbvt...\r\n");
866        printf("\tWorld scale: %f\r\n",cfgVolumeCenterScale);
867        printf("\tExtents base: %f\r\n",cfgVolumeExentsBase);
868        printf("\tExtents range: %f\r\n",cfgVolumeExentsScale);
869        printf("\tLeaves: %u\r\n",cfgLeaves);
870        printf("\tsizeof(btDbvtVolume): %u bytes\r\n",sizeof(btDbvtVolume));
871        printf("\tsizeof(btDbvtNode):   %u bytes\r\n",sizeof(btDbvtNode));
872        if(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        }
898        if(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        }
924        if(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        }
942        if(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        }
958        if(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        }
982        if(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        }
1004        if(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::rayTest: ");
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::rayTest(dbvt.m_root,rayorg[j],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        }
1033        if(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        }
1052        if(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        }
1074        if(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        }
1105        if(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        }
1121        if(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        }
1147        if(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        }
1172        if(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        }
1199        if(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        }
1227        if(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        }
1253        if(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        }
1287        printf("\r\n\r\n");
1288}
1289#endif
Note: See TracBrowser for help on using the repository browser.