Deforming meshes that split and merge

ABSTRACT

We present a method for accurately tracking the moving surface of deformable materials in a manner that gracefully handles topological changes. We employ a Lagrangian surface tracking method, and we use a triangle mesh for our surface representation so that fine features can be retained. We make topological changes to the mesh by first identifying merging or splitting events at a particular grid resolution, and then locally creating new pieces of the mesh in the affected cells using a standard isosurface creation method. We stitch the new, topologically simplified portion of the mesh to the rest of the mesh at the cell boundaries. Our method detects and treats topological events with an emphasis on the preservation of detailed features, while simultaneously simplifying those portions of the material that are not visible. Our surface tracker is not tied to a particular method for simulating deformable materials. In particular, we show results from two significantly different simulators: a Lagrangian FEM simulator with tetrahedral elements, and an Eulerian grid-based fluid simulator. Although our surface tracking method is generic, it is particularly well-suited for simulations that exhibit fine surface details and numerous topological events. Highlights of our results include merging of viscoplastic materials with complex geometry, a taffy-pulling animation with many fold and merge events, and stretching and slicing of stiff plastic material.

REFERENCES

• 1: David Adalsteinsson , James A. Sethian, A fast level set method for propagating interfaces, Journal of Computational Physics, v.118 n.2, p.269-277, May 1995 [doi>10.1006/jcph.1995.1098]
• 2: Bart Adams , Mark Pauly , Richard Keiser , Leonidas J. Guibas, Adaptively sampled particle fluids, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 3: Adam W. Bargteil , Tolga G. Goktekin , James F. O'brien , John A. Strain, A semi-Lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), v.25 n.1, p.19-38, January 2006 [doi>10.1145/1122501.1122503]
• 4: Adam W. Bargteil , Chris Wojtan , Jessica K. Hodgins , Greg Turk, A finite element method for animating large viscoplastic flow, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 5: Christopher Batty , Florence Bertails , Robert Bridson, A fast variational framework for accurate solid-fluid coupling, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 6: Bischoff, S., and Kobbelt, L. 2003. Sub-voxel topology control for level-set surfaces. Comput. Graph. Forum 22(3), 273--280.
• 7: Bischoff, S., and Kobbelt, L. 2005. Structure preserving cad model repair. Comput. Graph. Forum 24(3), 527--536.
• 8: Jörg Bredno , Thomas M. Lehmann , Klaus Spitzer, A General Discrete Contour Model in Two, Three, and Four Dimensions for Topology-Adaptive Multichannel Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.550-563, May 2003 [doi>10.1109/TPAMI.2003.1195990]
• 9: Robert Bridson, Fluid Simulation, A. K. Peters, Ltd., Natick, MA, 2008
• 10: Brochu, T. 2006. Fluid Animation with Explicit Surface Meshes and Boundary-Only Dynamics. Master's thesis, University of British Columbia.
• 11: Jian Du , Brian Fix , James Glimm , Xicheng Jia , Xiaolin Li , Yuanhua Li , Lingling Wu, A simple package for front tracking, Journal of Computational Physics, v.213 n.2, p.613-628, 10 April 2006 [doi>10.1016/j.jcp.2005.08.034]
• 12: Douglas Enright , Ronald Fedkiw , Joel Ferziger , Ian Mitchell, A hybrid particle level set method for improved interface capturing, Journal of Computational Physics, v.183 n.1, p.83-116, November 20, 2002 [doi>10.1006/jcph.2002.7166]
• 13: Douglas Enright , Stephen Marschner , Ronald Fedkiw, Animation and rendering of complex water surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 14: Nick Foster , Ronald Fedkiw, Practical animation of liquids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.23-30, August 2001 [doi>10.1145/383259.383261]
• 15: James Glimm , John W. Grove , Xiao Lin Li , Keh-ming Shyue , Yanni Zeng , Qiang Zhang, Three-Dimensional Front Tracking, SIAM Journal on Scientific Computing, v.19 n.3, p.703-727, May 1998 [doi>10.1137/S1064827595293600]
• 16: Tolga G. Goktekin , Adam W. Bargteil , James F. O'Brien, A method for animating viscoelastic fluids, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 17: Eran Guendelman , Andrew Selle , Frank Losasso , Ronald Fedkiw, Coupling water and smoke to thin deformable and rigid shells, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 18: Simone E. Hieber , Petros Koumoutsakos, A Lagrangian particle level set method, Journal of Computational Physics, v.210 n.1, p.342-367, 20 November 2005 [doi>10.1016/j.jcp.2005.04.013]
• 19: Hirt, C. W., and Nichols, B. D. 1981. Volume of Fluid (VOF) Method for the Dynamics of Free Boundaries. J. Comp. Phys. 39, 201--225.
• 20: Jeong-Mo Hong , Chang-Hun Kim, Discontinuous fluids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 21: Geoffrey Irving , Craig Schroeder , Ronald Fedkiw, Volume conserving finite element simulations of deformable models, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 22: Xiangmin Jiao, Face offsetting: A unified approach for explicit moving interfaces, Journal of Computational Physics, v.220 n.2, p.612-625, January, 2007 [doi>10.1016/j.jcp.2006.05.021]
• 23: Michael Kass , Gavin Miller, Rapid, stable fluid dynamics for computer graphics, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.49-57, September 1990, Dallas, TX, USA
• 24: Kass, M., Witkin, A., and Terzopoulos, D. 1988. Snakes: active contour models. Int. Journal Computer Vision 1(4), 321--331.
• 25: Keiser, R., Adams, B., Gasser, D., Bazzi, P., Dutre, P., and Gross, M. 2005. A unified Lagrangian approach to solid-fluid animation. Proc. of the 2005 Eurographics Symposium on Point-Based Graphics.
• 26: Byungmoon Kim , Yingjie Liu , Ignacio Llamas , Xiangmin Jiao , Jarek Rossignac, Simulation of bubbles in foam with the volume control method, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 27: Theodore Kim , Nils Thürey , Doug James , Markus Gross, Wavelet turbulence for fluid simulation, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 28: J.-O. Lachaud , B. Taton, Deformable model with a complexity independent from image resolution, Computer Vision and Image Understanding, v.99 n.3, p.453-475, September 2005 [doi>10.1016/j.cviu.2005.04.002]
• 29: Xu-Dong Liu , Stanley Osher , Tony Chan, Weighted essentially non-oscillatory schemes, Journal of Computational Physics, v.115 n.1, p.200-212, Nov. 1994 [doi>10.1006/jcph.1994.1187]
• 30: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 31: Frank Losasso , Tamar Shinar , Andrew Selle , Ronald Fedkiw, Multiple interacting liquids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 32: McInerney, T., and Terzopoulos, D. 2000. T-snakes: Topology adaptive snakes. Medical Image Analysis 4, 2, 73--91.
• 33: Mihalef, V., Metaxas, D., and Sussman, M. 2007. Textured liquids based on the marker level set. Computer Graphics Forum 26, 3, 457--466.
• 34: Matthias Müller , David Charypar , Markus Gross, Particle-based fluid simulation for interactive applications, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 35: Matthias Müller , Bruno Heidelberger , Matthias Teschner , Markus Gross, Meshless deformations based on shape matching, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 36: F. S. Nooruddin , Greg Turk, Interior/exterior classification of polygonal models, Proceedings of the conference on Visualization '00, p.415-422, October 2000, Salt Lake City, Utah, United States
• 37: 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]
• 38: Stanley Osher , James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, v.79 n.1, p.12-49, Nov. 1988 [doi>10.1016/0021-9991(88)90002-2]
• 39: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 40: Pons, J.-P., and Boissonnat, J.-D. 2007. Delaunay deformable models: Topology-adaptive meshes based on the restricted Delaunay triangulation. Proceedings of CVPR '07, 1--8.
• 41: Reynolds, C. W., 1992. Adaptive polyhedral resampling for vertex flow animation, unpublished. http://www.red3d.com/cwr/papers/1992/df.html.
• 42: Rosenfeld, A. 1979. Digital topology. American Mathematical Monthly 86, 621--630.
• 43: Andrew Selle , Ronald Fedkiw , Byungmoon Kim , Yingjie Liu , Jarek Rossignac, An Unconditionally Stable MacCormack Method, Journal of Scientific Computing, v.35 n.2-3, p.350-371, June 2008 [doi>10.1007/s10915-007-9166-4]
• 44: Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. Proc. of the National Academy of Sciences of the USA 93, 4 (February), 1591--1595.
• 45: Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods, 2^nd ed. Cambridge Monograph on Applies and Computational Mathematics. Cambridge University Press, Cambridge, U.K.
• 46: 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
• 47: Jos Stam, Stable fluids, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.121-128, July 1999 [doi>10.1145/311535.311548]
• 48: Strain, J. A. 2001. A fast semi-lagrangian contouring method for moving interfaces. Journal of Computational Physics 169, 1 (May), 1--22.
• 49: Mark Sussman, A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles, Journal of Computational Physics, v.187 n.1, p.110-136, May 2003 [doi>10.1016/S0021-9991(03)00087-1]
• 50: Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 306--331.
• 51: Terzopoulos, D., Platt, J., and Fleischer, K. 1989. Heating and melting deformable models (from goop to glop). In the Proceedings of Graphics Interface, 219--226.
• 52: Thürey, N., and Rüde, U. 2004. Free Surface Lattice-Boltzmann fluid simulations with and without level sets. Proc. of Vision, Modelling, and Visualization VMV, 199--208.
• 53: Adrien Treuille , Andrew Lewis , Zoran Popović, Model reduction for real-time fluids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 54: Gokul Varadhan , Shankar Krishnan , TVN Sriram , Dinesh Manocha, Topology preserving surface extraction using adaptive subdivision, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057464]
• 55: Chris Wojtan , Greg Turk, Fast viscoelastic behavior with thin features, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 56: Yongning Zhu , Robert Bridson, Animating sand as a fluid, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.8 Partial Differential Equations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory

Keywords:
deformable meshes, fluid simulation, physically based animation, topological control