Article

Collision between deformable objects using fast-marching on tetrahedral models

Authors:

C. ChaillouAuthors Info & Claims

SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation

Pages 121 - 129

https://doi.org/10.1145/1028523.1028540

Published: 27 August 2004 Publication History

Abstract

This paper presents an approach to handling collision between deformable objects using tetrahedral decomposition. The tetrahedral volumetric model is often used to simulate deformable objects that handle cuts and splits. Interaction between such objects in a complex environment is still an open problem in interactive simulation. This paper is mainly focused on obtaining a fast computation of a reliable penalty response. The method consists in using an approximated distance map to compute a penalty based response. We propose to compute the distances to the boundary using a modified "Closest Point" algorithm derived from Fast Marching. The presented algorithm, inspired by the [FL01], has the advantage of computing rapidly the "Closest Point" in the volumetric tetrahedral mesh without any use of an additional computation grid. From the resulting distance map a response is computed using a new "segment-in-object" response that offers more reliable results than the "point-in-object" generally used in previous works. Using this collision model, simulation at interactive rate can be considered in an environment composed of objects that can be deformed and cut.

Supplementary Material

JPG File (p121-marchal_fig14.jpg)

Download
3.60 KB

JPG File (p121-marchal_fig15.jpg)

Download
6.77 KB

JPG File (p121-marchal_fig18.jpg)

Download
24.61 KB

AVI File (p121-marchal_fig14.avi)

Supplemental video for figure 14

Download
540.71 KB

AVI File (p121-marchal_fig15.avi)

Supplemental video for figure 15

Download
2.00 MB

AVI File (p121-marchal_fig18.avi)

Supplemental video for figure 18

Download
2.36 MB

References

[1]

{BWK03} Baraff D., Witkin A., Kass M.: Untangling cloth. Proceedings of ACM SIGGRAPH (2003).

Digital Library

[2]

{Cam97} Cameron S.: Enhancing gjk: computing minimum and penetration distances between convex polyhedra, 1997.

[3]

{CLMP95} Cohen J., Lin M., Manocha D., Ponamgi M.: I-collide: An interactive and exact collision detection system for large-scale environments. In Proc. ACM Interactive 3D Graphics Conf (1995), pp. 189--196.

Digital Library

[4]

{DMC02} Davanne J., Meseure P., Chaillou C.: Stable haptic interaction in a dynamic virtual environment. In Proceeding of IROS (2002).

[5]

{EL01} Ehmann S. A., Lin M. C.: Accurate and fast proximity queries between polyhedra using surface decomposition. In Proc. of Eurographics (2001).

[6]

{FG03} F. Ganovelli F. Ponchio C. R.: Fast tetrahedron-tetrahedron overlap algorithm. ACM Journal of Graphics Tools 7-2 (2003).

[7]

{FL01} Fisher S., Lin M.: Fast penetration depth estimation for elastic bodies using deformed distance fields. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2001).

[8]

{GBF03} Guendelman E., Bridson R., Fedkiw R.: Nonconvex rigid bodies with stacking. In SIGGRAPH (2003), pp. 871--878.

Digital Library

[9]

{Gei00} Geiger B.: Real-time collision detection and response for complex environments. In Proc. CGI (2000).

Digital Library

[10]

{GR} Geuzaine C., Remacle J.-F.: Gmesh. http://www.geuze.org/gmesh.

[11]

{GRLM03} Govindaraju N. K., Redon S., Lin M. C., Manocha D.: Cullide: Interactive collision detection between complex models in large environments using graphics hardware. In ACM SIGGRAPH/Eurographics Graphics Hardware Proceedings (2003).

Digital Library

[12]

{HFL00} Hirota G., Fisher S., Lin M.: Simulation of Non-penetrating Elastic Bodies Using Distance Fields. Tech. Rep. TR00-018, University Of North Carolina, 23 2000.

Digital Library

[13]

{HTG03} Heidelberger B., Teschner M., Gross M.: Real-time volumetric intersections of deforming objects,. VMV Proceeding (2003), 461--468.

[14]

{Jam96} James A S.: A fast marching level set method for monotonically advancing fronts. In Proceedings of the National Academy of Sciences (1996), vol. 93, 4, pp. 1591--1595.

[15]

{KLM02} Kim Y. J., Lin M. C., Manocha D.: Deep: Dual-space expansion for estimating penetration depth between convex polytopes. In IEEE International Conference on Robotics and Automation (2002).

[16]

{LMP94} Lin M., Manocha D., Ponamgi M.: Fast algorithms for penetration and contact determination between non-convex polyhedral models, 1994.

[17]

{MB} Mauch S., Breen D.: A fast marching method of computing closest points. http://www.cco.caltech.edu/sean/closestpoint/closept.html.

[18]

