To give some context, this is only part one in a series of blog posts I plan on writing about rigid body physics.
The post is aimed at people like myself, who aren't game devs and don't necessarily have a strong math background. Which is why I spend so much time explaining concepts that would appear almost trivial to someone who has experience in this area.
Making a 2d rigid-body physics engine is a really fun project. I made one myself in javascript before learning about linear algebra. And I dug deep into the maths to get it working. Despite months of work, I barely scratched the surface beyond the widely known basics.
Making a stable engine where objects don't compress into one another or jitter is a rabbit hole without a bottom that even the most math-heavy articles I could find rarely touched.
Sounds intriguing! I’m probably your ideal audience, given a large coding background, low math background, and current writing 2D focused games.
If I may ask a question, in your mind what’s the benefit of more deeply understanding these implementations when physics frameworks handle a lot of the really mathy logic behind collisions and simulations.
Either way I’m putting this in my read queue. Thanks!
Very cool! Game rigid body engines (to my knowledge) usually use symplectic Euler (v^{n+1} = v^n + h M^{-1} F^n, q^{n+1} = q^n + h v^n) with a Moreau/Stewart-Trinkle velocity level discretization of non-penetration constraint (effectively impulses), usually lobbing off the quadratic velocity term (so no precession). These constraints are typically solved in a (projected) Gauss-Seidel fashion to horribly loose tolerances, with liberal post-stabilization thrown in. Outside of rigid bodies, for the most part in games, these days, you don't get 'simulations' that can be derived from a variational principle, but that are instead constraint satisfaction problems with some notion of momentum hacked in the side (see 'Position Based Dynamics', 'Shape Matching').
The movie folks have larger compute time budgets, and I've seen various geometric integrators used there. I know of at least one studio that uses implicit midpoint for thin shell simulation. The Cal-Tech influence has wormed its way into the graphics research world, at least, and you see some papers pop up there frequently looking at geometric integrators. This Danish guy (I'm forgetting his name) at Disney publishes papers every now and then on the topic.
I'm curious whether you've considered using Box2D[1] as a reference, since it is a pretty complete implementation of rigid body physics? Or is it more that you want to re-implement things from scratch as part of this tutorial?
Dr. Rao’s systematic approach to solving dynamics problems is consistent and concise. He also has a companion set of lecture notes on YouTube. I remember it as one of the most challenging but rewarding aspects of my engineering school experience. All the principles are described mathematically in a coordinate-free manner. You’ll learn to set up equations of rigid bodies and constraints without all the guesswork and haphazard construction of coordinates typically encountered in a physics textbook.
> Most other engines (PhysX and Havok) are to the best of my knowledge using something very similar.
PhysX is position based dynamics. The Mueller guy who wrote that paper was a Co-founder of PhysX (back when it was NovodeX, then purchased by Ageia, then purchased by Nvidia) and is now a lead researcher at Nvidia. [1]
> The common method in open source engines is a projected gauss Seidel [0] which is used in bullet physics.
PGS is just the numerical method that Bullet uses to solve for the collision impulses between the rigid bodies (there are tons of other possible methods, Nvidia again had a cool paper a few years back, there are also global approaches with better convergence, etc). This is solving a so-called 'Contact Dynamics' contact model [2], which originates in the work of French mechanicians in the 70s and 80s.
Actually, if op is interested in PDEs in games, check out 'Digital Molecular Matter' [3]. It was used in some Star Wars games, iirc. It is a pretty straightforward Lagrangian discretization (linear shape functions on tets) of a linearized hyperelastic energy density. They added a simple fracture model on top which allowed for cool destruction effects in games.
I'm interested in this but I have no idea what you are talking about. What does "numerically" mean and how does it allow one to implement rigid body physics in a "much easier way" than using the known formulae?
Indeed, and physics engines in games often have to deal with capsules, convex hulls and per-poly collision as well, not just spheres, planes and boxes.
Not to discount the effort involved here though; it's pretty impressive, I know I couldn't write this without a lot of mental effort.
Nice. I played with a similar thing years ago: rigid bodies connected with various constraints. The simple solving for the acceleration of the point masses under the forces from the connections that this computation seems to do works fine as long as the cloth is elastic. If you try to compute the dynamics of points connected by rigid rods, the large forces makes the system really stiff and your integration time step drops precipitously. In that case you have to generate a large linear system of equations and solve for the global motion of the system. It's quite a bit trickier. It's also interesting how situations that are familiar from real life, like a drawer getting stuck diagonally in the slot, really are singularities in the equations.
Most games since Half Life 2 use constraint forces like this to solve collisions. Springs/penalty forces are still used sometimes in commercial physics solvers since they're easier to couple with other simulations, but they require many small timesteps to ensure convergence.
With the right algebra (PGA2D which adds an additional dimension whose unit vector squares to 0), rigid body physics simulation with collision detection/response can be implemented in < 50 lines of Javascript: https://bivector.net/PGADYN.html
Basically in PGA2D, rotations, angular velocity/acceleration, torque etc automatically get handled by geometric product of multivectors. The additional dimension makes all rotations centered at origin, which makes them compose much more nicely.
A new way of doing real time physics that dramatically outperforms state of the art by simply introducing a new algorithm. No crazy AI or incremental improvements to existing approaches.
My comment directed people to a paper that explains the underlying maths behind this well established game physics algorithm. This is much more useful than looking at an implementation of the same thing in my mind.
Totally rigid body physics is reasonably well solved by now. It suffers from the "boink" problem; in impulse-constraint systems, there are instantaneous changes in velocity on collisions. This looks OK for small objects and terrible for large ones. This is the main reason game simulations usually look wrong.
If you make everything soft, that works OK. But everything looks like Jell-O, as some early Pixar devs wrote. That's a soft-body system.
What's hard is doing things which have just a little elasticity. Which is most real-world materials. That's because you have to simulate what's happening on very short time scales, much shorter than a visual frame time. This is possible, but the compute load suddenly jumps by orders of magnitude during some collisions. That's hard for real-time systems. Also, you start to need double precision. If you don't need real time, as for film work, it's not too bad. Integration of stiff systems of differential equations is Not Fun. I used to do that stuff.
Hey! Congrats on the launch, the touted performance increases are mind blowing.
I think physics engines are difficult for a few reasons:
- They don't mesh with a lot of features that modelers take for granted (non-uniform scaling, concave meshes, lax model scaling)
- It's hard know intuitively what values to use for things like acceleration, density, velocity, damping, friction. Especially because they are very inter-dependent.
- Interaction with moving kinematic or non-physics objects is an undefined behavior that has to be tested pretty rigorously.
- In gamedev, rigidbody physics are basically a trojan horse for gameplay bugs like clipping through the map and sudden bursts of high speeds (Which is both magical and frustrating). It's a non-trivial task to sandbox those behaviors completely.
- Projectiles. There's no catch-all solution for small fast-moving objects, it's always a tradeoff. But that's mostly because big O dictates it to be so.
Most games aren’t using anything remotely near as sophisticated as that. Most games use rigid body simulations, and while the details of each implementation is different, most of them work in a similar way. The common method in open source engines is a projected gauss Seidel [0] which is used in bullet physics. Most other engines (PhysX and Havok) are to the best of my knowledge using something very similar.
To give some context, this is only part one in a series of blog posts I plan on writing about rigid body physics.
The post is aimed at people like myself, who aren't game devs and don't necessarily have a strong math background. Which is why I spend so much time explaining concepts that would appear almost trivial to someone who has experience in this area.
Happy to answer any questions you might have.
reply