Sign in to follow this  
Geometrian

Constraint-Based Physics

Recommended Posts

Geometrian    1810
Hi,

I'm having a go at implementing a physics engine. I understand the force-based resolution method, but I do not understand constraint-based resolution on any practical level.

I have a sense that one sets up constraints (e.g., the box can't move through the plane, and, a second box stacked above can't move through the first, etc.). This leads to a system of equations (from Lagrange Multipliers?) that one can solve with matrix algebra (or, more practically, a sparse matrix solver).

I have no practical knowledge of how this works. I've been trying to reverse engineer some Physics libraries (ODE, mostly), but it would be really great to have some practical examples to go for--and to know if this approach is even right.

Thanks,
-G

Share this post


Link to post
Share on other sites
wildbunny    550
[quote name='Geometrian' timestamp='1306391563' post='4815929']
Hi,

I'm having a go at implementing a physics engine. I understand the force-based resolution method, but I do not understand constraint-based resolution on any practical level.

I have a sense that one sets up constraints (e.g., the box can't move through the plane, and, a second box stacked above can't move through the first, etc.). This leads to a system of equations (from Lagrange Multipliers?) that one can solve with matrix algebra (or, more practically, a sparse matrix solver).

I have no practical knowledge of how this works. I've been trying to reverse engineer some Physics libraries (ODE, mostly), but it would be really great to have some practical examples to go for--and to know if this approach is even right.

Thanks,
-G
[/quote]

If its contact constraints you're talking about, you can't use a plain matrix solver because contacts are 'inequality' constraints which must only 'push' and never pull. You *can* solve a system of pin-joints with a matrix solver, though.

For contacts you'll need to look into linear programming methods, LCP and MLCP for solving on a force/acceleration level (David Baraff is a good reference) - or you can go the impulse route and use relaxation instead which is easier in my opinion (Erin Catto is a good reference there)...

Hope that helps,

Cheers, Paul.


Share this post


Link to post
Share on other sites
Geometrian    1810
[quote name='wildbunny' timestamp='1306399245' post='4815951']For contacts you'll need to look into linear programming methods, LCP and MLCP for solving on a force/acceleration level (David Baraff is a good reference) - or you can go the impulse route and use relaxation instead which is easier in my opinion (Erin Catto is a good reference there)...[/quote]After searching some more, I found your website on the topic ([url="http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/"]http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/[/url]). It gives a very nice explanation, and I followed you through the whole article. I found some stuff on cmu.edu that was helpful and to the same effect. However, that place where you say:[quote]In addition to the velocity part, there will also be some positional fix-up to do, since with more than one constraint acting in the system simultaneously it will often fail to be resolved with one one solver iteration.[/quote]That's the key part--and where I'm vaguely seeing the application of a matrix solver--to solve in one "step".

I guess what I'm looking for is an extremely simple example from somewhere. My current goal is to get a cube to fall onto a floor realistically and build up from there. In the case where the cube is resting on the floor, there are four simultaneous constraints. If I stack another cube on top of the first, then obviously problems will start to occur if I solve for restoring impulses individually.

Thanks!
Ian

Share this post


Link to post
Share on other sites
wildbunny    550
[quote name='Geometrian' timestamp='1306735125' post='4817399']
[quote name='wildbunny' timestamp='1306399245' post='4815951']For contacts you'll need to look into linear programming methods, LCP and MLCP for solving on a force/acceleration level (David Baraff is a good reference) - or you can go the impulse route and use relaxation instead which is easier in my opinion (Erin Catto is a good reference there)...[/quote]After searching some more, I found your website on the topic ([url="http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/"]http://www.wildbunny...es-for-dummies/[/url]). It gives a very nice explanation, and I followed you through the whole article. I found some stuff on cmu.edu that was helpful and to the same effect. However, that place where you say:[quote]In addition to the velocity part, there will also be some positional fix-up to do, since with more than one constraint acting in the system simultaneously it will often fail to be resolved with one one solver iteration.[/quote]That's the key part--and where I'm vaguely seeing the application of a matrix solver--to solve in one "step".

I guess what I'm looking for is an extremely simple example from somewhere. My current goal is to get a cube to fall onto a floor realistically and build up from there. In the case where the cube is resting on the floor, there are four simultaneous constraints. If I stack another cube on top of the first, then obviously problems will start to occur if I solve for restoring impulses individually.

Thanks!
Ian
[/quote]


Even with a matrix solver there will still be some drift to account for. I'm afraid I don't know of any simple examples of using a MLCP for solving simultaneous contact; you can download the source to ODE and take a look at that - I think there is an MLCP solver in there.

Cheers, Paul.

Share this post


Link to post
Share on other sites
IMHO, the simplest example if Erin Catto's box2d lite
http://code.google.com/p/box2d/downloads/detail?name=Box2D_Lite.zip&can=2&q=

It was a good start point for me.
Plus as wildbunny noticed Erin Catto's papers and presentations are really good for understanding the mathematical background.

Share this post


Link to post
Share on other sites
Geometrian    1810
[quote]Even with a matrix solver there will still be some drift to account for. I'm afraid I don't know of any simple examples of using a MLCP for solving simultaneous contact; you can download the source to ODE and take a look at that - I think there is an MLCP solver in there.[/quote]I was unable to find the solver in ODE.[quote]IMHO, the simplest example if Erin Catto's box2d lite[/quote]I don't think that uses a matrix solver. Perhaps I'm not looking in the right place. I may just start out with an iterative solver and work from there until everything is working. It seems either a physics engine is very large and complicated, and uses a matrix solver, or it doesn't have one.
Thanks,
-G

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this