Article

Interactive collision detection for complex and deformable models using programmable graphics hardware

Authors:

Qunsheng PengAuthors Info & Claims

VRST '04: Proceedings of the ACM symposium on Virtual reality software and technology

Pages 10 - 15

https://doi.org/10.1145/1077534.1077539

Published: 10 November 2004 Publication History

Abstract

In this paper we present an interactive collision detection algorithm for complex and deformable objects. For two target models, our approach rapidly calculates their region of interests (ROI), which is the overlapping of their axis aligned bounding boxes (AABBs), in CPU. The surfaces of both models inside the ROI are then voxelized using a novel GPU-based real-time voxelization method. The resultant volumes are represented by two 2D textures in video memory. The collision query is efficiently accomplished by comparing these 2D textures in GPU. The algorithm is robust to handle arbitrary shapes, no matter geometric models are convex or concave, closed or open, rigid or deformable. Our preliminary implementation achieves interactive frame rate for complex models with up to one million triangles on commodity desktop PCs.

References

[1]

G. Baciu, S. K. Wong, and H. Q. Sun. An image-based collision detection algorithm. In Proceedings of Pacific Graphics 1998, pages 497--512, 1998.

Digital Library

[2]

S. Beckhaus, J. Wind, and T. Strothotte. Hardware-based voxelization for 3d spatial analysis. In Proceedings of CGIM 2002, pages 15--20, 2002.

[3]

G. Bergen. Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools, 2(4):1--14, 1997.

Digital Library

[4]

G. Bergen. A fast and robust gjk implementation for collision detection of convex objects. Journal of Graphics Tools, 4(2):7--25, 1999.

Digital Library

[5]

M. Boyles and S. Fang. Slicing-based volumetric collision detection. Journal of Graphics Tools, 4(4):23--32, 1999.

Digital Library

[6]

S. Cameron. Enhancing gjk: computing minimum and penetration distances between convex polyhedra. In Proceedings of IEEE International Conference of Robotics and Automation, pages 3112--3117, 1997.

[7]

K. Chunk and W. Wang. Quick collision detection of polytopes in virtual environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pages 125--131, 1996.

Digital Library

[8]

J. Cohen, M. Lin, D. Manocha, and M. Ponamgi. I-collide: An interactive and exact collision detection system for large-scale environments. In Proceeding of ACM Interactive 3D Graphics Conference, pages 189--196, 1995.

Digital Library

[9]

S. Ehmann and M. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Proceedings of Eurographics 2001, pages 500--510, 2001.

[10]

S. Fang and H. Chen. Hardware accelerated voxeliation. Computers and Graphics, 24(3):433--442, 2000.

[11]

N. Gagvani and D. Silver. Shape-based volumetric collision detection. In Proceedings of the 2000 IEEE symposium on volume visualization, pages 57--61, 2000.

Digital Library

[12]

S. Gibson. Beyond volume rendering: visualization, haptic exploration, and physical modeling of voxel-based objects. In Proceedings of 6th Eurographics Workshop on Visualization in Scientific Computing, pages 10--24, 1995.

[13]

S. Gottsahalk, M. Lin, and D. Manocha. Obb-tree: a hierarchical structure for rapid interference detection. In Proceedings of ACM SIGGRAPH, pages 171--180, 1996.

Digital Library

[14]

N. K. Govindaraju, S. Redon, and D. Manocha. Cullide: Interactive collision detection between complex models in large environments using graphics hardware. In ACM SIGGRAPH/Eurographics Workshop On Graphics Hardware, pages 25--32, 2003.

Digital Library

[15]

T. He and A. Kaufman. Collision detection for volumetric objects. In Proceedings of the 8th conference on Visualization, pages 27--35, 1997.

Digital Library

[16]

B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetric intersections of deforming objects. In Proceedings of Vision, Modeling, Visualization, pages 461--468, 2003.

[17]

K. Hoff, A. Zaferakis, M. Lin, and D. Manocha. Fast and simple 2d geometric proximity queries using graphics hardware. In Proceedings of ACM Symposium on Interactive 3D Graphics, pages 145--148, 2001.

Digital Library

[18]

K. Hoff, A. Zaferakis, M. Lin, and D. Manocha. Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Technical Report TR02--004, 2002.

[19]

P. Hubbard. Collision detection for interactive graphics applications. IEEE Transactions on Visualization and Computer Graphics, 1(3):218--230, 1995.

Digital Library

[20]

T. Hudson, M. Lin, J. Cohen, S. Gottschalk, and D. Manocha. V-collide: accelerated collision detection for vrml. In Proceedings of VRML Conference, pages 119--125, 1997.

Digital Library

[21]

P. Jimzenez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001.

[22]

A. Kaufman, D. Cohen, and R. Yagel. Volume graphics. IEEE Computer, 26(7):51--64, 1993.

Digital Library

[23]

Y. Kim, M. Otaduy, M. Lin, and D. Manocha. Fast penetration depth computation using rasterization hardware and hierarchical refinement. UNC-CH Technical Report TR02--014, 2002.

[24]

Y. Kitamura, A. Smith, H. Takemura, and F. Kishino. A real-time algorithm for accurate collision detection for deformable polyhedral objects. Presence, 7(1):36--52, 1998.

Digital Library

[25]

J. T. Klosowski, J. T. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Transaction on Visualization and Computer Graphics, 4(1):21--36, 1998.

Digital Library

[26]

T. Larsson and T. Akenine-Moller. Efficient collision detection for models deformed by morphing. The Visual Computer, 9(2):164--174, 2003.

[27]

M. Lin and S. Gottschalk. Collision detection between geometric models: a survey. In Proceedings of IMA Conference on Mathematics of Surfaces, pages 37--56, 1998.

