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

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