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

ABSTRACT

We develop an algorithm to detect geometric collisions between pairs of time-dependent parametric surfaces. The algorithm works on surfaces that are continuous and have bounded derivatives, and includes objects that move or deform as a function of time. The algorithm numerically solves for the parametric values corresponding to coincident points and near-misses between the surfaces of two parametric functions.Upper bounds on the parametric derivatives make it possible to guarantee the successful detection of collisions and near-misses; we describe a method to find the derivative bounds for many surface types. To compute collisions between new types of surfaces, the mathematical collision analysis is needed only once per surface type, rather than analyzing for each pair of surface types.The algorithm is hierarchical, first finding potential collisions over large volumes, and then refining the solution to smaller volumes. The user may specify the desired accuracy of the solution. A C-code implementation is described, with results for several non-bicubic and bicubic time-dependent parametric functions. An animation of the collision computation demonstrates collisions between complex parametric functions.

REFERENCES

• Baraff 89: D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.223-232, July 1989
• Barr 83: Alan I4. Barr, Geometric Modeling and Fluid Dynamic Analysis o} Swimming Spermatozoa, Ph.D. Dissertation, Rensselaer Polytechnic Institute, 1983.
• Barr 84: Alan H. Barr, Global and local deformations of solid primitives, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.21-30, July 1984
• Barzel et al. 88: Ronen Barzel , Alan H. Barr, A modeling system based on dynamic constraints, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.179-188, Aug. 1988
• Bentley et al. 79: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• Besl et al. 88: P. J. Besl , R. C. Jain, Segmentation through Variable-Order Surface Fitting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.2, p.167-192, March 1988 [doi>10.1109/34.3881]
• Bezier 74: Pierre Bezier, "Mathematical and Practical Possibilities of UNISURF," in Computer-Aided Geometric Design, edited by Robert E. Bamhill and Richard F. Riesenfeld, Academic Press, New York, 1974, pp. 127-152.
• Blinn 78: James Frederick Blinn, Computer display of curved surfaces., 1978
• Cameron et al. 86: S.A. Cameron and R. K. Culley, "Determining the Minimum Translational Distance Between Two Convex Polyhedra," IEEE International Con}erence oft Robotics and Automation, 1986.
• Canny 84: John Canny, Collision Detection for Moving Polyhedra, Massachusetts Institute of Technology, Cambridge, MA, 1984
• Catmull 75: Catmull, Ed, "Computer Display of Curved Surfaces," IEEE Con}erence Proceedings on Computer Graphics, Pattern Recognition and Data Structures, May 1975, 11.
• Chadwick et al. 89: J. E. Chadwick , D. R. Haumann , R. E. Parent, Layered construction for deformable animated characters, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.243-252, July 1989
• Culley et al. 86: R. K. Culley and K. G. Kempf, "A Collision Detection Algorithm Based on Velocity and Distance Bounds," Proceedings 1986 IEEE International Conference on Robotics and Automation, Volume 2, pp. 1064-1069.
• Filip et al. 86: Daniel Filip , Robert Magedson , Robert Markot, Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, v.3 n.4, p.295-311, 1987 [doi>10.1016/0167-8396(86)90005-1]
• Gear 71: C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice Hall PTR, Upper Saddle River, NJ, 1971
• Going Bananas 88: John Snyder, Jed Lengyel, Devendra Kada'a, Ronen Baxzel, John C. Platt, Alan H. Barr and Brian Von Herzen, Going Bananas, 1988 Siggraph Film Show.
• Hopcroft et al. 83: J.E. Hopcroft, J. T. Schwartz and M. Sharir, "Efficient Detection of Intersections among Spheres," The Internatior~al Journal of Robotics Research 2, 4, Winter 1983, 77-80.
• Kalra et al. 89: D. Kalra , A. H. Barr, Guaranteed ray intersections with implicit surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.297-306, July 1989
• Kaufman 87: Arie Kaufman, Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.171-179, July 1987
• Knuth 69: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• Lane et al. 79: Jeff Lane and Loren Carpenter, "A Generalized Scan Line Algorithm for the Computer Display of Parametrically Defined Surfaces," Computer Graphics and Image Processin.q 11 1979. 290.
• Lane et al. 80: Jeff Lane and Richard F. Riesenfeld, "A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces," IEEE Transactions on Pattern Analysis and Machine Intelligence 2, 1, January 1980.35-46.
• Lee et al. 84: D. 2". Lee and Franco P. Preparata, "Computational Geometrym A Survey," IEEE Transactions on Computers G_-33,12, December 1984, 1072.
• Lin et al. 74: C. C. Lin and L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Publishing Co., Inc., New York, 1974, pp. 57-58.
• Moore et al. 88: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• NAG: Graphics ~$, 4, August 1988, 289-298. NAG Fortran Library, Numerical Algorithms Group, 1400 Opus Place, Suite 200, Downers (}rove, IL 60515 (312) 971- 2337.
• Platt et al. 88: John C. Platt , Alan H. Barr, Constraints methods for flexible models, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.279-288, Aug. 1988
• Platt 89: John C. Platt, personal communication.
• Samet 84: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• Samet 90a: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Samet 90b: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Schmitt et al. 86: Francis J M Schmitt , Brian A. Barsky , Wen-hui Du, An adaptive subdivision method for surface-fitting from sampled data, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.179-188, Aug. 1986
• Schwarz 81: J.T. Schwarz, "Finding the Minimum Distance Between Two Convex Polygons," lnforma~io~ Processing Lett ors 13, 4, 1981, 168-170.
• Schweitzer et al. 82: Dino Schweitzer , Elizabeth S. Cobb, Scanline rendering of parametric surfaces, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.265-271, July 1982
• Sederberg et al. 86: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.151-160, Aug. 1986
• Snyder 90: John-Snyder Generative Models, Ph.D. Dissertation, California Institute of Technology, in progress.
• Terzopoulos et al. 88: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.269-278, Aug. 1988
• Uchiki et al. 83: Tetsuya Uchiki, Toshiakl Ohashl and Mario Tokoro, "Collision Detection in Motion Simulation," Cornputers and Graphics 7, 3, 1983, 285-293.
• Von Herzen et al. 87: Brian Von Herzen , Alan H. Barr, Accurate triangulations of deformed, intersecting surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.103-110, July 1987
• Von Herzen 85: Brian Von Herzen, Sampling De}ormed, Intersecting Surfaces with Quadtrees, Masters Thesis, California Institute of Technology, Computer Science Dept., 5179:TR:85, 1985.
• Von Herzen 89: B. Von Herzen, Applications of surface networks to sampling problems in computer graphics, California Institute of Technology, Pasadena, CA, 1989

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

General Terms:
Algorithms, Design, Languages