diff options
Diffstat (limited to 'extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp')
| -rw-r--r-- | extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp | 1422 |
1 files changed, 741 insertions, 681 deletions
diff --git a/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp b/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp index 2ca20cdd8b8..166cb04c0b0 100644 --- a/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp +++ b/extern/bullet2/src/BulletCollision/BroadphaseCollision/btDbvt.cpp @@ -17,210 +17,226 @@ subject to the following restrictions: #include "btDbvt.h" // -typedef btAlignedObjectArray<btDbvtNode*> tNodeArray; -typedef btAlignedObjectArray<const btDbvtNode*> tConstNodeArray; +typedef btAlignedObjectArray<btDbvtNode*> tNodeArray; +typedef btAlignedObjectArray<const btDbvtNode*> tConstNodeArray; // struct btDbvtNodeEnumerator : btDbvt::ICollide { - tConstNodeArray nodes; + tConstNodeArray nodes; void Process(const btDbvtNode* n) { nodes.push_back(n); } }; // -static DBVT_INLINE int indexof(const btDbvtNode* node) +static DBVT_INLINE int indexof(const btDbvtNode* node) { - return(node->parent->childs[1]==node); + return (node->parent->childs[1] == node); } // -static DBVT_INLINE btDbvtVolume merge( const btDbvtVolume& a, +static DBVT_INLINE btDbvtVolume merge(const btDbvtVolume& a, const btDbvtVolume& b) { -#if (DBVT_MERGE_IMPL==DBVT_IMPL_SSE) - ATTRIBUTE_ALIGNED16( char locals[sizeof(btDbvtAabbMm)]); - btDbvtVolume* ptr = (btDbvtVolume*) locals; - btDbvtVolume& res=*ptr; +#ifdef BT_USE_SSE + ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtAabbMm)]); + btDbvtVolume* ptr = (btDbvtVolume*)locals; + btDbvtVolume& res = *ptr; #else - btDbvtVolume res; + btDbvtVolume res; #endif - Merge(a,b,res); - return(res); + Merge(a, b, res); + return (res); } // volume+edge lengths -static DBVT_INLINE btScalar size(const btDbvtVolume& a) +static DBVT_INLINE btScalar size(const btDbvtVolume& a) { - const btVector3 edges=a.Lengths(); - return( edges.x()*edges.y()*edges.z()+ - edges.x()+edges.y()+edges.z()); + const btVector3 edges = a.Lengths(); + return (edges.x() * edges.y() * edges.z() + + edges.x() + edges.y() + edges.z()); } // -static void getmaxdepth(const btDbvtNode* node,int depth,int& maxdepth) +static void getmaxdepth(const btDbvtNode* node, int depth, int& maxdepth) { - if(node->isinternal()) + if (node->isinternal()) { - getmaxdepth(node->childs[0],depth+1,maxdepth); - getmaxdepth(node->childs[1],depth+1,maxdepth); - } else maxdepth=btMax(maxdepth,depth); + getmaxdepth(node->childs[0], depth + 1, maxdepth); + getmaxdepth(node->childs[1], depth + 1, maxdepth); + } + else + maxdepth = btMax(maxdepth, depth); } // -static DBVT_INLINE void deletenode( btDbvt* pdbvt, - btDbvtNode* node) +static DBVT_INLINE void deletenode(btDbvt* pdbvt, + btDbvtNode* node) { btAlignedFree(pdbvt->m_free); - pdbvt->m_free=node; + pdbvt->m_free = node; } // -static void recursedeletenode( btDbvt* pdbvt, - btDbvtNode* node) +static void recursedeletenode(btDbvt* pdbvt, + btDbvtNode* node) { - if(!node->isleaf()) + if (node == 0) return; + if (!node->isleaf()) { - recursedeletenode(pdbvt,node->childs[0]); - recursedeletenode(pdbvt,node->childs[1]); + recursedeletenode(pdbvt, node->childs[0]); + recursedeletenode(pdbvt, node->childs[1]); } - if(node==pdbvt->m_root) pdbvt->m_root=0; - deletenode(pdbvt,node); + if (node == pdbvt->m_root) pdbvt->m_root = 0; + deletenode(pdbvt, node); } // -static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt, - btDbvtNode* parent, - void* data) +static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt, + btDbvtNode* parent, + void* data) { - btDbvtNode* node; - if(pdbvt->m_free) - { node=pdbvt->m_free;pdbvt->m_free=0; } + btDbvtNode* node; + if (pdbvt->m_free) + { + node = pdbvt->m_free; + pdbvt->m_free = 0; + } else - { node=new(btAlignedAlloc(sizeof(btDbvtNode),16)) btDbvtNode(); } - node->parent = parent; - node->data = data; - node->childs[1] = 0; - return(node); + { + node = new (btAlignedAlloc(sizeof(btDbvtNode), 16)) btDbvtNode(); + } + node->parent = parent; + node->data = data; + node->childs[1] = 0; + return (node); } // -static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt, - btDbvtNode* parent, - const btDbvtVolume& volume, - void* data) +static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt, + btDbvtNode* parent, + const btDbvtVolume& volume, + void* data) { - btDbvtNode* node=createnode(pdbvt,parent,data); - node->volume=volume; - return(node); + btDbvtNode* node = createnode(pdbvt, parent, data); + node->volume = volume; + return (node); } // -static DBVT_INLINE btDbvtNode* createnode( btDbvt* pdbvt, - btDbvtNode* parent, - const btDbvtVolume& volume0, - const btDbvtVolume& volume1, - void* data) +static DBVT_INLINE btDbvtNode* createnode(btDbvt* pdbvt, + btDbvtNode* parent, + const btDbvtVolume& volume0, + const btDbvtVolume& volume1, + void* data) { - btDbvtNode* node=createnode(pdbvt,parent,data); - Merge(volume0,volume1,node->volume); - return(node); + btDbvtNode* node = createnode(pdbvt, parent, data); + Merge(volume0, volume1, node->volume); + return (node); } // -static void insertleaf( btDbvt* pdbvt, - btDbvtNode* root, - btDbvtNode* leaf) +static void insertleaf(btDbvt* pdbvt, + btDbvtNode* root, + btDbvtNode* leaf) { - if(!pdbvt->m_root) + if (!pdbvt->m_root) { - pdbvt->m_root = leaf; - leaf->parent = 0; + pdbvt->m_root = leaf; + leaf->parent = 0; } else { - if(!root->isleaf()) + if (!root->isleaf()) { - do { - root=root->childs[Select( leaf->volume, - root->childs[0]->volume, - root->childs[1]->volume)]; - } while(!root->isleaf()); + do + { + root = root->childs[Select(leaf->volume, + root->childs[0]->volume, + root->childs[1]->volume)]; + } while (!root->isleaf()); } - btDbvtNode* prev=root->parent; - btDbvtNode* node=createnode(pdbvt,prev,leaf->volume,root->volume,0); - if(prev) + btDbvtNode* prev = root->parent; + btDbvtNode* node = createnode(pdbvt, prev, leaf->volume, root->volume, 0); + if (prev) { - prev->childs[indexof(root)] = node; - node->childs[0] = root;root->parent=node; - node->childs[1] = leaf;leaf->parent=node; - do { - if(!prev->volume.Contain(node->volume)) - Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume); + prev->childs[indexof(root)] = node; + node->childs[0] = root; + root->parent = node; + node->childs[1] = leaf; + leaf->parent = node; + do + { + if (!prev->volume.Contain(node->volume)) + Merge(prev->childs[0]->volume, prev->childs[1]->volume, prev->volume); else break; - node=prev; - } while(0!=(prev=node->parent)); + node = prev; + } while (0 != (prev = node->parent)); } else { - node->childs[0] = root;root->parent=node; - node->childs[1] = leaf;leaf->parent=node; - pdbvt->m_root = node; + node->childs[0] = root; + root->parent = node; + node->childs[1] = leaf; + leaf->parent = node; + pdbvt->m_root = node; } } } // -static btDbvtNode* removeleaf( btDbvt* pdbvt, - btDbvtNode* leaf) +static btDbvtNode* removeleaf(btDbvt* pdbvt, + btDbvtNode* leaf) { - if(leaf==pdbvt->m_root) + if (leaf == pdbvt->m_root) { - pdbvt->m_root=0; - return(0); + pdbvt->m_root = 0; + return (0); } else { - btDbvtNode* parent=leaf->parent; - btDbvtNode* prev=parent->parent; - btDbvtNode* sibling=parent->childs[1-indexof(leaf)]; - if(prev) + btDbvtNode* parent = leaf->parent; + btDbvtNode* prev = parent->parent; + btDbvtNode* sibling = parent->childs[1 - indexof(leaf)]; + if (prev) { - prev->childs[indexof(parent)]=sibling; - sibling->parent=prev; - deletenode(pdbvt,parent); - while(prev) + prev->childs[indexof(parent)] = sibling; + sibling->parent = prev; + deletenode(pdbvt, parent); + while (prev) { - const btDbvtVolume pb=prev->volume; - Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume); - if(NotEqual(pb,prev->volume)) + const btDbvtVolume pb = prev->volume; + Merge(prev->childs[0]->volume, prev->childs[1]->volume, prev->volume); + if (NotEqual(pb, prev->volume)) { - prev=prev->parent; - } else break; + prev = prev->parent; + } + else + break; } - return(prev?prev:pdbvt->m_root); + return (prev ? prev : pdbvt->m_root); } else - { - pdbvt->m_root=sibling; - sibling->parent=0; - deletenode(pdbvt,parent); - return(pdbvt->m_root); - } + { + pdbvt->m_root = sibling; + sibling->parent = 0; + deletenode(pdbvt, parent); + return (pdbvt->m_root); + } } } // -static void fetchleaves(btDbvt* pdbvt, - btDbvtNode* root, - tNodeArray& leaves, - int depth=-1) +static void fetchleaves(btDbvt* pdbvt, + btDbvtNode* root, + tNodeArray& leaves, + int depth = -1) { - if(root->isinternal()&&depth) + if (root->isinternal() && depth) { - fetchleaves(pdbvt,root->childs[0],leaves,depth-1); - fetchleaves(pdbvt,root->childs[1],leaves,depth-1); - deletenode(pdbvt,root); + fetchleaves(pdbvt, root->childs[0], leaves, depth - 1); + fetchleaves(pdbvt, root->childs[1], leaves, depth - 1); + deletenode(pdbvt, root); } else { @@ -229,170 +245,204 @@ static void fetchleaves(btDbvt* pdbvt, } // -static void split( const tNodeArray& leaves, - tNodeArray& left, - tNodeArray& right, - const btVector3& org, - const btVector3& axis) +static bool leftOfAxis(const btDbvtNode* node, + const btVector3& org, + const btVector3& axis) { - left.resize(0); - right.resize(0); - for(int i=0,ni=leaves.size();i<ni;++i) + return btDot(axis, node->volume.Center() - org) <= 0; +} + +// Partitions leaves such that leaves[0, n) are on the +// left of axis, and leaves[n, count) are on the right +// of axis. returns N. +static int split(btDbvtNode** leaves, + int count, + const btVector3& org, + const btVector3& axis) +{ + int begin = 0; + int end = count; + for (;;) { - if(btDot(axis,leaves[i]->volume.Center()-org)<0) - left.push_back(leaves[i]); - else - right.push_back(leaves[i]); + while (begin != end && leftOfAxis(leaves[begin], org, axis)) + { + ++begin; + } + + if (begin == end) + { + break; + } + + while (begin != end && !leftOfAxis(leaves[end - 1], org, axis)) + { + --end; + } + + if (begin == end) + { + break; + } + + // swap out of place nodes + --end; + btDbvtNode* temp = leaves[begin]; + leaves[begin] = leaves[end]; + leaves[end] = temp; + ++begin; } + + return begin; } // -static btDbvtVolume bounds( const tNodeArray& leaves) +static btDbvtVolume bounds(btDbvtNode** leaves, + int count) { -#if DBVT_MERGE_IMPL==DBVT_IMPL_SSE - ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtVolume)]); - btDbvtVolume* ptr = (btDbvtVolume*) locals; - btDbvtVolume& volume=*ptr; - volume=leaves[0]->volume; +#ifdef BT_USE_SSE + ATTRIBUTE_ALIGNED16(char locals[sizeof(btDbvtVolume)]); + btDbvtVolume* ptr = (btDbvtVolume*)locals; + btDbvtVolume& volume = *ptr; + volume = leaves[0]->volume; #else - btDbvtVolume volume=leaves[0]->volume; + btDbvtVolume volume = leaves[0]->volume; #endif - for(int i=1,ni=leaves.size();i<ni;++i) + for (int i = 1, ni = count; i < ni; ++i) { - Merge(volume,leaves[i]->volume,volume); + Merge(volume, leaves[i]->volume, volume); } - return(volume); + return (volume); } // -static void bottomup( btDbvt* pdbvt, - tNodeArray& leaves) +static void bottomup(btDbvt* pdbvt, + btDbvtNode** leaves, + int count) { - while(leaves.size()>1) + while (count > 1) { - btScalar minsize=SIMD_INFINITY; - int minidx[2]={-1,-1}; - for(int i=0;i<leaves.size();++i) + btScalar minsize = SIMD_INFINITY; + int minidx[2] = {-1, -1}; + for (int i = 0; i < count; ++i) { - for(int j=i+1;j<leaves.size();++j) + for (int j = i + 1; j < count; ++j) { - const btScalar sz=size(merge(leaves[i]->volume,leaves[j]->volume)); - if(sz<minsize) + const btScalar sz = size(merge(leaves[i]->volume, leaves[j]->volume)); + if (sz < minsize) { - minsize = sz; - minidx[0] = i; - minidx[1] = j; + minsize = sz; + minidx[0] = i; + minidx[1] = j; } } } - btDbvtNode* n[] = {leaves[minidx[0]],leaves[minidx[1]]}; - btDbvtNode* p = createnode(pdbvt,0,n[0]->volume,n[1]->volume,0); - p->childs[0] = n[0]; - p->childs[1] = n[1]; - n[0]->parent = p; - n[1]->parent = p; - leaves[minidx[0]] = p; - leaves.swap(minidx[1],leaves.size()-1); - leaves.pop_back(); + btDbvtNode* n[] = {leaves[minidx[0]], leaves[minidx[1]]}; + btDbvtNode* p = createnode(pdbvt, 0, n[0]->volume, n[1]->volume, 0); + p->childs[0] = n[0]; + p->childs[1] = n[1]; + n[0]->parent = p; + n[1]->parent = p; + leaves[minidx[0]] = p; + leaves[minidx[1]] = leaves[count - 1]; + --count; } } // -static btDbvtNode* topdown(btDbvt* pdbvt, - tNodeArray& leaves, - int bu_treshold) +static btDbvtNode* topdown(btDbvt* pdbvt, + btDbvtNode** leaves, + int count, + int bu_treshold) { - static const btVector3 axis[]={btVector3(1,0,0), - btVector3(0,1,0), - btVector3(0,0,1)}; - if(leaves.size()>1) + static const btVector3 axis[] = {btVector3(1, 0, 0), + btVector3(0, 1, 0), + btVector3(0, 0, 1)}; + btAssert(bu_treshold > 2); + if (count > 1) { - if(leaves.size()>bu_treshold) + if (count > bu_treshold) { - const btDbvtVolume vol=bounds(leaves); - const btVector3 org=vol.Center(); - tNodeArray sets[2]; - int bestaxis=-1; - int bestmidp=leaves.size(); - int splitcount[3][2]={{0,0},{0,0},{0,0}}; + const btDbvtVolume vol = bounds(leaves, count); + const btVector3 org = vol.Center(); + int partition; + int bestaxis = -1; + int bestmidp = count; + int splitcount[3][2] = {{0, 0}, {0, 0}, {0, 0}}; int i; - for( i=0;i<leaves.size();++i) + for (i = 0; i < count; ++i) { - const btVector3 x=leaves[i]->volume.Center()-org; - for(int j=0;j<3;++j) + const btVector3 x = leaves[i]->volume.Center() - org; + for (int j = 0; j < 3; ++j) { - ++splitcount[j][btDot(x,axis[j])>0?1:0]; + ++splitcount[j][btDot(x, axis[j]) > 0 ? 1 : 0]; } } - for( i=0;i<3;++i) + for (i = 0; i < 3; ++i) { - if((splitcount[i][0]>0)&&(splitcount[i][1]>0)) + if ((splitcount[i][0] > 0) && (splitcount[i][1] > 0)) { - const int midp=(int)btFabs(btScalar(splitcount[i][0]-splitcount[i][1])); - if(midp<bestmidp) + const int midp = (int)btFabs(btScalar(splitcount[i][0] - splitcount[i][1])); + if (midp < bestmidp) { - bestaxis=i; - bestmidp=midp; + bestaxis = i; + bestmidp = midp; } } } - if(bestaxis>=0) + if (bestaxis >= 0) { - sets[0].reserve(splitcount[bestaxis][0]); - sets[1].reserve(splitcount[bestaxis][1]); - split(leaves,sets[0],sets[1],org,axis[bestaxis]); + partition = split(leaves, count, org, axis[bestaxis]); + btAssert(partition != 0 && partition != count); } else { - sets[0].reserve(leaves.size()/2+1); - sets[1].reserve(leaves.size()/2); - for(int i=0,ni=leaves.size();i<ni;++i) - { - sets[i&1].push_back(leaves[i]); - } + partition = count / 2 + 1; } - btDbvtNode* node=createnode(pdbvt,0,vol,0); - node->childs[0]=topdown(pdbvt,sets[0],bu_treshold); - node->childs[1]=topdown(pdbvt,sets[1],bu_treshold); - node->childs[0]->parent=node; - node->childs[1]->parent=node; - return(node); + btDbvtNode* node = createnode(pdbvt, 0, vol, 0); + node->childs[0] = topdown(pdbvt, &leaves[0], partition, bu_treshold); + node->childs[1] = topdown(pdbvt, &leaves[partition], count - partition, bu_treshold); + node->childs[0]->parent = node; + node->childs[1]->parent = node; + return (node); } else { - bottomup(pdbvt,leaves); - return(leaves[0]); + bottomup(pdbvt, leaves, count); + return (leaves[0]); } } - return(leaves[0]); + return (leaves[0]); } // -static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n,btDbvtNode*& r) +static DBVT_INLINE btDbvtNode* sort(btDbvtNode* n, btDbvtNode*& r) { - btDbvtNode* p=n->parent; + btDbvtNode* p = n->parent; btAssert(n->isinternal()); - if(p>n) + if (p > n) { - const int i=indexof(n); - const int j=1-i; - btDbvtNode* s=p->childs[j]; - btDbvtNode* q=p->parent; - btAssert(n==p->childs[i]); - if(q) q->childs[indexof(p)]=n; else r=n; - s->parent=n; - p->parent=n; - n->parent=q; - p->childs[0]=n->childs[0]; - p->childs[1]=n->childs[1]; - n->childs[0]->parent=p; - n->childs[1]->parent=p; - n->childs[i]=p; - n->childs[j]=s; - btSwap(p->volume,n->volume); - return(p); + const int i = indexof(n); + const int j = 1 - i; + btDbvtNode* s = p->childs[j]; + btDbvtNode* q = p->parent; + btAssert(n == p->childs[i]); + if (q) + q->childs[indexof(p)] = n; + else + r = n; + s->parent = n; + p->parent = n; + n->parent = q; + p->childs[0] = n->childs[0]; + p->childs[1] = n->childs[1]; + n->childs[0]->parent = p; + n->childs[1]->parent = p; + n->childs[i] = p; + n->childs[j] = s; + btSwap(p->volume, n->volume); + return (p); } - return(n); + return (n); } #if 0 @@ -410,11 +460,11 @@ static DBVT_INLINE btDbvtNode* walkup(btDbvtNode* n,int count) // btDbvt::btDbvt() { - m_root = 0; - m_free = 0; - m_lkhd = -1; - m_leaves = 0; - m_opath = 0; + m_root = 0; + m_free = 0; + m_lkhd = -1; + m_leaves = 0; + m_opath = 0; } // @@ -424,228 +474,233 @@ btDbvt::~btDbvt() } // -void btDbvt::clear() +void btDbvt::clear() { - if(m_root) - recursedeletenode(this,m_root); + if (m_root) + recursedeletenode(this, m_root); btAlignedFree(m_free); - m_free=0; - m_lkhd = -1; + m_free = 0; + m_lkhd = -1; m_stkStack.clear(); - m_opath = 0; - + m_opath = 0; } // -void btDbvt::optimizeBottomUp() +void btDbvt::optimizeBottomUp() { - if(m_root) + if (m_root) { tNodeArray leaves; leaves.reserve(m_leaves); - fetchleaves(this,m_root,leaves); - bottomup(this,leaves); - m_root=leaves[0]; + fetchleaves(this, m_root, leaves); + bottomup(this, &leaves[0], leaves.size()); + m_root = leaves[0]; } } // -void btDbvt::optimizeTopDown(int bu_treshold) +void btDbvt::optimizeTopDown(int bu_treshold) { - if(m_root) + if (m_root) { - tNodeArray leaves; + tNodeArray leaves; leaves.reserve(m_leaves); - fetchleaves(this,m_root,leaves); - m_root=topdown(this,leaves,bu_treshold); + fetchleaves(this, m_root, leaves); + m_root = topdown(this, &leaves[0], leaves.size(), bu_treshold); } } // -void btDbvt::optimizeIncremental(int passes) +void btDbvt::optimizeIncremental(int passes) { - if(passes<0) passes=m_leaves; - if(m_root&&(passes>0)) + if (passes < 0) passes = m_leaves; + if (m_root && (passes > 0)) { - do { - btDbvtNode* node=m_root; - unsigned bit=0; - while(node->isinternal()) + do + { + btDbvtNode* node = m_root; + unsigned bit = 0; + while (node->isinternal()) { - node=sort(node,m_root)->childs[(m_opath>>bit)&1]; - bit=(bit+1)&(sizeof(unsigned)*8-1); + node = sort(node, m_root)->childs[(m_opath >> bit) & 1]; + bit = (bit + 1) & (sizeof(unsigned) * 8 - 1); } update(node); ++m_opath; - } while(--passes); + } while (--passes); } } // -btDbvtNode* btDbvt::insert(const btDbvtVolume& volume,void* data) +btDbvtNode* btDbvt::insert(const btDbvtVolume& volume, void* data) { - btDbvtNode* leaf=createnode(this,0,volume,data); - insertleaf(this,m_root,leaf); + btDbvtNode* leaf = createnode(this, 0, volume, data); + insertleaf(this, m_root, leaf); ++m_leaves; - return(leaf); + return (leaf); } // -void btDbvt::update(btDbvtNode* leaf,int lookahead) +void btDbvt::update(btDbvtNode* leaf, int lookahead) { - btDbvtNode* root=removeleaf(this,leaf); - if(root) + btDbvtNode* root = removeleaf(this, leaf); + if (root) { - if(lookahead>=0) + if (lookahead >= 0) { - for(int i=0;(i<lookahead)&&root->parent;++i) + for (int i = 0; (i < lookahead) && root->parent; ++i) { - root=root->parent; + root = root->parent; } - } else root=m_root; + } + else + root = m_root; } - insertleaf(this,root,leaf); + insertleaf(this, root, leaf); } // -void btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume) +void btDbvt::update(btDbvtNode* leaf, btDbvtVolume& volume) { - btDbvtNode* root=removeleaf(this,leaf); - if(root) + btDbvtNode* root = removeleaf(this, leaf); + if (root) { - if(m_lkhd>=0) + if (m_lkhd >= 0) { - for(int i=0;(i<m_lkhd)&&root->parent;++i) + for (int i = 0; (i < m_lkhd) && root->parent; ++i) { - root=root->parent; + root = root->parent; } - } else root=m_root; + } + else + root = m_root; } - leaf->volume=volume; - insertleaf(this,root,leaf); + leaf->volume = volume; + insertleaf(this, root, leaf); } // -bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity,btScalar margin) +bool btDbvt::update(btDbvtNode* leaf, btDbvtVolume& volume, const btVector3& velocity, btScalar margin) { - if(leaf->volume.Contain(volume)) return(false); - volume.Expand(btVector3(margin,margin,margin)); + if (leaf->volume.Contain(volume)) return (false); + volume.Expand(btVector3(margin, margin, margin)); volume.SignedExpand(velocity); - update(leaf,volume); - return(true); + update(leaf, volume); + return (true); } // -bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,const btVector3& velocity) +bool btDbvt::update(btDbvtNode* leaf, btDbvtVolume& volume, const btVector3& velocity) { - if(leaf->volume.Contain(volume)) return(false); + if (leaf->volume.Contain(volume)) return (false); volume.SignedExpand(velocity); - update(leaf,volume); - return(true); + update(leaf, volume); + return (true); } // -bool btDbvt::update(btDbvtNode* leaf,btDbvtVolume& volume,btScalar margin) +bool btDbvt::update(btDbvtNode* leaf, btDbvtVolume& volume, btScalar margin) { - if(leaf->volume.Contain(volume)) return(false); - volume.Expand(btVector3(margin,margin,margin)); - update(leaf,volume); - return(true); + if (leaf->volume.Contain(volume)) return (false); + volume.Expand(btVector3(margin, margin, margin)); + update(leaf, volume); + return (true); } // -void btDbvt::remove(btDbvtNode* leaf) +void btDbvt::remove(btDbvtNode* leaf) { - removeleaf(this,leaf); - deletenode(this,leaf); + removeleaf(this, leaf); + deletenode(this, leaf); --m_leaves; } // -void btDbvt::write(IWriter* iwriter) const +void btDbvt::write(IWriter* iwriter) const { - btDbvtNodeEnumerator nodes; - nodes.nodes.reserve(m_leaves*2); - enumNodes(m_root,nodes); - iwriter->Prepare(m_root,nodes.nodes.size()); - for(int i=0;i<nodes.nodes.size();++i) + btDbvtNodeEnumerator nodes; + nodes.nodes.reserve(m_leaves * 2); + enumNodes(m_root, nodes); + iwriter->Prepare(m_root, nodes.nodes.size()); + for (int i = 0; i < nodes.nodes.size(); ++i) { - const btDbvtNode* n=nodes.nodes[i]; - int p=-1; - if(n->parent) p=nodes.nodes.findLinearSearch(n->parent); - if(n->isinternal()) + const btDbvtNode* n = nodes.nodes[i]; + int p = -1; + if (n->parent) p = nodes.nodes.findLinearSearch(n->parent); + if (n->isinternal()) { - const int c0=nodes.nodes.findLinearSearch(n->childs[0]); - const int c1=nodes.nodes.findLinearSearch(n->childs[1]); - iwriter->WriteNode(n,i,p,c0,c1); + const int c0 = nodes.nodes.findLinearSearch(n->childs[0]); + const int c1 = nodes.nodes.findLinearSearch(n->childs[1]); + iwriter->WriteNode(n, i, p, c0, c1); } else { - iwriter->WriteLeaf(n,i,p); - } + iwriter->WriteLeaf(n, i, p); + } } } // -void btDbvt::clone(btDbvt& dest,IClone* iclone) const +void btDbvt::clone(btDbvt& dest, IClone* iclone) const { dest.clear(); - if(m_root!=0) - { - btAlignedObjectArray<sStkCLN> stack; + if (m_root != 0) + { + btAlignedObjectArray<sStkCLN> stack; stack.reserve(m_leaves); - stack.push_back(sStkCLN(m_root,0)); - do { - const int i=stack.size()-1; - const sStkCLN e=stack[i]; - btDbvtNode* n=createnode(&dest,e.parent,e.node->volume,e.node->data); + stack.push_back(sStkCLN(m_root, 0)); + do + { + const int i = stack.size() - 1; + const sStkCLN e = stack[i]; + btDbvtNode* n = createnode(&dest, e.parent, e.node->volume, e.node->data); stack.pop_back(); - if(e.parent!=0) - e.parent->childs[i&1]=n; + if (e.parent != 0) + e.parent->childs[i & 1] = n; else - dest.m_root=n; - if(e.node->isinternal()) + dest.m_root = n; + if (e.node->isinternal()) { - stack.push_back(sStkCLN(e.node->childs[0],n)); - stack.push_back(sStkCLN(e.node->childs[1],n)); + stack.push_back(sStkCLN(e.node->childs[0], n)); + stack.push_back(sStkCLN(e.node->childs[1], n)); } else { iclone->CloneLeaf(n); } - } while(stack.size()>0); + } while (stack.size() > 0); } } // -int btDbvt::maxdepth(const btDbvtNode* node) +int btDbvt::maxdepth(const btDbvtNode* node) { - int depth=0; - if(node) getmaxdepth(node,1,depth); - return(depth); + int depth = 0; + if (node) getmaxdepth(node, 1, depth); + return (depth); } // -int btDbvt::countLeaves(const btDbvtNode* node) +int btDbvt::countLeaves(const btDbvtNode* node) { - if(node->isinternal()) - return(countLeaves(node->childs[0])+countLeaves(node->childs[1])); + if (node->isinternal()) + return (countLeaves(node->childs[0]) + countLeaves(node->childs[1])); else - return(1); + return (1); } // -void btDbvt::extractLeaves(const btDbvtNode* node,btAlignedObjectArray<const btDbvtNode*>& leaves) +void btDbvt::extractLeaves(const btDbvtNode* node, btAlignedObjectArray<const btDbvtNode*>& leaves) { - if(node->isinternal()) + if (node->isinternal()) { - extractLeaves(node->childs[0],leaves); - extractLeaves(node->childs[1],leaves); + extractLeaves(node->childs[0], leaves); + extractLeaves(node->childs[1], leaves); } else { leaves.push_back(node); - } + } } // @@ -694,603 +749,608 @@ struct btDbvtBenchmark { struct NilPolicy : btDbvt::ICollide { - NilPolicy() : m_pcount(0),m_depth(-SIMD_INFINITY),m_checksort(true) {} - void Process(const btDbvtNode*,const btDbvtNode*) { ++m_pcount; } - void Process(const btDbvtNode*) { ++m_pcount; } - void Process(const btDbvtNode*,btScalar depth) + NilPolicy() : m_pcount(0), m_depth(-SIMD_INFINITY), m_checksort(true) {} + void Process(const btDbvtNode*, const btDbvtNode*) { ++m_pcount; } + void Process(const btDbvtNode*) { ++m_pcount; } + void Process(const btDbvtNode*, btScalar depth) { ++m_pcount; - if(m_checksort) - { if(depth>=m_depth) m_depth=depth; else printf("wrong depth: %f (should be >= %f)\r\n",depth,m_depth); } + if (m_checksort) + { + if (depth >= m_depth) + m_depth = depth; + else + printf("wrong depth: %f (should be >= %f)\r\n", depth, m_depth); + } } - int m_pcount; - btScalar m_depth; - bool m_checksort; + int m_pcount; + btScalar m_depth; + bool m_checksort; }; struct P14 : btDbvt::ICollide { struct Node { - const btDbvtNode* leaf; - btScalar depth; + const btDbvtNode* leaf; + btScalar depth; }; - void Process(const btDbvtNode* leaf,btScalar depth) + void Process(const btDbvtNode* leaf, btScalar depth) { - Node n; - n.leaf = leaf; - n.depth = depth; + Node n; + n.leaf = leaf; + n.depth = depth; } - static int sortfnc(const Node& a,const Node& b) + static int sortfnc(const Node& a, const Node& b) { - if(a.depth<b.depth) return(+1); - if(a.depth>b.depth) return(-1); - return(0); + if (a.depth < b.depth) return (+1); + if (a.depth > b.depth) return (-1); + return (0); } - btAlignedObjectArray<Node> m_nodes; + btAlignedObjectArray<Node> m_nodes; }; struct P15 : btDbvt::ICollide { struct Node { - const btDbvtNode* leaf; - btScalar depth; + const btDbvtNode* leaf; + btScalar depth; }; void Process(const btDbvtNode* leaf) { - Node n; - n.leaf = leaf; - n.depth = dot(leaf->volume.Center(),m_axis); + Node n; + n.leaf = leaf; + n.depth = dot(leaf->volume.Center(), m_axis); } - static int sortfnc(const Node& a,const Node& b) + static int sortfnc(const Node& a, const Node& b) { - if(a.depth<b.depth) return(+1); - if(a.depth>b.depth) return(-1); - return(0); + if (a.depth < b.depth) return (+1); + if (a.depth > b.depth) return (-1); + return (0); } - btAlignedObjectArray<Node> m_nodes; - btVector3 m_axis; + btAlignedObjectArray<Node> m_nodes; + btVector3 m_axis; }; - static btScalar RandUnit() + static btScalar RandUnit() { - return(rand()/(btScalar)RAND_MAX); + return (rand() / (btScalar)RAND_MAX); } - static btVector3 RandVector3() + static btVector3 RandVector3() { - return(btVector3(RandUnit(),RandUnit(),RandUnit())); + return (btVector3(RandUnit(), RandUnit(), RandUnit())); } - static btVector3 RandVector3(btScalar cs) + static btVector3 RandVector3(btScalar cs) { - return(RandVector3()*cs-btVector3(cs,cs,cs)/2); + return (RandVector3() * cs - btVector3(cs, cs, cs) / 2); } - static btDbvtVolume RandVolume(btScalar cs,btScalar eb,btScalar es) + static btDbvtVolume RandVolume(btScalar cs, btScalar eb, btScalar es) { - return(btDbvtVolume::FromCE(RandVector3(cs),btVector3(eb,eb,eb)+RandVector3()*es)); + return (btDbvtVolume::FromCE(RandVector3(cs), btVector3(eb, eb, eb) + RandVector3() * es)); } - static btTransform RandTransform(btScalar cs) + static btTransform RandTransform(btScalar cs) { - btTransform t; + btTransform t; t.setOrigin(RandVector3(cs)); - t.setRotation(btQuaternion(RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2,RandUnit()*SIMD_PI*2).normalized()); - return(t); + t.setRotation(btQuaternion(RandUnit() * SIMD_PI * 2, RandUnit() * SIMD_PI * 2, RandUnit() * SIMD_PI * 2).normalized()); + return (t); } - static void RandTree(btScalar cs,btScalar eb,btScalar es,int leaves,btDbvt& dbvt) + static void RandTree(btScalar cs, btScalar eb, btScalar es, int leaves, btDbvt& dbvt) { dbvt.clear(); - for(int i=0;i<leaves;++i) + for (int i = 0; i < leaves; ++i) { - dbvt.insert(RandVolume(cs,eb,es),0); + dbvt.insert(RandVolume(cs, eb, es), 0); } } }; -void btDbvt::benchmark() +void btDbvt::benchmark() { - static const btScalar cfgVolumeCenterScale = 100; - static const btScalar cfgVolumeExentsBase = 1; - static const btScalar cfgVolumeExentsScale = 4; - static const int cfgLeaves = 8192; - static const bool cfgEnable = true; + static const btScalar cfgVolumeCenterScale = 100; + static const btScalar cfgVolumeExentsBase = 1; + static const btScalar cfgVolumeExentsScale = 4; + static const int cfgLeaves = 8192; + static const bool cfgEnable = true; //[1] btDbvtVolume intersections - bool cfgBenchmark1_Enable = cfgEnable; - static const int cfgBenchmark1_Iterations = 8; - static const int cfgBenchmark1_Reference = 3499; + bool cfgBenchmark1_Enable = cfgEnable; + static const int cfgBenchmark1_Iterations = 8; + static const int cfgBenchmark1_Reference = 3499; //[2] btDbvtVolume merges - bool cfgBenchmark2_Enable = cfgEnable; - static const int cfgBenchmark2_Iterations = 4; - static const int cfgBenchmark2_Reference = 1945; + bool cfgBenchmark2_Enable = cfgEnable; + static const int cfgBenchmark2_Iterations = 4; + static const int cfgBenchmark2_Reference = 1945; //[3] btDbvt::collideTT - bool cfgBenchmark3_Enable = cfgEnable; - static const int cfgBenchmark3_Iterations = 512; - static const int cfgBenchmark3_Reference = 5485; + bool cfgBenchmark3_Enable = cfgEnable; + static const int cfgBenchmark3_Iterations = 512; + static const int cfgBenchmark3_Reference = 5485; //[4] btDbvt::collideTT self - bool cfgBenchmark4_Enable = cfgEnable; - static const int cfgBenchmark4_Iterations = 512; - static const int cfgBenchmark4_Reference = 2814; + bool cfgBenchmark4_Enable = cfgEnable; + static const int cfgBenchmark4_Iterations = 512; + static const int cfgBenchmark4_Reference = 2814; //[5] btDbvt::collideTT xform - bool cfgBenchmark5_Enable = cfgEnable; - static const int cfgBenchmark5_Iterations = 512; - static const btScalar cfgBenchmark5_OffsetScale = 2; - static const int cfgBenchmark5_Reference = 7379; + bool cfgBenchmark5_Enable = cfgEnable; + static const int cfgBenchmark5_Iterations = 512; + static const btScalar cfgBenchmark5_OffsetScale = 2; + static const int cfgBenchmark5_Reference = 7379; //[6] btDbvt::collideTT xform,self - bool cfgBenchmark6_Enable = cfgEnable; - static const int cfgBenchmark6_Iterations = 512; - static const btScalar cfgBenchmark6_OffsetScale = 2; - static const int cfgBenchmark6_Reference = 7270; + bool cfgBenchmark6_Enable = cfgEnable; + static const int cfgBenchmark6_Iterations = 512; + static const btScalar cfgBenchmark6_OffsetScale = 2; + static const int cfgBenchmark6_Reference = 7270; //[7] btDbvt::rayTest - bool cfgBenchmark7_Enable = cfgEnable; - static const int cfgBenchmark7_Passes = 32; - static const int cfgBenchmark7_Iterations = 65536; - static const int cfgBenchmark7_Reference = 6307; + bool cfgBenchmark7_Enable = cfgEnable; + static const int cfgBenchmark7_Passes = 32; + static const int cfgBenchmark7_Iterations = 65536; + static const int cfgBenchmark7_Reference = 6307; //[8] insert/remove - bool cfgBenchmark8_Enable = cfgEnable; - static const int cfgBenchmark8_Passes = 32; - static const int cfgBenchmark8_Iterations = 65536; - static const int cfgBenchmark8_Reference = 2105; + bool cfgBenchmark8_Enable = cfgEnable; + static const int cfgBenchmark8_Passes = 32; + static const int cfgBenchmark8_Iterations = 65536; + static const int cfgBenchmark8_Reference = 2105; //[9] updates (teleport) - bool cfgBenchmark9_Enable = cfgEnable; - static const int cfgBenchmark9_Passes = 32; - static const int cfgBenchmark9_Iterations = 65536; - static const int cfgBenchmark9_Reference = 1879; + bool cfgBenchmark9_Enable = cfgEnable; + static const int cfgBenchmark9_Passes = 32; + static const int cfgBenchmark9_Iterations = 65536; + static const int cfgBenchmark9_Reference = 1879; //[10] updates (jitter) - bool cfgBenchmark10_Enable = cfgEnable; - static const btScalar cfgBenchmark10_Scale = cfgVolumeCenterScale/10000; - static const int cfgBenchmark10_Passes = 32; - static const int cfgBenchmark10_Iterations = 65536; - static const int cfgBenchmark10_Reference = 1244; + bool cfgBenchmark10_Enable = cfgEnable; + static const btScalar cfgBenchmark10_Scale = cfgVolumeCenterScale / 10000; + static const int cfgBenchmark10_Passes = 32; + static const int cfgBenchmark10_Iterations = 65536; + static const int cfgBenchmark10_Reference = 1244; //[11] optimize (incremental) - bool cfgBenchmark11_Enable = cfgEnable; - static const int cfgBenchmark11_Passes = 64; - static const int cfgBenchmark11_Iterations = 65536; - static const int cfgBenchmark11_Reference = 2510; + bool cfgBenchmark11_Enable = cfgEnable; + static const int cfgBenchmark11_Passes = 64; + static const int cfgBenchmark11_Iterations = 65536; + static const int cfgBenchmark11_Reference = 2510; //[12] btDbvtVolume notequal - bool cfgBenchmark12_Enable = cfgEnable; - static const int cfgBenchmark12_Iterations = 32; - static const int cfgBenchmark12_Reference = 3677; + bool cfgBenchmark12_Enable = cfgEnable; + static const int cfgBenchmark12_Iterations = 32; + static const int cfgBenchmark12_Reference = 3677; //[13] culling(OCL+fullsort) - bool cfgBenchmark13_Enable = cfgEnable; - static const int cfgBenchmark13_Iterations = 1024; - static const int cfgBenchmark13_Reference = 2231; + bool cfgBenchmark13_Enable = cfgEnable; + static const int cfgBenchmark13_Iterations = 1024; + static const int cfgBenchmark13_Reference = 2231; //[14] culling(OCL+qsort) - bool cfgBenchmark14_Enable = cfgEnable; - static const int cfgBenchmark14_Iterations = 8192; - static const int cfgBenchmark14_Reference = 3500; + bool cfgBenchmark14_Enable = cfgEnable; + static const int cfgBenchmark14_Iterations = 8192; + static const int cfgBenchmark14_Reference = 3500; //[15] culling(KDOP+qsort) - bool cfgBenchmark15_Enable = cfgEnable; - static const int cfgBenchmark15_Iterations = 8192; - static const int cfgBenchmark15_Reference = 1151; + bool cfgBenchmark15_Enable = cfgEnable; + static const int cfgBenchmark15_Iterations = 8192; + static const int cfgBenchmark15_Reference = 1151; //[16] insert/remove batch - bool cfgBenchmark16_Enable = cfgEnable; - static const int cfgBenchmark16_BatchCount = 256; - static const int cfgBenchmark16_Passes = 16384; - static const int cfgBenchmark16_Reference = 5138; + bool cfgBenchmark16_Enable = cfgEnable; + static const int cfgBenchmark16_BatchCount = 256; + static const int cfgBenchmark16_Passes = 16384; + static const int cfgBenchmark16_Reference = 5138; //[17] select - bool cfgBenchmark17_Enable = cfgEnable; - static const int cfgBenchmark17_Iterations = 4; - static const int cfgBenchmark17_Reference = 3390; + bool cfgBenchmark17_Enable = cfgEnable; + static const int cfgBenchmark17_Iterations = 4; + static const int cfgBenchmark17_Reference = 3390; - btClock wallclock; + btClock wallclock; printf("Benchmarking dbvt...\r\n"); - printf("\tWorld scale: %f\r\n",cfgVolumeCenterScale); - printf("\tExtents base: %f\r\n",cfgVolumeExentsBase); - printf("\tExtents range: %f\r\n",cfgVolumeExentsScale); - printf("\tLeaves: %u\r\n",cfgLeaves); - printf("\tsizeof(btDbvtVolume): %u bytes\r\n",sizeof(btDbvtVolume)); - printf("\tsizeof(btDbvtNode): %u bytes\r\n",sizeof(btDbvtNode)); - if(cfgBenchmark1_Enable) - {// Benchmark 1 + printf("\tWorld scale: %f\r\n", cfgVolumeCenterScale); + printf("\tExtents base: %f\r\n", cfgVolumeExentsBase); + printf("\tExtents range: %f\r\n", cfgVolumeExentsScale); + printf("\tLeaves: %u\r\n", cfgLeaves); + printf("\tsizeof(btDbvtVolume): %u bytes\r\n", sizeof(btDbvtVolume)); + printf("\tsizeof(btDbvtNode): %u bytes\r\n", sizeof(btDbvtNode)); + if (cfgBenchmark1_Enable) + { // Benchmark 1 srand(380843); - btAlignedObjectArray<btDbvtVolume> volumes; - btAlignedObjectArray<bool> results; + btAlignedObjectArray<btDbvtVolume> volumes; + btAlignedObjectArray<bool> results; volumes.resize(cfgLeaves); results.resize(cfgLeaves); - for(int i=0;i<cfgLeaves;++i) + for (int i = 0; i < cfgLeaves; ++i) { - volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale); + volumes[i] = btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale); } printf("[1] btDbvtVolume intersections: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark1_Iterations;++i) + for (int i = 0; i < cfgBenchmark1_Iterations; ++i) { - for(int j=0;j<cfgLeaves;++j) + for (int j = 0; j < cfgLeaves; ++j) { - for(int k=0;k<cfgLeaves;++k) + for (int k = 0; k < cfgLeaves; ++k) { - results[k]=Intersect(volumes[j],volumes[k]); + results[k] = Intersect(volumes[j], volumes[k]); } } } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark1_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark1_Reference) * 100 / time); } - if(cfgBenchmark2_Enable) - {// Benchmark 2 + if (cfgBenchmark2_Enable) + { // Benchmark 2 srand(380843); - btAlignedObjectArray<btDbvtVolume> volumes; - btAlignedObjectArray<btDbvtVolume> results; + btAlignedObjectArray<btDbvtVolume> volumes; + btAlignedObjectArray<btDbvtVolume> results; volumes.resize(cfgLeaves); results.resize(cfgLeaves); - for(int i=0;i<cfgLeaves;++i) + for (int i = 0; i < cfgLeaves; ++i) { - volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale); + volumes[i] = btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale); } printf("[2] btDbvtVolume merges: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark2_Iterations;++i) + for (int i = 0; i < cfgBenchmark2_Iterations; ++i) { - for(int j=0;j<cfgLeaves;++j) + for (int j = 0; j < cfgLeaves; ++j) { - for(int k=0;k<cfgLeaves;++k) + for (int k = 0; k < cfgLeaves; ++k) { - Merge(volumes[j],volumes[k],results[k]); + Merge(volumes[j], volumes[k], results[k]); } } } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark2_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark2_Reference) * 100 / time); } - if(cfgBenchmark3_Enable) - {// Benchmark 3 + if (cfgBenchmark3_Enable) + { // Benchmark 3 srand(380843); - btDbvt dbvt[2]; - btDbvtBenchmark::NilPolicy policy; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]); - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]); + btDbvt dbvt[2]; + btDbvtBenchmark::NilPolicy policy; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt[0]); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt[1]); dbvt[0].optimizeTopDown(); dbvt[1].optimizeTopDown(); printf("[3] btDbvt::collideTT: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark3_Iterations;++i) + for (int i = 0; i < cfgBenchmark3_Iterations; ++i) { - btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,policy); + btDbvt::collideTT(dbvt[0].m_root, dbvt[1].m_root, policy); } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark3_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark3_Reference) * 100 / time); } - if(cfgBenchmark4_Enable) - {// Benchmark 4 + if (cfgBenchmark4_Enable) + { // Benchmark 4 srand(380843); - btDbvt dbvt; - btDbvtBenchmark::NilPolicy policy; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvt dbvt; + btDbvtBenchmark::NilPolicy policy; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[4] btDbvt::collideTT self: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark4_Iterations;++i) + for (int i = 0; i < cfgBenchmark4_Iterations; ++i) { - btDbvt::collideTT(dbvt.m_root,dbvt.m_root,policy); + btDbvt::collideTT(dbvt.m_root, dbvt.m_root, policy); } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark4_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark4_Reference) * 100 / time); } - if(cfgBenchmark5_Enable) - {// Benchmark 5 + if (cfgBenchmark5_Enable) + { // Benchmark 5 srand(380843); - btDbvt dbvt[2]; - btAlignedObjectArray<btTransform> transforms; - btDbvtBenchmark::NilPolicy policy; + btDbvt dbvt[2]; + btAlignedObjectArray<btTransform> transforms; + btDbvtBenchmark::NilPolicy policy; transforms.resize(cfgBenchmark5_Iterations); - for(int i=0;i<transforms.size();++i) + for (int i = 0; i < transforms.size(); ++i) { - transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale); + transforms[i] = btDbvtBenchmark::RandTransform(cfgVolumeCenterScale * cfgBenchmark5_OffsetScale); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]); - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt[0]); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt[1]); dbvt[0].optimizeTopDown(); dbvt[1].optimizeTopDown(); printf("[5] btDbvt::collideTT xform: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark5_Iterations;++i) + for (int i = 0; i < cfgBenchmark5_Iterations; ++i) { - btDbvt::collideTT(dbvt[0].m_root,dbvt[1].m_root,transforms[i],policy); + btDbvt::collideTT(dbvt[0].m_root, dbvt[1].m_root, transforms[i], policy); } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark5_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark5_Reference) * 100 / time); } - if(cfgBenchmark6_Enable) - {// Benchmark 6 + if (cfgBenchmark6_Enable) + { // Benchmark 6 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btTransform> transforms; - btDbvtBenchmark::NilPolicy policy; + btDbvt dbvt; + btAlignedObjectArray<btTransform> transforms; + btDbvtBenchmark::NilPolicy policy; transforms.resize(cfgBenchmark6_Iterations); - for(int i=0;i<transforms.size();++i) + for (int i = 0; i < transforms.size(); ++i) { - transforms[i]=btDbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale); + transforms[i] = btDbvtBenchmark::RandTransform(cfgVolumeCenterScale * cfgBenchmark6_OffsetScale); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[6] btDbvt::collideTT xform,self: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark6_Iterations;++i) + for (int i = 0; i < cfgBenchmark6_Iterations; ++i) { - btDbvt::collideTT(dbvt.m_root,dbvt.m_root,transforms[i],policy); + btDbvt::collideTT(dbvt.m_root, dbvt.m_root, transforms[i], policy); } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark6_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark6_Reference) * 100 / time); } - if(cfgBenchmark7_Enable) - {// Benchmark 7 + if (cfgBenchmark7_Enable) + { // Benchmark 7 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btVector3> rayorg; - btAlignedObjectArray<btVector3> raydir; - btDbvtBenchmark::NilPolicy policy; + btDbvt dbvt; + btAlignedObjectArray<btVector3> rayorg; + btAlignedObjectArray<btVector3> raydir; + btDbvtBenchmark::NilPolicy policy; rayorg.resize(cfgBenchmark7_Iterations); raydir.resize(cfgBenchmark7_Iterations); - for(int i=0;i<rayorg.size();++i) + for (int i = 0; i < rayorg.size(); ++i) { - rayorg[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2); - raydir[i]=btDbvtBenchmark::RandVector3(cfgVolumeCenterScale*2); + rayorg[i] = btDbvtBenchmark::RandVector3(cfgVolumeCenterScale * 2); + raydir[i] = btDbvtBenchmark::RandVector3(cfgVolumeCenterScale * 2); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[7] btDbvt::rayTest: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark7_Passes;++i) + for (int i = 0; i < cfgBenchmark7_Passes; ++i) { - for(int j=0;j<cfgBenchmark7_Iterations;++j) + for (int j = 0; j < cfgBenchmark7_Iterations; ++j) { - btDbvt::rayTest(dbvt.m_root,rayorg[j],rayorg[j]+raydir[j],policy); + btDbvt::rayTest(dbvt.m_root, rayorg[j], rayorg[j] + raydir[j], policy); } } - const int time=(int)wallclock.getTimeMilliseconds(); - unsigned rays=cfgBenchmark7_Passes*cfgBenchmark7_Iterations; - printf("%u ms (%i%%),(%u r/s)\r\n",time,(time-cfgBenchmark7_Reference)*100/time,(rays*1000)/time); + const int time = (int)wallclock.getTimeMilliseconds(); + unsigned rays = cfgBenchmark7_Passes * cfgBenchmark7_Iterations; + printf("%u ms (%i%%),(%u r/s)\r\n", time, (time - cfgBenchmark7_Reference) * 100 / time, (rays * 1000) / time); } - if(cfgBenchmark8_Enable) - {// Benchmark 8 + if (cfgBenchmark8_Enable) + { // Benchmark 8 srand(380843); - btDbvt dbvt; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvt dbvt; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[8] insert/remove: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark8_Passes;++i) + for (int i = 0; i < cfgBenchmark8_Passes; ++i) { - for(int j=0;j<cfgBenchmark8_Iterations;++j) + for (int j = 0; j < cfgBenchmark8_Iterations; ++j) { - dbvt.remove(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0)); + dbvt.remove(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale), 0)); } } - const int time=(int)wallclock.getTimeMilliseconds(); - const int ir=cfgBenchmark8_Passes*cfgBenchmark8_Iterations; - printf("%u ms (%i%%),(%u ir/s)\r\n",time,(time-cfgBenchmark8_Reference)*100/time,ir*1000/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int ir = cfgBenchmark8_Passes * cfgBenchmark8_Iterations; + printf("%u ms (%i%%),(%u ir/s)\r\n", time, (time - cfgBenchmark8_Reference) * 100 / time, ir * 1000 / time); } - if(cfgBenchmark9_Enable) - {// Benchmark 9 + if (cfgBenchmark9_Enable) + { // Benchmark 9 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<const btDbvtNode*> leaves; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvt dbvt; + btAlignedObjectArray<const btDbvtNode*> leaves; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); - dbvt.extractLeaves(dbvt.m_root,leaves); + dbvt.extractLeaves(dbvt.m_root, leaves); printf("[9] updates (teleport): "); wallclock.reset(); - for(int i=0;i<cfgBenchmark9_Passes;++i) + for (int i = 0; i < cfgBenchmark9_Passes; ++i) { - for(int j=0;j<cfgBenchmark9_Iterations;++j) + for (int j = 0; j < cfgBenchmark9_Iterations; ++j) { - dbvt.update(const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]), - btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale)); + dbvt.update(const_cast<btDbvtNode*>(leaves[rand() % cfgLeaves]), + btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale)); } } - const int time=(int)wallclock.getTimeMilliseconds(); - const int up=cfgBenchmark9_Passes*cfgBenchmark9_Iterations; - printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark9_Reference)*100/time,up*1000/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int up = cfgBenchmark9_Passes * cfgBenchmark9_Iterations; + printf("%u ms (%i%%),(%u u/s)\r\n", time, (time - cfgBenchmark9_Reference) * 100 / time, up * 1000 / time); } - if(cfgBenchmark10_Enable) - {// Benchmark 10 + if (cfgBenchmark10_Enable) + { // Benchmark 10 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<const btDbvtNode*> leaves; - btAlignedObjectArray<btVector3> vectors; + btDbvt dbvt; + btAlignedObjectArray<const btDbvtNode*> leaves; + btAlignedObjectArray<btVector3> vectors; vectors.resize(cfgBenchmark10_Iterations); - for(int i=0;i<vectors.size();++i) + for (int i = 0; i < vectors.size(); ++i) { - vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1))*cfgBenchmark10_Scale; + vectors[i] = (btDbvtBenchmark::RandVector3() * 2 - btVector3(1, 1, 1)) * cfgBenchmark10_Scale; } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); - dbvt.extractLeaves(dbvt.m_root,leaves); + dbvt.extractLeaves(dbvt.m_root, leaves); printf("[10] updates (jitter): "); wallclock.reset(); - for(int i=0;i<cfgBenchmark10_Passes;++i) + for (int i = 0; i < cfgBenchmark10_Passes; ++i) { - for(int j=0;j<cfgBenchmark10_Iterations;++j) - { - const btVector3& d=vectors[j]; - btDbvtNode* l=const_cast<btDbvtNode*>(leaves[rand()%cfgLeaves]); - btDbvtVolume v=btDbvtVolume::FromMM(l->volume.Mins()+d,l->volume.Maxs()+d); - dbvt.update(l,v); + for (int j = 0; j < cfgBenchmark10_Iterations; ++j) + { + const btVector3& d = vectors[j]; + btDbvtNode* l = const_cast<btDbvtNode*>(leaves[rand() % cfgLeaves]); + btDbvtVolume v = btDbvtVolume::FromMM(l->volume.Mins() + d, l->volume.Maxs() + d); + dbvt.update(l, v); } } - const int time=(int)wallclock.getTimeMilliseconds(); - const int up=cfgBenchmark10_Passes*cfgBenchmark10_Iterations; - printf("%u ms (%i%%),(%u u/s)\r\n",time,(time-cfgBenchmark10_Reference)*100/time,up*1000/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int up = cfgBenchmark10_Passes * cfgBenchmark10_Iterations; + printf("%u ms (%i%%),(%u u/s)\r\n", time, (time - cfgBenchmark10_Reference) * 100 / time, up * 1000 / time); } - if(cfgBenchmark11_Enable) - {// Benchmark 11 + if (cfgBenchmark11_Enable) + { // Benchmark 11 srand(380843); - btDbvt dbvt; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvt dbvt; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[11] optimize (incremental): "); - wallclock.reset(); - for(int i=0;i<cfgBenchmark11_Passes;++i) + wallclock.reset(); + for (int i = 0; i < cfgBenchmark11_Passes; ++i) { dbvt.optimizeIncremental(cfgBenchmark11_Iterations); } - const int time=(int)wallclock.getTimeMilliseconds(); - const int op=cfgBenchmark11_Passes*cfgBenchmark11_Iterations; - printf("%u ms (%i%%),(%u o/s)\r\n",time,(time-cfgBenchmark11_Reference)*100/time,op/time*1000); + const int time = (int)wallclock.getTimeMilliseconds(); + const int op = cfgBenchmark11_Passes * cfgBenchmark11_Iterations; + printf("%u ms (%i%%),(%u o/s)\r\n", time, (time - cfgBenchmark11_Reference) * 100 / time, op / time * 1000); } - if(cfgBenchmark12_Enable) - {// Benchmark 12 + if (cfgBenchmark12_Enable) + { // Benchmark 12 srand(380843); - btAlignedObjectArray<btDbvtVolume> volumes; - btAlignedObjectArray<bool> results; + btAlignedObjectArray<btDbvtVolume> volumes; + btAlignedObjectArray<bool> results; volumes.resize(cfgLeaves); results.resize(cfgLeaves); - for(int i=0;i<cfgLeaves;++i) + for (int i = 0; i < cfgLeaves; ++i) { - volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale); + volumes[i] = btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale); } printf("[12] btDbvtVolume notequal: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark12_Iterations;++i) + for (int i = 0; i < cfgBenchmark12_Iterations; ++i) { - for(int j=0;j<cfgLeaves;++j) + for (int j = 0; j < cfgLeaves; ++j) { - for(int k=0;k<cfgLeaves;++k) + for (int k = 0; k < cfgLeaves; ++k) { - results[k]=NotEqual(volumes[j],volumes[k]); + results[k] = NotEqual(volumes[j], volumes[k]); } } } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark12_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark12_Reference) * 100 / time); } - if(cfgBenchmark13_Enable) - {// Benchmark 13 + if (cfgBenchmark13_Enable) + { // Benchmark 13 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btVector3> vectors; - btDbvtBenchmark::NilPolicy policy; + btDbvt dbvt; + btAlignedObjectArray<btVector3> vectors; + btDbvtBenchmark::NilPolicy policy; vectors.resize(cfgBenchmark13_Iterations); - for(int i=0;i<vectors.size();++i) + for (int i = 0; i < vectors.size(); ++i) { - vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized(); + vectors[i] = (btDbvtBenchmark::RandVector3() * 2 - btVector3(1, 1, 1)).normalized(); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); printf("[13] culling(OCL+fullsort): "); - wallclock.reset(); - for(int i=0;i<cfgBenchmark13_Iterations;++i) + wallclock.reset(); + for (int i = 0; i < cfgBenchmark13_Iterations; ++i) { - static const btScalar offset=0; - policy.m_depth=-SIMD_INFINITY; - dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy); + static const btScalar offset = 0; + policy.m_depth = -SIMD_INFINITY; + dbvt.collideOCL(dbvt.m_root, &vectors[i], &offset, vectors[i], 1, policy); } - const int time=(int)wallclock.getTimeMilliseconds(); - const int t=cfgBenchmark13_Iterations; - printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark13_Reference)*100/time,(t*1000)/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int t = cfgBenchmark13_Iterations; + printf("%u ms (%i%%),(%u t/s)\r\n", time, (time - cfgBenchmark13_Reference) * 100 / time, (t * 1000) / time); } - if(cfgBenchmark14_Enable) - {// Benchmark 14 + if (cfgBenchmark14_Enable) + { // Benchmark 14 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btVector3> vectors; - btDbvtBenchmark::P14 policy; + btDbvt dbvt; + btAlignedObjectArray<btVector3> vectors; + btDbvtBenchmark::P14 policy; vectors.resize(cfgBenchmark14_Iterations); - for(int i=0;i<vectors.size();++i) + for (int i = 0; i < vectors.size(); ++i) { - vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized(); + vectors[i] = (btDbvtBenchmark::RandVector3() * 2 - btVector3(1, 1, 1)).normalized(); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); policy.m_nodes.reserve(cfgLeaves); printf("[14] culling(OCL+qsort): "); - wallclock.reset(); - for(int i=0;i<cfgBenchmark14_Iterations;++i) + wallclock.reset(); + for (int i = 0; i < cfgBenchmark14_Iterations; ++i) { - static const btScalar offset=0; + static const btScalar offset = 0; policy.m_nodes.resize(0); - dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy,false); + dbvt.collideOCL(dbvt.m_root, &vectors[i], &offset, vectors[i], 1, policy, false); policy.m_nodes.quickSort(btDbvtBenchmark::P14::sortfnc); } - const int time=(int)wallclock.getTimeMilliseconds(); - const int t=cfgBenchmark14_Iterations; - printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark14_Reference)*100/time,(t*1000)/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int t = cfgBenchmark14_Iterations; + printf("%u ms (%i%%),(%u t/s)\r\n", time, (time - cfgBenchmark14_Reference) * 100 / time, (t * 1000) / time); } - if(cfgBenchmark15_Enable) - {// Benchmark 15 + if (cfgBenchmark15_Enable) + { // Benchmark 15 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btVector3> vectors; - btDbvtBenchmark::P15 policy; + btDbvt dbvt; + btAlignedObjectArray<btVector3> vectors; + btDbvtBenchmark::P15 policy; vectors.resize(cfgBenchmark15_Iterations); - for(int i=0;i<vectors.size();++i) + for (int i = 0; i < vectors.size(); ++i) { - vectors[i]=(btDbvtBenchmark::RandVector3()*2-btVector3(1,1,1)).normalized(); + vectors[i] = (btDbvtBenchmark::RandVector3() * 2 - btVector3(1, 1, 1)).normalized(); } - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); policy.m_nodes.reserve(cfgLeaves); printf("[15] culling(KDOP+qsort): "); - wallclock.reset(); - for(int i=0;i<cfgBenchmark15_Iterations;++i) + wallclock.reset(); + for (int i = 0; i < cfgBenchmark15_Iterations; ++i) { - static const btScalar offset=0; + static const btScalar offset = 0; policy.m_nodes.resize(0); - policy.m_axis=vectors[i]; - dbvt.collideKDOP(dbvt.m_root,&vectors[i],&offset,1,policy); + policy.m_axis = vectors[i]; + dbvt.collideKDOP(dbvt.m_root, &vectors[i], &offset, 1, policy); policy.m_nodes.quickSort(btDbvtBenchmark::P15::sortfnc); } - const int time=(int)wallclock.getTimeMilliseconds(); - const int t=cfgBenchmark15_Iterations; - printf("%u ms (%i%%),(%u t/s)\r\n",time,(time-cfgBenchmark15_Reference)*100/time,(t*1000)/time); + const int time = (int)wallclock.getTimeMilliseconds(); + const int t = cfgBenchmark15_Iterations; + printf("%u ms (%i%%),(%u t/s)\r\n", time, (time - cfgBenchmark15_Reference) * 100 / time, (t * 1000) / time); } - if(cfgBenchmark16_Enable) - {// Benchmark 16 + if (cfgBenchmark16_Enable) + { // Benchmark 16 srand(380843); - btDbvt dbvt; - btAlignedObjectArray<btDbvtNode*> batch; - btDbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt); + btDbvt dbvt; + btAlignedObjectArray<btDbvtNode*> batch; + btDbvtBenchmark::RandTree(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale, cfgLeaves, dbvt); dbvt.optimizeTopDown(); batch.reserve(cfgBenchmark16_BatchCount); - printf("[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount); + printf("[16] insert/remove batch(%u): ", cfgBenchmark16_BatchCount); wallclock.reset(); - for(int i=0;i<cfgBenchmark16_Passes;++i) + for (int i = 0; i < cfgBenchmark16_Passes; ++i) { - for(int j=0;j<cfgBenchmark16_BatchCount;++j) + for (int j = 0; j < cfgBenchmark16_BatchCount; ++j) { - batch.push_back(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0)); + batch.push_back(dbvt.insert(btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale), 0)); } - for(int j=0;j<cfgBenchmark16_BatchCount;++j) + for (int j = 0; j < cfgBenchmark16_BatchCount; ++j) { dbvt.remove(batch[j]); } batch.resize(0); } - const int time=(int)wallclock.getTimeMilliseconds(); - const int ir=cfgBenchmark16_Passes*cfgBenchmark16_BatchCount; - printf("%u ms (%i%%),(%u bir/s)\r\n",time,(time-cfgBenchmark16_Reference)*100/time,int(ir*1000.0/time)); + const int time = (int)wallclock.getTimeMilliseconds(); + const int ir = cfgBenchmark16_Passes * cfgBenchmark16_BatchCount; + printf("%u ms (%i%%),(%u bir/s)\r\n", time, (time - cfgBenchmark16_Reference) * 100 / time, int(ir * 1000.0 / time)); } - if(cfgBenchmark17_Enable) - {// Benchmark 17 + if (cfgBenchmark17_Enable) + { // Benchmark 17 srand(380843); - btAlignedObjectArray<btDbvtVolume> volumes; - btAlignedObjectArray<int> results; - btAlignedObjectArray<int> indices; + btAlignedObjectArray<btDbvtVolume> volumes; + btAlignedObjectArray<int> results; + btAlignedObjectArray<int> indices; volumes.resize(cfgLeaves); results.resize(cfgLeaves); indices.resize(cfgLeaves); - for(int i=0;i<cfgLeaves;++i) + for (int i = 0; i < cfgLeaves; ++i) { - indices[i]=i; - volumes[i]=btDbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale); + indices[i] = i; + volumes[i] = btDbvtBenchmark::RandVolume(cfgVolumeCenterScale, cfgVolumeExentsBase, cfgVolumeExentsScale); } - for(int i=0;i<cfgLeaves;++i) + for (int i = 0; i < cfgLeaves; ++i) { - btSwap(indices[i],indices[rand()%cfgLeaves]); + btSwap(indices[i], indices[rand() % cfgLeaves]); } printf("[17] btDbvtVolume select: "); wallclock.reset(); - for(int i=0;i<cfgBenchmark17_Iterations;++i) + for (int i = 0; i < cfgBenchmark17_Iterations; ++i) { - for(int j=0;j<cfgLeaves;++j) + for (int j = 0; j < cfgLeaves; ++j) { - for(int k=0;k<cfgLeaves;++k) + for (int k = 0; k < cfgLeaves; ++k) { - const int idx=indices[k]; - results[idx]=Select(volumes[idx],volumes[j],volumes[k]); + const int idx = indices[k]; + results[idx] = Select(volumes[idx], volumes[j], volumes[k]); } } } - const int time=(int)wallclock.getTimeMilliseconds(); - printf("%u ms (%i%%)\r\n",time,(time-cfgBenchmark17_Reference)*100/time); + const int time = (int)wallclock.getTimeMilliseconds(); + printf("%u ms (%i%%)\r\n", time, (time - cfgBenchmark17_Reference) * 100 / time); } printf("\r\n\r\n"); } |