“Deforming meshes that split and merge” by Wojtan, Thürey, Gross and Turk

  • ©Chris Wojtan, Nils Thürey, Markus Gross, and Greg Turk




    Deforming meshes that split and merge



    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.


    1. Adalsteinsson, D., and Sethian, J. 1995. A fast level set method for propagating interfaces. J. Comp. Phys. 118, 269–277. Google ScholarDigital Library
    2. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. 26, 3, 48. Google ScholarDigital Library
    3. Bargteil, A. W., Goktekin, T. G., O’Brien, J. F., and Strain, J. A. 2006. A semi-Lagrangian contouring method for fluid simulation. ACM Trans. Graph. 25, 1, 19–38. Google ScholarDigital Library
    4. Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A finite element method for animating large viscoplastic flow. ACM Trans. Graph. 26, 3, 16. Google ScholarDigital Library
    5. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. 26, 3, 100. Google ScholarDigital Library
    6. Bischoff, S., and Kobbelt, L. 2003. Sub-voxel topology control for level-set surfaces. Comput. Graph. Forum 22(3), 273–280.Google ScholarCross Ref
    7. Bischoff, S., and Kobbelt, L. 2005. Structure preserving cad model repair. Comput. Graph. Forum 24(3), 527–536.Google ScholarCross Ref
    8. Bredno, J., Lehmann, T. M., and Spitzer, K. 2003. A general discrete contour model in two, three, and four dimensions for topology-adaptive multichannel segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 25, 5, 550–563. Google ScholarDigital Library
    9. Bridson, R. 2008. Fluid Simulation for Computer Graphics. A K Peters. Google ScholarDigital Library
    10. Brochu, T. 2006. Fluid Animation with Explicit Surface Meshes and Boundary-Only Dynamics. Master’s thesis, University of British Columbia.Google Scholar
    11. Du, J., Fix, B., Glimm, J., Jiaa, X., and Lia, X. 2006. A simple package for front tracking. J. Comp. Phys 213, 2, 613–628. Google ScholarDigital Library
    12. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comput. Phys. 183, 1, 83–116. Google ScholarDigital Library
    13. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3, 736–744. Google ScholarDigital Library
    14. Foster, N., and Fedkiw, R. 2001. Practical animation of liquids. In SIGGRAPH ’01, ACM, New York, NY, USA, 23–30. Google ScholarDigital Library
    15. Glimm, J., Grove, J. W., and Li, X. L. 1998. Three dimensional front tracking. SIAM J. Sci. Comp 19, 703–727. Google ScholarDigital Library
    16. Goktekin, T. G., Bargteil, A. W., and O’Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Trans. Graph. 23, 3, 463–468. Google ScholarDigital Library
    17. Guendelman, E., Selle, A., Losasso, F., and Fedkiw, R. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Trans. Graph. 24, 3, 973–981. Google ScholarDigital Library
    18. Hieber, S. E., and Koumoutsakos, P. 2005. A Lagrangian particle level set method. J. Comp. Phys. 210, 1, 342–367. Google ScholarDigital Library
    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.Google ScholarCross Ref
    20. Hong, J.-M., and Kim, C.-H. 2005. Discontinuous fluids. ACM Trans. Graph. 24, 3, 915–920. Google ScholarDigital Library
    21. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3, 13. Google ScholarDigital Library
    22. Jiao, X. 2007. Face offsetting: A unified approach for explicit moving interfaces. J. Comput. Phys. 220, 2, 612–625. Google ScholarDigital Library
    23. Kass, M., and Miller, G. 1990. Rapid, stable fluid dynamics for computer graphics. In SIGGRAPH ’90, ACM, New York, NY, USA, 49–57. Google ScholarDigital Library
    24. Kass, M., Witkin, A., and Terzopoulos, D. 1988. Snakes: active contour models. Int. Journal Computer Vision 1(4), 321–331.Google ScholarCross Ref
    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. Google ScholarDigital Library
    26. Kim, B., Liu, Y., Llamas, I., Jiao, X., and Rossignac, J. 2007. Simulation of bubbles in foam with the volume control method. ACM Trans. Graph. 26, 3, 98. Google ScholarDigital Library
    27. Kim, T., Thuerey, N., James, D., and Gross, M. 2008. Wavelet turbulence for fluid simulation. ACM Trans. Graph. 27, 3, 50. Google ScholarDigital Library
    28. Lachaud, J.-O., and Taton, B. 2005. Deformable model with a complexity independent from image resolution. Comput. Vis. Image Underst. 99, 3, 453–475. Google ScholarDigital Library
    29. Liu, X.-D., Osher, S., and Chan, T. 1994. Weighted essentially non-oscillatory schemes. J. Comput. Phys. 115, 1, 200–212. Google ScholarDigital Library
    30. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In SIGGRAPH ’87, ACM, New York, NY, USA, 163–169. Google ScholarDigital Library
    31. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. 25, 3, 812–819. Google ScholarDigital Library
    32. McInerney, T., and Terzopoulos, D. 2000. T-snakes: Topology adaptive snakes. Medical Image Analysis 4, 2, 73–91.Google ScholarCross Ref
    33. Mihalef, V., Metaxas, D., and Sussman, M. 2007. Textured liquids based on the marker level set. Computer Graphics Forum 26, 3, 457–466.Google ScholarCross Ref
    34. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. Proc. of the ACM Siggraph/Eurographics Symposium on Computer Animation, 154–159. Google ScholarDigital Library
    35. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471–478. Google ScholarDigital Library
    36. Nooruddin, F. S., and Turk, G. 2000. Interior/exterior classification of polygonal models. In VIS ’00: Proceedings of the conference on Visualization ’00, IEEE Computer Society Press, Los Alamitos, CA, USA, 415–422. Google ScholarDigital Library
    37. O’Brien, J. F., and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In SIGGRAPH ’99, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 137–146. Google ScholarDigital Library
    38. Osher, S., and Sethian, J. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics 79, 12–49. Google ScholarDigital Library
    39. Pauly, M., Keiser, R., Adams, B., Dutré;, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. 24, 3, 957–964. Google ScholarDigital Library
    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.Google Scholar
    41. Reynolds, C. W., 1992. Adaptive polyhedral resampling for vertex flow animation, unpublished. http://www.red3d.com/cwr/papers/1992/df.html.Google Scholar
    42. Rosenfeld, A. 1979. Digital topology. American Mathematical Monthly 86, 621–630.Google ScholarCross Ref
    43. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable maccormack method. J. Sci. Comput. 35, 2–3, 350–371. Google ScholarDigital Library
    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.Google ScholarCross Ref
    45. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods, 2nd ed. Cambridge Monograph on Applies and Computational Mathematics. Cambridge University Press, Cambridge, U.K.Google Scholar
    46. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid simulation of deformable solids. In Proc. Symposium on Computer Animation, 81–90. Google ScholarDigital Library
    47. Stam, J. 1999. Stable fluids. In SIGGRAPH ’99, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 121–128. Google ScholarDigital Library
    48. Strain, J. A. 2001. A fast semi-lagrangian contouring method for moving interfaces. Journal of Computational Physics 169, 1 (May), 1–22.Google Scholar
    49. Sussman, M. 2003. A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles. J. Comp. Phys. 187/1. Google ScholarDigital Library
    50. Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 306–331.Google ScholarCross Ref
    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.Google Scholar
    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.Google Scholar
    53. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. Graph. 25, 3, 826–834. Google ScholarDigital Library
    54. Varadhan, G., Krishnan, S., Sriram, T., and Manocha, D. 2004. Topology preserving surface extraction using adaptive subdivision. In Proceedings of SGP ’04, ACM, 235–244. Google ScholarDigital Library
    55. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. ACM Trans. Graph. 27, 3, 47. Google ScholarDigital Library
    56. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3, 965–972. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: