Regarding BEPU algorithms used.

Discuss topics related to BEPUphysics or physics engine development.
Post Reply
olhovsky
Posts: 8
Joined: Fri Apr 15, 2011 8:42 am

Regarding BEPU algorithms used.

Post by olhovsky »

I've been reading about how physics engines work a bit, before jumping in and trying to blindly use BEPU.

I'm just curious about a few things, which I'm sure I can discover from the source, but it would be nice if you could just tell me :)

Does BEPU use Projected Gauss-Siedel? If not, then what?

Is BEPU using continuous collision detection? It looks like no. Edit: No, I see that you're using raycasts instead.

If it's not using CCD, then is there a name for the method being used to resolve penetration and collisions? Is it impulse based?

It looks like BEPU is using MPR like in GPG7's XenoCollide article to detect collision of convex objects -- is that true? (I saw the MPR code in their somewhere but I didn't determine if that's primarily what's used.) If so, then are there plans to add special collision detection cases like sphere-sphere? If not that's fine, but maybe it's worth my time to build a special case for that, if I know that my game will primarily have spheres colliding?

Are you just using Euler integration? Or something fancier?

Feel free to mention any other theories/algorithms used, I'm curious to go read about them.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Regarding BEPU algorithms used.

Post by Norbo »

Does BEPU use Projected Gauss-Siedel? If not, then what?
No, but it does use Sequential Impulses. They are different forms of an equivalent process. Here's a thread that discusses the equivalence and its origin, amongst other things: http://www.bulletphysics.org/Bullet/php ... f=22&t=208
Is BEPU using continuous collision detection? It looks like no. Edit: No, I see that you're using raycasts instead.
Yes, it does have continuous collision detection. Yes, it is commonly implemented as sphere casts (not raycasts) simulating the 'cores' of objects, though the process is defined on a pairwise basis so different algorithms can be used. CCD is not performed between the cores, but rather from one core to the full geometry of the other and vice versa. Older versions used full strict conservative advancement, but this has downsides when combined with motion clamping. Allowing some types of collisions to penetrate offers a much smoother simulation. I detailed the approach here: http://www.gamedev.net/topic/596865-swe ... try4787224

For a long time I've wanted to experiment with speculative contacts (which are also discussed in the previous link), since they solve some of the 'lost time' issues associated with motion clamping. There are still some issues to overcome though, such as ghost collisions versus missed collisions. Tentative plans for the future include an integration of speculative contacts with conservative advancement (to avoid ghost collisions) to handle 'first stage' collisions, and resorting to motion clamping to manage secondary collisions that the CA-pruned speculative contacts might have missed. This would also benefit from a reordering of the internal update processes to ensure the correct velocity expansion of bounding boxes.
If it's not using CCD, then is there a name for the method being used to resolve penetration and collisions? Is it impulse based?
Even strict CCD cannot avoid penetration entirely without severe side effects. To resolve penetrations, simple baumgarte stabilization is used. The whole solver is impulse based and works on the velocity level. Baumgarte stabilization is just adjusting the velocity goal of a constraint according to position-level error. This does introduce energy to the simulation, but the effect tends to be smooth and intuitive.
It looks like BEPU is using MPR like in GPG7's XenoCollide article to detect collision of convex objects -- is that true?
An MPR implementation is used for deep collisions (and it's actually currently being rewritten for better quality). For shallow collisions, GJK closest points queries are used. For separated objects, a fast ISA-GJK implementation is used. Each pair acts like a state machine, moving from one algorithm to the other and efficiently keeping track of which option to use.
If so, then are there plans to add special collision detection cases like sphere-sphere? If not that's fine, but maybe it's worth my time to build a special case for that, if I know that my game will primarily have spheres colliding?
The engine supports special cases already. These include box-box, box-sphere, sphere-sphere, and triangle-convex. Some more may become available later (most likely for Capsules if anything).
Post Reply