Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: code/trunk/src/external/bullet/BulletCollision/BroadphaseCollision/btDbvtBroadphase.cpp @ 7122

Last change on this file since 7122 was 5781, checked in by rgrieder, 15 years ago
Reverted trunk again. We might want to find a way to delete these revisions again (x3n's changes are still available as diff in the commit mails).
Property svn:eol-style set to `native`
File size: 19.3 KB

Rev	Line
[1963]	1	/*
	2	Bullet Continuous Collision Detection and Physics Library
	3	Copyright (c) 2003-2007 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	///btDbvtBroadphase implementation by Nathanael Presson
	16
	17	#include "btDbvtBroadphase.h"
	18
	19	//
	20	// Profiling
	21	//
	22
	23	#if DBVT_BP_PROFILE\|\|DBVT_BP_ENABLE_BENCHMARK
	24	#include <stdio.h>
	25	#endif
	26
	27	#if DBVT_BP_PROFILE
	28	struct ProfileScope
[2430]	29	{
	30	__forceinline ProfileScope(btClock& clock,unsigned long& value) :
	31	m_clock(&clock),m_value(&value),m_base(clock.getTimeMicroseconds())
[1972]	32	{
[2430]	33	}
[1963]	34	__forceinline ~ProfileScope()
[2430]	35	{
[1963]	36	(*m_value)+=m_clock->getTimeMicroseconds()-m_base;
[2430]	37	}
[1963]	38	btClock* m_clock;
	39	unsigned long* m_value;
	40	unsigned long m_base;
[2430]	41	};
[1963]	42	#define SPC(_value_) ProfileScope spc_scope(m_clock,_value_)
	43	#else
	44	#define SPC(_value_)
	45	#endif
	46
	47	//
	48	// Helpers
	49	//
	50
	51	//
	52	template <typename T>
	53	static inline void listappend(T* item,T*& list)
	54	{
[2430]	55	item->links[0]=0;
	56	item->links[1]=list;
	57	if(list) list->links[0]=item;
	58	list=item;
[1963]	59	}
	60
	61	//
	62	template <typename T>
	63	static inline void listremove(T* item,T*& list)
	64	{
[2430]	65	if(item->links[0]) item->links[0]->links[1]=item->links[1]; else list=item->links[1];
	66	if(item->links[1]) item->links[1]->links[0]=item->links[0];
[1963]	67	}
	68
	69	//
	70	template <typename T>
	71	static inline int listcount(T* root)
	72	{
[2430]	73	int n=0;
	74	while(root) { ++n;root=root->links[1]; }
	75	return(n);
[1963]	76	}
	77
	78	//
	79	template <typename T>
	80	static inline void clear(T& value)
	81	{
[2430]	82	static const struct ZeroDummy : T {} zerodummy;
	83	value=zerodummy;
[1963]	84	}
	85
	86	//
	87	// Colliders
	88	//
	89
	90	/* Tree collider */
	91	struct btDbvtTreeCollider : btDbvt::ICollide
	92	{
[2430]	93	btDbvtBroadphase* pbp;
	94	btDbvtProxy* proxy;
	95	btDbvtTreeCollider(btDbvtBroadphase* p) : pbp(p) {}
	96	void Process(const btDbvtNode* na,const btDbvtNode* nb)
[1963]	97	{
[2430]	98	if(na!=nb)
[1963]	99	{
[2430]	100	btDbvtProxy* pa=(btDbvtProxy*)na->data;
	101	btDbvtProxy* pb=(btDbvtProxy*)nb->data;
	102	#if DBVT_BP_SORTPAIRS
[2882]	103	if(pa->m_uniqueId>pb->m_uniqueId)
	104	btSwap(pa,pb);
[2430]	105	#endif
	106	pbp->m_paircache->addOverlappingPair(pa,pb);
	107	++pbp->m_newpairs;
[1963]	108	}
	109	}
[2430]	110	void Process(const btDbvtNode* n)
[1963]	111	{
[2430]	112	Process(n,proxy->leaf);
[1963]	113	}
	114	};
	115
	116	//
	117	// btDbvtBroadphase
	118	//
	119
	120	//
	121	btDbvtBroadphase::btDbvtBroadphase(btOverlappingPairCache* paircache)
	122	{
[2430]	123	m_deferedcollide = false;
	124	m_needcleanup = true;
	125	m_releasepaircache = (paircache!=0)?false:true;
	126	m_prediction = 1/(btScalar)2;
	127	m_stageCurrent = 0;
	128	m_fixedleft = 0;
	129	m_fupdates = 1;
	130	m_dupdates = 0;
	131	m_cupdates = 10;
	132	m_newpairs = 1;
	133	m_updates_call = 0;
	134	m_updates_done = 0;
	135	m_updates_ratio = 0;
[2882]	136	m_paircache = paircache? paircache : new(btAlignedAlloc(sizeof(btHashedOverlappingPairCache),16)) btHashedOverlappingPairCache();
[2430]	137	m_gid = 0;
	138	m_pid = 0;
	139	m_cid = 0;
	140	for(int i=0;i<=STAGECOUNT;++i)
[1963]	141	{
[2430]	142	m_stageRoots[i]=0;
[1963]	143	}
	144	#if DBVT_BP_PROFILE
[2430]	145	clear(m_profiling);
[1963]	146	#endif
	147	}
	148
	149	//
	150	btDbvtBroadphase::~btDbvtBroadphase()
	151	{
[2430]	152	if(m_releasepaircache)
	153	{
	154	m_paircache->~btOverlappingPairCache();
	155	btAlignedFree(m_paircache);
	156	}
[1963]	157	}
	158
	159	//
	160	btBroadphaseProxy* btDbvtBroadphase::createProxy( const btVector3& aabbMin,
[2430]	161	const btVector3& aabbMax,
	162	int /shapeType/,
	163	void* userPtr,
	164	short int collisionFilterGroup,
	165	short int collisionFilterMask,
	166	btDispatcher* /dispatcher/,
	167	void* /multiSapProxy/)
[1963]	168	{
[2430]	169	btDbvtProxy* proxy=new(btAlignedAlloc(sizeof(btDbvtProxy),16)) btDbvtProxy( aabbMin,aabbMax,userPtr,
	170	collisionFilterGroup,
	171	collisionFilterMask);
	172
	173	btDbvtAabbMm aabb = btDbvtVolume::FromMM(aabbMin,aabbMax);
	174
	175	//bproxy->aabb = btDbvtVolume::FromMM(aabbMin,aabbMax);
	176	proxy->stage = m_stageCurrent;
	177	proxy->m_uniqueId = ++m_gid;
	178	proxy->leaf = m_sets[0].insert(aabb,proxy);
	179	listappend(proxy,m_stageRoots[m_stageCurrent]);
	180	if(!m_deferedcollide)
[1963]	181	{
[2430]	182	btDbvtTreeCollider collider(this);
	183	collider.proxy=proxy;
	184	m_sets[0].collideTV(m_sets[0].m_root,aabb,collider);
	185	m_sets[1].collideTV(m_sets[1].m_root,aabb,collider);
[1963]	186	}
[2430]	187	return(proxy);
[1963]	188	}
	189
	190	//
	191	void btDbvtBroadphase::destroyProxy( btBroadphaseProxy* absproxy,
[2430]	192	btDispatcher* dispatcher)
[1963]	193	{
[2430]	194	btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
	195	if(proxy->stage==STAGECOUNT)
	196	m_sets[1].remove(proxy->leaf);
[1963]	197	else
[2430]	198	m_sets[0].remove(proxy->leaf);
	199	listremove(proxy,m_stageRoots[proxy->stage]);
	200	m_paircache->removeOverlappingPairsContainingProxy(proxy,dispatcher);
	201	btAlignedFree(proxy);
	202	m_needcleanup=true;
[1963]	203	}
	204
[2430]	205	void btDbvtBroadphase::getAabb(btBroadphaseProxy* absproxy,btVector3& aabbMin, btVector3& aabbMax ) const
	206	{
	207	btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
	208	aabbMin = proxy->m_aabbMin;
	209	aabbMax = proxy->m_aabbMax;
	210	}
	211
[2882]	212	struct BroadphaseRayTester : btDbvt::ICollide
[2430]	213	{
[2882]	214	btBroadphaseRayCallback& m_rayCallback;
	215	BroadphaseRayTester(btBroadphaseRayCallback& orgCallback)
	216	:m_rayCallback(orgCallback)
[2430]	217	{
[2882]	218	}
	219	void Process(const btDbvtNode* leaf)
	220	{
	221	btDbvtProxy* proxy=(btDbvtProxy*)leaf->data;
	222	m_rayCallback.process(proxy);
	223	}
	224	};
[2430]	225
[2882]	226	void btDbvtBroadphase::rayTest(const btVector3& rayFrom,const btVector3& rayTo, btBroadphaseRayCallback& rayCallback,const btVector3& aabbMin,const btVector3& aabbMax)
	227	{
[2430]	228	BroadphaseRayTester callback(rayCallback);
	229
	230	m_sets[0].rayTestInternal( m_sets[0].m_root,
	231	rayFrom,
	232	rayTo,
	233	rayCallback.m_rayDirectionInverse,
	234	rayCallback.m_signs,
	235	rayCallback.m_lambda_max,
	236	aabbMin,
	237	aabbMax,
	238	callback);
	239
	240	m_sets[1].rayTestInternal( m_sets[1].m_root,
	241	rayFrom,
	242	rayTo,
	243	rayCallback.m_rayDirectionInverse,
	244	rayCallback.m_signs,
	245	rayCallback.m_lambda_max,
	246	aabbMin,
	247	aabbMax,
	248	callback);
	249
	250	}
	251
[1963]	252	//
	253	void btDbvtBroadphase::setAabb( btBroadphaseProxy* absproxy,
[2430]	254	const btVector3& aabbMin,
	255	const btVector3& aabbMax,
	256	btDispatcher* /dispatcher/)
[1963]	257	{
[2430]	258	btDbvtProxy* proxy=(btDbvtProxy*)absproxy;
	259	ATTRIBUTE_ALIGNED16(btDbvtVolume) aabb=btDbvtVolume::FromMM(aabbMin,aabbMax);
[1963]	260	#if DBVT_BP_PREVENTFALSEUPDATE
[2430]	261	if(NotEqual(aabb,proxy->leaf->volume))
[1963]	262	#endif
	263	{
[2430]	264	bool docollide=false;
	265	if(proxy->stage==STAGECOUNT)
[1963]	266	{/* fixed -> dynamic set */
[2430]	267	m_sets[1].remove(proxy->leaf);
	268	proxy->leaf=m_sets[0].insert(aabb,proxy);
	269	docollide=true;
[1963]	270	}
	271	else
	272	{/* dynamic set */
[2430]	273	++m_updates_call;
	274	if(Intersect(proxy->leaf->volume,aabb))
[1963]	275	{/* Moving */
[2430]	276
	277	const btVector3 delta=aabbMin-proxy->m_aabbMin;
	278	btVector3 velocity(((proxy->m_aabbMax-proxy->m_aabbMin)/2)*m_prediction);
	279	if(delta[0]<0) velocity[0]=-velocity[0];
	280	if(delta[1]<0) velocity[1]=-velocity[1];
	281	if(delta[2]<0) velocity[2]=-velocity[2];
	282	if (
	283	#ifdef DBVT_BP_MARGIN
	284	m_sets[0].update(proxy->leaf,aabb,velocity,DBVT_BP_MARGIN)
	285	#else
	286	m_sets[0].update(proxy->leaf,aabb,velocity)
	287	#endif
	288	)
[1963]	289	{
[2430]	290	++m_updates_done;
	291	docollide=true;
[1963]	292	}
	293	}
	294	else
	295	{/* Teleporting */
[2430]	296	m_sets[0].update(proxy->leaf,aabb);
	297	++m_updates_done;
	298	docollide=true;
[1963]	299	}
	300	}
[2430]	301	listremove(proxy,m_stageRoots[proxy->stage]);
	302	proxy->m_aabbMin = aabbMin;
	303	proxy->m_aabbMax = aabbMax;
	304	proxy->stage = m_stageCurrent;
	305	listappend(proxy,m_stageRoots[m_stageCurrent]);
	306	if(docollide)
[1963]	307	{
[2430]	308	m_needcleanup=true;
	309	if(!m_deferedcollide)
[1963]	310	{
[2430]	311	btDbvtTreeCollider collider(this);
	312	m_sets[1].collideTTpersistentStack(m_sets[1].m_root,proxy->leaf,collider);
	313	m_sets[0].collideTTpersistentStack(m_sets[0].m_root,proxy->leaf,collider);
[1963]	314	}
	315	}
	316	}
	317	}
	318
	319	//
	320	void btDbvtBroadphase::calculateOverlappingPairs(btDispatcher* dispatcher)
	321	{
[2430]	322	collide(dispatcher);
[1963]	323	#if DBVT_BP_PROFILE
[2430]	324	if(0==(m_pid%DBVT_BP_PROFILING_RATE))
[1963]	325	{
[2430]	326	printf("fixed(%u) dynamics(%u) pairs(%u)\r\n",m_sets[1].m_leaves,m_sets[0].m_leaves,m_paircache->getNumOverlappingPairs());
	327	unsigned int total=m_profiling.m_total;
	328	if(total<=0) total=1;
	329	printf("ddcollide: %u%% (%uus)\r\n",(50+m_profiling.m_ddcollide*100)/total,m_profiling.m_ddcollide/DBVT_BP_PROFILING_RATE);
	330	printf("fdcollide: %u%% (%uus)\r\n",(50+m_profiling.m_fdcollide*100)/total,m_profiling.m_fdcollide/DBVT_BP_PROFILING_RATE);
	331	printf("cleanup: %u%% (%uus)\r\n",(50+m_profiling.m_cleanup*100)/total,m_profiling.m_cleanup/DBVT_BP_PROFILING_RATE);
	332	printf("total: %uus\r\n",total/DBVT_BP_PROFILING_RATE);
	333	const unsigned long sum=m_profiling.m_ddcollide+
	334	m_profiling.m_fdcollide+
	335	m_profiling.m_cleanup;
	336	printf("leaked: %u%% (%uus)\r\n",100-((50+sum*100)/total),(total-sum)/DBVT_BP_PROFILING_RATE);
	337	printf("job counts: %u%%\r\n",(m_profiling.m_jobcount100)/((m_sets[0].m_leaves+m_sets[1].m_leaves)DBVT_BP_PROFILING_RATE));
	338	clear(m_profiling);
	339	m_clock.reset();
[1963]	340	}
	341	#endif
[2882]	342
	343	performDeferredRemoval(dispatcher);
	344
[1963]	345	}
	346
[2882]	347	void btDbvtBroadphase::performDeferredRemoval(btDispatcher* dispatcher)
	348	{
	349
	350	if (m_paircache->hasDeferredRemoval())
	351	{
	352
	353	btBroadphasePairArray& overlappingPairArray = m_paircache->getOverlappingPairArray();
	354
	355	//perform a sort, to find duplicates and to sort 'invalid' pairs to the end
	356	overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
	357
	358	int invalidPair = 0;
	359
	360
	361	int i;
	362
	363	btBroadphasePair previousPair;
	364	previousPair.m_pProxy0 = 0;
	365	previousPair.m_pProxy1 = 0;
	366	previousPair.m_algorithm = 0;
	367
	368
	369	for (i=0;i<overlappingPairArray.size();i++)
	370	{
	371
	372	btBroadphasePair& pair = overlappingPairArray[i];
	373
	374	bool isDuplicate = (pair == previousPair);
	375
	376	previousPair = pair;
	377
	378	bool needsRemoval = false;
	379
	380	if (!isDuplicate)
	381	{
	382	//important to perform AABB check that is consistent with the broadphase
	383	btDbvtProxy* pa=(btDbvtProxy*)pair.m_pProxy0;
	384	btDbvtProxy* pb=(btDbvtProxy*)pair.m_pProxy1;
	385	bool hasOverlap = Intersect(pa->leaf->volume,pb->leaf->volume);
	386
	387	if (hasOverlap)
	388	{
	389	needsRemoval = false;
	390	} else
	391	{
	392	needsRemoval = true;
	393	}
	394	} else
	395	{
	396	//remove duplicate
	397	needsRemoval = true;
	398	//should have no algorithm
	399	btAssert(!pair.m_algorithm);
	400	}
	401
	402	if (needsRemoval)
	403	{
	404	m_paircache->cleanOverlappingPair(pair,dispatcher);
	405
	406	pair.m_pProxy0 = 0;
	407	pair.m_pProxy1 = 0;
	408	invalidPair++;
	409	}
	410
	411	}
	412
	413	//perform a sort, to sort 'invalid' pairs to the end
	414	overlappingPairArray.quickSort(btBroadphasePairSortPredicate());
	415	overlappingPairArray.resize(overlappingPairArray.size() - invalidPair);
	416	}
	417	}
	418
[1963]	419	//
	420	void btDbvtBroadphase::collide(btDispatcher* dispatcher)
	421	{
[2882]	422	/*printf("---------------------------------------------------------\n");
	423	printf("m_sets[0].m_leaves=%d\n",m_sets[0].m_leaves);
	424	printf("m_sets[1].m_leaves=%d\n",m_sets[1].m_leaves);
	425	printf("numPairs = %d\n",getOverlappingPairCache()->getNumOverlappingPairs());
	426	{
	427	int i;
	428	for (i=0;i<getOverlappingPairCache()->getNumOverlappingPairs();i++)
	429	{
	430	printf("pair[%d]=(%d,%d),",i,getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy0->getUid(),
	431	getOverlappingPairCache()->getOverlappingPairArray()[i].m_pProxy1->getUid());
	432	}
	433	printf("\n");
	434	}
	435	*/
	436
	437
	438
[2430]	439	SPC(m_profiling.m_total);
	440	/* optimize */
	441	m_sets[0].optimizeIncremental(1+(m_sets[0].m_leaves*m_dupdates)/100);
	442	if(m_fixedleft)
[1963]	443	{
[2430]	444	const int count=1+(m_sets[1].m_leaves*m_fupdates)/100;
	445	m_sets[1].optimizeIncremental(1+(m_sets[1].m_leaves*m_fupdates)/100);
	446	m_fixedleft=btMax<int>(0,m_fixedleft-count);
[1963]	447	}
[2430]	448	/* dynamic -> fixed set */
	449	m_stageCurrent=(m_stageCurrent+1)%STAGECOUNT;
	450	btDbvtProxy* current=m_stageRoots[m_stageCurrent];
	451	if(current)
[1963]	452	{
[2430]	453	btDbvtTreeCollider collider(this);
	454	do {
	455	btDbvtProxy* next=current->links[1];
	456	listremove(current,m_stageRoots[current->stage]);
	457	listappend(current,m_stageRoots[STAGECOUNT]);
	458	#if DBVT_BP_ACCURATESLEEPING
	459	m_paircache->removeOverlappingPairsContainingProxy(current,dispatcher);
	460	collider.proxy=current;
	461	btDbvt::collideTV(m_sets[0].m_root,current->aabb,collider);
	462	btDbvt::collideTV(m_sets[1].m_root,current->aabb,collider);
	463	#endif
	464	m_sets[0].remove(current->leaf);
	465	ATTRIBUTE_ALIGNED16(btDbvtVolume) curAabb=btDbvtVolume::FromMM(current->m_aabbMin,current->m_aabbMax);
	466	current->leaf = m_sets[1].insert(curAabb,current);
	467	current->stage = STAGECOUNT;
	468	current = next;
[1963]	469	} while(current);
[2430]	470	m_fixedleft=m_sets[1].m_leaves;
	471	m_needcleanup=true;
[1963]	472	}
[2430]	473	/* collide dynamics */
[1963]	474	{
[2430]	475	btDbvtTreeCollider collider(this);
	476	if(m_deferedcollide)
[1963]	477	{
[2430]	478	SPC(m_profiling.m_fdcollide);
	479	m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[1].m_root,collider);
[1963]	480	}
[2430]	481	if(m_deferedcollide)
[1963]	482	{
[2430]	483	SPC(m_profiling.m_ddcollide);
	484	m_sets[0].collideTTpersistentStack(m_sets[0].m_root,m_sets[0].m_root,collider);
[1963]	485	}
	486	}
[2430]	487	/* clean up */
	488	if(m_needcleanup)
[1963]	489	{
[2430]	490	SPC(m_profiling.m_cleanup);
	491	btBroadphasePairArray& pairs=m_paircache->getOverlappingPairArray();
	492	if(pairs.size()>0)
[1963]	493	{
[2882]	494
	495	int ni=btMin(pairs.size(),btMax<int>(m_newpairs,(pairs.size()*m_cupdates)/100));
[2430]	496	for(int i=0;i<ni;++i)
[1963]	497	{
[2882]	498	btBroadphasePair& p=pairs[(m_cid+i)%pairs.size()];
[2430]	499	btDbvtProxy* pa=(btDbvtProxy*)p.m_pProxy0;
	500	btDbvtProxy* pb=(btDbvtProxy*)p.m_pProxy1;
	501	if(!Intersect(pa->leaf->volume,pb->leaf->volume))
[1963]	502	{
[2430]	503	#if DBVT_BP_SORTPAIRS
[2882]	504	if(pa->m_uniqueId>pb->m_uniqueId)
	505	btSwap(pa,pb);
[2430]	506	#endif
	507	m_paircache->removeOverlappingPair(pa,pb,dispatcher);
	508	--ni;--i;
[1963]	509	}
	510	}
[2430]	511	if(pairs.size()>0) m_cid=(m_cid+ni)%pairs.size(); else m_cid=0;
[1963]	512	}
	513	}
[2430]	514	++m_pid;
	515	m_newpairs=1;
	516	m_needcleanup=false;
	517	if(m_updates_call>0)
[1963]	518	{ m_updates_ratio=m_updates_done/(btScalar)m_updates_call; }
	519	else
	520	{ m_updates_ratio=0; }
[2430]	521	m_updates_done/=2;
	522	m_updates_call/=2;
[1963]	523	}
	524
	525	//
	526	void btDbvtBroadphase::optimize()
	527	{
[2430]	528	m_sets[0].optimizeTopDown();
	529	m_sets[1].optimizeTopDown();
[1963]	530	}
	531
	532	//
	533	btOverlappingPairCache* btDbvtBroadphase::getOverlappingPairCache()
	534	{
[2430]	535	return(m_paircache);
[1963]	536	}
	537
	538	//
	539	const btOverlappingPairCache* btDbvtBroadphase::getOverlappingPairCache() const
	540	{
[2430]	541	return(m_paircache);
[1963]	542	}
	543
	544	//
	545	void btDbvtBroadphase::getBroadphaseAabb(btVector3& aabbMin,btVector3& aabbMax) const
	546	{
	547
	548	ATTRIBUTE_ALIGNED16(btDbvtVolume) bounds;
	549
[2430]	550	if(!m_sets[0].empty())
	551	if(!m_sets[1].empty()) Merge( m_sets[0].m_root->volume,
	552	m_sets[1].m_root->volume,bounds);
	553	else
	554	bounds=m_sets[0].m_root->volume;
	555	else if(!m_sets[1].empty()) bounds=m_sets[1].m_root->volume;
	556	else
	557	bounds=btDbvtVolume::FromCR(btVector3(0,0,0),0);
	558	aabbMin=bounds.Mins();
	559	aabbMax=bounds.Maxs();
[1963]	560	}
	561
