ACM SIGGRAPH 2004 Electronic Theater Animation:
Output-Sensitive Collision Processing for Reduced-Coordinate Deformable Models

This animation shows offline animations of deformable collision phenomena created using a new collision-detection bounding volume hierarchy called a Bounded Deformation Tree, or BD-Tree. This algorithm can make collision detection for reduced-coordinate deformable models as asymptotically cheap as with rigid models. The bounding volumes of a BD-Tree can be updated in any order following deformation, and without need for explicit access to the deformed geometry. Consequently, collisions with very large and/or numerous models can be processed at very modest costs on the CPU, with deformations synthesized in programmable graphics hardware. In all of our examples, deformable collision, contact, and multibody dynamics processing are typically faster than rendering all models using programmable hardware (NVIDIA Quadro FX 3000). Our animation shows that large-scale physically based deformable simulations can be achieved at little more than the cost of rendering. The final chair sequence involves 3,601 plastic chairs, with more than 60 million deforming triangles and 1.6 billion sphere-collision events, and has a mean collision processing cost of two seconds per time-step.

This animation was shown in the ACM SIGGRAPH 2004 Electronic Theater.


Research and Development
Video Production
Additional Modeling

Video Formats


The music used in this animation is In the Hall of the Mountain King, from Peer Gynt Suite No. 1 Op. 46. It was composed by Edvard Grieg and performed by The Moscow International Symphony Orchestra.

Creation Details

This short was produced using a single machine with two Xeon 3GHz processors and 2GB RAM. All models were deformed and rendered using a NVIDIA Quadro FX 3000 GPU. Final compositing and editing was done using Adobe After Effects 6.5 visual effects software.

For further details please see our paper and sketch in the technical portion of ACM SIGGRAPH:

No fish were harmed in the production of this film.


Doug L. James, Dinesh K. Pai, and Christopher D. Twigg. Output-Sensitive Collision Processing for Reduced-Coordinate Deformable Models. In The Visual Proceedings of ACM SIGGRAPH 2004 (Electronic Theater), August 2004.


This research is supported by:

We would also like to thank NVIDIA Corporation for their generous hardware donations and support.

Copyright notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.