Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Collision handling plays a fundamental role for achieving realism and interactivity in 3D graphical systems. Nevertheless, it is still one of the bottlenecks of such systems. In this work, we use the Sweep & Prune algorithm and Sphere-Tree approximations of the objects to perform the collision detection. Besides, we show how to compute the contact data for the narrow phase out of the overlapping leaf spheres from the Sphere-Trees. For collision response, we have implemented a simple, yet efficient and accurate, impulse-based method. A number of experiments in virtual scenarios with objects falling in a static plane were conducted. The results show that when Sphere-Trees with 2 levels are used for scenarios with a great number of objects (up to 200 falling objects) and simultaneous contacts among them (up to 16381.50 contacts at each frame on average), our system is capable of generating real time plausible rigid body animation, with always more than 30 frames per second (FPS) on average.

REFERENCES

• 1: David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.23-34, July 1994 [doi>10.1145/192161.192168]
• 2: G. Bradshaw. Sphere-Tree Construction Toolkit. http://isg.cs.tcd.ie/spheretree/, February 2003. Last visited 11/11/06.
• 3: Gareth Bradshaw , Carol O'Sullivan, Adaptive medial-axis approximation for sphere-tree construction, ACM Transactions on Graphics (TOG), v.23 n.1, p.1-26, January 2004 [doi>10.1145/966131.966132]
• 4: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 5: D. Coming and O. Staadt. Kinetic Sweep and Prune for Collision Detection. In Proceedings of the Second Workshop in Virtual Reality Interactions and Physical Simulations (VRIPHYS'05), pages 81--90, Pisa, Italy, November 2005.
• 6: J. Dingliana and C. O'Sullivan. Graceful Degradation of Collision Handling in Physically Based Animation. Computer Graphics Forum, 19(3):239--248, 2000.
• 7: Christer Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 8: T. Giang, G. Bradshaw, and C. OSullivan. Complementarity Based Multiple Point Collision Resolution. In Proceedings of the Fourth Irish Workshop on Computer Graphics, 2003.
• 9: S. Gottschalk, M. C. Lin, and D. Manocha. OBBTree: A Hierarchical Structure for Rapid Interference Detection. Computer Graphics, 30:171--180, 1996.
• 10: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
• 11: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 12: Rodrigo G. Luque , João L. D. Comba , Carla M. D. S. Freitas, Broad-phase collision detection using semi-adjusting BSP-trees, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053457]
• 13: Brian Mirtich , John Canny, Impulse-based dynamic simulation, Proceedings of the workshop on Algorithmic foundations of robotics, p.407-418, May 1995, San Francisco, California, United States
• 14: R. Parent. Computer Animation: Algorithms and Techniques. The Morgan Kaufmann Series in Computer Graphics and Geometrical Modelling. Morgan and Kaufmann Publishers, 2002.
• 15: S. Redon. Continuous Collision Detection for Rigid and Articulated Bodies. Tutorial, 2004. ACM SIGGRAPH Course Notes.
• 16: S. Redon, A. Kheddar, and S. Coquillart. CONTACT: Arbitrary in-between Motions for Collision Detection. In Proceedings of IEEE Workshop on Robot-Human Interaction, ROMAN'2001, pages 106--111, Bordeaux, Paris, France, 2001.
• 17: R. S. Rocha, M. A. F. Rodrigues, and L. S. Taddeo. Performance Evaluation of a Hybrid Algorithm for Collision Detection in Crowded Interactive Environments. In Proceedings of the XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2006), pages 86--93, Manaus, AM, Brazil, 2006. IEEE CS Press.
• 18: S.-E. Yoon and D. Manocha. Cache-Efficient Layouts of Bounding Volume Hierarchies. Computer Graphics Forum (Eurographics), 25(3):507--516, 2006.
• 19: G. Zachmann. Optimizing the Collision Detection Pipeline. In Proceedings of the First International Game Technology Conference (GTEC'01), 2001.
• 20: Liangjun Zhang , Young J. Kim , Gokul Varadhan , Dinesh Manocha, Generalized penetration depth computation, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom [doi>10.1145/1128888.1128914]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Keywords:
collision detection, performance analysis, physically-based animation, sphere-tree