Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: code/trunk/src/bullet/BulletCollision/BroadphaseCollision/btDbvt.cpp @ 2801

Last change on this file since 2801 was 2662, checked in by rgrieder, 16 years ago
Merged presentation branch back to trunk.
Property svn:eol-style set to `native`
File size: 35.3 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: