The GDC sessions have finally been announced, and I’m pretty excited about the tutorial this year. Instead of doing the usual 2-3 people talking about a variety of subjects, some of which is not their specialty, this year we have 6 people with a broad range of experience. This should allow us to have deeper coverage and present an overall better tutorial.
Here are the speakers, with their current proposed topics:
Jim Van Verth: Physics Engine Overview
Christer Ericson: Numerical Robustness
Squirrel Eiserloh: Relative Motion and Collision
Gino van den Bergen: Narrow (GJK) and Broad (Sweep and Prune) Phase Collision
Erin Catto: Constraints and Solvers
Marq Singer: Dynamic Destruction
The full session description can be found on the GDC 2006 site. Hope to see some of you there!
One of the questions asked during the tutorial was whether matrices or quaternions were more efficient for angular rigid body dynamics. My response was that a matrix would be more efficient, because a quaternion requires a conversion to a matrix to compute the transformed inertial tensor matrix. If we analyze the operation count, this certainly appears to be true:
(more…)
Having promised to post about center-of-mass calculations, and subsequently having put it off for a week, I’m going to punt.
First, you can read the seminal Brian Mirtich paper on the subject. Then Dave Eberly responds with a more efficient method. Both rely computing solid integrals across a polytope of constant density by treating them as surface integrals across the polytope’s faces. In the end they end up with total mass (assuming a density of 1), center of mass, and the inertial tensor matrix for the polytope.
If those haven’t scared you off, Jonathan Blow has a more intuitive approach, noting that the solid integral is basically a volume calculation. By breaking the object into tetrahedrons, we can compute the total solid integral as a weighted sum of tetrahedral solid integrals. The tetrahedrons can be computed by selecting a single point — the origin or the centroid will work — and using that point together with the points on each triangular face. As he notes, it’s likely that the Eberly and Mirtich approaches are more efficient, but not as easy to understand from a geometric standpoint. Blow doesn’t provide an implementation, but you can grab a similar one from Stan Melax here.
Finally, Erin Catto pointed out to me after the tutorial that you can compute the center of mass by computing the centroids of the tetrahedrons and then performing a weighted sum of all the centroids, where the weight is the volume of a particular centroid’s tetrahedron divided by the total volume of the polytope. Blow also covers this in his paper as well. To get an intuitive sense of this, I recommend messing around with some origin-centered triangles (e.g. (1,0),(-.5,-.5),(0,-.5),(.5,-.5)) and using areas instead of volumes.
Due to sickness and unexpected work, I haven’t had a chance to do some of the updates I’d planned. I’m working on a write-up about computing center of mass, since I botched that badly during the presentation. I still need to do a little more research to make sure I got it right, though. The Mirtich and Eberly presentations are mostly formula manipulation, and not intuitive from the geometric standpoint.
Until then, here’s an article by Joe van den Heuvel and
Miles Jackson regarding sphere collision: Pool Hall Lessons. Someone recommended it as an alternative method for dynamic sphere-sphere collision. Looking at it, it appears that it might be faster than the one I came up with; certainly so in the average case, as it culls out obvious misses early. But again, I haven’t had a chance to do an in-depth analysis of it.
The Win32 sample code has been updated to match what was shown at GDC. The ZIP file also includes the old Mac base code because someone (didn’t catch your name, sorry) expressed an interest in porting it. If you’ve downloaded the code previously, it includes three new examples: an integration methods demo which shows the effect of using three different integration techniques with a spring force; a resting contact demo using impulses to resolve the collision; a resting contact demo which uses contact forces to resolve the collision. For the last two, I have commented out the code which slows it down to 10 fps, so it should look fairly smooth in both cases. If you want to uncomment it, it’s in Game::Update().
For those who picked up the book, there are two code demos in the Chapter 11 folder that are also apropos. The first shows the bounding hierarchy for a simple submarine model. The second shows a one-dimensional example of the use of sweep and prune.
Just finished rewriting the basic collision response demo to make use of a new dynamic collision model. Originally it determined whether collision is occurring in the current frame, pushed the objects apart, and then reset the velocities for the next frame. Now it determines whether a collision will occur interframe, advances to that timestep and computes the collision response, and then continues movement for the remainder of the frame. Took a bit to deal with the vagaries of floating point, but it appears to work. I’ll write up a bit more detail on this tomorrow; it’s late.
Tomorrow I work on slides and explore the world of resting forces. Also known as “fun with LCP.”