[28]

J. C. Lombardo, M.-P. Cani, and F. Neyret. Real-time collision detection for virtual surgery. In Proceedings of Computer Animation, pages 33--39, 1999.

Digital Library

[29]

W. McNeely, K. Puterbaugh, and J. Troy. Six degree-of freedom haptic rendering using voxel sampling. In Proceedings of ACM SIGGRAPH, pages 401--408, 1999.

Digital Library

[30]

B. Mirtich. V-clip: fast and robust polyhedral collision detection. ACM Transactions on Graphics, 17(3):177--208, 1998.

Digital Library

[31]

K. Myszkowski, O. G. Okunev, and T. L. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9):497--512, 1995.

[32]

S. Redon, A. Kheddar, and S. Coquillart. Fast continuous collision detection between rigid bodies. In Proceedings of Eurographics, pages 278--288, 2002.

[33]

J. Rossignac, A. Megahed, and B. D. Schneider. Interactive inspection of solids: cross-sections and interferences. In Proceedings of SIGGRAPH 1992, pages 353--360, 1992.

Digital Library

[34]

M. Shinya and M. C. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 2(4):131--134, 1991.

[35]

A. Smith, Y. Kitamura, H. Takemura, and F. Kishino. A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion. In Proceedings of Virtual reality annual international symposium, pages 136--145, 1995.

Digital Library

[36]

T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation on walking avatars. Computer Graphics Forum, 20(3):260--267, 2001.

[37]

S. Wang and A. Kaufman. Volume-sampled 3d modeling. IEEE Computer Graphics & Appplications, 14(5):26--32, 1994.

Digital Library

[38]

D. Zhang and M. Yuen. Collision detection for clothed human animation. In Proceedings of Pacific Graphics 2000, pages 328--337, 2000.

Digital Library

Cited By

Sanchez BRausch CHaas CHartmann T(2021)A framework for BIM-based disassembly models to support reuse of building componentsResources, Conservation and Recycling10.1016/j.resconrec.2021.105825175(105825)Online publication date: Dec-2021
https://doi.org/10.1016/j.resconrec.2021.105825
Kim J(2019)Acceleration Technique in Particle-based Collision Detection Using Cone Area Based Dynamic Collision RegionsJournal of the Korea Computer Graphics Society10.15701/kcgs.2019.25.2.1125:2(11-18)Online publication date: 1-Jun-2019
https://doi.org/10.15701/kcgs.2019.25.2.11
Weller RWeller R(2013)A Brief Overview of Collision DetectionNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_2(9-46)Online publication date: 2013
https://doi.org/10.1007/978-3-319-01020-5_2
Show More Cited By

Index Terms

Interactive collision detection for complex and deformable models using programmable graphics hardware
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Fast continuous collision detection among deformable models using graphics processors

We present an interactive algorithm to perform continuous collision detection between general deformable models using graphics processors (GPUs). We model the motion of each object in the environment as a continuous path and check for collisions along ...
Interactive on-surface signal deformation
SIGGRAPH '10: ACM SIGGRAPH 2010 papers

We present an interactive system for the artistic control of visual phenomena visible on surfaces. Our method allows the user to intuitively reposition shadows, caustics, and indirect illumination using a simple click-and-drag user interface working ...
Interactive on-surface signal deformation

We present an interactive system for the artistic control of visual phenomena visible on surfaces. Our method allows the user to intuitively reposition shadows, caustics, and indirect illumination using a simple click-and-drag user interface working ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

VRST '04: Proceedings of the ACM symposium on Virtual reality software and technology

November 2004

226 pages

ISBN:1581139071

DOI:10.1145/1077534

Program Chairs:
Rynson W. H. Lau
City University of Hong Kong, Hong Kong
,
George Baciu
The Hong Kong Polytechnic University, Hong Kong

Copyright © 2004 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VRST04

Sponsor:

VRST04: The ACM Symposium on Virtual Reality Software and Technology 2004

November 10 - 12, 2004

Hong Kong

Acceptance Rates

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
463
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sanchez BRausch CHaas CHartmann T(2021)A framework for BIM-based disassembly models to support reuse of building componentsResources, Conservation and Recycling10.1016/j.resconrec.2021.105825175(105825)Online publication date: Dec-2021
https://doi.org/10.1016/j.resconrec.2021.105825
Kim J(2019)Acceleration Technique in Particle-based Collision Detection Using Cone Area Based Dynamic Collision RegionsJournal of the Korea Computer Graphics Society10.15701/kcgs.2019.25.2.1125:2(11-18)Online publication date: 1-Jun-2019
https://doi.org/10.15701/kcgs.2019.25.2.11
Weller RWeller R(2013)A Brief Overview of Collision DetectionNew Geometric Data Structures for Collision Detection and Haptics10.1007/978-3-319-01020-5_2(9-46)Online publication date: 2013
https://doi.org/10.1007/978-3-319-01020-5_2
Zink NHardy ASlay HBangay S(2007)Cloth simulation and collision detection using geometry imagesProceedings of the 5th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa10.1145/1294685.1294716(187-195)Online publication date: 29-Oct-2007
https://dl.acm.org/doi/10.1145/1294685.1294716
Zhang XKim Y(2007)Interactive Collision Detection for Deformable Models Using Streaming AABBsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2007.4213:2(318-329)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1109/TVCG.2007.42
Wong WBaciu G(2007)Robust continuous collision detection for interactive deformable surfacesComputer Animation and Virtual Worlds10.1002/cav.17318:3(179-192)Online publication date: 3-May-2007
https://doi.org/10.1002/cav.173

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten