Optimal way to detect collisions.

Post Reply
red
Posts: 6
Joined: Wed Mar 13, 2013 9:18 pm

Optimal way to detect collisions.

Post by red » Wed Mar 13, 2013 9:44 pm

Ok, i've got my simulation set up and working, which was dead easy, thanks.

Now I have a question.
Is there any way to get collisions when they start and finish instead of continuously (if you get what I mean)?

My test simulation is a basic 'drop a sphere every second onto a terrain' which runs fine on android (in a seperate thread to render of course), and from the perf counters i've chucked in, i'm reading 66% of the spheres are generating collisions, which gets a bit slow when there's 300 of the buggers and no NEON.

Btw, i've also got the per-collision overhead of calling lua.

Basically, is there a way to generate events when 2 bodies collide and when they stop colliding, or is this something i'd have to track myself.

red
Posts: 6
Joined: Wed Mar 13, 2013 9:18 pm

Re: Optimal way to detect collisions.

Post by red » Fri Mar 15, 2013 12:49 pm

Well, I've got the collisions down to about 45% by playing with the numbers (setSleepingThresholds(0.4,1.0) and tweaking gDeactivationTime to 1.0), but it still suffers when there are a few spheres in the scene.

Anyone???

dumbo2007
Posts: 66
Joined: Sun Jan 30, 2011 8:46 pm

Re: Optimal way to detect collisions.

Post by dumbo2007 » Sun Mar 17, 2013 3:28 pm

Would the collision callbacks be of any help ?

red
Posts: 6
Joined: Wed Mar 13, 2013 9:18 pm

Re: Optimal way to detect collisions.

Post by red » Tue Mar 19, 2013 7:07 pm

Well, i've been playing a bit more and setting a non zero restitution to all my objects has helped immensely - i'm now getting about 20% collision per step, which is a lot more acceptable. although the simulation starts to crawl around the 300 sphere mark - more than enough .

