More Web Proxy on the site http://driver.im/

research-article

VolCCD: Fast continuous collision culling between deforming volume meshes

Authors:

Dinesh Manocha,

Ruo-Feng TongAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 30, Issue 5

Article No.: 111, Pages 1 - 15

https://doi.org/10.1145/2019627.2019630

Published: 22 October 2011 Publication History

Abstract

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. In addition, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra, hexahedra, triangular prisms, etc.). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

References

[1]

ABAQUS. 2003. ABAQUS 6.4. Analysis User's Manual. Hibbitt, Karlsson & Sorensen, Inc.

[2]

Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. In Proceedings of the ACM SIGGRAPH Conference. ACM, 1--10.

Digital Library

[3]

Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594--603.

Digital Library

[4]

Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proceedings of the Symposium on Interactive 3D Graphics and Games. 61--69.

Digital Library

[5]

Eberly, D. H. 2000. 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics. Morgan Kaufmann.

Digital Library

[6]

Erleben, K., Dohlmann, H., and Sporring, J. 2005. The adaptive thin shell tetrahedral mesh. In J. WSCG. 17--24.

[7]

Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In Proceedings of the Symposium on Computer Animation. 155--162.

Digital Library

[8]

Fisher, S. and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Proceedings of the Eurographic Workshop on Computer Animation and Simulation. Springer, 99--111.

Digital Library

[9]

