skip to main content
research-article

Multimaterial mesh-based surface tracking

Published: 27 July 2014 Publication History

Abstract

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.

Supplementary Material

ZIP File (a112-da.zip)
Supplemental material.
MP4 File (a112-sidebyside.mp4)

References

[1]
Alexa, M. 2002. Recent advances in mesh morphing. Computer Graphics Forum 21, 2, 173--198.
[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.
[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.
[4]
Batty, C., and Bridson, R. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. In Symposium on Computer Animation, 219--228.
[5]
Bernstein, G., and Wojtan, C. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Trans. Graph. (SIGGRAPH) 32, 4, 34.
[6]
Bojsen-Hansen, M., and Wojtan, C. 2013. Liquid surface tracking with error compensation. ACM Trans. Graph. (SIGGRAPH) 32, 4, 79:1--79:10.
[7]
Brakke, K. 1992. The surface evolver. Experimental Mathematics 1, 2, 141--165.
[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.
[9]
Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472--2493.
[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.
[11]
Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. (SIGGRAPH) 31, 4, 96.
[12]
Campen, M., and Kobbelt, L. 2010. Exact and robust (self-)intersections for polygonal meshes. Computer Graphics Forum (Eurographics) 29, 2 (June), 397--406.
[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.
[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.
[15]
Crane, K., Pinkall, U., and Schröder, P. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. (SIGGRAPH) 32, 4, 61.
[16]
Da, F., Batty, C., and Grinspun, E. 2014. A convergence study of multimaterial mesh-based surface tracking. Tech. rep., Columbia University.
[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.
[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.
[19]
Dyadechko, V., and Shashkov, M. 2008. Reconstruction of multi-material interfaces from moment data. J. Comp. Phys. 227, 11, 5361--5384.
[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.
[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.
[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.
[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.
[24]
Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. (SIGGRAPH) 27, 3, 23.
[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.
[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.
[27]
Jiao, X. 2007. Face offsetting: A unified approach for explicit moving interfaces. J. Comp. Phys. 220, 2, 612--625.
[28]
Kim, B. 2010. Multiphase fluid simulation using regional level sets. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6, 175.
[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.
[30]
Lazar, E. 2011. The evolution of cellular structures via curvature flow. PhD thesis, Columbia University.
[31]
Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. (SIGGRAPH) 25, 3, 812--819.
[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.
[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.
[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.
[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.
[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.
[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.
[38]
Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Symposium on Computer Animation, ACM, New York, NY, USA, 237--245.
[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.
[40]
Osher, S., and Fedkiw, R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer, New York.
[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.
[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.
[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.
[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.
[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.
[46]
Saye, R., and Sethian, J. 2012. Analysis and applications of the Voronoi Implicit Interface Method. J. Comp. Phys. 231, 18, 6051--6085.
[47]
Sethian, J. 1999. Level set methods and fast marching methods. Cambridge University Press.
[48]
Solenthaler, B., and Pajarola, R. 2008. Density contrast SPH interfaces. In Symposium on Computer Animation, Eurographics Association, Dublin, 211--218.
[49]
Stanculescu, L., Chaine, R., and Cani, M.-P. 2011. Freestyle: Sculpting meshes with self-adaptive topology. Computers and Graphics 35, 3, 614--622.
[50]
Starinshak, D. P., Karni, S., and Roe, P. L. 2014. A new level set model for multimaterial flows. J. Comp. Phys. In press.
[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.
[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.
[53]
Toutant, A., Mathieu, B., and Lebaigue, O. 2012. Volume-conserving smoothing for front tracking methods. Computers & Fluids 67, 16--25.
[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.
[55]
Weaire, D., and Hutzler, S. 2001. Physics of Foams. Oxford University Press, New York.
[56]
Weygand, D., and Brechet, Y. 1999. Three-dimensional grain growth: a vertex dynamics simulation. Philosophical Magazine B 79, 5, 703--716.
[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.
[58]
Wojtan, C., Thuerey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. (SIGGRAPH) 28, 3, 76.
[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.
[60]
Wojtan, C., Muller-Fischer, M., and Brochu, T. 2011. Liquid simulation with mesh-based surface tracking. In SIGGRAPH Courses, ACM, Vancouver, 8.
[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.
[62]
Yuan, Z., Yu, Y., and Wang, W. 2012. Object-space multiphase implicit functions. ACM Trans. Graph. (SIGGRAPH) 31, 4, 114.
[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.
[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.
[65]
Zheng, W., Yong, J.-H., and Paul, J.-C. 2006. Simulation of bubbles. In Symposium on Computer Animation, Eurographics Association, Vienna, 325--333.

Cited By

View all
  • (2024)Multi-Material Mesh-Based Surface Tracking with Implicit Topology ChangesACM Transactions on Graphics10.1145/365822343:4(1-14)Online publication date: 19-Jul-2024
  • (2024)An Induce-on-Boundary Magnetostatic Solver for Grid-Based FerrofluidsACM Transactions on Graphics10.1145/365812443:4(1-14)Online publication date: 19-Jul-2024
  • (2024)SimuCell3D: three-dimensional simulation of tissue mechanics with cell polarizationNature Computational Science10.1038/s43588-024-00620-94:4(299-309)Online publication date: 9-Apr-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 33, Issue 4
July 2014
1366 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/2601097
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2014
Published in TOG Volume 33, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. multimaterial flows
  2. nonmanifold meshes
  3. surface tracking
  4. topology change

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)47
  • Downloads (Last 6 weeks)2
Reflects downloads up to 03 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Multi-Material Mesh-Based Surface Tracking with Implicit Topology ChangesACM Transactions on Graphics10.1145/365822343:4(1-14)Online publication date: 19-Jul-2024
  • (2024)An Induce-on-Boundary Magnetostatic Solver for Grid-Based FerrofluidsACM Transactions on Graphics10.1145/365812443:4(1-14)Online publication date: 19-Jul-2024
  • (2024)SimuCell3D: three-dimensional simulation of tissue mechanics with cell polarizationNature Computational Science10.1038/s43588-024-00620-94:4(299-309)Online publication date: 9-Apr-2024
  • (2024)PolyHoop: Soft particle and tissue dynamics with topological transitionsComputer Physics Communications10.1016/j.cpc.2024.109128299(109128)Online publication date: Jun-2024
  • (2024)Physics-based fluid simulation in computer graphics: Survey, research trends, and challengesComputational Visual Media10.1007/s41095-023-0368-y10:5(803-858)Online publication date: 27-Apr-2024
  • (2023)Embryo mechanics cartography: inference of 3D force atlases from fluorescence microscopyNature Methods10.1038/s41592-023-02084-720:12(1989-1999)Online publication date: 6-Dec-2023
  • (2023)Biophysical models of early mammalian embryogenesisStem Cell Reports10.1016/j.stemcr.2022.11.02118:1(26-46)Online publication date: Jan-2023
  • (2023)MPM‐driven dynamic desiccation cracking and curling in unsaturated soilsComputer Animation and Virtual Worlds10.1002/cav.217234:3-4Online publication date: 17-May-2023
  • (2021)Multi-Reconstruction from Points Cloud by Using a Modified Vector-Valued Allen–Cahn EquationMathematics10.3390/math91213269:12(1326)Online publication date: 9-Jun-2021
  • (2021)Ships, splashes, and waves on a vast oceanACM Transactions on Graphics10.1145/3478513.348049540:6(1-15)Online publication date: 10-Dec-2021
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media