research-article

Image-based collision detection and response between arbitrary volume objects

Authors:

François Faure,

Sébastien Barbier,

Jérémie Allard,

Florent FalipouAuthors Info & Claims

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 155 - 162

Published: 07 July 2008 Publication History

Abstract

We present a new image-based method to process contacts between objects bounded by triangular surfaces. Unlike previous methods, it relies on image-based volume minimization, which eliminates complex geometrical computations and robustly handles deep intersections.

The surfaces are rasterized in three orthogonal directions, and intersections are detected based on pixel depth and normal orientation. Per-pixel contact forces are computed and accumulated at the vertices. We show how to compute pressure forces which serve to minimize the intersection volume, as well as friction forces.

No geometrical precomputation is required, which makes the method efficient for both deformable and rigid objects. We demonstrate it on rigid, skinned, and particle-based physical models with detailed surfaces in contacts at interactive frame rates.

References

[1]

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

[2]

{Bar94} Baraff D.: Fast contact force computation for nonpenetrating rigid bodies. In Proc. of ACM SIGGRAPH 94 (1994).

Digital Library

[3]

{BFA02} Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics 21 (2002), 594--603.

Digital Library

[4]

{BJ07} Barbič J., James D.: Time-critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In Proc. of ACM/Eurographics SCA (2007).

Digital Library

[5]

{BM08} Bavoil L., Myers K.: Order independent transparency with dual depth peeling. NVIDIA OpenGL SDK, 2008.

[6]

{BW98} Baraff D., Witkin A.: Large steps in cloth simulation. In Proc. of ACM SIGGRAPH 98 (1998), pp. 43--54.

Digital Library

[7]

{CW05} Cirak F., West M.: Decomposition-based contact response (dcr) for explicit finite element dynamics. Int. Journal for Numerical Methods in Engineering 64, 8 (2005), 1078--1110.

[8]

{Eve01} Everitt C.: Interactive order-independent transparency. Tech. rep., NVIDIA Corporation, 2001.

[9]

{FL01} Fisher S., Lin M. C.: Fast penetration depth estimation for elastic bodies using deformed distance fields. In Proc. of IEEE/RSJ IROS (2001).

[10]

{GKLM07} Govindaraju N. K., Kabul I., Lin M. C., Manocha D.: Fast continuous collision detection among deformable models using graphics processors. Computers and Graphics 31, 1 (2007), 5--14.

Digital Library

[11]

{GLM05} Govindaraju N. K., Lin M. C., Manocha D.: Quick-cullide: Fast inter- and intra-object collision culling using graphics hardware. In IEEE Conf. on Virtual Reality (2005).

Digital Library

[12]

{HFS*01} Hirota G., Fisher S., State A., Fuchs H., Lee. C.: An implicit finite element method for elastic solids in contact. In Proc. Computer Animation (2001).

[13]

{HTG03} Heidelberger B., Teschner M., Gross M.: Real-time volumetric intersections of deforming objects. In Proc. of Vision, Modeling, Visualization (VMV) (2003).

[14]

{HTG04} Heidelberger B., Teschner M., Gross M.: Detection of collisions and self-collisions using image-space techniques. In Proc. of WSCG'04 (2004), pp. 145--152.

[15]

{HTK*04} Heidelberger B., Teschner M., Keiser R., Muller M., Gross M.: Consistent penetration depth estimation for deformable collision response. In Proc. of VMV'04 (2004), pp. 339--346.

[16]

{JTT01} Jimenez P., Thomas F., Torras C.: 3d collision detection: A survey. Computer and Graphics 25, 2 (2001), 269--285.

[17]

{LM03} Lin M., Manocha D.: Collision and proximity queries. In Handbook of Discrete and Computational Geometry (2003).

[18]

{MC95} Mirtich B., Canny J.: Impulse-based simulation of rigid bodies. In Interactive 3D graphics (1995).

Digital Library

[19]

{OJSL04} Otaduy M. A., Jain N., Sud A., Lin M. C.: Haptic display of interaction between textured models. In Proc. of IEEE Visualization Conference (2004).

Digital Library

[20]

{Pro97} Provot X.: Collision and self-collision handling in cloth model dedicated to design garments. In Proc. of 8th Eurographics Workshop on Animation and Simulation (1997).

[21]

{SGwHS98} Shade J., Gortler S., wei He L., Szeliski R.: Layered depth images. In Proc. of ACM SIGGRAPH 98 (1998).

Digital Library

[22]

{SOM04} Sud A., Otaduy M. A., Manocha. D.: Difi: Fast 3d distance field computation using graphics hardware. Computer Graphics Forum 23, 3 (2004), 557--566.

[23]

{TKH*05} Teschner M., Kimmerle S., Heidelberger B., Zachmann G., Raghupathi L., Fuhrmann A., Cani M.-P., Faure F., Magnetat-Thalmann N., Strasser W., Volino P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1 (2005), 61--81.

[24]

{VMT00} Volino P., Magnenat-Thalmann N.: Implementing fast cloth simulation with collision response. In Computer Graphics International (2000).

Digital Library

[25]

{VMT06} Volino P., Magnenat-Thalmann N.: Resolving surface collisions through intersection contour minimization. ACM Transactions on Graphics 25, 3 (2006), 1154--1159.

Digital Library

[26]

{VSC01} Vassilev T., Spanlang B., Chrysanthou Y.: Fast cloth animation on walking avatars. In Proc. Eurographics (2001), vol. 20.

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
Friston SDoboš JWong CFan CMontero SSteed APolys NMcCann MLiu FPlesch A(2019)Rectangular Selection of Components in Large 3D Models on the WebProceedings of the 24th International Conference on 3D Web Technology10.1145/3329714.3338125(1-9)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3329714.3338125
Bargteil AShinar T(2019)An introduction to physics-based animationACM SIGGRAPH 2019 Courses10.1145/3305366.3328050(1-57)Online publication date: 28-Jul-2019
https://dl.acm.org/doi/10.1145/3305366.3328050
Show More Cited By

Index Terms

Image-based collision detection and response between arbitrary volume objects
1. Computing methodologies
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Real-Time Volume Caustics with Image-Based Photon Tracing
CADGRAPHICS '11: Proceedings of the 2011 12th International Conference on Computer-Aided Design and Computer Graphics

Rendering of volume caustics in participating media is often expensive, even with different acceleration approaches. Basic volume photon tracing is used to render such effects, but rather slow due to its massive quantity of photons to be traced. In this ...
Image Plane Sweep Volume Illumination

In recent years, many volumetric illumination models have been proposed, which have the potential to simulate advanced lighting effects and thus support improved image comprehension. Although volume ray-casting is widely accepted as the volume rendering ...
Shear-image order ray casting volume rendering
I3D '03: Proceedings of the 2003 symposium on Interactive 3D graphics

This paper describes shear-image order ray casting, a new method for volume rendering. This method renders sampled data in three dimensions with image quality equivalent to the best of ray-per-pixel volume rendering algorithms (full image order), while ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2008

230 pages

ISBN:9783905674101

Conference Chairs:
Eugene Fiume,
Jerry Tessendorf,
Program Chairs:
Markus Gross,
Doug James

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 07 July 2008

Check for updates

Qualifiers

Research-article

Conference

SCA08

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA08: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

July 7 - 9, 2008

Dublin, Ireland

Acceptance Rates

SCA '08 Paper Acceptance Rate 24 of 60 submissions, 40%;

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
456
Total Downloads

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

Reflects downloads up to 05 Mar 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
Friston SDoboš JWong CFan CMontero SSteed APolys NMcCann MLiu FPlesch A(2019)Rectangular Selection of Components in Large 3D Models on the WebProceedings of the 24th International Conference on 3D Web Technology10.1145/3329714.3338125(1-9)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3329714.3338125
Bargteil AShinar T(2019)An introduction to physics-based animationACM SIGGRAPH 2019 Courses10.1145/3305366.3328050(1-57)Online publication date: 28-Jul-2019
https://dl.acm.org/doi/10.1145/3305366.3328050
Bargteil AShinar T(2018)An introduction to physics-based animationACM SIGGRAPH 2018 Courses10.1145/3214834.3214849(1-1)Online publication date: 12-Aug-2018
https://dl.acm.org/doi/10.1145/3214834.3214849
Erleben K(2018)Methodology for Assessing Mesh-Based Contact Point MethodsACM Transactions on Graphics10.1145/309623937:3(1-30)Online publication date: 27-Jul-2018
https://dl.acm.org/doi/10.1145/3096239
Jacobson A(2017)Generalized MatryoshkaComputer Graphics Forum10.1111/cgf.1324236:5(27-35)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1111/cgf.13242
Lu LRahimian AZorin D(2017)Contact-aware simulations of particulate Stokesian suspensionsJournal of Computational Physics10.1016/j.jcp.2017.06.039347:C(160-182)Online publication date: 15-Oct-2017
https://dl.acm.org/doi/10.1016/j.jcp.2017.06.039
Marvie JSourimant GDufay ARonfard RChristie MGalvane QJhala A(2016)Contact visualizationProceedings of the Eurographics Workshop on Intelligent Cinematography and Editing10.5555/3056983.3056985(9-13)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3056983.3056985
Koschier DDeul CBender JSolenthaler BTeschner MKavan LWojtan C(2016)Hierarchical hp-adaptive signed distance fieldsProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2982818.2982844(189-198)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.5555/2982818.2982844
Wu KYuksel CWyman CYuksel C(2016)Real-time hair mesh simulationProceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/2856400.2856412(59-64)Online publication date: 27-Feb-2016
https://dl.acm.org/doi/10.1145/2856400.2856412
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten