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

research-article

Volume contact constraints at arbitrary resolution

Authors:

Jérémie Allard,

François Faure,

Hadrien Courtecuisse,

Florent Falipou,

Christian Duriez,

Paul G. KryAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 29, Issue 4

Article No.: 82, Pages 1 - 10

https://doi.org/10.1145/1778765.1778819

Published: 26 July 2010 Publication History

Abstract

We introduce a new method for simulating frictional contact between volumetric objects using interpenetration volume constraints. When applied to complex geometries, our formulation results in dramatically simpler systems of equations than those of traditional mesh contact models. Contact between highly detailed meshes can be simplified to a single unilateral constraint equation, or accurately processed at arbitrary geometry-independent resolution with simultaneous sticking and sliding across contact patches. We exploit fast GPU methods for computing layered depth images, which provides us with the intersection volumes and gradients necessary to formulate the contact equations as linear complementarity problems. Straightforward and popular numerical methods, such as projected Gauss-Seidel, can be used to solve the system. We demonstrate our method in a number of scenarios and present results involving both rigid and deformable objects at interactive rates.

Supplementary Material

JPG File (tp026-10.jpg)

Download
23.94 KB

Supplemental material. (082.zip)

Download
26.20 MB

MP4 File (tp026-10.mp4)

Download
63.67 MB

References

[1]

