research-article

An adaptive virtual node algorithm with robust mesh cutting

Authors:

Chenfanfu Jiang,

Craig Schroeder,

Joseph TeranAuthors Info & Claims

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

Pages 77 - 85

Published: 21 July 2015 Publication History

Abstract

We present a novel virtual node algorithm (VNA) for changing tetrahedron mesh topology to represent arbitrary cutting triangulated surfaces. Our approach addresses a number of shortcomings in the original VNA of [MBF04]. First, we generalize the VNA so that cuts can pass through tetrahedron mesh vertices and lie on mesh edges and faces. The original algorithm did not make sense for these cases and required often ambiguous perturbation of the cutting surface to avoid them. Second, we develop an adaptive approach to the definition of embedded material used for element duplication. The original algorithm could only handle a limited number of configurations which restricted cut surfaces to have curvature at the scale of the tetrahedron elements. Our adaptive approach allows for cut surfaces with curvatures independent of the embedding tetrahedron mesh resolution. Finally, we present a novel, provably-robust floating point mesh intersection routine that accurately registers triangulated surface cuts against the background tetrahedron mesh without the need for exact arithmetic.

References

[1]

{BG00} Bielser D., Gross M. H.: Interactive simulation of surgical cuts. In Proc. Pac. Conf. Comp. Graph. App. (2000), pp. 116--442. 2

Digital Library

[2]

{BHTF07} Bao Z., Hong J., Teran J., Fedkiw R.: Fracturing rigid materials. IEEE Trans. Vis. Comp. Graph. 13 (2007), 370--378. 2

Digital Library

[3]

{BSM*02} Bruyns C. D., Senger S., Menon A., Montgomery K., Wildermuth S., Boyle R.: A survey of interactive mesh-cutting techniques and a new method for implementing generalized interactive mesh cutting using virtual tools. Journal Vis. Comp. Anim. 13 (2002), 21--42. 2

[4]

{BWHT07} Bargteil A., Wojtan C., Hodgins J., Turk G.: A finite element method for animating large viscoplastic flow. ACM Trans. Graph. 26 (2007), 19--38. 2

Digital Library

[5]

{CDA00} Cotin S., Delingette H., Ayache N.: A hybrid elastic model for real-time cutting, deformations, and force feedback for surgery training and simulation. Vis. Comp. 16 (2000), 437--452. 2

[6]

{CGC*02} Capell S., Green S., Curless B., Duchamp T., Popović Z.: Interactive skeleton-driven dynamic deformations. ACM Trans. Graph. 21 (2002), 586--593. 2

Digital Library

[7]

{CWSO13} Clausen P., Wicke M., Shewchuk J. R., O'Brien J. F.: Simulating liquids and solid-liquid interactions with lagrangian meshes. ACM Trans. Graph. 32 (2013), 17:1--15. 2

Digital Library

[8]

{FDA02} Forest C., Delingette H., Ayache N.: Removing tetrahedra from a manifold mesh. In Proc. Comp. Anim. (2002), pp. 225--229. 2

Digital Library

[9]

{FG99} Frisken-Gibson S. F.: Using linked volumes to model object collisions, deformation, cutting, carving, and joining. Trans. Vis. Comp. Graph. 5 (1999), 333--348. 2

Digital Library

[10]

{FVDPT97} Faloutsos P., Van De Panne M., Terzopoulos D.: Dynamic free-form deformations for animation synthesis. IEEE Trans. Vis. Comp. Graph. 3 (1997), 201--214. 2

Digital Library

[11]

{GBO04} Goktekin T., Bargteil A., O'Brien J.: A method for animating viscoelastic fluids. ACM Trans. Graph. 23 (2004), 463--468. 2

Digital Library

[12]

{GBT07} Gissler M., Becker M., Teschner M.: Constraint sets for topology-changing finite element models. In Virt. Real. Inter. Phys. Sim. (2007), pp. 21--26. 2

[13]

{HJST13} Hegemann J., Jiang C., Schroeder C., Teran J. M.: A level set method for ductile fracture. In Proc. Symp. Comp. Anim. (2013), pp. 193--201. 2

Digital Library

[14]

{IO06} Iben H. N., O'Brien J. F.: Generating surface crack patterns. In Proc. Symp. Comp. Anim. (2006), pp. 177--185. 2

Digital Library

[15]

{IO09} Iben H., O'Brien J.: Generating surface crack patterns. Graph. Mod. 71 (2009), 198--208. 2

