Rigid Body Simulation, 2009 edition
A couple of years ago me and a couple of friends (Jonas, Nypan and Henke) developed a rigid body simulator as a course project. I’ve considered it the project I’m most proud of so far, only now perhaps superseded by GAV Flash and OECD eXplorer (and winning the MT-Awards with Linnaeus made me proud of that too, of course).
Back then, we had a lot of trouble with collision detection and its performance. I’ve since then felt that I’ve matured quite a bit as a programmer and also picked up a thing or two about collision detection. So last weekend I decided to try and implement another rigid body simulator to see what I would do different and what performance I could achieve.
Last time we only used AABBs and then tested triangles against vertices and edges against edges for each triangle. What I did different this time around:
- Sweep-and-prune AABBs (very effective)
- A triangle-triangle query, either based on separating axis theorem or Tomas Möller's algorithm
- On intersecting triangles A & B, test points from A against surface of B, then vice versa
- Test edges only if triangle query positive but no other collisions found in step 3.
I got the system into a semi-working state quite quickly, but just like last time I’m having some problems with collision detection. But even though I haven't done any optimizations I have a lot better performance than the old project. Now I’ve started to use some interactive visualizations to debug the collision detection issues and will post about that again later. Btw, I think the use of visualizations in software debugging and profiling is a very interesting subject.
In the screen shot below (yes, the colorless one with the lame lighting), 60 bodies are simulated at approximately 90 fps.
The (convex) bodies are randomly generated using a simple scheme; a couple of vertices are placed at random positions on a circle, in addition to two vertices placed on each side of the circle, right above/below the center. Each triangle is made up of two vertices from the circle and one of the other points:
Comments
No comments so far. You leave the first:
© 2008 Markus Johnsson