My custom patch for collision callback events

lunkhound
Posts: 99
Joined: Thu Nov 21, 2013 8:57 pm

Re: My custom patch for collision callback events

Post by lunkhound »

N0vember wrote:
lunkhound wrote: For things like that I'm doing a query on the broadphase (broadphase->aabbTest()) to collect a list of objects of interest. I would think that having perception spheres as collision shapes in your physics world would add a large number of contacts for the physics to keep track of and slow things down.
Yes, which is why I made a separate collision world, it doesn't interferes with the "physics" of my world if there were any (because for now I don't need them. I don't even have a btDynamicsWorld). I won't go into to much length, but I need the spheres, and bullet (SphereSphere algorithm) is better than me at colliding spheres efficiently :)
That is why I was saying earlier that Bullet should satisfy the basic needs of people using just the Collision component. I think it's what makes it great, and useful to me. High efficiency dynamics-less collisions.
If this double-buffer GPU thing gets implemented it will be perfect.
Having the perception spheres in the collision world along with the objects they are trying to sense can be quite inefficient.

For one thing, if the perception spheres are large, they are likely to overlap each other, generating on the order of N-squared totally useless contacts with each other (where N is the number of perception spheres).

Also, having lots of large objects added to the broadphase (that don't need to be there) will certainly have a negative effect on the internal data structure of the broadphase, making it less efficient.

And sphere vs sphere intersection test is so simple, you really don't even need Bullet for this. If the number of objects you are dealing with is less than 5000 or so, you'd probably be better off just keeping all of your spheres in a big array and doing a brute-force sphere vs sphere check in a for loop.
N0vember
Posts: 10
Joined: Sat Mar 06, 2010 6:39 pm

Re: My custom patch for collision callback events

Post by N0vember »

lunkhound wrote: Having the perception spheres in the collision world along with the objects they are trying to sense can be quite inefficient.

For one thing, if the perception spheres are large, they are likely to overlap each other, generating on the order of N-squared totally useless contacts with each other (where N is the number of perception spheres).
The sensor spheres aren't colliding between themselve. They are only set to collide with the sensed objects which are often small spheres. I'm not going to reinvent the wheel here especially since the sensed objects can have shapes different than sphere, a brute-force sphere-sphere wouldn't suffice.
lunkhound wrote: Also, having lots of large objects added to the broadphase (that don't need to be there) will certainly have a negative effect on the internal data structure of the broadphase, making it less efficient.
"don't need to be there" makes sense to you because you are used to classic dynamics in games. I'm not using them like that so it seems irrelevant. Like I said the perception world is a separate collision world so it's not interfering with anything else. There are only objects there that matter to the perception model. That is, spheres, and the sensed objects (which can vary in shapes), and obstacles. Everything "needs" to be there.

As said above, the sensor spheres don't collide between each other. I suppose the broadphase is intelligent enough to organize its internal data structure according to the collision masks and the fact that objects need or not collisions, isn't it ? If it isn't what do you say about the collision mask feature ? That it shouldn't be used because of inefficiency ?

All this debate stresses my point that Bullet is torn between two sometimes conflicting interests : the one of the people using just the collision detection component and the ones using the dynamics. But the features that are here to satisfy the firsts shouldn't be sacrificed because they are just a minority. Bullet should stay useful and efficient for them too.
lunkhound
Posts: 99
Joined: Thu Nov 21, 2013 8:57 pm

Re: My custom patch for collision callback events

Post by lunkhound »

N0vember wrote:
lunkhound wrote: Also, having lots of large objects added to the broadphase (that don't need to be there) will certainly have a negative effect on the internal data structure of the broadphase, making it less efficient.
"don't need to be there" makes sense to you because you are used to classic dynamics in games. I'm not using them like that so it seems irrelevant. Like I said the perception world is a separate collision world so it's not interfering with anything else. There are only objects there that matter to the perception model. That is, spheres, and the sensed objects (which can vary in shapes), and obstacles. Everything "needs" to be there.
No, I'm not talking about dynamics, I'm talking specifically about the use-case you have described where you are using the collision world to detect intersections between a group of perception spheres and potentially visible objects.
The reason I say they "don't need to be there" is because they don't -- a more efficient way of doing things would be to have the collision world contain just the objects, and then for each perception sphere, do a broadphase query to generate a list of the objects it intersects. That would directly generate the results you are after -- for each perception sphere, a list of potentially visible objects -- without having Bullet do all that extra work you don't need.
You shouldn't be having Bullet generate manifolds -- the manifolds are there for supporting dynamics -- if all you care about is whether the perception sphere intersects with an object or not, then having bullet calculate all of that stuff (like deepest penetration, contact points, normals, etc) is all wasted effort.
N0vember wrote: As said above, the sensor spheres don't collide between each other. I suppose the broadphase is intelligent enough to organize its internal data structure according to the collision masks and the fact that objects need or not collisions, isn't it ? If it isn't what do you say about the collision mask feature ? That it shouldn't be used because of inefficiency ?

All this debate stresses my point that Bullet is torn between two sometimes conflicting interests : the one of the people using just the collision detection component and the ones using the dynamics. But the features that are here to satisfy the firsts shouldn't be sacrificed because they are just a minority. Bullet should stay useful and efficient for them too.
The broadphase is really just an acceleration structure to quickly find all possible pairs of overlapping bounding-boxes. The collision masks are only checked AFTER the broadphase has detected an overlap. The collision masks are there to filter out interactions between objects before they enter the narrowphase (which tends to be much more expensive). So collision masks won't save you any work in the broadphase, but they are totally worth it for all of the narrowphase work they can save.

I don't see any conflict here. Bullet collision is perfectly capable of handling all sorts of collision queries efficiently. However, it is easy to use the collision in a suboptimal way, causing lots of unwanted dynamics oriented work (like the creation of manifolds and such) to take place.
N0vember
Posts: 10
Joined: Sat Mar 06, 2010 6:39 pm

Re: My custom patch for collision callback events

Post by N0vember »

lunkhound wrote: No, I'm not talking about dynamics, I'm talking specifically about the use-case you have described where you are using the collision world to detect intersections between a group of perception spheres and potentially visible objects.
The reason I say they "don't need to be there" is because they don't -- a more efficient way of doing things would be to have the collision world contain just the objects, and then for each perception sphere, do a broadphase query to generate a list of the objects it intersects. That would directly generate the results you are after -- for each perception sphere, a list of potentially visible objects -- without having Bullet do all that extra work you don't need.
You shouldn't be having Bullet generate manifolds -- the manifolds are there for supporting dynamics -- if all you care about is whether the perception sphere intersects with an object or not, then having bullet calculate all of that stuff (like deepest penetration, contact points, normals, etc) is all wasted effort.
I completely agree that Bullet is computing things I don't need. That's why I'm saying Bullet Collision is torn between its "collision" library and its "dynamics" library. Collision library is in fact already a bit of a dynamics library.

But I just don't have a better option.
1. Broadphase vs narrowphase : I need narrowphase.
The broadphase collision yields me AABB detection.
The narrowphase yields me physically accurate collisions.

So your suggestion isn't enough. I need to perform narrowphase collision. I cannot use only a broadphase query. And the narrowphase algorithms do generate contact points, normals, etc... I'm not gonna write them, so I'll use the ones from bullet. So again what alternative do I have to computing manifolds ?

2. What you suggest is to brute-force recompute everything each frame. But I need persistence. So your solution would have to include coding a kind of persistence for contacts. That means recoding large parts of what bullet already does, again.
How do you propose a simple solution for persistent contacts ?
One option is writing my own custom broadphase, using the persistent contacts Bullet already has, but it doesn't solve your criticism about computing unneeded physical specifics in the narrowphase.

3. Given that I need persistence, I trust Bullet is much more intelligent than me to efficiently recompute collisions when something in the world has moved / changed.
Recoding everything myself will have an overhead compared to my present solution, because I'm not experienced in this kind of optimization.

So on one hand, I have the solution of using bullet system as-is, it works great, performs well, and has a slight overhead that you mention. And on the other hand, I have the option of doing a lot of stuff manually, not even being sure that the system I'll come up with will be that more efficient than bullet's broadphase / narrowphase is already doing.
So the bottom line for me, you've probably heard that saying about premature optimization. I'm not gonna rewrite all this stuff until it proves to be a serious bottleneck of my game.
N0vember wrote: The broadphase is really just an acceleration structure to quickly find all possible pairs of overlapping bounding-boxes. The collision masks are only checked AFTER the broadphase has detected an overlap. The collision masks are there to filter out interactions between objects before they enter the narrowphase (which tends to be much more expensive). So collision masks won't save you any work in the broadphase, but they are totally worth it for all of the narrowphase work they can save.

I don't see any conflict here. Bullet collision is perfectly capable of handling all sorts of collision queries efficiently. However, it is easy to use the collision in a suboptimal way, causing lots of unwanted dynamics oriented work (like the creation of manifolds and such) to take place.
Okay. I thought collision masks played a role in the broadphase.
Nonetheless, your point seems to be that, having hundreds of spheres, and about as many hundreds of objects colliding with these spheres.
-Doing one broadphase query per sphere each frame, and then computing the narrowphase "manually" on the results.
vs.
-Have bullet handle all these collisions in the broadphase itself, handle persistence, and notify me of new / removed collisions.

You are saying that the second option is gonna be substantially worse in terms of performances.
As far as I can tell, I may do better than the broadphase because I'll do only one AABB query where Bullet is doing maybe 5-10 useless ones (between the spheres).
But that means the overhead of my current solution is not at all in the narrowphase and the manifolds, but only in the broadphase.
lunkhound
Posts: 99
Joined: Thu Nov 21, 2013 8:57 pm

Re: My custom patch for collision callback events

Post by lunkhound »

N0vember wrote:
lunkhound wrote: No, I'm not talking about dynamics, I'm talking specifically about the use-case you have described where you are using the collision world to detect intersections between a group of perception spheres and potentially visible objects.
The reason I say they "don't need to be there" is because they don't -- a more efficient way of doing things would be to have the collision world contain just the objects, and then for each perception sphere, do a broadphase query to generate a list of the objects it intersects. That would directly generate the results you are after -- for each perception sphere, a list of potentially visible objects -- without having Bullet do all that extra work you don't need.
You shouldn't be having Bullet generate manifolds -- the manifolds are there for supporting dynamics -- if all you care about is whether the perception sphere intersects with an object or not, then having bullet calculate all of that stuff (like deepest penetration, contact points, normals, etc) is all wasted effort.
I completely agree that Bullet is computing things I don't need. That's why I'm saying Bullet Collision is torn between its "collision" library and its "dynamics" library. Collision library is in fact already a bit of a dynamics library.

But I just don't have a better option.
1. Broadphase vs narrowphase : I need narrowphase.
The broadphase collision yields me AABB detection.
The narrowphase yields me physically accurate collisions.
Do you really need such accurate collision detection for a perception model?

If so, what kinds of collision shapes do you need to support? And is it fair to assume that the perception spheres are large compared to the objects they are trying to sense?

If the collision shapes are all convex (derived from btConvexShape), and the second assumption is true, then you could probably get away with doing a pretty simple sphere-vs-convex object intersection test as follows:

1. Construct a direction vector from the center of the object (center of its Aabb) to the center of the sphere
2. Rotate the vector into the object's local space
3. Use the function btConvex::localGetSupportingVertex( dir ) to get a point on the object (in local space).
4. Transform the point back to world space.
5. Check if the point is inside the sphere

That should be a fairly accurate test so long as the perception spheres are large. It would be very little code to write -- bullet is still doing most of the heavy lifting with the supporting vertex calculation -- and it would avoid using the narrowphase and all of the extra work it does.

I would only make the perception model as accurate as it really needs to be, otherwise you'll be paying the price in performance.
N0vember wrote:So your suggestion isn't enough. I need to perform narrowphase collision. I cannot use only a broadphase query. And the narrowphase algorithms do generate contact points, normals, etc... I'm not gonna write them, so I'll use the ones from bullet. So again what alternative do I have to computing manifolds ?

2. What you suggest is to brute-force recompute everything each frame. But I need persistence. So your solution would have to include coding a kind of persistence for contacts. That means recoding large parts of what bullet already does, again.
How do you propose a simple solution for persistent contacts ?
One option is writing my own custom broadphase, using the persistent contacts Bullet already has, but it doesn't solve your criticism about computing unneeded physical specifics in the narrowphase.
I don't know the specifics of what you are trying to do, but I would assume that it isn't really going to be enough to simply know that an object intersects with the perception sphere. If the perception sphere represents vision, you'll need to do additional line-of-sight checks to see if the object is occluded by walls or other obstacles. If it represents hearing, you might need some other kinds of checks. The point is that in all likelyhood, the persistent contacts that bullet maintains isn't going to be all that useful to your perception model -- most likely you'll need to maintain your own customized persistent contact info for each perception-sphere/object pair.

It also seems to me that the way that Bullet maintains a big global list of all contacts isn't very useful for a perception model where you'd typically want to know things like "how many objects can this guy see". I would think you'd want to keep a separate list of contacts for each perception sphere.

If it were me, I would keep a list of MyContact structs for each perception sphere. When it is time to update a perception sphere, I'd use something like the sphere-vs-convex test I outlined above wrapped in a broadphase AabbTest callback to find a list of all overlapping btCollisionObjects. Loop over the list of overlaps and update the list of MyContact structs accordingly (maybe using a hash table to map from collision object to MyContact entry). Also doing raycasts here against the terrain to determine visibility.

One thing that design makes possible is to update the perception spheres independently of each other. This opens up a lot of optimization opportunities -- things like only updating a certain number of perception spheres each frame, or updating them at different rates depending on their state or how far from the player they are.

If you can get by with what Bullet is providing using the narrowphase and all that, and performance is fine, and you don't need to extend the persistent info it collects (such as with line of sight checks, etc), then there's no need to worry about all this...
N0vember
Posts: 10
Joined: Sat Mar 06, 2010 6:39 pm

Re: My custom patch for collision callback events

Post by N0vember »

lunkhound wrote: If the collision shapes are all convex (derived from btConvexShape), and the second assumption is true, then you could probably get away with doing a pretty simple sphere-vs-convex object intersection test as follows:
Yes, sensed objects will always be convex. Spheres, Cylinders or ConvexHulls mostly.
lunkhound wrote: It also seems to me that the way that Bullet maintains a big global list of all contacts isn't very useful for a perception model where you'd typically want to know things like "how many objects can this guy see". I would think you'd want to keep a separate list of contacts for each perception sphere.

If it were me, I would keep a list of MyContact structs for each perception sphere.
Yes, exactly, it already works like what you are describing. I have contacts stored per sensor, and I do some raycasts when something is moving. I have persistence there, yes.
But I meant persistence at the level of the collision detection, in order to update these contacts, to act only when something has changed in the actual collisions, which requires persistence at the lower level. But you propose to recompute all contacts on each update, so no persistence.
Why not, but :
1. It means that however simple the Sphere/Convex test is, I'm redoing it every frame for each sphere for each contact (whereas Bullet might have been more clever by only updating the contacts points that needed it, thanks to persistent manifolds ? but I'm not completely sure, it might not)
2. I thought doing a diff of the contacts for each updated object would be quite expensive, and would maybe outweigh the speed gains your proposition would otherwise brings. But I may be wrong. It may also be because I don't know the most efficient way.
You are proposing a hash table that would map from the contact pointer to its position in the list, do I understand correctly ? Is that for the concern of doing the diff the quickest possible ? Something like std::unordered_map<ColObject*, int> ? That would be one such map per sphere, right ?
If you can get by with what Bullet is providing using the narrowphase and all that, and performance is fine, and you don't need to extend the persistent info it collects (such as with line of sight checks, etc), then there's no need to worry about all this...
I don't know yet, like I said, if one day my perception model proves to be a bottleneck I'll be glad to have this alternative optimized method you propose.
lunkhound
Posts: 99
Joined: Thu Nov 21, 2013 8:57 pm

Re: My custom patch for collision callback events

Post by lunkhound »

N0vember wrote: Yes, exactly, it already works like what you are describing. I have contacts stored per sensor, and I do some raycasts when something is moving. I have persistence there, yes.
But I meant persistence at the level of the collision detection, in order to update these contacts, to act only when something has changed in the actual collisions, which requires persistence at the lower level. But you propose to recompute all contacts on each update, so no persistence.
Why not, but :
1. It means that however simple the Sphere/Convex test is, I'm redoing it every frame for each sphere for each contact (whereas Bullet might have been more clever by only updating the contacts points that needed it, thanks to persistent manifolds ? but I'm not completely sure, it might not)
I'm not sure about it either. I know there are conditions where bullet will short-circuit the collision detection, like when objects are "sleeping". But the activation state is updated by dynamics. The only way to know for sure would be to test it.
N0vember wrote: 2. I thought doing a diff of the contacts for each updated object would be quite expensive, and would maybe outweigh the speed gains your proposition would otherwise brings. But I may be wrong. It may also be because I don't know the most efficient way.
You are proposing a hash table that would map from the contact pointer to its position in the list, do I understand correctly ? Is that for the concern of doing the diff the quickest possible ? Something like std::unordered_map<ColObject*, int> ? That would be one such map per sphere, right ?
Yes one hash table per sphere. And yes that would be to speed up the diff. If the hash table is missing an entry, it means a new contact and you need to add it. To detect contacts that should be removed, mark each entry with a frame-counter (like a time-stamp). After all contacts are updated, walk the list of them and remove any with old time stamps.
N0vember wrote: I don't know yet, like I said, if one day my perception model proves to be a bottleneck I'll be glad to have this alternative optimized method you propose.
Good luck!
Sam Danielson
Posts: 1
Joined: Mon Dec 08, 2014 3:19 am

Re: My custom patch for collision callback events

Post by Sam Danielson »

Erwin Coumans wrote:It is good to sort this our for the upcoming Bullet 3.x release.

Indeed, iterating over the contact manifolds and using the lifetime flag should be sufficient to determine what contact points are 'new'.

In a new (GPU friendly) implementation, we could use double-buffering, maintaining the 'old' contact buffer and a 'new' contact buffer. We will need a parallel 'diff' then to determine the lifetime of contacts, carying over contact cache information (applied impulse). The new contact buffer would have entries for deleted points.

Would that be sufficient?
I created an issue to track progress on this, as I may not actively track the forums: https://github.com/bulletphysics/bullet3/issues/291

Sleeping bodies? I am doing something similar to the OP and I just found this thread. I had been using the lifetime flag without issue until today I found one particular body kept having a new collision at rest. When I set DISABLE_DEACTIVATION on the body the bug went away. It seems the body (island?) went to sleep at lifetime() == 1.

Also, for the OP, I track persistence with a counter e.g. std::map < entityId, unsigned int > groundContact, and it works well. It's kind of neat to think that an entity might behave differently based on the number of contact points. Just a possibility I haven't tested. Also, new for impacts, sum applied impulse of all contact points where lifetime == 1. I've been using that method to set the gain on impact sounds without issue.


update:

I've found one solution to my problem.

Code: Select all

if (manifoldPoint.getLifeTime() == 1) {
    collisionObjectA->activate();
    collisionObjectB->activate();
    ...
}
This will activate an object on collision and ensure the lifetime flag does not stay equal to 1. Seems bullet only activates objects above a velocity threshold, not for contact alone. Another more efficient trick might be to manually bump the lifetime to 2 iff it equals 1, but there are probably consequences to that. Actually it would seem more elegant if bullet started counting at zero, bumped all zeros to 1 next frame regardless of activation state, then behaved normally after that.
Jonathan
Posts: 36
Joined: Sun Feb 10, 2013 6:52 pm

Re: My custom patch for collision callback events

Post by Jonathan »

HELP! This is completely exploding with compound shapes. I have a normal rigidbody (bodyA) fully encased in a CF_NO_CONTACT_RESPONSE compound body (bodyB) and I am getting collision ended events when moving bodyA inside of bodyB. It's not even near the edges of bodyB.

In order to get useful information to the event, I modified this a tiny bit by passing btCollisionObjectWrappers when the contact point is added. Those wrappers have the fields "m_parent" and "m_index" which are EXTREMELY useful in recursively navigating a compound shape!

I thought about not using this custom callback patch and going with the normal "wiki way" (iterating over all manifolds), BUT that won't work either because there's no parent-child information being passed into to btPersistentManifold.

Any help would be greatly appreciated!

Edit: I think I might be able to fix my problem doing this collision started/ended event in the dispatcher rather than in the manifold. It looks like compound shapes remove all their contact points and then immediately re-add them during collision processing. I'm not sure why that is, but I think by checking for this event higher up (in the dispatcher), I can solve compounds going crazy with the events... or I could just be rambling at 6:00AM! :lol: Tomorrow will test!
Post Reply