Arbitrary cutting of deformable tetrahedralized objects

ABSTRACT

We propose a flexible geometric algorithm for placing arbitrary cracks and incisions on tetrahedralized deformable objects. Although techniques based on remeshing can also accommodate arbitrary fracture patterns, this flexibility comes at the risk of creating sliver elements leading to models that are inappropriate for subsequent simulation. Furthermore, interactive applications such as virtual surgery simulation require both a relatively low resolution mesh for efficient simulation of elastic deformation and highly detailed surface geometry to facilitate accurate manipulation and cut placement. Thus, we embed a high resolution material boundary mesh into a coarser tetrahedral mesh using our cutting algorithm as a meshing tool, obtaining meshes that can be efficiently simulated while preserving surface detail. Our algorithm is similar to the virtual node algorithm in that we avoid sliver elements and their associated stringent timestep restrictions, but it is significantly more general allowing for the arbitrary cutting of existing cuts, sub-tetrahedron resolution (e.g. we cut a single tetrahedron into over a thousand pieces), progressive introduction of cuts while the object is deforming, and moreover the ability to accurately cut the high resolution embedded mesh.

REFERENCES

• 1: Daniel Bielser , Markus H. Gross, Interactive Simulation of Surgical Cuts, Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, p.116, October 03-05, 2000
• 2: Daniel Bielser , Pascal Glardon , Matthias Teschner , Markus Gross, A State Machine for Real-Time Cutting of Tetrahedral Meshes, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.377, October 08-10, 2003
• 3: Zhaosheng Bao , Jeong-Mo Hong , Joseph Teran , Ronald Fedkiw, Fracturing Rigid Materials, IEEE Transactions on Visualization and Computer Graphics, v.13 n.2, p.370-378, March 2007 [doi>10.1109/TVCG.2007.39]
• 4: {BMG99} Bielser D., Maiwald V. A., Gross M. H.: Interactive cuts through 3-dimensional soft tissue. In Eurographics (1999).
• 5: Clement Forest , Herve Delingette , Nicholas Ayache, Removing Tetrahedra from a Manifold Mesh, Proceedings of the Computer Animation, p.225, June 19-21, 2002
• 6: Xiaohu Guo , Xin Li , Yunfan Bao , Xianfeng Gu , Hong Qin, Meshless Thin-Shell Simulation Based on Global Conformal Parameterization, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.375-385, May 2006 [doi>10.1109/TVCG.2006.52]
• 7: {GO01} Ganovelli F., O'Sullivan C.: Animating cuts with on-the-fly re-meshing. In Eurographics 2001, Short Presentations Programme (2001).
• 8: {GSH*05} Gingold Y., Secord A., Han J., Grinspun E., Zorin D.: A discrete model for inelastic deformations of thin shells. In Poster, Eurographics/ACM SIGGRAPH Symp. on Comput. Anima. (2005).
• 9: {HTK98} Hirota K., Tanoue Y., Kaneko T.: Generation of crack patterns with a physical model. The Vis. Comput. 14 (1998), 126--187.
• 10: Rolf M. Koch , Markus H. Gross , Friedrich R. Carls , Daniel F. von Büren , George Fankhauser , Yoav I. H. Parish, Simulating facial surgery using finite element models, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.421-428, August 1996 [doi>10.1145/237170.237281]
• 11: Erwin Keeve , Sabine Girod , Paula Pfeifle , Bernd Girod, Anatomy-based facial tissue modeling using the finite element method, Proceedings of the 7th conference on Visualization '96, p.21-ff., October 28-29, 1996, San Francisco, California, United States
• 12: Frank Losasso , Geoffrey Irving , Eran Guendelman , Ron Fedkiw, Melting and Burning Solids into Liquids and Gases, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.343-352, May 2006 [doi>10.1109/TVCG.2006.51]
• 13: Neil Molino , Zhaosheng Bao , Ron Fedkiw, A virtual node algorithm for changing mesh topology during simulation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 14: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of Graphics Interface 2004, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 15: Andrew B. Mor , Takeo Kanade, Modifying Soft Tissue Models: Progressive Cutting with Minimal New Element Creation, Proceedings of the Third International Conference on Medical Image Computing and Computer-Assisted Intervention, p.598-607, October 11-14, 2000
• 16: Oleg Mazarak , Claude Martins , John Amanatides, Animating exploding objects, Proceedings of the 1999 conference on Graphics interface '99, p.211-218, September 1999, Kingston, Ontario, Canada
• 17: Matthias Müller , Leonard McMillan , Julie Dorsey , Robert Jagnow, Real-time simulation of deformation and fracture of stiff materials, Proceedings of the Eurographic workshop on Computer animation and simulation, p.113-124, September 02-03, 2001, Manchester, UK
• 18: {MTG04} Müller M., Teschner M., Gross M.: Physically-based simulation of objects represented by surface meshes. In Proc. Comput. Graph. Int. (June 2004), pp. 156--165.
• 19: Michael Neff , Eugene Fiume, A visual model for blast waves and fracture, Proceedings of the 1999 conference on Graphics interface '99, p.193-202, September 1999, Kingston, Ontario, Canada
• 20: Alan Norton , Greg Turk , Bob Bacon , John Gerth , Paula Sweeney, Animation of fracture by physical modeling, The Visual Computer: International Journal of Computer Graphics, v.7 n.4, p.210-219, July 1991 [doi>10.1007/BF01900837]
• 21: {NvdS00} Nienhuys H.-W., Van Der Stappen A. F.: Combining finite element deformation with cutting for surgery simulations. In Eurographics 2000, Short Presentations Programme (2000).
• 22: {NvdS01} Nienhuys H.-W., van der Stappen A. F.: Supporting cuts and finite element deformation in interactive surgery simulation. Tech. rep., Utrecht University, Institute for Information and Computing Sciences, 2001.
• 23: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 24: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 25: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 26: Steven Pieper , Joseph Rosen , David Zeltzer, Interactive graphics for plastic surgery: a task-level analysis and implementation, Proceedings of the 1992 symposium on Interactive 3D graphics, p.127-134, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147180]
• 27: Denis Steinemann , Matthias Harders , Markus Gross , Gabor Szekely, Hybrid Cutting of Deformable Solids, Proceedings of the IEEE conference on Virtual Reality, p.35-42, March 25-29, 2006 [doi>10.1109/VR.2006.74]
• 28: D. Serby , Matthias Harders , Gábor Székely, A New Approach to Cutting into Finite Element Models, Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention, p.425-433, October 14-17, 2001
• 29: Denis Steinemann , Miguel A. Otaduy , Markus Gross, Fast arbitrary splitting of deforming objects, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 30: Eftychios Sifakis , Tamar Shinar , Geoffrey Irving , Ronald Fedkiw, Hybrid simulation of deformable solids, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 31: {SWB01} Smith J., Witkin A., Baraff D.: Fast and controllable simulation of the shattering of brittle objects. In Comput. Graph. Forum, Duke D., Scopigno R., (Eds.), vol. 20(2). Blackwell Publishing, 2001, pp. 81--91.
• 32: {TF88a} Terzopoulos D., Fleischer K.: Deformable models. The Vis. Comput. 4, 6 (1988), 306--331.
• 33: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.269-278, June 1988
• 34: Joseph Teran , Eftychios Sifakis , Silvia S. Blemker , Victor Ng-Thow-Hing , Cynthia Lau , Ronald Fedkiw, Creating and Simulating Skeletal Muscle from the Visible Human Data Set, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.317-328, May 2005 [doi>10.1109/TVCG.2005.42]
• 35: {WSG05} Wicke M., Steinemann D., Gross M.: Efficient animation of point-sampled thin shells. In Proc. of Eurographics (2005), vol. 24.
• 36: Gary D. Yngve , James F. O'Brien , Jessica K. Hodgins, Animating explosions, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.29-36, July 2000 [doi>10.1145/344779.344801]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism