path: root/thirdparty/bullet/src/Bullet3Collision/BroadPhaseCollision/b3DynamicBvh.cpp

/*
Bullet Continuous Collision Detection and Physics Library
Copyright (c) 2003-2013 Erwin Coumans  http://bulletphysics.org

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it freely,
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
///b3DynamicBvh implementation by Nathanael Presson

#include "b3DynamicBvh.h"

//
typedef b3AlignedObjectArray<b3DbvtNode*>			b3NodeArray;
typedef b3AlignedObjectArray<const b3DbvtNode*>	b3ConstNodeArray;

//
struct b3DbvtNodeEnumerator : b3DynamicBvh::ICollide
{
	b3ConstNodeArray	nodes;
	void Process(const b3DbvtNode* n) { nodes.push_back(n); }
};

//
static B3_DBVT_INLINE int			b3IndexOf(const b3DbvtNode* node)
{
	return(node->parent->childs[1]==node);
}

//
static B3_DBVT_INLINE b3DbvtVolume	b3Merge(	const b3DbvtVolume& a,
									  const b3DbvtVolume& b)
{
#if (B3_DBVT_MERGE_IMPL==B3_DBVT_IMPL_SSE)
	B3_ATTRIBUTE_ALIGNED16(char locals[sizeof(b3DbvtAabbMm)]);
	b3DbvtVolume&	res=*(b3DbvtVolume*)locals;
#else
		b3DbvtVolume	res;
#endif
	b3Merge(a,b,res);
	return(res);
}

// volume+edge lengths
static B3_DBVT_INLINE b3Scalar		b3Size(const b3DbvtVolume& a)
{
	const b3Vector3	edges=a.Lengths();
	return(	edges.x*edges.y*edges.z+
		edges.x+edges.y+edges.z);
}

//
static void						b3GetMaxDepth(const b3DbvtNode* node,int depth,int& maxdepth)
{
	if(node->isinternal())
	{
		b3GetMaxDepth(node->childs[0],depth+1,maxdepth);
		b3GetMaxDepth(node->childs[1],depth+1,maxdepth);
	} else maxdepth=b3Max(maxdepth,depth);
}

//
static B3_DBVT_INLINE void			b3DeleteNode(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* node)
{
	b3AlignedFree(pdbvt->m_free);
	pdbvt->m_free=node;
}

//
static void						b3RecurseDeleteNode(	b3DynamicBvh* pdbvt,
												  b3DbvtNode* node)
{
	if(!node->isleaf())
	{
		b3RecurseDeleteNode(pdbvt,node->childs[0]);
		b3RecurseDeleteNode(pdbvt,node->childs[1]);
	}
	if(node==pdbvt->m_root) pdbvt->m_root=0;
	b3DeleteNode(pdbvt,node);
}

//
static B3_DBVT_INLINE b3DbvtNode*	b3CreateNode(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* parent,
										   void* data)
{
	b3DbvtNode*	node;
	if(pdbvt->m_free)
	{ node=pdbvt->m_free;pdbvt->m_free=0; }
	else
	{ node=new(b3AlignedAlloc(sizeof(b3DbvtNode),16)) b3DbvtNode(); }
	node->parent	=	parent;
	node->data		=	data;
	node->childs[1]	=	0;
	return(node);
}

//
static B3_DBVT_INLINE b3DbvtNode*	b3CreateNode(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* parent,
										   const b3DbvtVolume& volume,
										   void* data)
{
	b3DbvtNode*	node=b3CreateNode(pdbvt,parent,data);
	node->volume=volume;
	return(node);
}

//
static B3_DBVT_INLINE b3DbvtNode*	b3CreateNode(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* parent,
										   const b3DbvtVolume& volume0,
										   const b3DbvtVolume& volume1,
										   void* data)
{
	b3DbvtNode*	node=b3CreateNode(pdbvt,parent,data);
	b3Merge(volume0,volume1,node->volume);
	return(node);
}

//
static void						b3InsertLeaf(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* root,
										   b3DbvtNode* leaf)
{
	if(!pdbvt->m_root)
	{
		pdbvt->m_root	=	leaf;
		leaf->parent	=	0;
	}
	else
	{
		if(!root->isleaf())
		{
			do	{
				root=root->childs[b3Select(	leaf->volume,
					root->childs[0]->volume,
					root->childs[1]->volume)];
			} while(!root->isleaf());
		}
		b3DbvtNode*	prev=root->parent;
		b3DbvtNode*	node=b3CreateNode(pdbvt,prev,leaf->volume,root->volume,0);
		if(prev)
		{
			prev->childs[b3IndexOf(root)]	=	node;
			node->childs[0]				=	root;root->parent=node;
			node->childs[1]				=	leaf;leaf->parent=node;
			do	{
				if(!prev->volume.Contain(node->volume))
					b3Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
				else
					break;
				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;
		}
	}
}

//
static b3DbvtNode*				b3RemoveLeaf(	b3DynamicBvh* pdbvt,
										   b3DbvtNode* leaf)
{
	if(leaf==pdbvt->m_root)
	{
		pdbvt->m_root=0;
		return(0);
	}
	else
	{
		b3DbvtNode*	parent=leaf->parent;
		b3DbvtNode*	prev=parent->parent;
		b3DbvtNode*	sibling=parent->childs[1-b3IndexOf(leaf)];			
		if(prev)
		{
			prev->childs[b3IndexOf(parent)]=sibling;
			sibling->parent=prev;
			b3DeleteNode(pdbvt,parent);
			while(prev)
			{
				const b3DbvtVolume	pb=prev->volume;
				b3Merge(prev->childs[0]->volume,prev->childs[1]->volume,prev->volume);
				if(b3NotEqual(pb,prev->volume))
				{
					prev=prev->parent;
				} else break;
			}
			return(prev?prev:pdbvt->m_root);
		}
		else
		{								
			pdbvt->m_root=sibling;
			sibling->parent=0;
			b3DeleteNode(pdbvt,parent);
			return(pdbvt->m_root);
		}			
	}
}

//
static void						b3FetchLeaves(b3DynamicBvh* pdbvt,
											b3DbvtNode* root,
											b3NodeArray& leaves,
											int depth=-1)
{
	if(root->isinternal()&&depth)
	{
		b3FetchLeaves(pdbvt,root->childs[0],leaves,depth-1);
		b3FetchLeaves(pdbvt,root->childs[1],leaves,depth-1);
		b3DeleteNode(pdbvt,root);
	}
	else
	{
		leaves.push_back(root);
	}
}

static bool						b3LeftOfAxis(	const b3DbvtNode* node,
										   const b3Vector3& org,
										   const b3Vector3& axis)
{
	return b3Dot(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						b3Split(	b3DbvtNode** leaves,
									  int count,
									  const b3Vector3& org,
									  const b3Vector3& axis)
{
	int begin=0;
	int end=count;
	for(;;)
	{
		while(begin!=end && b3LeftOfAxis(leaves[begin],org,axis))
		{
			++begin;
		}

		if(begin==end)
		{
			break;
		}

		while(begin!=end && !b3LeftOfAxis(leaves[end-1],org,axis))
		{
			--end;
		}

		if(begin==end)
		{
			break;
		}

		// swap out of place nodes
		--end;
		b3DbvtNode* temp=leaves[begin];
		leaves[begin]=leaves[end];
		leaves[end]=temp;
		++begin;
	}

	return begin;
}

//
static b3DbvtVolume				b3Bounds(	b3DbvtNode** leaves,
										 int count)
{
#if B3_DBVT_MERGE_IMPL==B3_DBVT_IMPL_SSE
	B3_ATTRIBUTE_ALIGNED16(char	locals[sizeof(b3DbvtVolume)]);
	b3DbvtVolume&	volume=*(b3DbvtVolume*)locals;
	volume=leaves[0]->volume;
#else
	b3DbvtVolume volume=leaves[0]->volume;
#endif
	for(int i=1,ni=count;i<ni;++i)
	{
		b3Merge(volume,leaves[i]->volume,volume);
	}
	return(volume);
}

//
static void						b3BottomUp(	b3DynamicBvh* pdbvt,
										 b3DbvtNode** leaves,
										 int count)
{
	while(count>1)
	{
		b3Scalar	minsize=B3_INFINITY;
		int			minidx[2]={-1,-1};
		for(int i=0;i<count;++i)
		{
			for(int j=i+1;j<count;++j)
			{
				const b3Scalar	sz=b3Size(b3Merge(leaves[i]->volume,leaves[j]->volume));
				if(sz<minsize)
				{
					minsize		=	sz;
					minidx[0]	=	i;
					minidx[1]	=	j;
				}
			}
		}
		b3DbvtNode*	n[]	=	{leaves[minidx[0]],leaves[minidx[1]]};
		b3DbvtNode*	p	=	b3CreateNode(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 b3DbvtNode*			b3TopDown(b3DynamicBvh* pdbvt,
									b3DbvtNode** leaves,
									int count,
									int bu_treshold)
{
	static const b3Vector3	axis[]={b3MakeVector3(1,0,0),
		b3MakeVector3(0,1,0),
		b3MakeVector3(0,0,1)};
	b3Assert(bu_treshold>1);
	if(count>1)
	{
		if(count>bu_treshold)
		{
			const b3DbvtVolume	vol=b3Bounds(leaves,count);
			const b3Vector3			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<count;++i)
			{
				const b3Vector3	x=leaves[i]->volume.Center()-org;
				for(int j=0;j<3;++j)
				{
					++splitcount[j][b3Dot(x,axis[j])>0?1:0];
				}
			}
			for( i=0;i<3;++i)
			{
				if((splitcount[i][0]>0)&&(splitcount[i][1]>0))
				{
					const int	midp=(int)b3Fabs(b3Scalar(splitcount[i][0]-splitcount[i][1]));
					if(midp<bestmidp)
					{
						bestaxis=i;
						bestmidp=midp;
					}
				}
			}
			if(bestaxis>=0)
			{
				partition=b3Split(leaves,count,org,axis[bestaxis]);
				b3Assert(partition!=0 && partition!=count);
			}
			else
			{
				partition=count/2+1;
			}
			b3DbvtNode*	node=b3CreateNode(pdbvt,0,vol,0);
			node->childs[0]=b3TopDown(pdbvt,&leaves[0],partition,bu_treshold);
			node->childs[1]=b3TopDown(pdbvt,&leaves[partition],count-partition,bu_treshold);
			node->childs[0]->parent=node;
			node->childs[1]->parent=node;
			return(node);
		}
		else
		{
			b3BottomUp(pdbvt,leaves,count);
			return(leaves[0]);
		}
	}
	return(leaves[0]);
}

//
static B3_DBVT_INLINE b3DbvtNode*	b3Sort(b3DbvtNode* n,b3DbvtNode*& r)
{
	b3DbvtNode*	p=n->parent;
	b3Assert(n->isinternal());
	if(p>n)
	{
		const int		i=b3IndexOf(n);
		const int		j=1-i;
		b3DbvtNode*	s=p->childs[j];
		b3DbvtNode*	q=p->parent;
		b3Assert(n==p->childs[i]);
		if(q) q->childs[b3IndexOf(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;
		b3Swap(p->volume,n->volume);
		return(p);
	}
	return(n);
}

#if 0
static B3_DBVT_INLINE b3DbvtNode*	walkup(b3DbvtNode* n,int count)
{
	while(n&&(count--)) n=n->parent;
	return(n);
}
#endif

//
// Api
//

//
b3DynamicBvh::b3DynamicBvh()
{
	m_root		=	0;
	m_free		=	0;
	m_lkhd		=	-1;
	m_leaves	=	0;
	m_opath		=	0;
}

//
b3DynamicBvh::~b3DynamicBvh()
{
	clear();
}

//
void			b3DynamicBvh::clear()
{
	if(m_root)	
		b3RecurseDeleteNode(this,m_root);
	b3AlignedFree(m_free);
	m_free=0;
	m_lkhd		=	-1;
	m_stkStack.clear();
	m_opath		=	0;
	
}

//
void			b3DynamicBvh::optimizeBottomUp()
{
	if(m_root)
	{
		b3NodeArray leaves;
		leaves.reserve(m_leaves);
		b3FetchLeaves(this,m_root,leaves);
		b3BottomUp(this,&leaves[0],leaves.size());
		m_root=leaves[0];
	}
}

//
void			b3DynamicBvh::optimizeTopDown(int bu_treshold)
{
	if(m_root)
	{
		b3NodeArray	leaves;
		leaves.reserve(m_leaves);
		b3FetchLeaves(this,m_root,leaves);
		m_root=b3TopDown(this,&leaves[0],leaves.size(),bu_treshold);
	}
}

//
void			b3DynamicBvh::optimizeIncremental(int passes)
{
	if(passes<0) passes=m_leaves;
	if(m_root&&(passes>0))
	{
		do	{
			b3DbvtNode*		node=m_root;
			unsigned	bit=0;
			while(node->isinternal())
			{
				node=b3Sort(node,m_root)->childs[(m_opath>>bit)&1];
				bit=(bit+1)&(sizeof(unsigned)*8-1);
			}
			update(node);
			++m_opath;
		} while(--passes);
	}
}

//
b3DbvtNode*	b3DynamicBvh::insert(const b3DbvtVolume& volume,void* data)
{
	b3DbvtNode*	leaf=b3CreateNode(this,0,volume,data);
	b3InsertLeaf(this,m_root,leaf);
	++m_leaves;
	return(leaf);
}

//
void			b3DynamicBvh::update(b3DbvtNode* leaf,int lookahead)
{
	b3DbvtNode*	root=b3RemoveLeaf(this,leaf);
	if(root)
	{
		if(lookahead>=0)
		{
			for(int i=0;(i<lookahead)&&root->parent;++i)
			{
				root=root->parent;
			}
		} else root=m_root;
	}
	b3InsertLeaf(this,root,leaf);
}

//
void			b3DynamicBvh::update(b3DbvtNode* leaf,b3DbvtVolume& volume)
{
	b3DbvtNode*	root=b3RemoveLeaf(this,leaf);
	if(root)
	{
		if(m_lkhd>=0)
		{
			for(int i=0;(i<m_lkhd)&&root->parent;++i)
			{
				root=root->parent;
			}
		} else root=m_root;
	}
	leaf->volume=volume;
	b3InsertLeaf(this,root,leaf);
}

//
bool			b3DynamicBvh::update(b3DbvtNode* leaf,b3DbvtVolume& volume,const b3Vector3& velocity,b3Scalar margin)
{
	if(leaf->volume.Contain(volume)) return(false);
	volume.Expand(b3MakeVector3(margin,margin,margin));
	volume.SignedExpand(velocity);
	update(leaf,volume);
	return(true);
}

//
bool			b3DynamicBvh::update(b3DbvtNode* leaf,b3DbvtVolume& volume,const b3Vector3& velocity)
{
	if(leaf->volume.Contain(volume)) return(false);
	volume.SignedExpand(velocity);
	update(leaf,volume);
	return(true);
}

//
bool			b3DynamicBvh::update(b3DbvtNode* leaf,b3DbvtVolume& volume,b3Scalar margin)
{
	if(leaf->volume.Contain(volume)) return(false);
	volume.Expand(b3MakeVector3(margin,margin,margin));
	update(leaf,volume);
	return(true);
}

//
void			b3DynamicBvh::remove(b3DbvtNode* leaf)
{
	b3RemoveLeaf(this,leaf);
	b3DeleteNode(this,leaf);
	--m_leaves;
}

//
void			b3DynamicBvh::write(IWriter* iwriter) const
{
	b3DbvtNodeEnumerator	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 b3DbvtNode* 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);
		}
		else
		{
			iwriter->WriteLeaf(n,i,p);
		}	
	}
}

//
void			b3DynamicBvh::clone(b3DynamicBvh& dest,IClone* iclone) const
{
	dest.clear();
	if(m_root!=0)
	{	
		b3AlignedObjectArray<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];
			b3DbvtNode*			n=b3CreateNode(&dest,e.parent,e.node->volume,e.node->data);
			stack.pop_back();
			if(e.parent!=0)
				e.parent->childs[i&1]=n;
			else
				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));
			}
			else
			{
				iclone->CloneLeaf(n);
			}
		} while(stack.size()>0);
	}
}

//
int				b3DynamicBvh::maxdepth(const b3DbvtNode* node)
{
	int	depth=0;
	if(node) b3GetMaxDepth(node,1,depth);
	return(depth);
}

//
int				b3DynamicBvh::countLeaves(const b3DbvtNode* node)
{
	if(node->isinternal())
		return(countLeaves(node->childs[0])+countLeaves(node->childs[1]));
	else
		return(1);
}

//
void			b3DynamicBvh::extractLeaves(const b3DbvtNode* node,b3AlignedObjectArray<const b3DbvtNode*>& leaves)
{
	if(node->isinternal())
	{
		extractLeaves(node->childs[0],leaves);
		extractLeaves(node->childs[1],leaves);
	}
	else
	{
		leaves.push_back(node);
	}	
}

//
#if B3_DBVT_ENABLE_BENCHMARK

#include <stdio.h>
#include <stdlib.h>


/*
q6600,2.4ghz

/Ox /Ob2 /Oi /Ot /I "." /I "..\.." /I "..\..\src" /D "NDEBUG" /D "_LIB" /D "_WINDOWS" /D "_CRT_SECURE_NO_DEPRECATE" /D "_CRT_NONSTDC_NO_DEPRECATE" /D "WIN32"
/GF /FD /MT /GS- /Gy /arch:SSE2 /Zc:wchar_t- /Fp"..\..\out\release8\build\libbulletcollision\libbulletcollision.pch"
/Fo"..\..\out\release8\build\libbulletcollision\\"
/Fd"..\..\out\release8\build\libbulletcollision\bulletcollision.pdb"
/W3 /nologo /c /Wp64 /Zi /errorReport:prompt

Benchmarking dbvt...
World scale: 100.000000
Extents base: 1.000000
Extents range: 4.000000
Leaves: 8192
sizeof(b3DbvtVolume): 32 bytes
sizeof(b3DbvtNode):   44 bytes
[1] b3DbvtVolume intersections: 3499 ms (-1%)
[2] b3DbvtVolume merges: 1934 ms (0%)
[3] b3DynamicBvh::collideTT: 5485 ms (-21%)
[4] b3DynamicBvh::collideTT self: 2814 ms (-20%)
[5] b3DynamicBvh::collideTT xform: 7379 ms (-1%)
[6] b3DynamicBvh::collideTT xform,self: 7270 ms (-2%)
[7] b3DynamicBvh::rayTest: 6314 ms (0%),(332143 r/s)
[8] insert/remove: 2093 ms (0%),(1001983 ir/s)
[9] updates (teleport): 1879 ms (-3%),(1116100 u/s)
[10] updates (jitter): 1244 ms (-4%),(1685813 u/s)
[11] optimize (incremental): 2514 ms (0%),(1668000 o/s)
[12] b3DbvtVolume notequal: 3659 ms (0%)
[13] culling(OCL+fullsort): 2218 ms (0%),(461 t/s)
[14] culling(OCL+qsort): 3688 ms (5%),(2221 t/s)
[15] culling(KDOP+qsort): 1139 ms (-1%),(7192 t/s)
[16] insert/remove batch(256): 5092 ms (0%),(823704 bir/s)
[17] b3DbvtVolume select: 3419 ms (0%)
*/