Fleissner, F., Eberhard, P., Bischof, C., Bcker, M., Gibbon, P., Joubert, G. R., Mohr, B., (eds, F. P., Fleissner, F., and Eberhard, P. 2007. Load balanced parallel simulation of particle-fluid dem-sph systems with moving boundaries. In Proceedings of Parallel Computing: Architectures, Algorithms and Applications Conference. 37--44.

[10]

Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. In Proceedings of ACM Siggraph Conference. 171--180.

Digital Library

[11]

Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24, 3, 991--999.

Digital Library

[12]

Hallquist, J. 2006. LS-DYNA Theory Manual. Livermore Software Technology Corporation.

[13]

Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. In Proceedings of Vision Modeling Visualization Conference (VMV'03). 461--468.

[14]

Heidelberger, B., Teschner, M., Keiser, R., Müller, M., and Gross, M. 2004. Consistent peneration depth estimation for deformable collision response. In Proceedings of Vision Modeling Visualization Conference (VMV'04). 330--346.

[15]

Heo, J.-P., Seong, J.-K., Kim, D., Otaduy, M. A., Hong, J.-M., Tang, M., and Yoon, S.-E. 2010. FASTCD: Fracturing-Aware stable collision detection. In Proceedings of the ACM SIGGRAPH /Eurographics Symposium on Computer Animation.

Digital Library

[16]

Hutter, M. and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. In Proceedings of the WSCG '07. 25--32.

[17]

Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the Symposium on Computer Animation. 131--140.

Digital Library

[18]

Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. Vis. Comput. Graph. 4, 1, 21--37.

Digital Library

[19]

Levine, R. 2000. Collisions of moving objects. http://realtime collisiondetection.net/files/levine_swept_sat.txt.

[20]

Lombardo, J.-C., paule Cani, M., and Neyret, F. 1999. Real-time collision detection for virtual surgery. In Proceedings of the Symposium on Computer Animation. 26--28.

Digital Library

[21]

LS-DYNA. 2001. Contact modeling in LS-DYNA. http://www.dynasupport.com/tutorial/contact-modeling-in-ls-dyna/contact-types.

[22]

Mathias, E. and Gu, L. 2007. Hierarchical spatial hashing for real-time collision detection. In Proceedings of the IEEE International Conference on Shape Modeling and Applications. 61--70.

Digital Library

[23]

Müller, M., McMillan, L., Dorsey, J., and Jagnow, R. 2001. Real-time simulation of deformation and fracture of stiff materials. In Proceedings of the Eurographic Workshop on Computer Animation and Simulation. 113--124.

Digital Library

[24]

National-Crash-Analysis-Center. 2010. Finite element model archive. http://www.ncac.gwu.edu/vml/models.html.

[25]

Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809--836.

[26]

O'Brien, J. F. 2000. Graphical modeling and animation of brittle fracture. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA.

Digital Library

[27]

O'Brien, J. F. and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. 137--146.

Digital Library

[28]

Parker, E. G. and O'Brien, J. F. 2009. Real-Time deformation and fracture in a game environment. In Proceedings of the Symposium on Computer Animation. 165--175.

Digital Library

[29]

Plimpton, S., Attaway, S., Hendrickson, B., Swegle, J., Vaughan, C., and Gardner, D. 1998. Parallel transient dynamics simulations: Algorithms for contact detection and smoothed particle hydrodynamics. J. Parall. Distrib. Comput. 50, 1-2, 104--122.

Digital Library

[30]

Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. In Proceedings of the Graph. Interface Conference. 177--189.

[31]

Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Comput. Graph. Forum. 21, 3, 279--288.

[32]

Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 73--80.

Digital Library

[33]

Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. In Proceedings of the ACM SIGGRAPH Conference. 1144--1153.

Digital Library

[34]

Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Trans. Vis. Comput. Graph. 15, 4, 544--557.

Digital Library

[35]

Tang, M., Kim, Y. J., and Manocha, D. 2010b. Continuous collision detection for non-rigid contact computations using local advancement. In Proceedings of International Conference on Robotics and Automation.

[36]

Tang, M., Manocha, D., Lin, J., and Tong, R. 2011. Collision-streams: Fast GPU-based collision detection for deformable models. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D'11). 63--70.

Digital Library

[37]

Tang, M., Manocha, D., and Tong, R. 2010a. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D'10). ACM, New York, 7--13.

Digital Library

[38]

Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision Modeling Visualization Conference (VMV'03). 47--54.

[39]

Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Comput. Graph. Forum 19, 1, 61--81.

[40]

Volino, P. and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph. 25, 3, 1154--1159.

Digital Library

[41]

Volino, P. and Thalmann, N. M. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Comput. Graph. Forum 13, 3, 155--166.

[42]

Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. 28, 76:1--76:10.

Digital Library

[43]

Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Trans. Graph. 26, 3, 15.

Digital Library

[44]

Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2, 1--18.

Digital Library

Cited By

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
Li XSong SYao JZhang HZhou RHong Q(2023)Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulationGraphical Models10.1016/j.gmod.2023.101180128:COnline publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.gmod.2023.101180
Wang BFerguson ZJiang XAttene MPanozzo DSchneider T(2022)Fast and Exact Root Parity for Continuous Collision DetectionComputer Graphics Forum10.1111/cgf.1447941:2(355-363)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14479
Show More Cited By

Index Terms

VolCCD: Fast continuous collision culling between deforming volume meshes
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

Recommendations

Interactive continuous collision detection between deformable models using connectivity-based culling
SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling

We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a ...
Evaluation of continuous collision detection accelerated with tetrahedral structures
SCCG '16: Proceedings of the 32nd Spring Conference on Computer Graphics

Continuous collision detection provides very good information about the interaction between objects. In this paper, we present a new method for computing the continuous collision detection between a static and a moving triangle mesh. We target our ...
GPU-based radial view-based culling for continuous self-collision detection of deformable surfaces

We propose a graphics processing unit-based approach to accelerate the radial view-based culling method for continuous self-collision detection of deformable surfaces. The deformable surfaces may have small round-shaped holes and ghost triangles are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 30, Issue 5

October 2011

198 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2019627

Issue’s Table of Contents

Copyright © 2011 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: 22 October 2011

Accepted: 01 June 2011

Revised: 01 January 2011

Received: 01 August 2010

Published in TOG Volume 30, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Natural Science Foundation of Zhejiang Province
Ministry of Culture, Sports and Tourism
Army Research Office
National Research Foundation of Korea
KMCC, MSRA, BK, DAPA/ADD
Ministry of Knowledge Economy
Important Science and Technology Specific Project of Zhejiang, China
National Natural Science Foundation of China
Korea Evaluation Institute of Industrial Technology
Ministry of Education, Science and Technology
Ministry of Science and Technology of the People's Republic of China
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
852
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Li XSong SYao JZhang HZhou RHong Q(2023)Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulationGraphical Models10.1016/j.gmod.2023.101180128:COnline publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.gmod.2023.101180
Wang BFerguson ZJiang XAttene MPanozzo DSchneider T(2022)Fast and Exact Root Parity for Continuous Collision DetectionComputer Graphics Forum10.1111/cgf.1447941:2(355-363)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14479
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
Li MKaufman DJiang C(2021)Codimensional incremental potential contactACM Transactions on Graphics10.1145/3450626.345976740:4(1-24)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459767
Sonlu SGüdükbay UDurupinar F(2021)A Conversational Agent Framework with Multi-modal Personality ExpressionACM Transactions on Graphics10.1145/343979540:1(1-16)Online publication date: 6-Jan-2021
https://dl.acm.org/doi/10.1145/3439795
Huang ZYang XMin JWang HWei P(2021)Collision detection algorithm on abrasive belt grinding blisk based on improved octree segmentationThe International Journal of Advanced Manufacturing Technology10.1007/s00170-021-08213-w118:11-12(4105-4121)Online publication date: 22-Oct-2021
https://doi.org/10.1007/s00170-021-08213-w
Wang MCao J(2021)A review of collision detection for deformable objectsComputer Animation and Virtual Worlds10.1002/cav.198732:5Online publication date: Feb-2021
https://doi.org/10.1002/cav.1987
Wu LWu BYang YWang H(2020)A Safe and Fast Repulsion Method for GPU-based Cloth Self CollisionsACM Transactions on Graphics10.1145/343002540:1(1-18)Online publication date: 25-Dec-2020
https://dl.acm.org/doi/10.1145/3430025
Borges C(2020)Algorithm 1014ACM Transactions on Mathematical Software10.1145/342844647:1(1-12)Online publication date: 8-Dec-2020
https://dl.acm.org/doi/10.1145/3428446
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents