“Differentiable Voronoi Diagrams for Simulation of Cell-based Mechanical Systems”
Conference:
Type(s):
Title:
- Differentiable Voronoi Diagrams for Simulation of Cell-based Mechanical Systems
Presenter(s)/Author(s):
Abstract:
We present a computational model leveraging analytical derivatives of Voronoi diagram geometry for simulation of cell-based mechanical systems. Boundary coupling formulation enables interaction with rigid bodies, elastic membranes, and free surfaces. Examples model complex dynamic processes involving frequent neighborhood changes, including foam coarsening and embryonic cleavage.
References:
[1]
Silvanus Alt, Poulami Ganguly, and Guillaume Salbreux. 2017. Vertex models: From cell mechanics to tissue morphogenesis. Philosophical Transactions of the Royal Society B: Biological Sciences 372 (05 2017), 20150520.
[2]
Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk. 2007. A finite element method for animating large viscoplastic flow. In ACM SIGGRAPH 2007 Papers (San Diego, California) (SIGGRAPH ’07). Association for Computing Machinery, New York, NY, USA, 16–es.
[3]
Bernd Bickel, Moritz B?cher, Miguel A. Otaduy, Wojciech Matusik, Hanspeter Pfister, and Markus Gross. 2009. Capture and modeling of non-linear heterogeneous soft tissue. ACM Trans. Graph. 28, 3, Article 89 (jul 2009), 9 pages.
[4]
Beniamin Bogosel and Edouard Oudet. 2022. Longest minimal length partitions. Interfaces and Free Boundaries 24, 1 (Jan. 2022), 95–135.
[5]
Tyson Brochu and Robert Bridson. 2009. Robust Topological Operations for Dynamic Explicit Surfaces. SIAM J. Sci. Comput. 31, 4 (jun 2009), 2472–2493.
[6]
G. Wayne Brodland, Daniel I-Li Chen, and Jim H. Veldhuis. 2006. A cell-based constitutive model for embryonic epithelia and other planar aggregates of biological cells. International Journal of Plasticity 22, 6 (2006), 965–995.
[7]
Oleksiy Busaryev, Tamal K. Dey, Huamin Wang, and Zhong Ren. 2012. Animating Bubble Interactions in a Liquid Foam. ACM Trans. Graph. 31, 4, Article 63 (jul 2012), 8 pages.
[8]
Xiang Chen, Changxi Zheng, Weiwei Xu, and Kun Zhou. 2014. An asymptotic numerical method for inverse elastic shape design. ACM Trans. Graph. 33, 4, Article 95 (jul 2014), 11 pages.
[9]
Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical Software (TOMS) 35, 3 (2008), 1–14.
[10]
Rapha?l Conradin, Christophe Coreixas, Jonas Latt, and Bastien Chopard. 2021. Pala-Cell2D: A framework for detailed tissue morphogenesis. Journal of Computational Science 53 (2021), 101353.
[11]
Fang Da, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2015. Double Bubbles Sans Toil and Trouble: Discrete Circulation-Preserving Vortex Sheets for Soap Films and Foams. ACM Trans. on Graphics (SIGGRAPH North America 2015) (2015).
[12]
Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power Particles: An Incompressible Fluid Solver Based on Power Diagrams. ACM Trans. Graph. 34, 4, Article 50 (jul 2015), 11 pages.
[13]
Yitong Deng, Mengdi Wang, Xiangxin Kong, Shiying Xiong, Zangyueyang Xian, and Bo Zhu. 2022. A moving eulerian-lagrangian particle method for thin film and foam simulation. ACM Trans. Graph. 41, 4, Article 154 (jul 2022), 17 pages.
[14]
David Eppstein. 2012. The Graphs of Planar Soap Bubbles.
[15]
Reza Farhadifar, Jens-Christian R?per, Benoit Aigouy, Suzanne Eaton, and Frank J?licher. 2007. The Influence of Cell Mechanics, Cell-Cell Interactions, and Proliferation on Epithelial Packing. Current Biology 17, 24 (2007), 2095–2104.
[16]
Fan Feng, Shiying Xiong, Ziyue Liu, Zangyueyang Xian, Yuqing Zhou, Hiroki Kobayashi, Atsushi Kawamoto, Tsuyoshi Nomura, and Bo Zhu. 2022. Cellular topology optimization on differentiable Voronoi diagrams. Internat. J. Numer. Methods Engrg. 124, 1 (sep 2022), 282–304.
[17]
Zachary Ferguson, Teseo Schneider, Danny Kaufman, and Daniele Panozzo. 2023. In-Timestep Remeshing for Contacting Elastodynamics. ACM Trans. Graph. 42, 4, Article 145 (jul 2023), 15 pages.
[18]
Alexander G. Fletcher, Miriam Osterfield, Ruth E. Baker, and Stanislav Y. Shvartsman. 2014. Vertex Models of Epithelial Morphogenesis. Biophysical Journal 106, 11 (2014), 2291–2304.
[19]
Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz B?cher, Bernhard Thomaszewski, and Stelian Coros. 2020. Add: Analytically differentiable dynamics for multi-body systems with frictional contact. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–15.
[20]
Ahmadreza Ghaffarizadeh, Randy Heiland, Samuel H. Friedman, Shannon M. Mumenthaler, and Paul Macklin. 2018. PhysiCell: An open source physics-based cell simulator for 3-D multicellular systems. PLOS Computational Biology 14, 2 (02 2018), 1–31.
[21]
Ryan Goldade, Mridul Aanjaneya, and Christopher Batty. 2020. Constraint bubbles and affine regions: reduced fluid models for efficient immersed bubbles and flexible spatial coarsening. ACM Trans. Graph. 39, 4, Article 43 (aug 2020), 15 pages.
[22]
Pedro G?mez-G?lvez, Pablo Vicente-Munuera, Antonio Tagua, Cristina Forja, Ana M Castro, Marta Letr?n, Andrea Valencia-Exp?sito, Clara Grima, Marina Berm?dez-Gallardo, ?scar Serrano-P?rez-Higueras, et al. 2018. Scutoids are a geometrical solution to three-dimensional packing of epithelia. Nature communications 9, 1 (2018), 2960.
[23]
Ga?l Guennebaud, Beno?t Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
[24]
David Hahn, Pol Banzet, James M Bern, and Stelian Coros. 2019. Real2sim: Visco-elastic parameter estimation from dynamic motion. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–13.
[25]
Hisao Honda, Masaharu Tanemura, and Tatsuzo Nagai. 2004. A three-dimensional vertex dynamics cell model of space-filling polyhedra simulating cell behavior in a cell aggregate. Journal of Theoretical Biology 226, 4 (2004), 439–453.
[26]
Jeong-Mo Hong, Ho-Young Lee, Jong-Chul Yoon, and Chang-Hun Kim. 2008. Bubbles alive. ACM Trans. Graph. 27, 3 (aug 2008), 1–4.
[27]
Yuanming Hu, Jiancheng Liu, Andrew Spielberg, Joshua B Tenenbaum, William T Freeman, Jiajun Wu, Daniela Rus, and Wojciech Matusik. 2019. Chainqueen: A real-time differentiable physical simulator for soft robotics. In 2019 International conference on robotics and automation (ICRA). IEEE, 6265–6271.
[28]
Weizhen Huang, Julian Iseringhausen, Tom Kneiphof, Ziyin Qu, Chenfanfu Jiang, and Matthias B. Hullin. 2020. Chemomechanical simulation of soap film flow on spherical bubbles. ACM Trans. Graph. 39, 4, Article 41 (aug 2020), 14 pages.
[29]
Sadashige Ishida, Peter Synak, Fumiya Narita, Toshiya Hachisuka, and Chris Wojtan. 2020. A model for soap film dynamics with evolving thickness. ACM Trans. Graph. 39, 4, Article 31 (aug 2020), 11 pages.
[30]
Sangwoo Kim, Marie Pochitaloff, Georgina Stooke-Vaughan, and Otger Camp?s. 2021. Embryonic Tissues as Active Foams. Nature Physics 17 (07 2021), 1–8.
[31]
Yohei Kondo, Kazuhiro Aoki, and Shin Ishii. 2018. Inverse tissue mechanics of cell monolayer expansion. PLOS Computational Biology 14 (03 2018), e1006029.
[32]
Dan Koschier, Sebastian Lipponer, and Jan Bender. 2014. Adaptive Tetrahedral Meshes for Brittle Fracture Simulation. In Symposium on Computer Animation, Vol. 3.
[33]
Bruno L?vy. 2015. Geogram. https://github.com/BrunoLevy/geogram.
[34]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (aug 2020), 20 pages.
[35]
Yang Liu, Wenping Wang, Bruno L?vy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang. 2009. On Centroidal Voronoi Tessellation—Energy Smoothness and Fast Computation. ACM Trans. Graph. 28, 4, Article 101 (sep 2009), 17 pages.
[36]
S. Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2 (1982), 129–137.
[37]
Thomas S Lumpe, Michael Tao, Kristina Shea, and David I W Levin. 2022. Computational design and fabrication of active 3D-printed multi-state structures for shape morphing. Smart Materials and Structures 32, 1 (dec 2022), 015008.
[38]
Micka?l Ly, Romain Casati, Florence Bertails-Descoubes, M?lina Skouras, and Laurence Boissieux. 2018. Inverse elastic shell design with contact and friction. ACM Trans. Graph. 37, 6, Article 201 (dec 2018), 16 pages.
[39]
Jon?s Mart?nez, Samuel Hornus, Haichuan Song, and Sylvain Lefebvre. 2018. Polyhedral Voronoi Diagrams for Additive Manufacturing. ACM Trans. Graph. 37, 4, Article 129 (jul 2018), 15 pages.
[40]
Jon?s Mart?nez, M?lina Skouras, Christian Schumacher, Samuel Hornus, Sylvain Lefebvre, and Bernhard Thomaszewski. 2019. Star-Shaped Metrics for Mechanical Metamaterial Design. ACM Trans. Graph. 38, 4, Article 82 (jul 2019), 13 pages.
[41]
J. L. Meijering. 1953. Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Research Reports 8 (1953), 270–290.
[42]
E. Miguel, D. Bradley, B. Thomaszewski, B. Bickel, W. Matusik, M. A. Otaduy, and S. Marschner. 2012. Data-Driven Estimation of Cloth Simulation Models. Comput. Graph. Forum 31, 2pt2 (may 2012), 519–528.
[43]
Marek K. Misztal, Kenny Erleben, Adam Bargteil, Jens Fursund, Brian Bunch Christensen, J. Andreas B?rentzen, and Robert Bridson. 2014. Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes. IEEE Transactions on Visualization and Computer Graphics 20, 1 (jan 2014), 4–16.
[44]
Juan Montes, Bernhard Thomaszewski, Sudhir Mudur, and Tiberiu Popa. 2020. Computational design of skintight clothing. ACM Trans. Graph. 39, 4, Article 105 (aug 2020), 12 pages.
[45]
C. Moukarzel. 1997. Geometrical consequences of foam equilibrium. Phys. Rev. E 55 (Jun 1997), 6866–6880. Issue 6.
[46]
Rahul Narain, Tobias Pfaff, and James F. O’Brien. 2013. Folding and crumpling adaptive sheets. ACM Trans. Graph. 32, 4, Article 51 (jul 2013), 8 pages.
[47]
Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. 31, 6, Article 152 (nov 2012), 10 pages.
[48]
James F. O’Brien, Adam W. Bargteil, and Jessica K. Hodgins. 2002. Graphical modeling and animation of ductile fracture. ACM Trans. Graph. 21, 3 (jul 2002), 291–294.
[49]
Satoru Okuda, Yasuhiro Inoue, Mototsugu Eiraku, Yoshiki Sasai, and Taiji Adachi. 2012. Reversible network reconnection model for simulating large deformation in dynamic tissue morphogenesis. Biomechanics and modeling in mechanobiology 12 (09 2012).
[50]
Julian Panetta, Florin Isvoranu, Tian Chen, Emmanuel Si?fert, Beno?t Roman, and Mark Pauly. 2021. Computational Inverse Design of Surface-Based Inflatables. ACM Trans. Graph. 40, 4, Article 40 (July 2021), 14 pages.
[51]
Julian Panetta, Abtin Rahimian, and Denis Zorin. 2017. Worst-case stress relief for microstructures. ACM Trans. Graph. 36, 4, Article 122 (jul 2017), 16 pages.
[52]
Tobias Pfaff, Rahul Narain, Juan Miguel de Joya, and James F. O’Brien. 2014. Adaptive tearing and cracking of thin sheets. ACM Trans. Graph. 33, 4, Article 110 (jul 2014), 9 pages.
[53]
Andrey Piatnitski and Mariya Ptashnyk. 2020. Homogenization of biomechanical models of plant tissues with randomly distributed cells. Nonlinearity 33 (09 2020), 5510–5542.
[54]
Camille Schreck, Damien Rohmer, Stefanie Hahmann, Marie-Paule Cani, Shuo Jin, Charlie C. L. Wang, and Jean-Francis Bloch. 2016. Nonsmooth Developable Geometry for Interactively Animating Paper Crumpling. ACM Trans. Graph. 35, 1, Article 10 (dec 2016), 18 pages.
[55]
Nicholas Sharp et al. 2019. Polyscope. www.polyscope.run.
[56]
M?lina Skouras, Bernhard Thomaszewski, Peter Kaufmann, Akash Garg, Bernd Bickel, Eitan Grinspun, and Markus Gross. 2014. Designing inflatable structures. ACM Trans. Graph. 33, 4, Article 63 (jul 2014), 10 pages.
[57]
Gilberto Thomas, Julio Belmonte, Fran?ois Graner, James Glazier, and Rita de Almeida. 2015. 3D simulations of wet foam coarsening evidence a self similar growth regime. Colloids and Surfaces A: Physicochemical and Engineering Aspects 473 (02 2015).
[58]
Nobuyuki Umetani, Danny M. Kaufman, Takeo Igarashi, and Eitan Grinspun. 2011. Sensitive couture for interactive garment modeling and editing. In ACM SIGGRAPH 2011 Papers (Vancouver, British Columbia, Canada) (SIGGRAPH ’11). Association for Computing Machinery, New York, NY, USA, Article 90, 12 pages.
[59]
Jan van Ijken. 2018. Becoming. https://www.janvanijken.com/films/becoming/
[60]
Bue Krogh Vedel-Larsen. 2010. Quasi-static Simulation of Foam in the Vertex Model. Master’s thesis. University of Copenhagen, Denmark Department of Computer Science.
[61]
Huamin Wang. 2018. Rule-free sewing pattern adjustment with precision and efficiency. ACM Trans. Graph. 37, 4, Article 53 (jul 2018), 13 pages.
[62]
Xiaoning Wang, Xiang Ying, Yong-Jin Liu, Shi-Qing Xin, Wenping Wang, Xianfeng Gu, Wolfgang Mueller-Wittig, and Ying He. 2015. Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes. Computer-Aided Design 58 (2015), 51–61.
[63]
Martin Wicke, Daniel Ritchie, Bryan M. Klingner, Sebastian Burke, Jonathan R. Shewchuk, and James F. O’Brien. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. 29, 4, Article 49 (jul 2010), 11 pages.
[64]
Francis Williams, Jerome Parent-Levesque, Derek Nowrouzezahrai, Daniele Panozzo, Kwang Moo Yi, and Andrea Tagliasacchi. 2020. Voronoinet: General functional approximators with local support. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. 264–265.
[65]
Chris Wojtan, Nils Th?rey, Markus Gross, and Greg Turk. 2009. Deforming meshes that split and merge. In ACM SIGGRAPH 2009 papers. 1–10.
[66]
Dong-Ming Yan, Bruno Levy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. Comput. Graph. Forum 28 (07 2009), 1445–1454.
[67]
Dong-Ming Yan, Wenping Wang, Bruno Levy, and Yang Liu. 2011. Efficient Computation of Clipped Voronoi Diagram for Mesh Generation. Computer-Aided Design 45 (09 2011).
[68]
Guowei Yan, Wei Li, Ruigang Yang, and Huamin Wang. 2018. Inexact descent methods for elastic parameter optimization. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–14.
[69]
Mariette Yvinec. 2023. 2D Triangulations. In CGAL User and Reference Manual. CGAL Editorial Board. https://doc.cgal.org/5.5.2/Manual/packages.html#PkgTriangulation2
[70]
Jiayi Eris Zhang, J?r?mie Dumas, Yun (Raymond) Fei, Alec Jacobson, Doug L. James, and Danny M. Kaufman. 2022. Progressive Simulation for Cloth Quasistatics. ACM Trans. Graph. 41, 6, Article 218 (nov 2022), 16 pages.
[71]
Xiaoting Zhang, Guoxin Fang, Chengkai Dai, Jouke Verlinden, Jun Wu, Emily Whiting, and Charlie C.L. Wang. 2017. Thermal-Comfort Design of Personalized Casts. In Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology (Qu?bec City, QC, Canada) (UIST ’17). Association for Computing Machinery, New York, NY, USA, 243–254.