Digital Library

[16]

{JBB*10} Jeřábková L., Bousquet G., Barbier S., Faure F., Allard J.: Volumetric modeling and interactive cutting of deformable bodies. Progress Biophs. Mol. Bio. 103 (2010), 217--224. 2

[17]

{KMOD09} Kharevych L., Mullen P., Owhadi H., Desbrun M.: Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28, 3 (2009), 51:1--51:8. 2

Digital Library

[18]

{MBF04} Molino N., Bao Z., Fedkiw R.: A virtual node algorithm for changing mesh topology during simulation. In ACM SIGGRAPH (2004), pp. 385--392. 1, 2

Digital Library

[19]

{MCK13} Müller M., Chentanez N., Kim T.-Y.: Real time dynamic fracture with volumetric approximate convex decompositions. ACM Trans. Graph. 32, 4 (2013), 115:1--115:10. 2

Digital Library

[20]

{MG04} Müller M., Gross M.: Interactive virtual materials. In Proc. Graph. Int. (2004), pp. 239--246. 2

Digital Library

[21]

{MK00} Mor A. B., Kanade T.: Modifying soft tissue models: Progressive cutting with minimal new element creation. In Proc. MICCAI (2000), pp. 598--607. 2

Digital Library

[22]

{MMA99} Mazarak O., Martins C., Amanatides J.: Animating exploding objects. In Graph. Int. (1999), pp. 211--218. 2

Digital Library

[23]

{MMDJ01} Müller M., McMillan L., Dorsey J., Jagnow R.: Real-time simulation of deformation and fracture of stiff materials. In Proc. Eurographics Workshop Comp. Anim. Sim. (2001), pp. 113--124. 2

Digital Library

[24]

{NF99} Neff M., Fiume E.: A visual model for blast waves and fracture. In Proc. Graph. Int. (1999), pp. 193--202. 2

Digital Library

[25]

{NKJF09} Nesme M., Kry P. G., Jeřábková L., Faure F.: Preserving topology and elasticity for embedded deformable models. In ACM SIGGRAPH (2009), pp. 52:1--52:9. 2

Digital Library

[26]

{NTB*91} Norton A., Turk G., Bacon B., Gerth J., Sweeney P.: Animation of fracture by physical modeling. Vis. Comp. 7 (1991), 210--219. 2

Digital Library

[27]

{NvdS00} Nienhuys H.-W., van der Stappen A. F.: Combining finite element deformation with cutting for surgery simulations. In Eurograph. Short Present. (2000), pp. 43--52. 2

[28]

{OBH02} O'Brien J., Bargteil A., Hodgins J.: Graphical modeling and animation of ductile fracture. ACM Trans. Graph. 21 (2002), 291--294. 2

Digital Library

[29]

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

Digital Library

[30]

{PKA*05} Pauly M., Keiser R., Adams B., Dutré P., Gross M., Guibas L.: Meshless animation of fracturing solids. ACM Trans. Graph. 24 (2005), 957--964. 2

Digital Library

[31]

{PO09} Parker E., O'Brien J.: Real-time deformation and fracture in a game environment. In Proc. Symp. Comp. Anim. (2009), pp. 165--175. 2

Digital Library

[32]

{SDF07} Sifakis E., Der K., Fedkiw R.: Arbitrary cutting of deformable tetrahedralized objects. In Proc. Symp. Comp. Anim. (2007), pp. 73--80. 1, 2, 3, 6

Digital Library

[33]

{SP86} Sederberg T., Parry S.: Free-form deformation of solid geometric models. In ACM SIGGRAPH (1986), pp. 151--160. 2

Digital Library

[34]

{SSF09} Su J., Schroeder C., Fedkiw R.: Energy stability and fracture for frame rate rigid body simulations. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2009), pp. 155--164. 2

Digital Library

[35]

{SWB01} Smith J., Witkin A., Baraff D.: Fast and controllable simulation of the shattering of brittle objects. Comp. Graph. Forum 20 (2001), 81--90. 2

[36]

{TF88} Terzopoulos D., Fleischer K.: Modeling inelastic deformation: viscolelasticity, plasticity, fracture. In ACM SIGGRAPH (1988), pp. 269--278. 2

Digital Library

[37]

{TSB*05} Teran J., Sifakis E., Blemker S., Ng-Thowhing V., Lau C., Fedkiw R.: Creating and simulating skeletal muscle from the visible human data set. IEEE Trans. Vis. Comp. Graph. 11 (2005), 317--328. 2

Digital Library

[38]

{WRK*10} Wicke M., Ritchie D., Klingner B., Burke S., Shewchuk J., O'Brien J.: Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. 29 (2010), 49:1--49:11. 2

Digital Library

[39]

{WT08} Wojtan C., Turk G.: Fast viscoelastic behavior with thin features. In ACM SIGGRAPH (2008), pp. 47:1--47:8. 2

Digital Library

[40]

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

Digital Library

[41]

{WWD14} Wu J., Westermann R., Dick C.: Physically-based simulation of cuts in deformable bodies: A survey. In Eurograph. State-of-the-Art Report (2014). 2

Cited By

Li JLiu TKavan LChen B(2021)Interactive cutting and tearing in projective dynamics with progressive cholesky updatesACM Transactions on Graphics10.1145/3478513.348050540:6(1-12)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480505
Wolper JChen YLi MFang YQu ZLu JCheng MJiang C(2020)AnisoMPMACM Transactions on Graphics10.1145/3386569.339242839:4(37:1-37:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392428
Wolper JFang YLi MLu JGao MJiang C(2019)CD-MPMACM Transactions on Graphics10.1145/3306346.332294938:4(1-15)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322949
Show More Cited By

Index Terms

An adaptive virtual node algorithm with robust mesh cutting
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

Adaptive mesh coarsening for quadrilateral and hexahedral meshes

Mesh adaptation methods can improve the efficiency and accuracy of solutions to computational modeling problems. In many applications involving quadrilateral and hexahedral meshes, local modifications which maintain the original element type are ...
Mesh simplification algorithm based on n-edge mesh collapse
ICAT'06: Proceedings of the 16th international conference on Advances in Artificial Reality and Tele-Existence

This paper presents a method for dividing the triangle mesh into n-edge mesh and puts forward a new mesh simplification algorithm based on n-edge mesh collapse. An n-edge mesh can be in the form of an edge, a triangle or a quadrangle, it depends on the ...
A consistent octree hanging node elimination algorithm for hexahedral mesh generation

A new algorithm for hanging node elimination in octree structures is developed. The proposed algorithm utilizes hanging node elimination by refinement templates and a new mesh conditioning technique based on decoupling templates. Refinement templates ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2014

191 pages

Conference Chairs:
Kenny Erleben
University of Copenhagen, Denmark
,
Julien Pettré
Inria, France

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: 21 July 2015

Check for updates

Qualifiers

Research-article

Conference

SCA'14

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA'14: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

July 21 - 23, 2014

Copenhagen, Denmark

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
126
Total Downloads

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

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JLiu TKavan LChen B(2021)Interactive cutting and tearing in projective dynamics with progressive cholesky updatesACM Transactions on Graphics10.1145/3478513.348050540:6(1-12)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480505
Wolper JChen YLi MFang YQu ZLu JCheng MJiang C(2020)AnisoMPMACM Transactions on Graphics10.1145/3386569.339242839:4(37:1-37:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392428
Wolper JFang YLi MLu JGao MJiang C(2019)CD-MPMACM Transactions on Graphics10.1145/3306346.332294938:4(1-15)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322949
Li YBarbič J(2018)Immersion of self-intersecting solids and surfacesACM Transactions on Graphics10.1145/3197517.320132737:4(1-14)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201327
Hu YFang YGe ZQu ZZhu YPradhana AJiang C(2018)A moving least squares material point method with displacement discontinuity and two-way rigid body couplingACM Transactions on Graphics10.1145/3197517.320129337:4(1-14)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201293
Zhang JDuan FZhou MJiang DWang XWu ZHuang YDu GLiu SZhou PShang X(2018)Stable and realistic crack pattern generation using a cracking node methodFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5511-912:4(777-797)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11704-016-5511-9
Manteaux PWojtan CNarain RRedon SFaure FCani M(2017)Adaptive Physically Based Models in Computer GraphicsComputer Graphics Forum10.1111/cgf.1294136:6(312-337)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1111/cgf.12941
Azevedo VBatty COliveira M(2016)Preserving geometry and topology for fluid flows with thin obstacles and narrow gapsACM Transactions on Graphics10.1145/2897824.292591935:4(1-12)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2897824.2925919
Wu JWestermann RDick C(2015)A Survey of Physically Based Simulation of Cuts in Deformable BodiesComputer Graphics Forum10.1111/cgf.1252834:6(161-187)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1111/cgf.12528

View Options

Get Access

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