article

Free access

Geometric collisions for time-dependent parametric surfaces

Authors:

Brian Von Herzen,

Harold R. ZatzAuthors Info & Claims

ACM SIGGRAPH Computer Graphics, Volume 24, Issue 4

Pages 39 - 48

https://doi.org/10.1145/97880.97883

Published: 01 September 1990 Publication History

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.

Digital Library

[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.

Digital Library

[4]

Rouen Barzel and Alan H. Baxr, "A Modeling System Based oft Dyrtamic Constraints," Computer Graphics $2, 4, August 1988, 179-188.

Digital Library

[5]

don L. Bentley and Jerome H. Friedman, "Data Structures for Range Searching," A Cite Computing Surveys 11, 4, December 1979, 397-409.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[15]

C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1971, p. 55.

Digital Library

[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.

Digital Library

[19]

Ane Kaufmart, "Efficient Algorithms for 3D Scan- Conversion of Parametric Curves, Surfaces, and Volumes," Comp_uter Graphics $i, 4, July 1987, 171-180.

Digital Library

[20]

Donald Knuth, The Art o} Computer Programming; Vol. i, Fundamental Algorithms, Addisort-Wesley, Menlo Park, CA~ 1969, Section 2.2.4.

Digital Library

[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-

Digital Library

[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.

Digital Library

[28]

John C. Platt, personal communication.

[29]

Hartan Samet, "The Quadtree and Related Hierarchlcol Data Structures," Computing Surveys 16, 2, June 1984, 187-260.

Digital Library

[30]

Hanan Samet, The Design and A~alysis o} Spatial Data Structures, Addison-Wesley, Menlo Park, CA, 1990, Section 2.4, pp. 66--80.

Digital Library

[31]

Hanan Samet, Applications of Spatial Data Structures, Addison-Wesley, Menlo Park, CA, 1990, Section 1.3, pp. 15-16.

Digital Library

[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.

Digital Library

[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.

Digital Library

[35]

Tom Sederberg and Scott Parry, "Free-Form Deformation of Solid Geometric Models~" Computer Graphics 20 4, August 1986, 151-160.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Ni XChen Xyu CWang BChen B(2024)Simulating Thin Shells by Bicubic Hermite ElementsComputer-Aided Design10.1016/j.cad.2024.103734174(103734)Online publication date: Sep-2024
https://doi.org/10.1016/j.cad.2024.103734
Wang TChen JLi DLiu XWang HZhou K(2023)Fast GPU-based Two-way Continuous Collision HandlingACM Transactions on Graphics10.1145/360455142:5(1-15)Online publication date: 28-Jul-2023
https://dl.acm.org/doi/10.1145/3604551
Gottschalk SLin MManocha D(2023)OBBTree: A Hierarchical Structure for Rapid Interference DetectionSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596791(757-766)Online publication date: 2-Aug-2023
https://doi.org/10.1145/3596711.3596791
Show More Cited By

Index Terms

Geometric collisions for time-dependent parametric surfaces

Recommendations

Geometric collisions for time-dependent parametric surfaces
SIGGRAPH '90: Proceedings of the 17th annual conference on Computer graphics and interactive techniques

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. ...
Blending parametric surfaces

A blending surface is a surface that smoothly connects two given surfaces along two arbitrary curves, one on each surface. This is particularly useful in the modeling operations of filleting a sharp edge between joining surfaces or connecting disjoint ...
A geometric method for computation of geodesic on parametric surfaces

This paper proposes a geometric algorithm for computation of geodesic on surfaces. The geodesics on surfaces are traced in a simple way which is independent of the complex description of the geodesic equations. Through derivation process, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGGRAPH Computer Graphics

ACM SIGGRAPH Computer Graphics Volume 24, Issue 4

Aug. 1990

377 pages

ISSN:0097-8930

DOI:10.1145/97880

Editor:
Richard J. Beach

Issue’s Table of Contents

SIGGRAPH '90: Proceedings of the 17th annual conference on Computer graphics and interactive techniques
September 1990
452 pages
ISBN:0897913442
DOI:10.1145/97879
Chairman:
Forest Baskett

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1990

Published in SIGGRAPH Volume 24, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
1,006
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)21

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ni XChen Xyu CWang BChen B(2024)Simulating Thin Shells by Bicubic Hermite ElementsComputer-Aided Design10.1016/j.cad.2024.103734174(103734)Online publication date: Sep-2024
https://doi.org/10.1016/j.cad.2024.103734
Wang TChen JLi DLiu XWang HZhou K(2023)Fast GPU-based Two-way Continuous Collision HandlingACM Transactions on Graphics10.1145/360455142:5(1-15)Online publication date: 28-Jul-2023
https://dl.acm.org/doi/10.1145/3604551
Gottschalk SLin MManocha D(2023)OBBTree: A Hierarchical Structure for Rapid Interference DetectionSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596791(757-766)Online publication date: 2-Aug-2023
https://doi.org/10.1145/3596711.3596791
Ferguson ZJain PZorin DSchneider TPanozzo D(2023)High-Order Incremental Potential Contact for Elastodynamic Simulation on Curved MeshesACM SIGGRAPH 2023 Conference Proceedings10.1145/3588432.3591488(1-11)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.1145/3588432.3591488
Geršak J(2022)Digital fashion: Customisation of the productDesign of Clothing Manufacturing Processes10.1016/B978-0-08-102648-9.00007-4(115-152)Online publication date: 2022
https://doi.org/10.1016/B978-0-08-102648-9.00007-4
Kim YLin MManocha D(2018)Collision DetectionHumanoid Robotics: A Reference10.1007/978-94-007-6046-2_26(1933-1956)Online publication date: 10-Oct-2018
https://doi.org/10.1007/978-94-007-6046-2_26
Kim YLin MManocha D(2017)Collision DetectionHumanoid Robotics: A Reference10.1007/978-94-007-7194-9_26-1(1-24)Online publication date: 27-Jul-2017
https://doi.org/10.1007/978-94-007-7194-9_26-1
Constantinescu DSalcudean SCroft E(2016)Local Model of Interaction for Haptic Manipulation of Rigid Virtual WorldsThe International Journal of Robotics Research10.1177/027836490505785624:10(789-804)Online publication date: 2-Jul-2016
https://doi.org/10.1177/0278364905057856
Marvel JBostelman R(2014)A Cross-Domain Survey of Metrics for Modelling and Evaluating CollisionsInternational Journal of Advanced Robotic Systems10.5772/5884611:9Online publication date: 1-Jan-2014
https://doi.org/10.5772/58846
Khulief Y(2012)Modeling of Impact in Multibody Systems: An OverviewJournal of Computational and Nonlinear Dynamics10.1115/1.40062028:2Online publication date: 31-Aug-2012
https://doi.org/10.1115/1.4006202
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents