“Multimaterial mesh-based surface tracking” by Da, Batty and Grinspun

  • ©Fang Da, Christopher Batty, and Eitan Grinspun




    Multimaterial mesh-based surface tracking

Session/Category Title: Mesh-Based Simulation




    We present a triangle mesh-based technique for tracking the evolution of three-dimensional multimaterial interfaces undergoing complex deformations. It is the first non-manifold triangle mesh tracking method to simultaneously maintain intersection-free meshes and support the proposed broad set of multimaterial remeshing and topological operations. We represent the interface as a non-manifold triangle mesh with material labels assigned to each half-face to distinguish volumetric regions. Starting from proposed application-dependent vertex velocities, we deform the mesh, seeking a non-intersecting, watertight solution. This goal necessitates development of various collision-safe, label-aware non-manifold mesh operations: multimaterial mesh improvement; T1 and T2 processes, topological transitions arising in foam dynamics and multiphase flows; and multimaterial merging, in which a new interface is created between colliding materials. We demonstrate the robustness and effectiveness of our approach on a range of scenarios including geometric flows and multiphase fluid animation.


    1. Alexa, M. 2002. Recent advances in mesh morphing. Computer Graphics Forum 21, 2, 173–198.Google ScholarCross Ref
    2. Anderson, J. C., Garth, C., Duchaineau, M. A., and Joy, K. I. 2010. Smooth, volume-accurate material interface reconstruction. IEEE TVCG 16, 5, 802–814. Google ScholarDigital Library
    3. Bargteil, A. W., O’Brien, J. F., Goktekin, T. G., and Strain, J. A. 2006. A semi-Lagrangian contouring method for fluid simulation. ACM Trans. Graph. 25, 1 (Jan.), 19–38. Google ScholarDigital Library
    4. Batty, C., and Bridson, R. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. In Symposium on Computer Animation, 219–228. Google ScholarDigital Library
    5. Bernstein, G., and Wojtan, C. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Trans. Graph. (SIGGRAPH) 32, 4, 34. Google ScholarDigital Library
    6. Bojsen-Hansen, M., and Wojtan, C. 2013. Liquid surface tracking with error compensation. ACM Trans. Graph. (SIGGRAPH) 32, 4, 79:1–79:10. Google ScholarDigital Library
    7. Brakke, K. 1992. The surface evolver. Experimental Mathematics 1, 2, 141–165.Google ScholarCross Ref
    8. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (SIGGRAPH) 21, 3, 594–603. Google ScholarDigital Library
    9. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472–2493. Google ScholarDigital Library
    10. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. (SIGGRAPH) 29, 4, 47. Google ScholarDigital Library
    11. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. (SIGGRAPH) 31, 4, 96. Google ScholarDigital Library
    12. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-)intersections for polygonal meshes. Computer Graphics Forum (Eurographics) 29, 2 (June), 397–406.Google ScholarCross Ref
    13. Clark, B., Ray, N., and Jiao, X. 2012. Surface mesh optimization, adaption, and untangling with high-order accuracy. In International Meshing Roundtable, Springer, Berlin, X. Jiao and J.-C. Weill, Eds., 385–402.Google Scholar
    14. Clausen, P., Wicke, M., Shewchuk, J. R., and O’Brien, J. F. 2013. Simulating liquids and solid-liquid interactions with Lagrangian meshes. ACM Trans. Graph. 32, 2, 17. Google ScholarDigital Library
    15. Crane, K., Pinkall, U., and Schröder, P. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. (SIGGRAPH) 32, 4, 61. Google ScholarDigital Library
    16. Da, F., Batty, C., and Grinspun, E. 2014. A convergence study of multimaterial mesh-based surface tracking. Tech. rep., Columbia University.Google Scholar
    17. de Sousa, F. S., Mangiavacchi, N., Nonato, L. G., Castelo, A., Tomé, M. F., and McKee, S. 2004. A front-tracking/front-capturing method for the simulation of 3D multi-fluid flows with free surfaces. J. Comp. Phys. 198, 2, 469–499. Google ScholarDigital Library
    18. Du, J., Fix, B., Glimm, J., Jia, X., Li, X., Li, Y., and Wu, L. 2006. A simple package for front tracking. J. Comp. Phys. 213, 2, 613–628. Google ScholarDigital Library
    19. Dyadechko, V., and Shashkov, M. 2008. Reconstruction of multi-material interfaces from moment data. J. Comp. Phys. 227, 11, 5361–5384. Google ScholarDigital Library
    20. Eckstein, I., Pons, J.-P., Tong, Y., Kuo, C.-C. J., and Desbrun, M. 2007. Generalized surface flows for mesh processing. In Symposium on Geometry Processing, 183–192. Google ScholarDigital Library
    21. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comp. Phys. 183, 1, 83–116. Google ScholarDigital Library
    22. Glimm, J., Grove, J. W., Li, X., Shyue, K.-m., Zeng, Y., and Zhang, Q. 1998. Three-dimensional front tracking. SIAM J. Sci. Comput. 19, 3, 703–727. Google ScholarDigital Library
    23. Glimm, J., Grove, J. W., Li, X. L., and Tan, D. C. 2000. Robust computational algorithms for dynamic interface tracking in three dimensions. SIAM J. Sci. Comput. 21, 6, 2240–2256. Google ScholarDigital Library
    24. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. (SIGGRAPH) 27, 3, 23. Google ScholarDigital Library
    25. Hirt, C. W., and Nichols, B. D. 1981. Volume of fluid (VOF) method for the dynamics of free boundaries. J. Comp. Phys. 39, 1, 201–225.Google ScholarCross Ref
    26. Jiao, X., Colombi, A., Ni, X., and Hart, J. 2010. Anisotropic mesh adaptation for evolving triangulated surfaces. Engineering with Computers 26, 4, 363–376. Google ScholarDigital Library
    27. Jiao, X. 2007. Face offsetting: A unified approach for explicit moving interfaces. J. Comp. Phys. 220, 2, 612–625. Google ScholarDigital Library
    28. Kim, B. 2010. Multiphase fluid simulation using regional level sets. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6, 175. Google ScholarDigital Library
    29. Kuprat, A., George, D., Straub, G., and Demirel, M. C. 2003. Modeling microstructure evolution in three dimensions with Grain3D and LaGriT. Computational Materials Science 28, 1, 199–208.Google ScholarCross Ref
    30. Lazar, E. 2011. The evolution of cellular structures via curvature flow. PhD thesis, Columbia University.Google Scholar
    31. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. (SIGGRAPH) 25, 3, 812–819. Google ScholarDigital Library
    32. McKee, S., Tomé, M. F., Ferreira, V. G., Cuminato, J. A., Castelo, A., de Sousa, F. S., and Mangiavacchi, N. 2008. The MAC method. Computers & Fluids 37, 8 (Sept.), 907–930.Google ScholarCross Ref
    33. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In VisMath, Springer-Verlag, Berlin, Germany, 35–54.Google Scholar
    34. Meyer, M., Whitaker, R. T., Kirby, R. M., Ledergerber, C., and Pfister, H. 2008. Particle-based sampling and meshing of surfaces in multimaterial volumes. IEEE TVCG 14, 6, 1539–1546. Google ScholarDigital Library
    35. Misztal, M., Erleben, K., Bargteil, A. W., Christensen, B. B., Baerentzen, A., and Bridson, R. 2012. Multiphase flow of immiscible fluids on unstructured moving meshes. In Symposium on Computer Animation, Eurographics Association, Lausanne, Switzerland, 97–106. Google ScholarDigital Library
    36. Mora, L. B., Gottstein, G., and Schvindlerman, L. S. 2008. Three-dimensional grain growth: Analytical approaches and computer simulations. Acta Materialia 56, 1, 5915–5926.Google ScholarCross Ref
    37. Müller, M., Solenthaler, B., Keiser, R., and Gross, M. 2005. Particle-based fluid-fluid interaction. In Symposium on Computer Animation, ACM, Los Angeles, CA, USA, 237–244. Google ScholarDigital Library
    38. Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Symposium on Computer Animation, ACM, New York, NY, USA, 237–245. Google ScholarDigital Library
    39. Narain, R., Samii, A., and O’Brien, J. F. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6, 147. Google ScholarDigital Library
    40. Osher, S., and Fedkiw, R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer, New York.Google Scholar
    41. Pan, H., Choi, Y.-K., Liu, Y., Hu, W., Du, Q., Polthier, K., Zhang, C., and Wang, W. 2012. Robust modeling of constant mean curvature surfaces. ACM Trans. Graph. (SIGGRAPH) 31, 4, 85. Google ScholarDigital Library
    42. Pons, J.-P., and Boissonnat, J.-D. 2007. A Lagrangian approach to dynamic interfaces through kinetic triangulation of the ambient space. Computer Graphics Forum 26, 2, 227–239.Google ScholarCross Ref
    43. Pons, J.-P., and Boissonnat, J.-D. 2007. Delaunay deformable models: Topology-adaptive meshes based on the restricted delaunay triangulation. In CVPR, IEEE, Minneapolis, Minnesota, USA, 1–8.Google Scholar
    44. Quan, S., and Schmidt, D. P. 2007. A moving mesh interface tracking method for 3D incompressible two-phase flows. Journal of Computational Physics 221, 2, 761–780. Google ScholarDigital Library
    45. Quan, S., Lou, J., and Schmidt, D. P. 2009. Modeling merging and breakup in the moving mesh interface tracking method for multiphase flow simulations. Journal of Computational Physics 228, 7, 2660–2675. Google ScholarDigital Library
    46. Saye, R., and Sethian, J. 2012. Analysis and applications of the Voronoi Implicit Interface Method. J. Comp. Phys. 231, 18, 6051–6085. Google ScholarDigital Library
    47. Sethian, J. 1999. Level set methods and fast marching methods. Cambridge University Press.Google Scholar
    48. Solenthaler, B., and Pajarola, R. 2008. Density contrast SPH interfaces. In Symposium on Computer Animation, Eurographics Association, Dublin, 211–218. Google ScholarDigital Library
    49. Stanculescu, L., Chaine, R., and Cani, M.-P. 2011. Freestyle: Sculpting meshes with self-adaptive topology. Computers and Graphics 35, 3, 614–622. Google ScholarDigital Library
    50. Starinshak, D. P., Karni, S., and Roe, P. L. 2014. A new level set model for multimaterial flows. J. Comp. Phys. In press. Google ScholarDigital Library
    51. Syha, M., and Weygand, D. 2010. A generalized vertex dynamics model for grain growth in three dimensions. Modelling Simul. Mater. Sci. Eng. 18, 1, 015010.Google ScholarCross Ref
    52. Thuerey, N., Wojtan, C., Gross, M., and Turk, G. 2010. A multiscale approach to mesh-based surface tension flows. ACM Trans. Graph. (SIGGRAPH) 29, 3. Google ScholarDigital Library
    53. Toutant, A., Mathieu, B., and Lebaigue, O. 2012. Volume-conserving smoothing for front tracking methods. Computers & Fluids 67, 16–25.Google ScholarCross Ref
    54. Wakai, F., Enomoto, N., and Ogawa, H. 2000. Three-dimensional microstructural evolution in ideal grain growth – general statistics. Acta Materialia 48, 1, 1297–1311.Google ScholarCross Ref
    55. Weaire, D., and Hutzler, S. 2001. Physics of Foams. Oxford University Press, New York.Google Scholar
    56. Weygand, D., and Brechet, Y. 1999. Three-dimensional grain growth: a vertex dynamics simulation. Philosophical Magazine B 79, 5, 703–716.Google ScholarCross Ref
    57. Wicke, M., Ritchie, D., Klingner, B. M., Burke, S., Shewchuk, J. R., and O’Brien, J. F. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. (SIGGRAPH) 29, 4, 49. Google ScholarDigital Library
    58. Wojtan, C., Thuerey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. (SIGGRAPH) 28, 3, 76. Google ScholarDigital Library
    59. Wojtan, C., Thuerey, N., Gross, M., and Turk, G. 2010. Physically-inspired topology changes for thin fluid features. ACM Trans. Graph. (SIGGRAPH) 29, 3, 50. Google ScholarDigital Library
    60. Wojtan, C., Muller-Fischer, M., and Brochu, T. 2011. Liquid simulation with mesh-based surface tracking. In SIGGRAPH Courses, ACM, Vancouver, 8. Google ScholarDigital Library
    61. Yu, J., Wojtan, C., Turk, G., and Yap, C. 2012. Explicit mesh surfaces for particle based fluids. Computer Graphics Forum (Eurographics) 31, 2, 815–824. Google ScholarDigital Library
    62. Yuan, Z., Yu, Y., and Wang, W. 2012. Object-space multiphase implicit functions. ACM Trans. Graph. (SIGGRAPH) 31, 4, 114. Google ScholarDigital Library
    63. Zaharescu, A., Boyer, E., and Horaud, R. 2011. Topology-adaptive mesh deformation for surface evolution, morphing, and multiview reconstruction. IEEE TPAMI 33, 4, 823–837. Google ScholarDigital Library
    64. Zhao, H.-K., Chan, T., Merriman, B., and Osher, S. 1996. A variational level set approach to multiphase motion. J. Comp. Phys. 127, 1, 179–195. Google ScholarDigital Library
    65. Zheng, W., Yong, J.-H., and Paul, J.-C. 2006. Simulation of bubbles. In Symposium on Computer Animation, Eurographics Association, Vienna, 325–333. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: