Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Ignore:
Timestamp:
Dec 13, 2008, 11:45:51 PM (15 years ago)
Author:
rgrieder
Message:

Updated to Bullet 2.73 (first part).

File:
1 edited

Legend:

Unmodified
Added
Removed

  • code/branches/physics/src/bullet/BulletCollision/BroadphaseCollision/btDbvt.cpp

    r2192 r2430  
    2424struct btDbvtNodeEnumerator : btDbvt::ICollide
    2525{
    26 tConstNodeArray nodes;
    27 void Process(const btDbvtNode* n) { nodes.push_back(n); }
     26        tConstNodeArray nodes;
     27        void Process(const btDbvtNode* n) { nodes.push_back(n); }
    2828};
    2929
    … …  
    3131static DBVT_INLINE int                  indexof(const btDbvtNode* node)
    3232{
    33 return(node->parent->childs[1]==node);
     33        return(node->parent->childs[1]==node);
    3434}
    3535
    3636//
    3737static DBVT_INLINE btDbvtVolume merge(  const btDbvtVolume& a,
    38                                                                                 const btDbvtVolume& b)
    39 {
    40 #if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
    41 DBVT_ALIGN char locals[sizeof(btDbvtAabbMm)];
    42 btDbvtVolume&   res=*(btDbvtVolume*)locals;
     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;
    4343#else
    44 btDbvtVolume    res;
     44                btDbvtVolume    res;
    4545#endif
    46 Merge(a,b,res);
    47 return(res);
     46        Merge(a,b,res);
     47        return(res);
    4848}
    4949
    … …  
    5151static DBVT_INLINE btScalar             size(const btDbvtVolume& a)
    5252{
    53 const btVector3 edges=a.Lengths();
    54 return( edges.x()*edges.y()*edges.z()+
     53        const btVector3 edges=a.Lengths();
     54        return( edges.x()*edges.y()*edges.z()+
    5555                edges.x()+edges.y()+edges.z());
    5656}
    … …  
    5959static void                                             getmaxdepth(const btDbvtNode* node,int depth,int& maxdepth)
    6060{
    61 if(node->isinternal())
    62         {
    63         getmaxdepth(node->childs[0],depth+1,maxdepth);
    64         getmaxdepth(node->childs[0],depth+1,maxdepth);
     61        if(node->isinternal())
     62        {
     63                getmaxdepth(node->childs[0],depth+1,maxdepth);
     64                getmaxdepth(node->childs[0],depth+1,maxdepth);
    6565        } else maxdepth=btMax(maxdepth,depth);
    6666}
    … …  
    6868//
    6969static DBVT_INLINE void                 deletenode(     btDbvt* pdbvt,
    70                                                                                         btDbvtNode* node)
    71 {
    72 btAlignedFree(pdbvt->m_free);
    73 pdbvt->m_free=node;
    74 }
    75        
     70                                                                                   btDbvtNode* node)
     71{
     72        btAlignedFree(pdbvt->m_free);
     73        pdbvt->m_free=node;
     74}
     75
    7676//
    7777static 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);
     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);
    8787}
    8888
    8989//
    9090static DBVT_INLINE btDbvtNode*  createnode(     btDbvt* pdbvt,
    91                                                                                         btDbvtNode* parent,
    92                                                                                         void* data)
    93 {
    94 btDbvtNode*     node;
    95 if(pdbvt->m_free)
     91                                                                                   btDbvtNode* parent,
     92                                                                                   void* data)
     93{
     94        btDbvtNode*     node;
     95        if(pdbvt->m_free)
    9696        { node=pdbvt->m_free;pdbvt->m_free=0; }
    9797        else
    9898        { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); }
    99 node->parent    =       parent;
    100 node->data              =       data;
    101 node->childs[1] =       0;
    102 return(node);
     99        node->parent    =       parent;
     100        node->data              =       data;
     101        node->childs[1] =       0;
     102        return(node);
    103103}
    104104
    105105//
    106106static 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);
     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);
    114114}
    115115
    116116//
    117117static 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);
     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);
    126126}
    127127
    128128//
    129129static 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;
     130                                                                                   btDbvtNode* root,
     131                                                                                   btDbvtNode* leaf)
     132{
     133        if(!pdbvt->m_root)
     134        {
     135                pdbvt->m_root   =       leaf;
     136                leaf->parent    =       0;
    137137        }
    138138        else
    139139        {
    140         if(!root->isleaf())
    141                 {
    142                 do      {
    143                         root=root->childs[Select(       leaf->volume,
    144                                                                                 root->childs[0]->volume,
    145                                                                                 root->childs[1]->volume)];
     140                if(!root->isleaf())
     141                {
     142                        do      {
     143                                root=root->childs[Select(       leaf->volume,
     144                                        root->childs[0]->volume,
     145                                        root->childs[1]->volume)];
    146146                        } while(!root->isleaf());
    147147                }
    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))
     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;
    157194                                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 //
    173 static 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))
     195                                if(NotEqual(pb,prev->volume))
    196196                                {
    197                                 prev=prev->parent;
     197                                        prev=prev->parent;
    198198                                } else break;
    199199                        }
    200                 return(prev?prev:pdbvt->m_root);
     200                        return(prev?prev:pdbvt->m_root);
    201201                }
    202202                else
    203203                {                                                               
    204                 pdbvt->m_root=sibling;
    205                 sibling->parent=0;
    206                 deletenode(pdbvt,parent);
    207                 return(pdbvt->m_root);
     204                        pdbvt->m_root=sibling;
     205                        sibling->parent=0;
     206                        deletenode(pdbvt,parent);
     207                        return(pdbvt->m_root);
    208208                }                       
    209209        }
    … …  
    216216                                                                                        int depth=-1)
    217217{
    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);
     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);
    223223        }
    224224        else
    225225        {
    226         leaves.push_back(root);
     226                leaves.push_back(root);
    227227        }
    228228}
    … …  
    230230//
    231231static 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]);
     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]);
    243243                else
    244                 right.push_back(leaves[i]);
     244                        right.push_back(leaves[i]);
    245245        }
    246246}
    … …  
    250250{
    251251#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE
    252 DBVT_ALIGN char locals[sizeof(btDbvtVolume)];
    253 btDbvtVolume&   volume=*(btDbvtVolume*)locals;
    254 volume=leaves[0]->volume;
     252        ATTRIBUTE_ALIGNED16(char        locals[sizeof(btDbvtVolume)]);
     253        btDbvtVolume&   volume=*(btDbvtVolume*)locals;
     254        volume=leaves[0]->volume;
    255255#else
    256 btDbvtVolume volume=leaves[0]->volume;
     256        btDbvtVolume volume=leaves[0]->volume;
    257257#endif
    258 for(int i=1,ni=leaves.size();i<ni;++i)
    259         {
    260         Merge(volume,leaves[i]->volume,volume);
    261         }
    262 return(volume);
     258        for(int i=1,ni=leaves.size();i<ni;++i)
     259        {
     260                Merge(volume,leaves[i]->volume,volume);
     261        }
     262        return(volume);
    263263}
    264264
    265265//
    266266static 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)
     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)
    279279                                {
    280                                 minsize         =       sz;
    281                                 minidx[0]       =       i;
    282                                 minidx[1]       =       j;
     280                                        minsize         =       sz;
     281                                        minidx[0]       =       i;
     282                                        minidx[1]       =       j;
    283283                                }
    284284                        }
    285285                }
    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();
     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();
    295295        }
    296296}
    … …  
    301301                                                                        int bu_treshold)
    302302{
    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)
     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)
    321321                                {
    322                                 ++splitcount[j][dot(x,axis[j])>0?1:0];
     322                                        ++splitcount[j][dot(x,axis[j])>0?1:0];
    323323                                }
    324324                        }
    325                 for( i=0;i<3;++i)
    326                         {
    327                         if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
     325                        for( i=0;i<3;++i)
     326                        {
     327                                if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
    328328                                {
    329                                 const int       midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
    330                                 if(midp<bestmidp)
     329                                        const int       midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1]));
     330                                        if(midp<bestmidp)
    331331                                        {
    332                                         bestaxis=i;
    333                                         bestmidp=midp;
     332                                                bestaxis=i;
     333                                                bestmidp=midp;
    334334                                        }
    335335                                }
    336336                        }
    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]);
     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]);
    342342                        }
    343343                        else
    344344                        {
    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)
     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)
    348348                                {
    349                                 sets[i&1].push_back(leaves[i]);
     349                                        sets[i&1].push_back(leaves[i]);
    350350                                }
    351351                        }
    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);
     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);
    358358                }
    359359                else
    360360                {
    361                 bottomup(pdbvt,leaves);
    362                 return(leaves[0]);
    363                 }
    364         }
    365 return(leaves[0]);
     361                        bottomup(pdbvt,leaves);
     362                        return(leaves[0]);
     363                }
     364        }
     365        return(leaves[0]);
    366366}
    367367
    … …  
    369369static DBVT_INLINE btDbvtNode*  sort(btDbvtNode* n,btDbvtNode*& r)
    370370{
    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);
     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);
    394394}
    395395
    … …  
    397397static DBVT_INLINE btDbvtNode*  walkup(btDbvtNode* n,int count)
    398398{
    399 while(n&&(count--)) n=n->parent;
    400 return(n);
     399        while(n&&(count--)) n=n->parent;
     400        return(n);
    401401}
    402402
    … …  
    406406
    407407//
    408                                 btDbvt::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 //
    418                                 btDbvt::~btDbvt()
    419 {
    420 clear();
     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();
    421421}
    422422
    … …  
    424424void                    btDbvt::clear()
    425425{
    426 if(m_root)      recursedeletenode(this,m_root);
    427 btAlignedFree(m_free);
    428 m_free=0;
     426        if(m_root)      recursedeletenode(this,m_root);
     427        btAlignedFree(m_free);
     428        m_free=0;
    429429}
    430430
    … …  
    432432void                    btDbvt::optimizeBottomUp()
    433433{
    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];
     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];
    441441        }
    442442}
    … …  
    445445void                    btDbvt::optimizeTopDown(int bu_treshold)
    446446{
    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);
     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);
    453453        }
    454454}
    … …  
    457457void                    btDbvt::optimizeIncremental(int passes)
    458458{
    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;
     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;
    472472                } while(--passes);
    473473        }
    … …  
    477477btDbvtNode*     btDbvt::insert(const btDbvtVolume& volume,void* data)
    478478{
    479 btDbvtNode*     leaf=createnode(this,0,volume,data);
    480 insertleaf(this,m_root,leaf);
    481 ++m_leaves;
    482 return(leaf);
     479        btDbvtNode*     leaf=createnode(this,0,volume,data);
     480        insertleaf(this,m_root,leaf);
     481        ++m_leaves;
     482        return(leaf);
    483483}
    484484
    … …  
    486486void                    btDbvt::update(btDbvtNode* leaf,int lookahead)
    487487{
    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;
     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;
    496496                        }
    497497                } else root=m_root;
    498498        }
    499 insertleaf(this,root,leaf);
    500 }
    501 
    502 //
    503 void                    btDbvt::update(btDbvtNode* leaf,const 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;
     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;
    513513                        }
    514514                } else root=m_root;
    515515        }
    516 leaf->volume=volume;
    517 insertleaf(this,root,leaf);
    518 }
    519 
    520 //
    521 bool                    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 //
    531 bool                    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 //
    540 bool                    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);
     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);
    546546}
    547547
    … …  
    549549void                    btDbvt::remove(btDbvtNode* leaf)
    550550{
    551 removeleaf(this,leaf);
    552 deletenode(this,leaf);
    553 --m_leaves;
     551        removeleaf(this,leaf);
     552        deletenode(this,leaf);
     553        --m_leaves;
    554554}
    555555
    … …  
    557557void                    btDbvt::write(IWriter* iwriter) const
    558558{
    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);
     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);
    573573                }
    574574                else
    575575                {
    576                 iwriter->WriteLeaf(n,i,p);
     576                        iwriter->WriteLeaf(n,i,p);
    577577                }       
    578578        }
    … …  
    582582void                    btDbvt::clone(btDbvt& dest,IClone* iclone) const
    583583{
    584 dest.clear();
    585 if(m_root!=0)
     584        dest.clear();
     585        if(m_root!=0)
    586586        {       
    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;
     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;
    597597                        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));
     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));
    603603                        }
    604604                        else
    605605                        {
    606                         iclone->CloneLeaf(n);
     606                                iclone->CloneLeaf(n);
    607607                        }
    608608                } while(stack.size()>0);
    … …  
    613613int                             btDbvt::maxdepth(const btDbvtNode* node)
    614614{
    615 int     depth=0;
    616 if(node) getmaxdepth(node,1,depth);
    617 return(depth);
     615        int     depth=0;
     616        if(node) getmaxdepth(node,1,depth);
     617        return(depth);
    618618}
    619619
    … …  
    621621int                             btDbvt::countLeaves(const btDbvtNode* node)
    622622{
    623 if(node->isinternal())
    624         return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
     623        if(node->isinternal())
     624                return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
    625625        else
    626         return(1);
     626                return(1);
    627627}
    628628
    … …  
    630630void                    btDbvt::extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves)
    631631{
    632 if(node->isinternal())
    633         {
    634         extractLeaves(node->childs[0],leaves);
    635         extractLeaves(node->childs[1],leaves);
     632        if(node->isinternal())
     633        {
     634                extractLeaves(node->childs[0],leaves);
     635                extractLeaves(node->childs[1],leaves);
    636636        }
    637637        else
    638638        {
    639         leaves.push_back(node);
     639                leaves.push_back(node);
    640640        }       
    641641}
    … …  
    658658
    659659Benchmarking 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
     660World scale: 100.000000
     661Extents base: 1.000000
     662Extents range: 4.000000
     663Leaves: 8192
     664sizeof(btDbvtVolume): 32 bytes
     665sizeof(btDbvtNode):   44 bytes
    666666[1] btDbvtVolume intersections: 3499 ms (-1%)
    667667[2] btDbvtVolume merges: 1934 ms (0%)
    … …  
    670670[5] btDbvt::collideTT xform: 7379 ms (-1%)
    671671[6] btDbvt::collideTT xform,self: 7270 ms (-2%)
    672 [7] btDbvt::collideRAY: 6314 ms (0%),(332143 r/s)
     672[7] btDbvt::rayTest: 6314 ms (0%),(332143 r/s)
    673673[8] insert/remove: 2093 ms (0%),(1001983 ir/s)
    674674[9] updates (teleport): 1879 ms (-3%),(1116100 u/s)
    … …  
    685685struct btDbvtBenchmark
    686686{
    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)
     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)
    696696                        { if(depth>=m_depth) m_depth=depth; else printf("wrong depth: %f (should be >= %f)\r\n",depth,m_depth); }
    697697                }
    698         int                     m_pcount;
    699         btScalar        m_depth;
    700         bool            m_checksort;
     698                int                     m_pcount;
     699                btScalar        m_depth;
     700                bool            m_checksort;
    701701        };
    702 struct P14 : btDbvt::ICollide
    703         {
    704         struct Node
    705                 {
    706                 const btDbvtNode*       leaf;
    707                 btScalar                        depth;
     702        struct P14 : btDbvt::ICollide
     703        {
     704                struct Node
     705                {
     706                        const btDbvtNode*       leaf;
     707                        btScalar                        depth;
    708708                };
    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;
     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;
    722722        };
    723 struct P15 : btDbvt::ICollide
    724         {
    725         struct Node
    726                 {
    727                 const btDbvtNode*       leaf;
    728                 btScalar                        depth;
     723        struct P15 : btDbvt::ICollide
     724        {
     725                struct Node
     726                {
     727                        const btDbvtNode*       leaf;
     728                        btScalar                        depth;
    729729                };
    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;
     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;
    744744        };
    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);
     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);
    774774                }
    775775        }
    … …  
    778778void                    btDbvt::benchmark()
    779779{
    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::collideRAY
    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)
     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)
    873873        {// 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)
     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)
    890890                                {
    891                                 results[k]=Intersect(volumes[j],volumes[k]);
     891                                        results[k]=Intersect(volumes[j],volumes[k]);
    892892                                }
    893893                        }
    894894                }
    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)
     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)
    899899        {// 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)
     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)
    916916                                {
    917                                 Merge(volumes[j],volumes[k],results[k]);
     917                                        Merge(volumes[j],volumes[k],results[k]);
    918918                                }
    919919                        }
    920920                }
    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)
     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)
    925925        {// 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)
     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)
    943943        {// 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)
     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)
    959959        {// 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)
     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)
    983983        {// 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)
     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)
    10051005        {// 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         }
    1033 if(cfgBenchmark8_Enable)
     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)
    10341034        {// 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)
     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)
    10531053        {// 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)
     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)
    10751075        {// 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)
     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)
    10941094                        {                       
    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)
     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)
    11061106        {// 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)
     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)
    11221122        {// 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)
     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)
    11391139                                {
    1140                                 results[k]=NotEqual(volumes[j],volumes[k]);
     1140                                        results[k]=NotEqual(volumes[j],volumes[k]);
    11411141                                }
    11421142                        }
    11431143                }
    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)
     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)
    11481148        {// 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)
     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)
    11731173        {// 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)
     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)
    12001200        {// 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)
     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)
    12281228        {// 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)
     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)
    12541254        {// 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)
     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)
    12781278                                {
    1279                                 const int idx=indices[k];
    1280                                 results[idx]=Select(volumes[idx],volumes[j],volumes[k]);
     1279                                        const int idx=indices[k];
     1280                                        results[idx]=Select(volumes[idx],volumes[j],volumes[k]);
    12811281                                }
    12821282                        }
    12831283                }
    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");
     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");
    12881288}
    12891289#endif
Note: See TracChangeset for help on using the changeset viewer.