[2882]	562	void btDbvtBroadphase::resetPool(btDispatcher* dispatcher)
	563	{
	564
	565	int totalObjects = m_sets[0].m_leaves + m_sets[1].m_leaves;
	566	if (!totalObjects)
	567	{
	568	//reset internal dynamic tree data structures
	569	m_sets[0].clear();
	570	m_sets[1].clear();
	571
	572	m_deferedcollide = false;
	573	m_needcleanup = true;
	574	m_prediction = 1/(btScalar)2;
	575	m_stageCurrent = 0;
	576	m_fixedleft = 0;
	577	m_fupdates = 1;
	578	m_dupdates = 0;
	579	m_cupdates = 10;
	580	m_newpairs = 1;
	581	m_updates_call = 0;
	582	m_updates_done = 0;
	583	m_updates_ratio = 0;
	584
	585	m_gid = 0;
	586	m_pid = 0;
	587	m_cid = 0;
	588	for(int i=0;i<=STAGECOUNT;++i)
	589	{
	590	m_stageRoots[i]=0;
	591	}
	592	}
	593	}
	594
[1963]	595	//
	596	void btDbvtBroadphase::printStats()
	597	{}
	598
	599	//
	600	#if DBVT_BP_ENABLE_BENCHMARK
	601
	602	struct btBroadphaseBenchmark
