Static collision test speed problem with convex -> concave

Post Reply
User avatar
Dragonlord
Posts: 198
Joined: Mon Sep 04, 2006 5:31 pm
Location: Switzerland
Contact:

Static collision test speed problem with convex -> concave

Post by Dragonlord »

I'm trying to replace all possible self-made collision testing with bullet ones to gain some speed and better coverage of collision shapes.

For btCollisionWorld::sweepTest this worked (albeit I did not get any speed increase... which is either speaks for my code of against bullet code).

But with btCollisionWorld::contactTest I ran into a huge brick wall. In the test case I use my code tests a large concave box (a user rect-selection in the editor) against convex/concave in roughly 2-3ms. Switching over to bullet though it takes more than 500ms (sometimes up to over 1s).

Looking closer I noticed that the collision algorithms try to create tons of contact points although I'm just interested in a plain "is hit at all" query while doing higher logic filtering on the results to deliver what the user expects. But as soon as bullet seems to come across a tri-mesh speed turns sour. In the editor tri-meshes are common in contrary to later game usage where it's the opposite.

So the main question is how can you do in bullet a simple "is A overlapping B anyhow?" instead of "give me all contact points of A with B" ?
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Static collision test speed problem with convex -> conca

Post by Basroil »

Dragonlord wrote: So the main question is how can you do in bullet a simple "is A overlapping B anyhow?" instead of "give me all contact points of A with B" ?
You can test "is A probably overlapping B?" using broadphase, which should do away with speed differences between types, but very poor accuracy for low density meshes.
User avatar
Dragonlord
Posts: 198
Joined: Mon Sep 04, 2006 5:31 pm
Location: Switzerland
Contact:

Re: Static collision test speed problem with convex -> conca

Post by Dragonlord »

Basroil wrote:
Dragonlord wrote: So the main question is how can you do in bullet a simple "is A overlapping B anyhow?" instead of "give me all contact points of A with B" ?
You can test "is A probably overlapping B?" using broadphase, which should do away with speed differences between types, but very poor accuracy for low density meshes.
That's not working for AI collision detection. You need there to figure out if A overlaps B. But for this test you need only an early-exit test. No need to calculate all contact points since if you found one you are already golden.
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Static collision test speed problem with convex -> conca

Post by Basroil »

Dragonlord wrote:That's not working for AI collision detection. You need there to figure out if A overlaps B. But for this test you need only an early-exit test. No need to calculate all contact points since if you found one you are already golden.
Sounds like you'll need to make a function for that yourself, shouldn't be as difficult as starting from scratch though, the available manifold code should be a good starting point.
User avatar
Dragonlord
Posts: 198
Joined: Mon Sep 04, 2006 5:31 pm
Location: Switzerland
Contact:

Re: Static collision test speed problem with convex -> conca

Post by Dragonlord »

With that I see though a problem. If you dig around in the code base and Edwin makes an update it's hell to get things back working again. Having to mess with a code base like that is bad for dynamic upgrade path.
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Static collision test speed problem with convex -> conca

Post by Basroil »

Dragonlord wrote:With that I see though a problem. If you dig around in the code base and Edwin makes an update it's hell to get things back working again. Having to mess with a code base like that is bad for dynamic upgrade path.
Collision detection code just got revamped and more independent from the code. If you wait a bit it might be just what you need.
Also, you don't need to upgrade after you pick a build, at least not without seriously considering pros and cons. You can always try to apply patches that improve what you want from the main branch and avoid messing with your modifications (though sometimes things make big changes, especially now with 3.X around the corner)
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Static collision test speed problem with convex -> conca

Post by drleviathan »

Well, you wouldn't actually modify the Bullet codebase per se. You would derive new classes from Bullet bases and modify and maintain them as part of your application. The basic Bullet API isn't going to change super fast.

Lots and lots of contact points when colliding concave objects is a problem in other physics engines. Havok-1.8 suffered from this and could take several seconds to large portions of an hour to process all contact points. By Havok-4 they had sorta fixed it limiting the number of contact points between two objects to 256 -- if a collision between two objects required more points then the truncation would cause them to fall through each other and snag in non-physical ways. Dunno if Havok has solved it better now.

One option might be to avoid complex concave shapes -- perform convex decomposition of your concave things.
Post Reply