Torque 2D: Informal technical overview - discussion on real-time rigid-body dynamics simulation and Torque 2D.
This discussion offers a simplistic overview of the common algorithms used in real-time rigid-body dynamics simulations, and relates them to the physics system in Torque 2D. This information is part of a .plan file created during the development of Torque 2D.
Introduction:
The point of this section isn’t to teach everything there is to know about real-time rigid body dynamics simulations (though you should walk away with a pretty good feel for it!). Much as I love thinking and talking about systems like this, there just isn’t room in this .plan, so the point of this section is to provide a context for understanding T2D’s rigid body simulation. I’ll try my best to offer a decent overview of some of the major techniques game-oriented rigid body physics simulators use, and to place T2D’s simulation in the context of these techniques, and other game physics sims.
Okay, first up, let’s talk about what the term “rigid body dynamics” means. It isn’t the friendliest-sounding term, but don’t let it put you off. While there is a *lot* of hard work involved in creating an accurate, robust, stable numerical simulation of rigid-body physics in real-time, the actual physics involved are simple.
Rigid-body simulations use a simplified representation of Newtonian physics. Yes, the same stuff most people learn about in high-school. I took high-school physics, and like most guys that age, easily 99% of my brain power was fixated exclusively on one of two things: videogames and girls (don’t ask which received the majority… it’s sad). That left only 1% brain power with which to understand Newtonian physics, deal with the daily ins-and-outs of life, and handle other classes. I’m pretty sure most high-schoolers are in a similar boat when they take physics, yet millions of ‘em around the world get a grip on this science every year. As such, you know the physics theory involved here isn’t too tough.
What is tougher to grasp is how modern real-time physics engines handle their dynamics simulations. Let’s take a look at some of the best and most popular approaches. If you aren’t already familiar with this area of research, it’ll help you more fully understand how T2D’s physics work.
First-up, what is a “rigid body”? To modern physics engines, the “rigid” part means that objects do not deform at all-- they are infinitely hard. A simple definition of this concept is that in a rigid body, any two points within the body are always the same distance from each other, no matter what forces are applied. Of course, no real-world objects are perfectly rigid, they all deform in some way. This assumption of perfect rigidity is a simplification, reducing the complexity (both conceptually and computationally) of the math involved, and making the simulation much easier to perform in real-time.
So, rigid-body dynamics (“RBD” from now on) engines simulate, with various degrees of complexity and fidelity, the behavior of physically-modeled systems of rigid-bodies. Simply put, the goal is to try to make objects move and interact realistically. Eg… when two bouncy balls run into each other, they should bounce off each other at believable angles and speeds.
How is this goal of realistic movement and interaction achieved? There are many, many methods, and this is an active area of research and development in both academia and private practice. But at this point, a nice body of public knowledge exists in the field, and I’ll attempt a brief overview of some of the known techniques here. I’ll try to relate these techniques to games, popular physics engines, and T2D in particular.
Methods of RBD simulation:
Realistic RBD sims define sub-systems for three things:
-Collision detection is discussed in some detail in one of the asides above. There are several well-known CD algorithms, and most game-oriented physics engines rely on fast implementations of the common convex polyhedra collision schemes (see the aside on these schemes). Some engines have even more support; for example, Havok can support concave rigid body collisions. Torque 2D is similar to other physics engines in that it supports very accurate convex polygonal collision (though T2D goes a step further than most and does full collision sweeping… but we’re in 2D so it’s hard to brag too much ;). As stated previously, there is lots of interesting research both on concave polygonal collision techniques and non-polygonal / non-primitive collision, and we’ll see if T2D leverages (or contributes to!) any of the work in this field in the future.
-Motion constraint is another well-understood area of RBD. A “motion constraint” is exactly what it sounds like-- a specified restriction on the movement of rigid bodies which the simulation attempts to enforce. The most common motion constraint in RBDs is that objects should not be allowed to penetrate each other. Other constraints are common as well-- most RBD systems impose friction constraints, for example. For an RBD to be considered very robust and accurate, it must model frictional forces in some way. The friction models used in RBD sims vary, and some engines (such as Havok, Karma, and ODE) allow the user to select amongst different friction models. Torque 2D has a good friction model, so it passes the bar there.
-Contact handling systems take contact points generated in the collision detection system, and attempt to generate a response based on the physics model and motion constraints applied to the RBD system. This generally involves calculating and applying appropriate forces to objects in the system in order to satisfy the system’s motion constraints at each time step. This is the real guts of an RBD sim.
-Articulated body control systems handle groups of rigid bodies which are connected via joints, often with specific constraints restricting movement about the joints. Rag doll demonstrations are common examples of simple articulated body support in an RBD engine. Most game physics engines support articulated bodies, at least in limited ways. T2D allows you to mount objects to other objects and physically act upon them, so there is some support for articulated bodies. However, we don’t have the ability to specify and adhere to most kinds of joint constraints yet, which is the hard part of these systems. So we can’t claim much articulated body support at this point. We’ll see where things go though. ;)
Those are the main sub-systems involved in RBD sims, but how do they work? People have developed a *bunch* of different algorithms for these sub-systems over the years. Again, collision detection has already been covered pretty well, and we won’t go into articulated dynamics, since T2D doesn’t have full support yet. As for addressing motion constraint and contact handling, techniques are usually categorized into three classes: penalty methods, impulse methods, and analytical methods.
Approaches for motion constraint and contact handling:
Penalty-based methods detect when object penetration occurs, and apply a corrective repellent ("penalty") force appropriate to negate the penetration. These methods essentially create very rigid springs at the contact points between objects, and use the spring force to separate the interpenetrating bodies.
Penalty-based methods are generally regarded as poor solutions for real-time RBD sims. They can be inaccurate, and very slow because a single contact can take many steps to resolve. This is because stiff spring constants must be used to create believable non-penetration behavior. The differential equations governing spring effects become very sensitive when stiff spring constants are used (which makes sense, physically), and this means it can take several very small time steps to evaluate the equations with acceptable accuracy. Partially because of this, penalty-based RBD methods degrade very poorly when dealing with many active bodies in an enforced real-time scenario. Moreover, these methods sometimes result in unrealistic behavior, such as objects bouncing against each other continually in what should be static contact scenarios.
Penalty-based techniques have other flaws, and are generally not the right solution for games. While they played an important role in the evolution of RBD simulators, and they can be useful in non-game-style sims, no real-time physics engine I know of uses penalty-based methods for contact handling and motion constraint.
Impulse methods are well-known, and are very impressive. These methods were first introduced by Mirtich in 1994 (see references below), and model all object interactions in a unified way. All object contacts are modeled as instantaneous collisions, and impulses are applied to resolve the collisions (in physics, an “impulse” is a change in momentum, as the result of an applied force).
The calculations involved with contact resolution in impulse-based techniques are simple and efficient. Yet, these methods are fully expressive, and can model realistic RBD quite well. In fact, they model many kinds of dynamics much better than other competitive techniques (see below). For example, impulse techniques can be very accurate and elegant for modeling rolling dynamics, an area which other approaches often have difficulty with.
For some time though, impulse methods suffered from problems related to minor stability. For example, many impulse-based RBD implementations are prone to experience jittering for objects which should be at rest. This is partially because of the unified manner in which contacts are treated under impulse techniques. Also, stacks of objects frequently behave very unrealistically, and object stacks can lead to very poor performance. Overall, modeling static friction (frictional resistance to coming out of rest) with impulse-based techniques is usually challenging. Recently however, new time integration, stability, and stacking-specific improvements have been added to the bag of impulse-based tricks, and these largely alleviate the problems with impulse systems.
T2D’s RBD sim uses impulse-based physics, with some specific enhancements to aid stability and dampen jittering. While it doesn’t yet take advantage of all the latest enhancements available for these systems, we’ll likely be adding some moretechniques soon. Still, the current implementation is quite stable and robust, as is explained in more detail below.
Analytical methods (also called “constraint-based methods”) differ from the preceding two approaches in a major way: analytical methods are global techniques, whereas penalty and impulse techniques are local. Local contact and constraint resolution systems only need information on the pair of contacts being presently solved at any given time. Analytical methods must consider all contact points in the system at once in each step in the simulation.
In these methods, constraints are defined formally and used in a calculus to find constraint-satisfying forces at all contact points. These forces are calculated using complex systems of equations and solvers, the exact details of which depend on the kind of algorithm being used. For example, in the most popular (for real-time sims) branch of these techniques, constraints are formally specified and Linear Complementarity Problem matrices are formed and solved for at each step in the simulation.
Since they use complex equation solvers, analytical techniques are generally considered difficult to implement. Also, since they solve contacts globally and must compute contact forces for active bodies, they are usually not performance friendly in highly dynamic situations.
There is a lot more to say about analytical methods for RBD simulation, this area represents a very large body of research work, and analytical methods have spawned many different branches of techniques. There are minimal coordinate techniques and maximal coordinate techniques; and maximal coordinate techniques can further be categorized into other groups, including positional-techniques and the complementarity techniques briefly mentioned above. Then complementarity techniques can further be split-up into acceleration-based (which formulize contacts and constraints in terms of force and acceleration) or velocity-based (which formulize contacts and constraints in terms of force and velocity) techniques. Whew!
This is all fun stuff to think about and experiment with, and you can probably tell by my rambling that I enjoy talking about this stuff. But the above high-level sketch of analytical techniques will have to remain as-is for now because T2D does not use analytical techniques in its RBD simulation, and I don’t want to distract too much from the rest of this .plan. All this information was offered simply to provide a contrasting context for T2D’s sim. (Though, if anyone is really interested in hearing more about this stuff, let me know. I’m very up-to-date with research in this area, and after T2D ships-- once I have some spare time again-- it'd be fun to do a full-on write-up in my spare time).
The majority of game physics engines use analytical complementarity techniques for their RBD simulations. Karma uses (as far as I can tell) velocity-based complementarity, while ODE uses acceleration-based. Havok uses complementarity techniques as well, and Novodex (now used in Unreal) probably does too.
These analytical algorithms require lots of optimization for use in real-time systems and are difficult to implement well, as you can probably imagine even from the brief descriptions above. However, the major physics engine developers have put in the careful work needed to optimize these techniques enough for use in games, and they can provide robust, stable simulations.
I find analytical and novel methods of RBD simulation very interesting, but for Torque 2D, they are not (in Melv and my opinions) as attractive overall as impulse-based techniques. Our impulse-based RBD sim was easy to implement (relative to most analytical techniques), yet it is very efficient, quite stable, and suitably accurate. Moreover, it is easy to extend, and incorporating some of the newer impulse technique enhancements wouldn’t be difficult. As an available-source project, this implementation has the additional benefit of being readable and simple enough for people to understand quickly.
As always though, T2D is designed for customizability, so anyone with an itch could easily replace the current physics model with their own implementation of a different approach. There’s really no need for this, but physics programming can be really fun. In fact, T2D makes an excellent test bed for attempting to implement various physics models, and I hope to see T2D used in academic or hobbyist settings for just this sort of thing!
Also, note that nothing stops you from using hybrid combinations of these techniques. Some physics engines utilize hybrid techniques, incorporating impulse-based or novel systems to optimize their RBD sim.
Okay, now we have a high-level understanding of the classes of algorithms which are applied to solve the problems of real-time RBD simulation. The next important concept to understand when learning about standard RBD sims is that of “integrators”.
Integrators:
An integrator is the portion of an RBD simulator which is responsible for stepping through time, calculating the actual dynamics at play in each step, and updating the rigid bodies accordingly.
No matter what model you use for handling conctacts and motion constraints, you’ll have some kind of integrator. There are various integration processes in common use, but any integrator can be judged on three important criteria: speed, stability, and accuracy.
An integration scheme is considered to have a baseline level of stability if it isn’t prone to exhibit totally unnatural behavior such as random explosions, due, for example, to the build-up of numerical inaccuracies. This is actually a very hard thing to achieve, as there are a number of difficult numerical / computational problems to solve in RBD integrators. Integration "Accuracy" refers to how closely the simulated behavior matches the desired behavior (the usual goal is real-world dynamics).
In general, stability and speed are the most important factors in evaluating an integrator’s fitness for use in game physics simulations. (See the closing comments at the end of this breakout for more comments to this end.)
Of course, all RBD sim integrators use some kind of numerical integration routine for the differential equations associated with their system’s physics models. There are many numerical integration algorithms, but most game-oriented RBD sims (even the big-name physics engines) use the simplest available: the Euler and Runge-Kutta routines. Most people are introduced to these routines (at least Euler’s method) in high school or early college, so I won’t go over them now. If you need to brush up, check out this or this for technical information.
T2D’s integrator uses the basic first-order forward Euler routine for its numerical integration. When dealing with complex systems like RBD sims, it is sometimes natural to assume that it’s better to use complicated algorithms everywhere than to use simpler counterparts. This is often a faulty assumption… certainly if presented with two integrators that perform equally well on speed, stability and accuracy, the integrator with the simpler algorithm or implementation would be most desirable. We chose to use simple Euler integration in T2D’s integrator routines because we didn’t need anything more complex. Our integrator and its simple Euler differential estimator are well-adapted for our purposes as it is fast, stable, and quite accurate.
I would note that ODE, Karma, Havok and other game physics engines all use first-order or Euler integrators too. ODE is of course a very popular, robust, and stable game physics engine... and it uses the first-order integration. Karma (formerly called “MathEngine”) was the physics engine used in the Unreal engine (until Karma was bought by Criterion, makers of the Renderware engine, and the relationship with Epic ended) uses Euler’s method. Havok is a popular game physics engine, used in Half-life 2 and other games, and it lets you choose different integration routines, with the basic Euler routine as the default. So, it’s not like T2D is in bad company here. :)
Moreover, the basic integration scheme in T2D is backed-up with a sub-integrator capable of intra-step discretization and iteration. Using this system, we can dynamically split up larger time-intervals (those above a configurable threshold) into smaller, more manageable chunks. These sub-intervals can be iterated up to a (configurable) maximum limit. If the sub-interval iteration limit is reached, time is lost. By default, sub-integration kicks in when operating below about 40fps. This initiates emergency stabilization, which can result in less accurate and believable dynamics (but saves all kinds of nasty potential breakdowns in the overall sim). As you can see, the simulation attempts to degrade gracefully, which is a nice feature of any real-time RBD system.
Combining the overall integration scheme and the intra-step sub-system results in a smoother, more stable simulation overall, and makes the choice of the simple Euler integrator even more appropriate.
T2D’s integration scheme is very fast, and extremely stable. The impulse-based dynamics and simple integrator do not result in the most accurate simulation, but it produces very convincing dynamics, and even when emergency stabilization kicks in, things look pretty good. Obviously, accuracy degrades as the time steps enlarge, but there isn’t a good way around that in general. Of course, T2D’s integration scheme is very fast, so getting to a degraded simulation state is hard in the first place! And as stated above, this integration scheme has the additional benefit that, as an available-source project, the code is fairly easy to read, understand, and even customize.
We will be doing a little more work on T2D’s physics and integration overall. We hope to introduce some of the newer impulse-based stability enhancements, such as sleep processing and stack layering / impulse stepping, and maybe some others. Also, we’ll be upgrading T2D’s basic ability to track time overall very soon, and this will have a nice effect on the physics simulation in and of itself. However, as it stands now, the physics system is already something to be proud of. :)
Closing:
The important thing to remember in all this talk about physics simulations is that, when it comes to games, the whole point is that your sim just needs to work well enough to satisfy the game design (ie allow fun, believable physics). A lot of people get hung-up over the accuracy (ie the approximation of real-world behaviors) of RBD and other physics sims. Accuracy, in and of itself, is a nice goal in general, and it is often a very important requirement for scientific and industrial simulations. But for game physics, all we really care about is performance and fun. As long as physics behave in a way that feels realistic (or unrealistic, but fun) to the player, you’re sim is in good shape. Besides, even the most detailed real-time collision representations still don’t do a good job of matching up with realistic shapes (the world isn’t made out of polygons). So, unless you have an amazing real-time surface-smoothing algorithm and some great concave cd scheme, fretting about creating extremely accurate physics based on collisions with these unrealistic polygonal representations of shapes is pretty silly-- no matter how accurate your dynamics sim, the results won’t match real-world behavior perfectly.
With T2D, we strove for physical accuracy, but like any good game-oriented physics sim, we tried to strike a balance between accuracy and performance. In the end, we've come out with a nicely stable simulation that's extremely performace-friendly, and is capable of simulating complex physical behavior very accurately, in all but the worst scenarios, when degrading gracefully is favored over maintaining accuracy.
This whole problem space has been vigorously researched, and in the last few years a lot of core techniques on both the impulse-based and analytical sides have been refined and enhanced. Obviously, much work remains to be done, but overall, the problem of real-time rigid-body dynamics simulations are pretty well understood and good solutions exist. Still, there’s lots of new stuff out there, and some interesting, novel techniques for dealing with these simulations have been coming out. Of course, Melv and I will be keeping our eyes on this stuff closely. We are both well-qualified to tackle physics code-- both of us have lots of experience with numerical simulations (me in finance, Melv in image processing), we’re both very interested in simulated physics (RBD and beyond!), and we read lots of this research. Of course, T2D’s physics system already rocks, and as you can tell from the above, it’s pretty high-tech. We’ll be adding some niceties as we go, but the core system is great and we don’t need to add a whole lot more to it. I’m REALLY happy with the core that we have, and I hope you can see why. :)
References:
*The most important references for the development of all this stuff are listed in the T2D source code:
http://www.d6.com/users/checker/pdfs/gdmphys3.pdf
http://www.d6.com/users/checker/dynamics.htm
http://www-2.cs.cmu.edu/afs/cs.cmu.edu/user/baraff/www/sigcourse/index.html
http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf
http://www.cs.berkeley.edu/~jfc/papers/94/ibds94.pdf
http://www.rowlhouse.co.uk/jiglib/
http://www.cs.unc.edu/~ehmann/RigidTutorial/
http://www.gdconf.com/archives/2004/baltman_rick.pdf
http://www.gamasutra.com/features/19991018/Gomez_1.htm
http://www.gamasutra.com/features/19990702/data_structures_01.htm
http://carini.physics.indiana.edu/E105/cor.html
http://www.roymech.co.uk/Useful_Tables/Tribology/co_of_frict.htm#coef
For interested readers, I’d add a few other references:
http://www.cs.rpi.edu/~trink/Papers/STicra.pdf
http://www-2.cs.cmu.edu/~baraff/papers/sig96.pdf
http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml
And special thanks from both Melv and I to Olivier Renault, for his friendly help in the development of T2D’s physics system, and for letting us adapt some of his code. Thanks Olivier!
-Josh Williams
GarageGames
Return to the T2D informal technical overview .plan