[2430]	603	{
	604	struct Experiment
[1972]	605	{
[1963]	606	const char* name;
	607	int object_count;
	608	int update_count;
	609	int spawn_count;
	610	int iterations;
	611	btScalar speed;
	612	btScalar amplitude;
[2430]	613	};
[1963]	614	struct Object
[2430]	615	{
[1963]	616	btVector3 center;
	617	btVector3 extents;
	618	btBroadphaseProxy* proxy;
	619	btScalar time;
	620	void update(btScalar speed,btScalar amplitude,btBroadphaseInterface* pbi)
[2430]	621	{
[1963]	622	time += speed;
	623	center[0] = btCos(time(btScalar)2.17)amplitude+
[2430]	624	btSin(time)*amplitude/2;
[1963]	625	center[1] = btCos(time(btScalar)1.38)amplitude+
[2430]	626	btSin(time)*amplitude;
[1963]	627	center[2] = btSin(time(btScalar)0.777)amplitude;
	628	pbi->setAabb(proxy,center-extents,center+extents,0);
[2430]	629	}
	630	};
[1963]	631	static int UnsignedRand(int range=RAND_MAX-1) { return(rand()%(range+1)); }
	632	static btScalar UnitRand() { return(UnsignedRand(16384)/(btScalar)16384); }
	633	static void OutputTime(const char* name,btClock& c,unsigned count=0)
[2430]	634	{
[1963]	635	const unsigned long us=c.getTimeMicroseconds();
	636	const unsigned long ms=(us+500)/1000;
	637	const btScalar sec=us/(btScalar)(1000*1000);
	638	if(count>0)
	639	printf("%s : %u us (%u ms), %.2f/s\r\n",name,us,ms,count/sec);
[2430]	640	else
[1963]	641	printf("%s : %u us (%u ms)\r\n",name,us,ms);
[2430]	642	}
	643	};
