addCollisionObject is very slow for many Objects - why?

[snoisius]

Hi,

i want to add many static sphere objects (representing a point cloud) and a static triangle mesh and check for collisions.

Currently i'm doing something like this:

First, i set up my collision world:

Code: Select all

btVector3 worldAabbMin( -1000, -1000 , -1000 );
btVector3 worldAabbMax( 1000 , 1000 , 1000 );

m_collisionConfiguration = new btDefaultCollisionConfiguration();
m_collisionDispatcher = new btCollisionDispatcher( m_collisionConfiguration );
m_collisionBPI = new bt32BitAxisSweep3( worldAabbMin, worldAabbMax );
m_collisionWorld = new btCollisionWorld( m_collisionDispatcher, m_collisionBPI , m_collisionConfiguration );

Then i add many spheres, e.g.:

Code: Select all

const unsigned int size = 50;

btCollisionShape * collisionShape = new btSphereShape( 0.45 );
btCollisionObject * collisionObjects = new btCollisionObject[size*size*size];

for ( unsigned int collisionObjectN = 0 ; collisionObjectN < size*size*size ; collisionObjectN++ )
{		
	collisionObjects[collisionObjectN].setCollisionShape( collisionShape ); 
	collisionObjects[collisionObjectN].setCollisionFlags( btCollisionObject::CF_STATIC_OBJECT );
	collisionObjects[collisionObjectN].getWorldTransform().setOrigin( 
		btVector3
		(
			double(collisionObjectN % size) * 5.0,
			double(collisionObjectN / (size)) * 5.0,
			double(collisionObjectN / (size*size)) * 5.0
		)
	);
	m_collisionWorld->addCollisionObject( &collisionObjects[collisionObjectN] );
}

The problem is, that adding 70k spheres like this already takes 1 minute (release built). That is way too long for my application. Almost all of that time is spent in addCollisionObject. Why does it take so long? Is there a way to add the objects to the collision world faster? Please help.

Thank you very much!

Patrick

[Erwin Coumans]

Use the btDbvtBroadphase, not a sweep and prune.

Thanks,
Erwin

[snoisius]

Hi,

thanks for the quick reply! Using btDbvtBroadphase indeed speeds up the process (10sec for 70k spheres, 30sec for all 125k).
Unfortunately, this still is too slow. Do you know other ways to further speed it up (significantly)?

Thank you very much!

Patrick

[snoisius]

I experimented a little bit and found out, that adding the spheres in an n * n * n grid greatly increases performance (which I did not do (although intended) with the code posted above). Now i can add 1 million spheres in 16 sec.

I add the spheres in the gridlike fashion and then transform them to their actual position (which takes only 0.02 secs for all).

Is there an disadvantage in doing this? Why is performance of adding a collision object so extremely dependant on its position but it can be transformed to a different position so easily afterwards ?!

Patrick

[Mako_energy02]

The reason it took so long in the first place is because when you initially insert an object into the world it performs an AABB check of all objects around it and then generates broadphase pairs for the dispatcher to use later when it finds hits. If these sphere's were overlapping when you inserted them, this is a lot of work. The reason your grid solution worked is because you ensured there is no overlap when they are added. Changing their transform after the fact does not incur additional broadphase checks.

I'm curious though if you had a performance hit on the first call to "stepSimulation", since your solution as I understand it is postponing the inevitable at best. If it was more performant then I'm curious as to why that is.

[Erwin Coumans]

The Bullet broadphases are optimized for incremental changes.

Initialization can be slow for various reasons. Your approach of using a grid sounds good. Note that the order of insertion can also affect performance.
Thanks,
Erwin

[bajo]

I'm also handling a lot of bodies and it takes a long time to add them to the collisionWorld. (>5min for 1 million spheres)

How do you implement the grid and how can I add 1 million particles in 16 seconds to my simulation?
Thanks!


Edit: If you increase the distance between the spheres, add them to world and then position them it is very fast and the simulation also needs fewer memory.

[Erwin Coumans]

Are you inserting them at the destination location, or in the same position?

What broadphase are you using? The btDbvtBroadphase or uniform grid should be faster than that. Our current research on GPU can easier deal with million objects.

[bajo]

Hello Erwin,

Thanks for your reply!

I'm inserting them in a cube with a distance between two spheres of about 5 times of their radii. After I have added them to the collisionWorld, I move them to their final position.
For the collision detection I used the btDbvtBroadphase.

I'm very interested in GPU collisions detection but I haven't found any example where a full collision detection with trimesh and complex geometries is implemented in bullet?
Is there any demo where I can test it?

thanks!

[Erwin Coumans]

What kind of complex geometries do you need? Can you describe it more in detail?

We can collide a (moving) convex hull against a static concave triangle mesh on GPU at the moment. This is all experimental work in a separate repository.

[bajo]

I would need a collision detection of moving triangle meshes like (moving trimesh - moving trimesh) and (moving trimesh - moving spheres).
But a moving convex hull against static triangle mesh wouldn't be bad for the first GPU test.

Where can I find this experimental work or isn't it published yet?

thanks!

[bajo]

Are you inserting them at the destination location, or in the same position?

What broadphase are you using? The btDbvtBroadphase or uniform grid should be faster than that. Our current research on GPU can easier deal with million objects.

How can I implement a uniform grid broadphase? Do you mean something like in the ParticleOpenCL Demo?

thanks!!