Allard, J., Cotin, S., Faure, F., Bensoussan, P.-J., Poyer, F., Duriez, C., Delingette, H., and Grisoni, L. 2007. SOFA -- an open source framework for medical simulation. In Medicine Meets Virtual Reality (MMVR'15), 13--18. http://www.sofa-framework.org.

[2]

Anitescu, M., and Hart, G. D. 2004. Constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. International Journal for Numerical Methods in Engineering 60, 14, 2335--2371.

[3]

Anitescu, M., and Potra, F. 1997. Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems. Nonlinear Dynamics 14, 3, 231--247.

[4]

Ascher, U. M., and Petzold, L. R. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.

Digital Library

[5]

Baciu, G., and Wong, W. S.-K. 2004. Image-based collision detection for deformable cloth models. IEEE Transactions on Visualization and Computer Graphics 10, 6, 649--663.

Digital Library

[6]

Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 98, ACM, 43--54.

Digital Library

[7]

Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. Computer Graphics (Proceedings of SIGGRAPH 91) 25, 4, 31--41.

Digital Library

[8]

Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of SIGGRAPH 94, ACM, 23--34.

Digital Library

[9]

Barbič, J., and James, D. 2007. Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 171--180.

Digital Library

[10]

Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Transactions on Graphics 26, 3, 100.

Digital Library

[11]

Baumgarte, J. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering 1, 1--16.

[12]

Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of SIGGRAPH 2002, ACM, 594--603.

Digital Library

[13]

Cline, M. B., and Pai, D. K. 2003. Post-stabilization for rigid body simulation with contact and constraints. In IEEE International Conference on Robotics and Automation, 3744--3751.

[14]

Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Proceedings of SIGGRAPH 2001, ACM, 31--36.

Digital Library

[15]

Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Transactions on Visualization and Computer Graphics 12, 1, 36--47.

Digital Library

[16]

Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Transactions on Graphics 26, 2, 12.

Digital Library

[17]

Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 155--162.

Digital Library

[18]

Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBB-Tree: a hierarchical structure for rapid interference detection. In Proceedings of SIGGRAPH 96, ACM, 171--180.

Digital Library

[19]

Guendelman, E., Bridson, R., and Fedkiw, R. Nonconvex rigid bodies with stacking. ACM Transactions on Graphics 22, 3, 871--878.

Digital Library

[20]

Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Transactions on Graphics 27, 3, 1--4.

Digital Library

[21]

Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics 28, 3.

Digital Library

[22]

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

[23]

Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. In Proceedings of WSCG'04, 145--152.

[24]

Hubbard, P. M. 1995. Collision Detection for Interactive Graphics Applications. PhD thesis, Brown University.

Digital Library

[25]

James, D. L., and Pai, D. K. 2004. BD-tree: output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3, 393--398.

Digital Library

[26]

Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Transactions on Graphics 24, 3, 946--956.

Digital Library

[27]

Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics 27, 5, 1--11.

Digital Library

[28]

Lloyd, J. E. 2005. Fast implementation of Lemke's algorithm for rigid body contact simulation. In IEEE International Conference on Robotics and Automation, 4538--4543.

[29]

Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proceedings of SIGGRAPH 2001, ACM, 37--46.

Digital Library

[30]

Müller, M. 2008. Hierarchical position based dynamics. In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations, Eurographics Association, 1--10.

[31]

Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics 2005 - State of the Art Reports, 71--94.

[32]

Nesme, M., Payan, Y., and Faure, F. 2005. Efficient, physically plausible finite elements. In Eurographics 2005 - Short Papers, 77--80.

[33]

Otaduy, M. A., Jain, N., Sud, A., and Lin, M. C. 2004. Haptic display of interaction between textured models. In Proceedings of IEEE Visualization Conference, 297--304.

Digital Library

[34]

Otaduy, M. A., Germann, D., Redon, S., and Gross, M. 2007. Adaptive deformations with fast tight bounds. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, 181--190.

Digital Library

[35]

Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit contact handling for deformable objects. Computer Graphics Forum (Proceedings of Eurographics) 28, 2, 559--568.

[36]

Pabst, S., Thomaszewski, B., and Strasser, W. 2009. Anisotropic friction for deformable surfaces and solids. In SCA '09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 149--154.

Digital Library

[37]

Parker, E. G., and O'Brien, J. F. 2009. Real-time deformation and fracture in a game environment. In SCA '09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 165--175.

Digital Library

[38]

Pauly, M., Pai, D. K., and Guibas, L. J. 2004. Quasi-rigid objects in contact. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, 109--119.

Digital Library

[39]

Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Proceedings of 8th Eurographics Workshop on Animation and Simulation, 177--189.

[40]

Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. ACM Transactions on Graphics 25, 3, 1108--1117.

Digital Library

[41]

Stewart, D. E., and Trinkle, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. International Journal of Numerical Methods Engineering 39, 15, 2673--2691.

[42]

Stewart, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Review 42, 1, 3--39.

Digital Library

[43]

Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. ACM Transactions on Graphics 25, 3, 1144--1153.

Digital Library

[44]

Teschner, M., Kimmerle, S., Heidelberge, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2004. Collision detection for deformable objects. In Eurographics 2004 - State of the Art Reports.

[45]

van den Bergen, G. 1997. Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools 2, 4, 1--13.

Digital Library

[46]

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

[47]

Volino, P., and Magnenat-Thalmann, N. 1995. Collision and self-collision detection: Efficient and robust solutions for higly deformable surfaces. In Computer Animation and Simulation '95, 55--65.

[48]

Wong, W. S.-K., and Baciu, G. 2005. GPU-based intrinsic collision detection for deformable surfaces: Collision detection and deformable objects. Computer Animation and Virtual Worlds 16, 3--4, 153--161.

Digital Library

Cited By

Ando R(2024)A Cubic Barrier with Elasticity-Inclusive Dynamic StiffnessACM Transactions on Graphics10.1145/368790843:6(1-13)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687908
Zhang ZBrandt CJouve JWang YChen TPauly MPanetta J(2023)Computational Design of Flexible Planar MicrostructuresACM Transactions on Graphics10.1145/361839642:6(1-16)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618396
Probst TTeschner M(2023)Monolithic Friction and Contact Handling for Rigid Bodies and Fluids Using SPHComputer Graphics Forum10.1111/cgf.1472742:1(155-179)Online publication date: 20-Jan-2023
https://doi.org/10.1111/cgf.14727
Show More Cited By

Index Terms

Volume contact constraints at arbitrary resolution
1. Computing methodologies
  1. Computer graphics
    1. Animation
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Volume contact constraints at arbitrary resolution
SIGGRAPH '10: ACM SIGGRAPH 2010 papers

We introduce a new method for simulating frictional contact between volumetric objects using interpenetration volume constraints. When applied to complex geometries, our formulation results in dramatically simpler systems of equations than those of ...
Analysis of Dynamic Contact Forces for Forging Manipulator Grippers
ICMA '10: Proceedings of the 2010 International Conference on Manufacturing Automation

A contact model has been presented which assume that the contact forces between the work-piece and the tongs are simplified as the four resultant forces with friction point contact. And the contact forces are calculated based on this contact model. To ...
Influence of pantograph suspension characteristics on the contact quality with the catenary for high speed trains

In general the electrical energy is provided to the trainsets by the pantograph-catenary contact. The study of this system contributes to decrease the number of incidents and the maintenance and interoperability costs. Here a finite element method and a ...

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 29, Issue 4

July 2010

942 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1778765

Issue’s Table of Contents

Copyright © 2010 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: 26 July 2010

Published in TOG Volume 29, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

77
Total Citations
View Citations
1,411
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ando R(2024)A Cubic Barrier with Elasticity-Inclusive Dynamic StiffnessACM Transactions on Graphics10.1145/368790843:6(1-13)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687908
Zhang ZBrandt CJouve JWang YChen TPauly MPanetta J(2023)Computational Design of Flexible Planar MicrostructuresACM Transactions on Graphics10.1145/361839642:6(1-16)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618396
Probst TTeschner M(2023)Monolithic Friction and Contact Handling for Rigid Bodies and Fluids Using SPHComputer Graphics Forum10.1111/cgf.1472742:1(155-179)Online publication date: 20-Jan-2023
https://doi.org/10.1111/cgf.14727
Fang GTian YWeightman AWang C(2022)Collision-Aware Fast Simulation for Soft Robots by Optimization-Based Geometric Computing2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS47612.2022.9981870(12614-12621)Online publication date: 23-Oct-2022
https://doi.org/10.1109/IROS47612.2022.9981870
Kugelstadt TBender JFernández-Fernández JJeske SLöschner FLongva A(2021)Fast Corotated Elastic SPH Solids with Implicit Zero-Energy Mode ControlProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801424:3(1-21)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480142
Wang XFujisawa MMikawa M(2021)Visual Simulation of Soil-Structure Destruction with Seepage FlowsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801414:3(1-18)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480141
Musoni PMarin RMelzi SCastellani U(2021)A functional skeleton transferProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801404:3(1-15)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480140
Andrews SNassif LErleben KKry P(2021)Coupling Friction with Visual AppearanceProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801384:3(1-20)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480138
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
Geilinger MHahn DZehnder JBächer MThomaszewski BCoros S(2020)ADDACM Transactions on Graphics10.1145/3414685.341776639:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417766
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