struct b3DbvtBenchmark
{
	struct NilPolicy : b3DynamicBvh::ICollide
	{
		NilPolicy() : m_pcount(0),m_depth(-B3_INFINITY),m_checksort(true)		{}
		void	Process(const b3DbvtNode*,const b3DbvtNode*)				{ ++m_pcount; }
		void	Process(const b3DbvtNode*)									{ ++m_pcount; }
		void	Process(const b3DbvtNode*,b3Scalar 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); }
		}
		int			m_pcount;
		b3Scalar	m_depth;
		bool		m_checksort;
	};
	struct P14 : b3DynamicBvh::ICollide
	{
		struct Node
		{
			const b3DbvtNode*	leaf;
			b3Scalar			depth;
		};
		void Process(const b3DbvtNode* leaf,b3Scalar depth)
		{
			Node	n;
			n.leaf	=	leaf;
			n.depth	=	depth;
		}
		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);
		}
		b3AlignedObjectArray<Node>		m_nodes;
	};
	struct P15 : b3DynamicBvh::ICollide
	{
		struct Node
		{
			const b3DbvtNode*	leaf;
			b3Scalar			depth;
		};
		void Process(const b3DbvtNode* leaf)
		{
			Node	n;
			n.leaf	=	leaf;
			n.depth	=	dot(leaf->volume.Center(),m_axis);
		}
		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);
		}
		b3AlignedObjectArray<Node>		m_nodes;
		b3Vector3						m_axis;
	};
	static b3Scalar			RandUnit()
	{
		return(rand()/(b3Scalar)RAND_MAX);
	}
	static b3Vector3		RandVector3()
	{
		return(b3Vector3(RandUnit(),RandUnit(),RandUnit()));
	}
	static b3Vector3		RandVector3(b3Scalar cs)
	{
		return(RandVector3()*cs-b3Vector3(cs,cs,cs)/2);
	}
	static b3DbvtVolume	RandVolume(b3Scalar cs,b3Scalar eb,b3Scalar es)
	{
		return(b3DbvtVolume::FromCE(RandVector3(cs),b3Vector3(eb,eb,eb)+RandVector3()*es));
	}
	static b3Transform		RandTransform(b3Scalar cs)
	{
		b3Transform	t;
		t.setOrigin(RandVector3(cs));
		t.setRotation(b3Quaternion(RandUnit()*B3_PI*2,RandUnit()*B3_PI*2,RandUnit()*B3_PI*2).normalized());
		return(t);
	}
	static void				RandTree(b3Scalar cs,b3Scalar eb,b3Scalar es,int leaves,b3DynamicBvh& dbvt)
	{
		dbvt.clear();
		for(int i=0;i<leaves;++i)
		{
			dbvt.insert(RandVolume(cs,eb,es),0);
		}
	}
};

void			b3DynamicBvh::benchmark()
{
	static const b3Scalar	cfgVolumeCenterScale		=	100;
	static const b3Scalar	cfgVolumeExentsBase			=	1;
	static const b3Scalar	cfgVolumeExentsScale		=	4;
	static const int		cfgLeaves					=	8192;
	static const bool		cfgEnable					=	true;

	//[1] b3DbvtVolume intersections
	bool					cfgBenchmark1_Enable		=	cfgEnable;
	static const int		cfgBenchmark1_Iterations	=	8;
	static const int		cfgBenchmark1_Reference		=	3499;
	//[2] b3DbvtVolume merges
	bool					cfgBenchmark2_Enable		=	cfgEnable;
	static const int		cfgBenchmark2_Iterations	=	4;
	static const int		cfgBenchmark2_Reference		=	1945;
	//[3] b3DynamicBvh::collideTT
	bool					cfgBenchmark3_Enable		=	cfgEnable;
	static const int		cfgBenchmark3_Iterations	=	512;
	static const int		cfgBenchmark3_Reference		=	5485;
	//[4] b3DynamicBvh::collideTT self
	bool					cfgBenchmark4_Enable		=	cfgEnable;
	static const int		cfgBenchmark4_Iterations	=	512;
	static const int		cfgBenchmark4_Reference		=	2814;
	//[5] b3DynamicBvh::collideTT xform
	bool					cfgBenchmark5_Enable		=	cfgEnable;
	static const int		cfgBenchmark5_Iterations	=	512;
	static const b3Scalar	cfgBenchmark5_OffsetScale	=	2;
	static const int		cfgBenchmark5_Reference		=	7379;
	//[6] b3DynamicBvh::collideTT xform,self
	bool					cfgBenchmark6_Enable		=	cfgEnable;
	static const int		cfgBenchmark6_Iterations	=	512;
	static const b3Scalar	cfgBenchmark6_OffsetScale	=	2;
	static const int		cfgBenchmark6_Reference		=	7270;
	//[7] b3DynamicBvh::rayTest
	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;
	//[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;
	//[10] updates (jitter)
	bool					cfgBenchmark10_Enable		=	cfgEnable;
	static const b3Scalar	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;
	//[12] b3DbvtVolume notequal
	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;
	//[14] culling(OCL+qsort)
	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;
	//[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;
	//[17] select
	bool					cfgBenchmark17_Enable		=	cfgEnable;
	static const int		cfgBenchmark17_Iterations	=	4;
	static const int		cfgBenchmark17_Reference	=	3390;

	b3Clock					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(b3DbvtVolume): %u bytes\r\n",sizeof(b3DbvtVolume));
	printf("\tsizeof(b3DbvtNode):   %u bytes\r\n",sizeof(b3DbvtNode));
	if(cfgBenchmark1_Enable)
	{// Benchmark 1	
		srand(380843);
		b3AlignedObjectArray<b3DbvtVolume>	volumes;
		b3AlignedObjectArray<bool>			results;
		volumes.resize(cfgLeaves);
		results.resize(cfgLeaves);
		for(int i=0;i<cfgLeaves;++i)
		{
			volumes[i]=b3DbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
		}
		printf("[1] b3DbvtVolume intersections: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark1_Iterations;++i)
		{
			for(int j=0;j<cfgLeaves;++j)
			{
				for(int k=0;k<cfgLeaves;++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);
	}
	if(cfgBenchmark2_Enable)
	{// Benchmark 2	
		srand(380843);
		b3AlignedObjectArray<b3DbvtVolume>	volumes;
		b3AlignedObjectArray<b3DbvtVolume>	results;
		volumes.resize(cfgLeaves);
		results.resize(cfgLeaves);
		for(int i=0;i<cfgLeaves;++i)
		{
			volumes[i]=b3DbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
		}
		printf("[2] b3DbvtVolume merges: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark2_Iterations;++i)
		{
			for(int j=0;j<cfgLeaves;++j)
			{
				for(int k=0;k<cfgLeaves;++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);
	}
	if(cfgBenchmark3_Enable)
	{// Benchmark 3	
		srand(380843);
		b3DynamicBvh						dbvt[2];
		b3DbvtBenchmark::NilPolicy	policy;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
		dbvt[0].optimizeTopDown();
		dbvt[1].optimizeTopDown();
		printf("[3] b3DynamicBvh::collideTT: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark3_Iterations;++i)
		{
			b3DynamicBvh::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);
	}
	if(cfgBenchmark4_Enable)
	{// Benchmark 4
		srand(380843);
		b3DynamicBvh						dbvt;
		b3DbvtBenchmark::NilPolicy	policy;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[4] b3DynamicBvh::collideTT self: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark4_Iterations;++i)
		{
			b3DynamicBvh::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);
	}
	if(cfgBenchmark5_Enable)
	{// Benchmark 5	
		srand(380843);
		b3DynamicBvh								dbvt[2];
		b3AlignedObjectArray<b3Transform>	transforms;
		b3DbvtBenchmark::NilPolicy			policy;
		transforms.resize(cfgBenchmark5_Iterations);
		for(int i=0;i<transforms.size();++i)
		{
			transforms[i]=b3DbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark5_OffsetScale);
		}
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[0]);
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt[1]);
		dbvt[0].optimizeTopDown();
		dbvt[1].optimizeTopDown();
		printf("[5] b3DynamicBvh::collideTT xform: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark5_Iterations;++i)
		{
			b3DynamicBvh::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);
	}
	if(cfgBenchmark6_Enable)
	{// Benchmark 6	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3Transform>	transforms;
		b3DbvtBenchmark::NilPolicy			policy;
		transforms.resize(cfgBenchmark6_Iterations);
		for(int i=0;i<transforms.size();++i)
		{
			transforms[i]=b3DbvtBenchmark::RandTransform(cfgVolumeCenterScale*cfgBenchmark6_OffsetScale);
		}
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[6] b3DynamicBvh::collideTT xform,self: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark6_Iterations;++i)
		{
			b3DynamicBvh::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);
	}
	if(cfgBenchmark7_Enable)
	{// Benchmark 7	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3Vector3>		rayorg;
		b3AlignedObjectArray<b3Vector3>		raydir;
		b3DbvtBenchmark::NilPolicy			policy;
		rayorg.resize(cfgBenchmark7_Iterations);
		raydir.resize(cfgBenchmark7_Iterations);
		for(int i=0;i<rayorg.size();++i)
		{
			rayorg[i]=b3DbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
			raydir[i]=b3DbvtBenchmark::RandVector3(cfgVolumeCenterScale*2);
		}
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[7] b3DynamicBvh::rayTest: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark7_Passes;++i)
		{
			for(int j=0;j<cfgBenchmark7_Iterations;++j)
			{
				b3DynamicBvh::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);
	}
	if(cfgBenchmark8_Enable)
	{// Benchmark 8	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[8] insert/remove: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark8_Passes;++i)
		{
			for(int j=0;j<cfgBenchmark8_Iterations;++j)
			{
				dbvt.remove(dbvt.insert(b3DbvtBenchmark::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);
	}
	if(cfgBenchmark9_Enable)
	{// Benchmark 9	
		srand(380843);
		b3DynamicBvh										dbvt;
		b3AlignedObjectArray<const b3DbvtNode*>	leaves;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		dbvt.extractLeaves(dbvt.m_root,leaves);
		printf("[9] updates (teleport): ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark9_Passes;++i)
		{
			for(int j=0;j<cfgBenchmark9_Iterations;++j)
			{
				dbvt.update(const_cast<b3DbvtNode*>(leaves[rand()%cfgLeaves]),
					b3DbvtBenchmark::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);
	}
	if(cfgBenchmark10_Enable)
	{// Benchmark 10	
		srand(380843);
		b3DynamicBvh										dbvt;
		b3AlignedObjectArray<const b3DbvtNode*>	leaves;
		b3AlignedObjectArray<b3Vector3>				vectors;
		vectors.resize(cfgBenchmark10_Iterations);
		for(int i=0;i<vectors.size();++i)
		{
			vectors[i]=(b3DbvtBenchmark::RandVector3()*2-b3Vector3(1,1,1))*cfgBenchmark10_Scale;
		}
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		dbvt.extractLeaves(dbvt.m_root,leaves);
		printf("[10] updates (jitter): ");
		wallclock.reset();

		for(int i=0;i<cfgBenchmark10_Passes;++i)
		{
			for(int j=0;j<cfgBenchmark10_Iterations;++j)
			{			
				const b3Vector3&	d=vectors[j];
				b3DbvtNode*		l=const_cast<b3DbvtNode*>(leaves[rand()%cfgLeaves]);
				b3DbvtVolume		v=b3DbvtVolume::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);
	}
	if(cfgBenchmark11_Enable)
	{// Benchmark 11	
		srand(380843);
		b3DynamicBvh										dbvt;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[11] optimize (incremental): ");
		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);
	}
	if(cfgBenchmark12_Enable)
	{// Benchmark 12	
		srand(380843);
		b3AlignedObjectArray<b3DbvtVolume>	volumes;
		b3AlignedObjectArray<bool>				results;
		volumes.resize(cfgLeaves);
		results.resize(cfgLeaves);
		for(int i=0;i<cfgLeaves;++i)
		{
			volumes[i]=b3DbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
		}
		printf("[12] b3DbvtVolume notequal: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark12_Iterations;++i)
		{
			for(int j=0;j<cfgLeaves;++j)
			{
				for(int k=0;k<cfgLeaves;++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);
	}
	if(cfgBenchmark13_Enable)
	{// Benchmark 13	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3Vector3>		vectors;
		b3DbvtBenchmark::NilPolicy			policy;
		vectors.resize(cfgBenchmark13_Iterations);
		for(int i=0;i<vectors.size();++i)
		{
			vectors[i]=(b3DbvtBenchmark::RandVector3()*2-b3Vector3(1,1,1)).normalized();
		}
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		printf("[13] culling(OCL+fullsort): ");
		wallclock.reset();	
		for(int i=0;i<cfgBenchmark13_Iterations;++i)
		{
			static const b3Scalar	offset=0;
			policy.m_depth=-B3_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);
	}
	if(cfgBenchmark14_Enable)
	{// Benchmark 14	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3Vector3>		vectors;
		b3DbvtBenchmark::P14				policy;
		vectors.resize(cfgBenchmark14_Iterations);
		for(int i=0;i<vectors.size();++i)
		{
			vectors[i]=(b3DbvtBenchmark::RandVector3()*2-b3Vector3(1,1,1)).normalized();
		}
		b3DbvtBenchmark::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)
		{
			static const b3Scalar	offset=0;
			policy.m_nodes.resize(0);
			dbvt.collideOCL(dbvt.m_root,&vectors[i],&offset,vectors[i],1,policy,false);
			policy.m_nodes.quickSort(b3DbvtBenchmark::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);
	}
	if(cfgBenchmark15_Enable)
	{// Benchmark 15	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3Vector3>		vectors;
		b3DbvtBenchmark::P15				policy;
		vectors.resize(cfgBenchmark15_Iterations);
		for(int i=0;i<vectors.size();++i)
		{
			vectors[i]=(b3DbvtBenchmark::RandVector3()*2-b3Vector3(1,1,1)).normalized();
		}
		b3DbvtBenchmark::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)
		{
			static const b3Scalar	offset=0;
			policy.m_nodes.resize(0);
			policy.m_axis=vectors[i];
			dbvt.collideKDOP(dbvt.m_root,&vectors[i],&offset,1,policy);
			policy.m_nodes.quickSort(b3DbvtBenchmark::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);
	}
	if(cfgBenchmark16_Enable)
	{// Benchmark 16	
		srand(380843);
		b3DynamicBvh								dbvt;
		b3AlignedObjectArray<b3DbvtNode*>	batch;
		b3DbvtBenchmark::RandTree(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale,cfgLeaves,dbvt);
		dbvt.optimizeTopDown();
		batch.reserve(cfgBenchmark16_BatchCount);
		printf("[16] insert/remove batch(%u): ",cfgBenchmark16_BatchCount);
		wallclock.reset();
		for(int i=0;i<cfgBenchmark16_Passes;++i)
		{
			for(int j=0;j<cfgBenchmark16_BatchCount;++j)
			{
				batch.push_back(dbvt.insert(b3DbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale),0));
			}
			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));
	}
	if(cfgBenchmark17_Enable)
	{// Benchmark 17
		srand(380843);
		b3AlignedObjectArray<b3DbvtVolume>	volumes;
		b3AlignedObjectArray<int>			results;
		b3AlignedObjectArray<int>			indices;
		volumes.resize(cfgLeaves);
		results.resize(cfgLeaves);
		indices.resize(cfgLeaves);
		for(int i=0;i<cfgLeaves;++i)
		{
			indices[i]=i;
			volumes[i]=b3DbvtBenchmark::RandVolume(cfgVolumeCenterScale,cfgVolumeExentsBase,cfgVolumeExentsScale);
		}
		for(int i=0;i<cfgLeaves;++i)
		{
			b3Swap(indices[i],indices[rand()%cfgLeaves]);
		}
		printf("[17] b3DbvtVolume select: ");
		wallclock.reset();
		for(int i=0;i<cfgBenchmark17_Iterations;++i)
		{
			for(int j=0;j<cfgLeaves;++j)
			{
				for(int k=0;k<cfgLeaves;++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);
	}
	printf("\r\n\r\n");
}
#endif