Time-Critical Collision Detection

Philip Hubbard

Cornell University

Abstract

This seminar will explore a time-critical approach to collision detection. We begin by discussing why many interactive graphics applications need such an approach. One way to implement this approach is to approximate the shapes of objects at multiple levels of detail. We describe approximations based on sets of spheres, arranged into hierarchies we call "sphere-trees". Sphere-trees can be built automatically by a preprocess that uses medial-axis surfaces, which represent the shapes of objects in skeletal form. We conclude with some examples of the time-critical algorithm in practice, and a discussion of open questions for future research.

References

  1. Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav K. Ponamgi, "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments," Proceedings 1995 Symposium on Interactive 3D Graphics, pp. 189-196.
    ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/paper3dint.ps.Z
  2. Philip M. Hubbard, "Collision Detection for Interactive Graphics Applications," Ph.D. Thesis, Department of Computer Science, Brown University, Oct. 1994.
    ftp://ftp.cs.brown.edu/pub/techreports/95/cs95-08.ps.Z
  3. Philip M. Hubbard, "Real-Time Collision Detection and Time-Critical Computing," Proceedings First ACM Workshop on Simulation and Interaction in Virtual Environments, July 1995, pp. 92-96.
    http://www.graphics.cornell.edu/~pmh/sive95.ps.gz
  4. Philip M. Hubbard, "Collision Detection for Interactive Graphics Applications," IEEE Transactions on Visualization and Computer Graphics, 1(3), Sept. 1995, pp. 218-230.
    http://www.graphics.cornell.edu/~pmh/tvcg95.ps.gz
  5. Greg Turk, "Interactive Collision Detection for Molecular Graphics," TR90-014, Department of Computer Science, The University of North Carolina at Chapel Hill, Jan. 1990.
    ftp://ftp.cs.unc.edu/pub/technical-reports/90-014.uu
Brook Conner