{MBTF03} Molino N., Bridson R., Teran J., Fedkiw R.: A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In 12th Int. Meshing Roundtable (2003), pp. 103--114.

[19]

{OH99} O'Brien J. F., Hodgins J. K.: Graphical modeling and animation of brittle fracture. In The proceedings of ACM SIGGRAPH (1999), pp. 137--146.

Digital Library

[20]

{RJ98} Ron K., James A S.: Fast marching methods on triangulated domains. In Proceedings of the National Academy of Sciences (1998), vol. 95.

[21]

{SL00} Sundaraj K., Laugier C.: Fast contact localisation of moving deformable polyhedras. In IEEE Int. Conf. on Automation, Robotics, Control and Vision (2000).

[22]

{THM*03} Teschner M., Heidelberger B., Mueller M., Pomeranets D., Gross M.: Optimized spatial hashing for collision detection of deformable objects. VMV Proceeding (2003).

[23]

{Tsa02} Tsai Y. R.: Rapid and accurate computation of the distance function using grids. Journal of Computational Physics 178, 1 (may 2002), 175--195.

Digital Library

[24]

{vdB97} Van Den Bergen G.: Efficient collision detection of complex deformable models using aabb trees. Journal of Graphics Tools (1997).

Digital Library

[25]

{vdB99} Van Den Bergen G.: A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools: JGT 4, 2 (1999), 7--25.

Digital Library

Cited By

Rianto S(2020)A Virtual Reality Based Surgical Simulation as an Alternative of Halal Surgical Trainings and Better Surgical PlanningIOP Conference Series: Materials Science and Engineering10.1088/1757-899X/846/1/012020846:1(012020)Online publication date: 1-May-2020
https://doi.org/10.1088/1757-899X/846/1/012020
Friston SSteed A(2019)Real-Time Collision Detection for Deformable Characters with Radial FieldsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.285992425:8(2611-2622)Online publication date: 1-Aug-2019
https://doi.org/10.1109/TVCG.2018.2859924
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
Show More Cited By

Index Terms

Collision between deformable objects using fast-marching on tetrahedral models
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Fast tetrahedral meshing in the wild

We propose a new tetrahedral meshing method, fTetWild, to convert triangle soups into high-quality tetrahedral meshes. Our method builds on the TetWild algorithm, replacing the rational triangle insertion with a new incremental approach to construct and ...
Interruptible collision detection for deformable objects

This paper presents an approach to performing time-critical collision detection for deformable objects. The deformable objects are represented by dense meshes and their deformations are steered by a coarser mesh (reduced model) based on explicit finite ...
Collision detection for coarsely meshed deformable objects
CGIM '08: Proceedings of the Tenth IASTED International Conference on Computer Graphics and Imaging

Fast and accurate methods for collision detection of deformable bodies are essential in physically based interactive simulations and used in many applications including surgery simulations, computer games and Virtual Reality. As an efficient method for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation

August 2004

388 pages

ISBN:3905673142

Conference Chairs:
Norman Badler
University of Pennsylvania
,
Mathieu Desbrun
University of Southern California
,
Ronan Boulic,
Dinesh Pai

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: 27 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCA04

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA04: Symposium on Computer Animation 2004

August 27 - 29, 2004

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
886
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rianto S(2020)A Virtual Reality Based Surgical Simulation as an Alternative of Halal Surgical Trainings and Better Surgical PlanningIOP Conference Series: Materials Science and Engineering10.1088/1757-899X/846/1/012020846:1(012020)Online publication date: 1-May-2020
https://doi.org/10.1088/1757-899X/846/1/012020
Friston SSteed A(2019)Real-Time Collision Detection for Deformable Characters with Radial FieldsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.285992425:8(2611-2622)Online publication date: 1-Aug-2019
https://doi.org/10.1109/TVCG.2018.2859924
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
Barbič JJames D(2008)Six-DoF Haptic Rendering of Contact Between Geometrically Complex Reduced Deformable ModelsIEEE Transactions on Haptics10.1109/TOH.2008.11:1(39-52)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TOH.2008.1
Liu JPan W(2007)Automatic computation of range of motion for coherent contact maintenance/transition of moving scaled convex polyhedra2007 IEEE International Conference on Robotics and Biomimetics (ROBIO)10.1109/ROBIO.2007.4522348(1278-1284)Online publication date: Dec-2007
https://doi.org/10.1109/ROBIO.2007.4522348
Teran JSifakis EIrving GFedkiw RTerzopoulos DZordan VAnjyo KFaloutsos P(2005)Robust quasistatic finite elements and flesh simulationProceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation10.1145/1073368.1073394(181-190)Online publication date: 29-Jul-2005
https://dl.acm.org/doi/10.1145/1073368.1073394

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.

Media

Figures

Other

Tables

View Table of Contents