An Annotated Bibliography for Rigid Body Dynamics
Originally Presented at the 1997 Computer Game Developer's Conference.
todo: lots more work to do on this page
This paper and its accompanying lecture are not going to be able to teach you rigid body dynamics--not even close. The subject is huge, so the idea that a one-hour lecture and a 3,000-word paper can explain dynamics in any depth is just ludicrous. However, it is possible to provide a roadmap for the subject in the allotted time and space. This roadmap will help you avoid spending time figuring out what to teach yourself, and let you get on with actually learning the stuff.
This paper is organized as a heavily-annotated bibliography that's roughly sorted by the order I'd recommend reading the books, rather than the more traditional alphabetical sort by the author's name. It's in the order I'd read the books if I could start learning dynamics all over again. I've also put in "milestones" to give you some feedback on what you should be able to implement at certain points in your learning.
The way different people learn a complex subject like dynamics is an interesting topic by itself, and I don't think any two people do it the same way. I know I learn in what my friend Casey calls a "depth-first" manner--if I come across a sentence or equation I don't understand, I'll pound on it and read other books about that single topic until I understand it, and then move on. Casey, by contrast, learns in a "breadth-first" manner. He tries to get the big picture first, and will read through an entire article, even if there's stuff in it he doesn't understand. Then he goes back to fill in the holes as he works with the material. I think more people learn breadth-first, so I'm organizing the bibliography to suit that style, but don't worry, there's more than enough depth herein for us depth-first-ers.
A Few Notes
I'm going to use the terms physics, dynamics, and mechanics interchangeably here. They all refer to rigid-body dynamics except where noted.
You don't have to read every page of every book here, or read each book sequentially. There will be a lot of redundant material between all the books, and this is a good thing. I find it much easier to understand a concept when I've got multiple different descriptions of it available to me.
Get in the habit of spending time at bookstores before you make a technical book purchase. Read through sections of the books to see if it resonates with you, and look for coverage of specific materials in which you're interested. Don't forget the inexpensive Dover books and used bookstores!
Finally, the internet is your single biggest resource for technical information and papers, so the very first references I'll give are these:
[META] http://www.metacrawler.com
[ALTA] http://www.altavista.digital.com
[DEJA] http://www.dejanews.com
Metacrawler is a search engine which uses all the other search engines on the net to find information. This is good because it's complete, but you don't have as much control over your query as you do with Altavista. Dejanews searches Usenet news (be warned, it defaults to only searching the past couple months rather than the entire archive). Getting good at searching the net will do more for your technical education than any single book could ever do.
Basic Physics and Math
The first thing you need to do is get comfortable with the concepts and quantities of kinematics and dynamics, like position, velocity, acceleration, force, mass, torque, and the like. The first 20 chapters of the following book are a great introduction to the world of classical physics and will do nicely for this task:
[FEYN] The Feynman Lectures On Physics, Volume 1, Feynman, Leighton, and Sands, Addison Wesley
Feynman is a genius at explaining concepts intuitively and with understandable examples. It's not a very rigorous book for those of you who like proofs, but we'll get plenty of those in later books.
At the same time you're reading [FEYN], you should probably start reading my series in Game Developer Magazine:
[HECK] "Physics, Parts 1-3," Oct/Nov96, Dec/Jan97, Feb/Mar97, Game Developer Magazine, Hecker
These will go into a bit more practical detail than [FEYN], but I assume you're already comfortable with some of the concepts. At the time of the CGDC, the series will have covered everything you'll need (except for collision detection, mentioned below) to do a 2D rigid body simulator with proper angular effects from forces, torques, and collisions.
If the scalar and vector differential calculus in these articles is unfamiliar, I recommend my favorite calculus book:
[THOM] Calculus and Analytic Geometry, Thomas and Finney, Addison Wesley
In fact, even if you're comfortable with the math, I recommend this book. I have two [used] copies: one for the office and one for home. It's a great reference.
Milestone: You have a 2D rigid body simulator that handles forces, like springs and gravity, and correctly computes angular effects from those forces and from collisions. If you've got this working, take heart in the fact that your simulator is better than just about every other game's physics simulator at the time of this writing.
More Advanced Dynamics and Math
The programming difference between 2D and 3D is relatively small, and once you've got a good 2D simulator running you can modify it for 3D fairly easily. However, to do it right and really understand what you're doing, you'll need to learn more kinematics, dynamics, and math. While you're at it, you should tighten up your dynamics knowledge and get more rigorous. The next article in my Game Developer Magazine physics series will be about 3D, but while you're waiting for it to show up, your first step is to read a college-level classical mechanics text:
[SYMO] Mechanics, Second Edition, Symon, Addison Wesley
[GOLD] Classical Mechanics, Second Edition, Goldstein, Addison Wesley
[ARN1] Mathematical Methods of Classical Mechanics, Arnold, Springer Verlag
These books are listed in the order of difficulty and rigor. Symon is an undergraduate text, Goldstein is the classic graduate text, and Arnold is another graduate text, but it's more mathematically abstract than Goldstein. If you're only going to buy one of these, I recommend Goldstein for its completeness. His chapters on kinematics and 3D orientation representations are great. Be warned though, Goldstein moves quickly--Symon is much friendlier. All three of these books will have a lot of chapters we don't care about right now and can skip, but it's crucial that you master the basic rigid body kinematics and dynamics. In addition, these mechanics books will start to introduce you to the concepts of constraint equations and generalized coordinates, which will be very important later on.
Most publishers will also have a set of engineering textbooks called Statics and Dynamics. These are usually undergraduate level books that introduce rigid body dynamics to engineering students. For the most part they're not as rigorous as the classical mechanics texts, but they're more approachable, and they usually have many more real-world examples and exercises. I used a Dynamics book by Shames because my office-mate happened to have it, but they all look just about identical, so I don't think it matters which you use.
At this point you should also read Andy Witkin, Dave Baraff, and Michael Kass's physically based modeling tutorial from Siggraph:
[WIT1] http://www.cs.cmu.edu/afs/cs/user/baraff/www/pbm/pbm.html
To read these mechanics books and papers, you're going to have to be very facile with vector differential calculus, the building block of almost all dynamics. [THOM] has a good introduction to vector calculus, but you're also going to need some more advanced texts:
[KAPL] Advanced Calculus, Kaplan, Addison Wesley
[WIDD] Advanced Calculus, Widder, Dover
[EDW1] Advanced Calculus of Several Variables, Edwards, Jr., Dover
[EDW2] Advanced Calculus: A Differential Forms Approach, Edwards, Birkhauser
Kaplan is my reference advanced calculus text. It's sort of like the advanced version of [THOM]--very clear and well written, with lots of examples and exercises. The Widder book is a standard--but relatively old-fashioned--advanced calculus text, and it's from Dover so it's almost free. The last two are much more modern and abstract than the first two. They're very elegant and general, but slightly more advanced.
As I mention in my physics articles, the dynamics equations we're solving at runtime in our simulator are mostly Ordinary Differential Equations (ODEs). It would behoove you to start learning the basics of these with the following books:
[RAIN] Elementary Differential Equations, Rainville and Bedient, Macmillan
[BOYC] Elementary Differential Equations with Boundary Value Problems, Boyce and DiPrima, Wiley
[ZWIL] Handbook of Differential Equations, Zwillinger, Academic Press
[ARN2] Ordinary Differential Equations, Arnold, MIT Press.
The first two are very similar, but each covers things slightly differently, so both are useful. The third is an exhaustive reference of different types of differential equations, and the fourth is by V. I. Arnold, the same author as [ARN1]. It's a very abstract and elegant text, and is therefor a little more theoretically advanced.
Milestone: You should have a 3D rigid body simulator at this point, with an appropriate orientation representation chosen by understanding and weighing the advantages and disadvantages of the different methods. You should also be very comfortable solving dynamics problems using calculus, and be familiar with the dynamic differential equations of motion.
Collision Detection
The collision detection problem is intimately coupled with the dynamics problems, but has a decidedly different, and more geometric, flavor. Unlike basic rigid body dynamics, collision detection is still an active area of research, so most of the references here are in the academic literature:
[ICOL] http://www.cs.unc.edu/~geom/I_COLLIDE.html
[OBBT] http://www.cs.unc.edu/~geom/OBB/OBBT.html
[SIGG] http://www.siggraph.org/publications/bibliography/bibliography.html
The Siggraph Bibliography Server is an important resource for all of this stuff, not just collision detection.
The one mathematical field in common between the different collision detection approaches is computational geometry. You can learn about this in the following books:
[OROU] Computational Geometry in C, O'Rourke, Cambridge
[PREP] Computational Geometry, An Introduction, Preparata and Shamos, Springer-Verlag
Preparata and Shamos is the classic text in the field, but it moves pretty fast. O'Rourke is much easier to read, but not at all as fluffy as the title sounds; O'Rourke is a respected computational geometry researcher.
Milestone: At this point you should have your simulator detecting collisions between bodies, and you should know how your collision detection method will scale with scene complexity.
Articulated Rigid Bodies
Up to this point, we have some amazing simulations going, but our object are all individual rigid bodies, without joints between them to hold them together (although the adventurous among you might have tried to use springs to build an articulated rigid body, with varying levels of success). Since we need joints to build the interesting animating objects in our game, we need to figure out how to do articulation. There are two basic approaches: constraints and generalized coordinates. You can choose either or both for your simulator. You should learn both so you can make an educated decision.
Constraints
If you choose to learn constraints, you'll first need to understand linear algebra as it relates to solving simultaneous linear equations. For a wonderful and intuitive linear algebra textbook, I recommend:
[STRA] Introduction to Linear Algebra, Strang, Wellesley-Cambridge Press
Strang is the classic undergraduate linear algebra text, and it's easy to see why. Its lucid descriptions make you see the inner structure of matrices, rather than seeing them as a bag of numbers. It is lacking when it comes to rigor, however, but this next book more than fills that gap:
[HORN] Matrix Analysis, Horn and Johnson, Cambridge
This is a hard-core linear algebra book. It's great and it covers everything, but it's not for the faint of heart. You'll learn more doing a single exercise in this book than you will reading an entire section of Strang, but that single problem will take you much longer than reading the section! I recommend both.
While you're reading up on linear algebra, you should also begin reading this book:
[SHAB] Computational Dynamics, Shabana, Wiley
Shabana is extremely readable and it has many worked examples for doing constrained dynamics. This is a must-have book if you're going to do articulated bodies with constraints. This book will show you how to generate the linear equations you'll solve with linear algebra.
Doing linear algebra on a piece of paper and doing it on a computer are two totally different things, and this book is a good introduction to the difference:
[GILL] Numerical Linear Algebra and Optimization, Volume 1, Gill, Murray, and Wright, Addison-Wesley
This book assumes you know linear algebra (at the level of [STRA], not [HORN]), but it's well written and very easy reading.
Some of these papers are also very useful when learning about constrained dynamics:
[WIT2] http://www.cs.cmu.edu/afs/cs/user/aw/www/gallery.html
[BARA] http://www.cs.cmu.edu/afs/cs/user/baraff/www/papers/
Milestone: You should be able to link two or more rigid bodies with different kinds of joints, and derive the constraint equations and the constraint Jacobian matrix. Your code should take this information and simulate the linked body, solving the linear constraint system for each articulated body to generate the right behavior.
Generalized Coordinates
When it comes time to learn generalized coordinates you should go back and read the introduction chapters on Lagrangian dynamics in [SYMO] and [GOLD]. You should also take a look at the robotics literature, including:
[CRAI] Introduction to Robotics, Mechanics, and Control, Craig, Addison Wesley
[FEAT] Robot Dynamics Algorithms, Featherstone, Kluwer Academic Publishing
[BALA] Dynamics Analysis of Robot Manipulators: A Cartesian Tensor Approach, Balafoutis and Patel, Kluwer Academic Publishing
Craig is the standard robotics text book, so it deals with robot arm dynamics and the like. Featherstone and Balafoutis and Patel are much more advanced, and are basically about optimizations on the standard robotic generalized coordinates.
A slightly odd book, that starts out easy but gets hard quickly is:
[KANE] Dynamics: Theory and Applications, Kane and Levinson, McGraw-Hill
Buy this book when you know what this quote means: "This book is a treatise on using generalized coordinates for both holonomic and nonholonomic equality constrained dynamics." It has a bunch of worked examples and answers to the exercises, which is great.
If you get really interested in the theory behind generalized coordinates and how they operate, there are a ton of books for you to read. First, the calculus of variations is used to derive the dynamic equations for generalized coordinates, and here are three good books on that topic:
[FOX] An Introduction to the Calculus of Variations, Fox, Dover
[WEIN] Calculus of Variations with Applications to Physics and Engineering, Weinstock, Dover
[LANC] The Variational Principles of Mechanics, Lanczos, Dover
Lanczos is a classic text, and all three are Dover books, so they're dirt cheap. The next step in learning generalized coordinates is analyzing the space they create (called a manifold), and that's the job of differential geometry:
[MCCL] Geometry from a Differentiable Viewpoint, McCleary, Cambridge
[HILB] Geometry and the Imagination, Hilbert and Cohn-Vossen, Chelsea
[BURK] Applied Differential Geometry, Burke, Cambridge University Press
[MISN] Gravitation, Misner, Thorne, and Wheeler, W.H. Freeman and Company
[BISH] Tensor Analysis on Manifolds, Bishop and Goldberg, Dover
[ARN1] also has lots of information on Lagrangian dynamics on manifolds. These books are pretty out-there, so only get them if you're really interested. The first two are easy reads, and Burke is amazingly well written. Gravitation is listed not because we care about relativity, but because it has incredible descriptions of differential geometry. As a side note, Gravitation has a nice chapter on quaternions, one of the possible orientation representations.
Milestone: You should at least be able to use generalized coordinates to write a Lagrangian for simple jointed bodies and simulate it with external forces. If you're highly motivated, you can implement a robotics-style recursive dynamics simulator and compare its performance with your constraint-based simulator on the same articulated body.
Contact
Contact is what happens when two objects come to rest on one another. You can also use a contact method to handle collisions in a more general way than the single-point collisions we've been using up to this point. There are three well-known types of contact solvers: penalty force methods, analytical methods, and microcollision methods. All three are research topics, so don't expect to find introductory books about them.
Penalty force methods are easy to implement, but are hard to get robust. Your dynamic differential equations can become stiff, and it's hard to keep objects from interpenetrating. Here are some references to penalty force method literature from Siggraph:
[MOOR] "Collision detection and response for computer animation," Siggraph '88, Moore and Wilhelms
[PLAT] "Constraint methods for flexible models," Siggraph '88, Platt and Barr
To handle analytical contact, you'll need to understand a bit more linear algebra, including how to solve compatible systems. [GILL] has an entire chapter about them, and it's as easy to follow as the rest of the book. David Baraff is the main person behind analytical contact at Siggraph. [BARA] has many of his papers from Siggraph available in postscript format. [FEAT] also has a chapter on analytical contact.
Finally, the microcollision method is covered in the following:
[MIRT] http://www.cs.berkeley.edu/~mirtich/impulse.html
Milestone: Regardless of which contact method you implement, at this point you should be able to drop an object on a flat surface and have it stay there without crashing the simulator. If you've implemented friction you should be able to drop it on a slightly inclined plane and it shouldn't slide down. And finally, you should make your method handle contact for your articulated bodies.
It Doesn't Work
By this point you've got an incredibly powerful simulator, but it's probably touchy and not very robust. The key to making it bullet-proof is numerical analysis. This is the study of how to do math in a computer. You should start with these books to give you an overall flavor for the subject:
[ACT1] Numerical Methods That Work, Acton, MAA Spectrum
[ACT2] Real Computing Made Real, Acton, Princeton University Press
These books give you the big picture of what's important about numerical analysis, and they're both chock full of Forman Acton's hilarious personality. For more detail and rigor on the subject, you'll need:
[GERA] Applied Numerical Analysis, Gerald and Wheatley, Addison-Wesley
[STOE] Introduction to Numerical Analysis, Stoer and Bulirsch, Springer-Verlag
[WILK] Rounding Errors in Algebraic Processes, Wilkinson, Dover
[HIGH] Accuracy and Stability of Numerical Algorithms, Higham, SIAM
[PRES] Numerical Recipes, Press, Flannery, Teukolsky, and Vetterling, Cambridge University Press
Gerald and Wheatley is a standard undergraduate text that's easy to digest, and Stoer and Bulirsch is a more technical and rigorous book. Wilkinson and Higham are both on the same subject, but Wilkinson is a classic that's about 30 years old and about one-tenth the thickness of Higham. Finally, I've found Numerical Recipes to be useful (and it's now available in PDF form for free!), but make sure you read the following URL before using it:
[JPL] http://math.jpl.nasa.gov/nr/nr.html
For more detail on numerical linear algebra, you might try:
[GOLU] Matrix Computations, Golub and Van Loan, Johns Hopkins
[DUFF] Direct Methods for Sparse Matrices, Duff, Erisman, and Reid, Oxford
Both are classics. Also, don't forget the Usenet. The sci.math.num-analysis newsgroup is a great resource for information and getting answers to questions.
Milestone: Your simulator should be rock solid and uncrashable at this point. As a bonus, it should also be fast because you're taking advantage of the structure of each kind of matrix when solving it, and reusing computed values where appropriate.
What's Left?
Well, that's a ton of material. Is there anything left to learn? By the time you've read even part of the material listed here you'll know that's an absurd question, because each new thing you read will show you four or five new things you need to learn for complete mastery of the subject. It will be a long time--if ever--before I feel like I've mastered rigid body dynamics. And then after that, there's continuum dynamics for flexible bodies!
The biggest thing I've omitted here is how to control an articulated rigid body once you've got a simulator. That is, how do you get the thing to move around realistically? This is a very active area of research in the robotics field, so look for papers on locomotion and control--you'll find a million of them.
There are also the issues of how you create physically based worlds and articulated bodies; you can't just throw polygons together and make an animation loop anymore, but at the same time you can't expect your artists to know all this material. It remains to be seen how this will shake out.
So, what are you waiting for? Buy a ream of graph paper, a case of pencils, and a bunch of these books and get started!