[1963]	644
	645	void btDbvtBroadphase::benchmark(btBroadphaseInterface* pbi)
	646	{
[2430]	647	static const btBroadphaseBenchmark::Experiment experiments[]=
[1963]	648	{
[2430]	649	{"1024o.10%",1024,10,0,8192,(btScalar)0.005,(btScalar)100},
	650	/*{"4096o.10%",4096,10,0,8192,(btScalar)0.005,(btScalar)100},
	651	{"8192o.10%",8192,10,0,8192,(btScalar)0.005,(btScalar)100},*/
[1963]	652	};
[2430]	653	static const int nexperiments=sizeof(experiments)/sizeof(experiments[0]);
	654	btAlignedObjectArray<btBroadphaseBenchmark::Object*> objects;
	655	btClock wallclock;
	656	/* Begin */
	657	for(int iexp=0;iexp<nexperiments;++iexp)
[1963]	658	{
[2430]	659	const btBroadphaseBenchmark::Experiment& experiment=experiments[iexp];
	660	const int object_count=experiment.object_count;
	661	const int update_count=(object_count*experiment.update_count)/100;
	662	const int spawn_count=(object_count*experiment.spawn_count)/100;
	663	const btScalar speed=experiment.speed;
	664	const btScalar amplitude=experiment.amplitude;
	665	printf("Experiment #%u '%s':\r\n",iexp,experiment.name);
	666	printf("\tObjects: %u\r\n",object_count);
	667	printf("\tUpdate: %u\r\n",update_count);
	668	printf("\tSpawn: %u\r\n",spawn_count);
	669	printf("\tSpeed: %f\r\n",speed);
	670	printf("\tAmplitude: %f\r\n",amplitude);
	671	srand(180673);
	672	/* Create objects */
	673	wallclock.reset();
	674	objects.reserve(object_count);
	675	for(int i=0;i<object_count;++i)
[1963]	676	{
[2430]	677	btBroadphaseBenchmark::Object* po=new btBroadphaseBenchmark::Object();
	678	po->center[0]=btBroadphaseBenchmark::UnitRand()*50;
	679	po->center[1]=btBroadphaseBenchmark::UnitRand()*50;
	680	po->center[2]=btBroadphaseBenchmark::UnitRand()*50;
	681	po->extents[0]=btBroadphaseBenchmark::UnitRand()*2+2;
	682	po->extents[1]=btBroadphaseBenchmark::UnitRand()*2+2;
	683	po->extents[2]=btBroadphaseBenchmark::UnitRand()*2+2;
	684	po->time=btBroadphaseBenchmark::UnitRand()*2000;
	685	po->proxy=pbi->createProxy(po->center-po->extents,po->center+po->extents,0,po,1,1,0,0);
	686	objects.push_back(po);
[1963]	687	}
[2430]	688	btBroadphaseBenchmark::OutputTime("\tInitialization",wallclock);
	689	/* First update */
	690	wallclock.reset();
	691	for(int i=0;i<objects.size();++i)
[1963]	692	{
[2430]	693	objects[i]->update(speed,amplitude,pbi);
[1963]	694	}
[2430]	695	btBroadphaseBenchmark::OutputTime("\tFirst update",wallclock);
	696	/* Updates */
	697	wallclock.reset();
	698	for(int i=0;i<experiment.iterations;++i)
[1963]	699	{
[2430]	700	for(int j=0;j<update_count;++j)
[1963]	701	{
[2430]	702	objects[j]->update(speed,amplitude,pbi);
[1963]	703	}
[2430]	704	pbi->calculateOverlappingPairs(0);
[1963]	705	}
[2430]	706	btBroadphaseBenchmark::OutputTime("\tUpdate",wallclock,experiment.iterations);
	707	/* Clean up */
	708	wallclock.reset();
	709	for(int i=0;i<objects.size();++i)
[1963]	710	{
[2430]	711	pbi->destroyProxy(objects[i]->proxy,0);
	712	delete objects[i];
[1963]	713	}
[2430]	714	objects.resize(0);
	715	btBroadphaseBenchmark::OutputTime("\tRelease",wallclock);
[1963]	716	}
	717
	718	}
	719	#else
	720	void btDbvtBroadphase::benchmark(btBroadphaseInterface*)
	721	{}
	722	#endif
	723
	724	#if DBVT_BP_PROFILE
	725	#undef SPC
	726	#endif
[2882]	727

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

Download in other formats: