research-article

Collision Detection for Interactive Graphics Applications

Author:

Philip M. HubbardAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 1, Issue 3

Pages 218 - 230

https://doi.org/10.1109/2945.466717

Published: 01 September 1995 Publication History

Abstract

Collision detection and response are important for interactive graphics applications such as vehicle simulators and virtual reality. Unfortunately, previous collision detection algorithms are too slow for interactive use. The paper presents a new algorithm for rigid or articulated objects that meets performance goals through a form of time critical computing. The algorithm supports progressive refinement, detecting collisions between successively tighter approximations to object surfaces as the application allows it more processing time. The algorithm uses simple four dimensional geometry to approximate motion, and hierarchies of spheres to approximate three dimensional surfaces at multiple resolutions. In a sample application, the algorithm allows interactive performance that is not possible with a good previous algorithm. In particular, the new algorithm provides acceptable accuracy while maintaining a steady and high frame rate, which in some cases improves on the previous algorithm's rate by more than two orders of magnitude

References

[1]

D. Baraff, “Coping with friction for non-penetrating rigid body simulation,” SIGGRAPH ’91, vol. 25, no. 4, pp. 31–40, July 1991.

[2]

L. Bergman, H. Fuchs, E. Grant, and S. Spach, “Image rendering by adaptive refinement,” SIGGRAPH ’86, vol. 20, no. 4, pp. 29–37, Aug. 1986.

[3]

J. Canny, “Collision detection for moving polyhedra,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 2, pp. 200–209, Mar. 1986.

Digital Library

[4]

J.D. Cohen, M.C. Lin, D. Manocha, and M.K. Ponamgi, “I-COLLIDE: An interactive and exact collision detection system for large-scale environments,” Proc. 1995 Symp. Interactive 3D Graphics, Monterey, Calif., pp. 189–196, 1995.

Digital Library

[5]

R.K. Culley and K.G. Kempf, “A collision detection algorithm based on velocity and distance bounds,” Proc. IEEE Int’l Conf. Robotics and Automation, pp. 1,064–1,069, 1986.

[6]

T. Duff, “Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry,” SIGGRAPH ’92, vol. 26, no. 2, pp. 131–138, July 1992.

[7]

A. Foisy, V. Hayward, and S. Aubry, “The use of awareness in collision prediction,” Proc. 1990 IEEE Int’l Conf. Robotics and Automation, pp. 338–343, 1990.

[8]

T.A. Funkhouser and C.H. Séquin, “Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments,” SIGGRAPH ’93, pp. 247–254, Aug. 1993.

[9]

A. Garcia-Alonso, N. Serrano, and J. Flaquer, “Solving the collision detection problem,” IEEE Computer Graphics and Applications, vol. 14, no. 3, pp. 36–43, May 1995.

Digital Library

[10]

J.A. Goldak, X. Yu, A. Knight, and L. Dong, “Constructing discrete medial axis of 3-D objects,” Int’l J. Computational Geometry and Applications, vol. 1, no. 3, pp. 327–339, 1991.

[11]

J. Goldsmith and J. Salmon, “Automatic creation of object hierarchies for ray tracing,” IEEE Computer Graphics and Applications, vol. 7, no. 5, pp. 14–20, May 1987.

Digital Library

[12]

P.S. Heckbert and M. Garland, “Multiresolution modeling for fast rendering,” Proc. Graphics Interface ’94, pp. 43–50, May 1994.

[13]

P.M. Hubbard, “Interactive collision detection,” Proc. 1993 IEEE Symp. Research Frontiers in Virtual Reality, pp. 24–31, Oct. 1993.

[14]

P.M. Hubbard, “Collision detection for interactive graphics applications,” PhD thesis, Dept. of Computer Science, Brown Univ., Oct. 1994.

[15]

R.S. Kennedy, N.E. Lane, M.G. Lilienthal, K.S. Berbaum, and L.J. Hettinger, “Profile analysis of simulator sickness symptoms: Application to virtual environment systems,” Presence, vol. 1, no. 3, Summer 1992.

[16]

M.C. Lin, D. Manocha, and J.F. Canny, “Fast collision detection between geometric models,” Tech. Report TR93-004, Dept. of Computer Science, Univ. of North Carolina at Chapel Hill, Jan. 1993.

[17]

P.W.C. Maciel and P. Shirley, “Visual navigation of large environments using textured clusters,” Proc. 1995 Symp. Interactive 3D Graphics, Monterey, Calif., pp. 95–102, 1995.

Digital Library

[18]

M.P. Moore and J. Wilhelms, “Collision detection and response for computer animation,” SIGGRAPH ’88, vol. 22, no. 4, pp. 289–298, Aug. 1988.

[19]

B.F. Naylor, “Constructing good partitioning trees,” Proc. of Graphics Interface ’93, pp. 181–191, May 1993.

[20]

J. O’Rourke and N. Badler, “Decomposition of three-dimensional objects into spheres,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 1, no. 3, pp. 295–305, July 1979.

Digital Library

[21]

F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.

Digital Library

[22]

W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C, 2nd ed., Cambridge, England: Cambridge Univ. Press, 1992.

[23]

