A new speedy way to simulate collisions of objects
The computer graphics community is always interested in faster methods to generate images. This is why Pixar and several other organizations are funding the research of a Carnegie Mellon University (CMU) computer scientist who has developed a new method to simulate collisions of objects, according to the Pittsburgh Post-Gazette. This method, named Bounded Deformation Tree, or BD-Tree, uses a bounding sphere hierarchy for output-sensitive collision detection. And this method is a thousand times faster than previous ones. As an example, the BD-Tree was used to simulate collisions between more than 3,600 falling chairs in a few hours instead a couple of months with current techniques. This method could be used for applications in computer-generated animation and video games, but also for surgical simulations or drug design.
This new method is based on the work of Doug L. James, an assistant professor of computer science and robotics at CMU, and his colleagues. And James recently was named by Popular Science as one of its 'Brilliant 10' list of innovative young researchers (check this page and this CMU news release for more details).
Now, it's time for some quotes from the Pittsburgh Post-Gazette, which has the merit of explaining the basics of this computer graphics problem in plain English.
In a computer, the shape of an object is typically represented by tens of thousands of tiny triangles. In conventional programs, when an object collides with something, the shape of each triangle is recomputed, based on physical principles.
That requires a massive amount of computing, which means many such graphics programs run very, very slowly. To speed things up, Dr. James said, "you need to be able to cheat in some way."
An this is what he did, by eliminating the triangles which were far off the collision and by replacing the objects by spheres.
"In most cases, things don't touch each other all over their surfaces," he explained. So, using what he calls "bounded deformation trees," the computer does detailed computations only for those triangles that are touching. That reduces the amount of computing drastically and thus speeds up the entire process.
Below are two images describing the output-sensitive deformable collision processing (Credit: CMU). On the top, you can see 12 chairs crashing to the ground. And below that is an image of updated spheres replacing the chairs and illustrating the extent of sphere tree traversal.
For more details, here is a link to the BD-Tree project, and here is a short overview.
The Bounded Deformation Tree, or BD-Tree, can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear superpositions of arbitary displacement fields, and are used in a variety of applications of interactive computer graphics.
The BD-Tree is a bounding sphere hierarchy for output-sensitive collision detection with such models. Its bounding spheres can be updated after deformation in any order, and at a cost independent of the geometric complexity of the model; in fact the cost can be as low as one multiplication and addition per tested sphere, and at most linear in the number reduced deformation coordinates.
Now, it's time to have some fun and look at an image of the 3,601 chairs falling off a computer screen (Credit: CMU).
The image above is the last frame of this animation. And I also recommend you look at another one, representing skinning mesh animations.
But for more serious information, you should read a technical paper named "BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models." Here is a link to this paper (PDF format, 6 pages, 4.72 MB).
Sources: Byron Spice, Pittsburgh Post-Gazette, October 10, 2005; and various web sites
You'll find related stories by following the links below.