“Geometric collisions for time-dependent parametric surfaces” by Von Herzen, Barr and Zatz
Conference:
Type:
Title:
- Geometric collisions for time-dependent parametric surfaces
Session/Category Title: Dynamics
Presenter(s)/Author(s):
Moderator(s):
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:
1. David Baraff, “Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies,” Computer Graphics 23, 3, July 1989, 223-232.
2. Alan I4. Barr, Geometric Modeling and Fluid Dynamic Analysis o} Swimming Spermatozoa, Ph.D. Dissertation, Rensselaer Polytechnic Institute, 1983.
3. Alan H. Barr, “Local and Global Deformations of Solid Primitives,” Computer Graphics 18, 3, July 1984, 21-30.
4. Rouen Barzel and Alan H. Baxr, “A Modeling System Based oft Dyrtamic Constraints,” Computer Graphics $2, 4, August 1988, 179-188.
5. don L. Bentley and Jerome H. Friedman, “Data Structures for Range Searching,” A Cite Computing Surveys 11, 4, December 1979, 397-409.
6. Paul J. Besl and Ramesh C. Jain, “Segmentation through Variable-Order Surface Fitting,” IEEE Transactions on Pattern Analysis and Machine Intelligence 1 O, 2, March 1988, 167-192.
7. 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.
8. Jim Dlinn, Computer Display of Curved Surfaces, Ph.D. Dissertation, University of Utah, 1978.
9. 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.
10. John Canny, “Collision Detection for Moving Polyhedra,” MIT A r$ifieial Intelligence Lab Memo 806, October, 1984.
11. Catmull, Ed, “Computer Display of Curved Surfaces,” IEEE Con}erence Proceedings on Computer Graphics, Pattern Recognition and Data Structures, May 1975, 11.
12. John E. Chadwick, David R. Haumaxm and Richaxd El. Parent, “Layered Construction for Deformable Animated Characters,” Computer Graphics 23, 3, July 1989, 243-252.
13. 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.
14. Daniel Filip, Robert Magedsort and Robert Markot, “Surface Algorithms using Bounds on Derivatives,” Computer Aided Geometric Design 8, 1986, 295-311.
15. C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1971, p. 55.
16. 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.
17. 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.
18. Devendra Kalra and Alan H. Barr, “Guaranteed Ray Intersections with Implicit Surfaces,” Computer Graphics 23, 3, July. 1989, 297-306.
19. Ane Kaufmart, “Efficient Algorithms for 3D Scan- Conversion of Parametric Curves, Surfaces, and Volumes,” Comp_uter Graphics $i, 4, July 1987, 171-180.
20. Donald Knuth, The Art o} Computer Programming; Vol. i, Fundamental Algorithms, Addisort-Wesley, Menlo Park, CA~ 1969, Section 2.2.4.
21. 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.
22. 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.
23. D. 2″. Lee and Franco P. Preparata, “Computational Geometrym A Survey,” IEEE Transactions on Computers G_-33,12, December 1984, 1072.
24. 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.
25. Matthew Moore and Jane Wilhelms, “Collision Detection and Response for Computer Animation,” Gom-
26. Graphics ~$, 4, August 1988, 289-298. NAG Fortran Library, Numerical Algorithms Group, 1400 Opus Place, Suite 200, Downers (}rove, IL 60515 (312) 971- 2337.
27. John C. Platt and Alan H. Barr, “Constraint Methods for Flexible Models,” Computer Graphics 22, 4, August 1988, 279-288.
28. John C. Platt, personal communication.
29. Hartan Samet, “The Quadtree and Related Hierarchlcol Data Structures,” Computing Surveys 16, 2, June 1984, 187-260.
30. Hanan Samet, The Design and A~alysis o} Spatial Data Structures, Addison-Wesley, Menlo Park, CA, 1990, Section 2.4, pp. 66–80.
31. Hanan Samet, Applications of Spatial Data Structures, Addison-Wesley, Menlo Park, CA, 1990, Section 1.3, pp. 15-16.
32. Francis Schmitt, Brian Barsky and Wen-Hurl Du. “An Adaptive Subdivision Method for Surface-Fittlng from Sampled Data,” Computer Graphics ~0, 4, August 1986, 179-188.
33. J.T. Schwarz, “Finding the Minimum Distance Between Two Convex Polygons,” lnforma~io~ Processing Lett ors 13, 4, 1981, 168-170.
34. D. Schweitzer and E. S. Cobb, “Scanline Rendering of Parametric Surfaces,” Computer Graphics 16, 3, July 1982, 265.
35. Tom Sederberg and Scott Parry, “Free-Form Deformation of Solid Geometric Models~” Computer Graphics 20 4, August 1986, 151-160.
36. John-Snyder Generative Models, Ph.D. Dissertation, California Institute of Technology, in progress.
37. Demetri Terzopoulos and Kurt Fleischer, “Modeling Inelastic Deformation: Viscoelasticity, Plasticity, Fracture,” Computer Graphics ~, 4, August 1988, 269-278.
38. Tetsuya Uchiki, Toshiakl Ohashl and Mario Tokoro, “Collision Detection in Motion Simulation,” Cornputers and Graphics 7, 3, 1983, 285-293.
39. Brian Von Herzen and Alan H. Barr, “Accurate Triangulations of Deformed, Intersecting Surfaces,” Computer _Graphics ~1, 4~ July 1987, 103-110.
40. Brian Von Herzen, Sampling De}ormed, Intersecting Surfaces with Quadtrees, Masters Thesis, California Institute of Technology, Computer Science Dept., 5179:TR:85, 1985.
41. Brian Von Herzen, Applications o} Surface Networks to Sampling Problems it, Computer Graphics, PhD. Dissertation, California Institute of Technology, Computer Science Dept., Caltech-CS-TR-88-15, 1989.