Regarding the collision callbacks... If I could find some decent documentation (Unfortunately one of bullet's few pitfalls). Also, I don't think they work with multithreaded (which I think I will be using on this project).

Here's one for Erwin tho, would splitting the heightfield into smaller 'patches' speed up the simulation?

xexuxjy
Posts: 225
Joined: Wed Jan 07, 2009 11:43 am
Location: London

Re: Optimal way to detect collisions.

Post by xexuxjy » Wed Mar 20, 2013 9:50 am

I'm not Erwin (obviously <g>) , but I doubt that splitting the heightfield into different grids would make a great deal of difference as it's handled as a regular grid and the number of triangles tested is based on the aabb overlap onto a portion of that grid. Having multiple height fields would really just mean that some of them would be culled earlier in the broadphase but the number of narrow phase triangle test would likely be the same (or possibly more if the multiple grids had higher resolution)

STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Optimal way to detect collisions.

Post by STTrife » Wed Mar 20, 2013 11:32 am

I have been thinking about this too, and I do think that dividing the heightfield could give advantages in some situations...

Consider this heightfield (looking from aside)

Code: Select all

                  __
    O           /
               /
______________/

(O = object)
The BB will be very heigh, because of the hill at the right side. So whenever a moving object is floating quite hight on the left side like in the picture, it will still check all triangles that's it's floating over because it's inside the BB of the heightfield, even though you would hope it wouldn't because it's so heigh above the ground.
If you would split the heightfield in the flat part and the hill part, then you no longer have this problem. The BB of the flat part will be very thin, and it will only start checking triangles when an object is actually near the heightfield.

I hope I make clear what I mean, and also that I'm right about this :) any way, was far as I could see in the code: as long as an object is in the BB of the heightfield, it checks all triangles that are on the same width/length coordinates.
I was also thinking about a possible improvement on this part, but I haven't thought of a good way yet. In my case I use generated terrain so I cannot split up the terrain myself. But I think some sort of octree broadphase check, which includes height could reduce the number of unnecessary triangle checks.

xexuxjy
Posts: 225
Joined: Wed Jan 07, 2009 11:43 am
Location: London

Re: Optimal way to detect collisions.

Post by xexuxjy » Wed Mar 20, 2013 1:36 pm

It's an interesting problem, I think it partly depends on what your height map looks like, you could have a second set of data to provide minimum and maximum values for sections of the height field rather than the whole thing and use that as an optimisation, but taking that to it's extreme you'd potentially end up with a height map for each grid square... The heightmap because of it's regularity is pretty efficient already and 'slow' moving objects tend to only be testing a few triangles on any pass anyway (worst case is long diagonal raycasts as they will end up testing against every triangle in the heightmap).

red
Posts: 6
Joined: Wed Mar 13, 2013 9:18 pm

Re: Optimal way to detect collisions.

Post by red » Thu Mar 21, 2013 3:19 pm

Reason I asked was that I didn't know the codebase, only really looked into btHeightfieldTerrainShape. But seeming as it's (at least) fairly optimal, then nothing to see here...

Bit baffled by sphere's sliding (not rolling - I mean not changing local orientation when moving) tho. Any pointers???

<edit>
btw... i'm using btMotionState like this...

void Mesh::setWorldTransform(const btTransform& t) {
position=btTransform(t);
}

void Mesh::getWorldTransform(btTransform& t) const{
t=btTransform(position);
}

and i'm transferring the position to GL with... (later in the pipeline)
btQuaternion Q=position.getRotation();
btVector3 P=position.getOrigin();
quat=glm::quat(Q.w(),Q.x(),Q.y(),Q.z());
pos=glm::vec3(P.x(),P.y(),P.z());

<edit 2>
Fixed, didn't set inertia when creating the body
was...
body=new btRigidBody(mass,this,collisionShape,btVector3(0,0,0));

now...
btVector3 localInertia(0.0f, 0.0f, 0.0f);
collisionShape->calculateLocalInertia(1, localInertia);
body=new btRigidBody(mass,this,collisionShape,localInertia);

now to figure out... (next post)
Last edited by red on Thu Mar 21, 2013 4:48 pm, edited 1 time in total.

red
Posts: 6
Joined: Wed Mar 13, 2013 9:18 pm

Re: Optimal way to detect collisions.

Post by red » Thu Mar 21, 2013 4:41 pm

On a(nother) side note, here's a strange one...

Enabling rolling friction (0.3f) makes spheres disappear (as in teleport miles away) when they collide.

Is this normal????????

<edit>
Not sure what I did, but kirk's back on the bridge... (i.e. rolling friction back on and no teleporting).

User avatar
pccsoares
Posts: 13
Joined: Mon Jan 20, 2014 11:57 am
Contact:

Re: Optimal way to detect collisions.

Post by pccsoares » Sun Mar 16, 2014 12:27 am

I confirm that there is a bug in bullet related to rolling friction.
I spent the last 3 days trying to understand why in my soccer game, the ball behaved perfectly on IOS, but mysteriously disappeared on Android. After a few stepSimulation's the ball coordinates went to NaN.
After I saw your post I removed the rolling friction of the ball and confirmed that it was the problem.

DannyChapman
Posts: 81
Joined: Sun Jan 07, 2007 4:29 pm
Location: Oxford, England
Contact:

Re: Optimal way to detect collisions.

Post by DannyChapman » Wed Mar 19, 2014 12:30 pm

xexuxjy wrote:The heightmap because of it's regularity is pretty efficient already
I'm afraid that's not quite correct. When colliding an object against the heightmap, the code does an AABB test with the heightmap's whole AABB, and then if that passes it does low level tests against all the heightmap triangles in the 2D region below the object. This can end up being really expensive if your object is well above the surface at that point, but still inside the heightmap's AABB (e.g. in a valley).

I made local changes to add AABB checks between the object and the heightmap triangles. I only tested it in my application so can't say whether it might cause problems elsewhere (e.g. collisions against with convex shapes). I sent the changes to Erwin, but due to some uncertainty in going from my app-specific changes to a general one I think they got lost from the most recent version (I suggest checking). The changes are something like this:

void btConvexTriangleCallback::processTriangle(btVector3* triangle,int
partId, int triangleIndex)
{
const btCollisionObject* ob =
const_cast<btCollisionObject*>(m_triBodyWrap->getCollisionObject());

if (!TestTriangleAgainstAabb2(triangle, m_aabbMin, m_aabbMax))
{
return;
}

It makes a huge performance difference for my application, especially on mobile devices - http://www.rowlhouse.co.uk/PicaSim

xexuxjy
Posts: 225
Joined: Wed Jan 07, 2009 11:43 am
Location: London

Re: Optimal way to detect collisions.

Post by xexuxjy » Thu Mar 20, 2014 10:28 am

Yep thats a good point, and a nice fix. Just checked and it looks like your changes still seem to be in in the current version. Will have to give it a go.

Post Reply