H. Samet and R.E. Webber, “Hierarchical data structures and algorithms for computer graphics, part 1: Fundamentals,” IEEE Computer Graphics and Applications, vol. 8, no. 3, pp. 48–68, May 1988.

Digital Library

[24]

S. Sclaroff and A. Pentland, “Generalized implicit functions for computer graphics,” SIGGRAPH ’91, vol. 25, no. 4, pp. 247–250, Aug. 1991.

[25]

C.A. Shaffer and G.M. Herb, “A real-time robot arm collision avoidance system,” IEEE Trans. Robotics and Automation, vol. 8, no. 2, pp. 149–160, Apr. 1992.

[26]

A. Smith, Y. Kitamura, H. Takemura, and F. Kishino, “A simple and efficient method for accurate collision detection among deformable objects in arbitrary motion,” Proc. IEEE Virtual Reality Ann. Int’l Symp., pp. 136–145, Mar. 1995.

[27]

J.M. Snyder, A.R. Woodbury, K. Fleischer, B. Currin, and A.H. Barr, “Interval methods for multi-point collisions between time-dependent curved surfaces,” SIGGRAPH ’93, pp. 321–334, Aug. 1993.

[28]

W.C. Thibault and B.F. Naylor, “Set operations on polyhedra using binary space partitioning trees,” SIGGRAPH ’87, vol. 21, no. 4, pp. 153–162, July 1987.

[29]

G. Turk, “Interactive collision detection for molecular graphics,” Tech. Report 90-014, Dept. of Computer Science, Univ. of North Carolina at Chapel Hill, Jan. 1990.

Cited By

Zong CXu JSong JChen SXin SWang WTu C(2023)P2M: A Fast Solver for Querying Distance from Point to Mesh SurfaceACM Transactions on Graphics10.1145/359243942:4(1-13)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592439
Xu JPan SSun PHyeong Park SGuo K(2023)Human-Factors-in-Driving-Loop: Driver Identification and Verification via a Deep Learning Approach using Psychological Behavioral DataIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.322578224:3(3383-3394)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TITS.2022.3225782
Wang XGao JZhou XGu X(2023)Path Planning for the Gantry Welding Robot System Based on Improved RRT*Robotics and Computer-Integrated Manufacturing10.1016/j.rcim.2023.10264385:COnline publication date: 17-Oct-2023
https://dl.acm.org/doi/10.1016/j.rcim.2023.102643
Show More Cited By

Collision Detection for Interactive Graphics Applications
1. Computing methodologies
  1. Computer graphics

Recommendations

Collision detection for interactive graphics applications
Collision Detection for Interactive Graphics Applications
Realtime collision detection for virtual reality applications
VRAIS '93: Proceedings of the 1993 IEEE Virtual Reality Annual International Symposium

Virtual reality technology aims at the expansion of the communication bandwidth by providing users with 3D immersive environments. For the true direct manipulation of the environments, fast collision detection must be provided to increase the sense of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 1, Issue 3

September 1995

77 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © © 1995 IEEE.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 September 1995

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zong CXu JSong JChen SXin SWang WTu C(2023)P2M: A Fast Solver for Querying Distance from Point to Mesh SurfaceACM Transactions on Graphics10.1145/359243942:4(1-13)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592439
Xu JPan SSun PHyeong Park SGuo K(2023)Human-Factors-in-Driving-Loop: Driver Identification and Verification via a Deep Learning Approach using Psychological Behavioral DataIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.322578224:3(3383-3394)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TITS.2022.3225782
Wang XGao JZhou XGu X(2023)Path Planning for the Gantry Welding Robot System Based on Improved RRT*Robotics and Computer-Integrated Manufacturing10.1016/j.rcim.2023.10264385:COnline publication date: 17-Oct-2023
https://dl.acm.org/doi/10.1016/j.rcim.2023.102643
He T(2023)Volumetric virtual environmentsJournal of Computer Science and Technology10.1007/BF0295192515:1(37-46)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02951925
Lan LKaufman DLi MJiang CYang Y(2022)Affine body dynamicsACM Transactions on Graphics10.1145/3528223.353006441:4(1-14)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530064
Wang BFerguson ZSchneider TJiang XAttene MPanozzo D(2021)A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision DetectionACM Transactions on Graphics10.1145/346077540:5(1-16)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1145/3460775
Lan LYang YKaufman DYao JLi MJiang C(2021)Medial IPCACM Transactions on Graphics10.1145/3450626.345975340:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459753
Lan LLuo RFratarcangeli MXu WWang HGuo XYao JYang Y(2020)Medial ElasticsACM Transactions on Graphics10.1145/338451539:3(1-17)Online publication date: 21-Apr-2020
https://dl.acm.org/doi/10.1145/3384515
Attali DNguyen TSivignon I(2019)($$\delta ,{\varepsilon }$$?,?)-Ball Approximation of a ShapeDiscrete & Computational Geometry10.1007/s00454-018-0019-861:3(595-625)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00454-018-0019-8
Thul DLadický LJeong SPollefeys M(2018)Approximate convex decomposition and transfer for animated meshesACM Transactions on Graphics10.1145/3272127.327502937:6(1-10)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275029
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents