Project: NSF IIS-0953096

 

CAREER: Theory and Practice of Space-Time Variational Integrators

for Simulation and Animation

 

(July 01, 2010 - June 30, 2016)

 

PI: Yiying Tong (http://www.cse.msu.edu/~ytong/, ytong@msu.edu), Michigan State University

 


Abstract:

Physics-based simulation has played an increasingly important role in computer graphics over the past few years, for fluid simulation, deformable object simulation, fluid-solid interaction, fracture, keyframing, primary and secondary motions in character animation, or even sound simulation.  Despite different emphases and goals, simulation algorithms used in graphics share a lot of commonalities with simulation methods used in other computational sciences. We wish to investigate theoretical foundations that are common and beneficial to both, namely, geometric time integrators and discrete differential geometry. Relevance to graphics and computational mechanics will be practically demonstrated through a series of targeted applications.

The primary goal of the project is to develop simulation/animation methods which preserve defining geometric properties of the continuous equations of motion. Thus, the inherently interdisciplinary research effort aims at providing efficient and stable numerical methods of controllable accuracy for partial differential equations. Our research focuses on the geometric aspects of discrete dynamics, drawing from geometric mechanics, differential geometry, numerical computation, and approximation theory. Novel mathematical representations of motion in spacetime are developed. Novel spatial meshing tools and time integration schemes are developed using the underlying geometry to facilitate the computation. These theoretical developments provide crucial computational foundations to a seemingly-diverse series of applications being explored, leveraging the improved numerics brought on by these structure-preserving computations.

The combination of geometric mechanics and discrete differential geometry will help a wide spectrum of applications. The research experience acquired from this project will also directly impact the ongoing collaborations, the research and the educational activities. Outreach efforts are geared towards recruiting students from underrepresented groups to help with this research project, in particular by leveraging existing efforts for enhancing the participation of women and minorities in scientific research.

Students:

 

  1. Beibei Liu (PhD student, joined the project since Aug., 2010, graduated in Jan., 2016)
  2. Yuanzhen Wang (PhD student, joined the project since Aug., 2010, graduated in Aug, 2013)
  3. Xiaojun Wang (PhD student, joined the project since Jan., 2011)
  4. Rosemary Dutka (Master student, joined the project since Jan., 2012, graduated in Aug., 2013)
  5. Xin Feng (PhD student, joined the project since May, 2012, graduated in March, 2014)

6.     Hayam Abdelrahman (Master student, joined the project since Fall 2014, transitioned to PhD program in Fall 2016)

  1. Ze Zhang (PhD student, joined the project since Aug, 2015)

 

Collaborator:

  1. Mathieu Desbrun, California Institute of Technology. The collaboration with Dr. Desbrun is focused on computer graphics applications and fluid simulation.
  2. Hans Dulimarta, Grand Valley State University. The collaboration with Dr. Dulimarta is focused on thin-shell simulation.
  3. Jin Huang, Zhejiang University. The collaboration with Dr. Huang is focused on spatial discretization methods and solid-fluid interaction.
  4. Eva Kanso, University of Southern California. The collaboration with Dr. Kanso is focused on fluid simulation.
  5. Huaming Wang, Ohio State University. The collaboration with Dr. Wang is focused on fluid solid interaction.
  6. Guowei Wei, Math Dept, Michigan State University. The collaboration with Dr. Wei is focused on applications in biomolecular dynamics.
  7. Kun Zhou, Zhejiang University. The collaboration with Dr. Zhou is focused on graphics application, and physically-based simulation.
  8. Leslie Kuhn, Biochem&Molecular Biology, MSU. The collaboration with Dr. Kuhn is focused on applications in deformable matching.
  9. Shanker Balasubramaniam, ECE Dept., MSU. The collaboration with Dr. Balasubramaniam is focused on applications in micro-bubble simulation in sound waves.

 

Project Goal:

The primary goal of the project is to develop simulation/animation methods which preserve defining geometric properties of the continuous equations of motion. Thus, the inherently interdisciplinary research effort aims at providing efficient and stable numerical methods of controllable accuracy for partial differential equations. Drawing from geometric mechanics, differential geometry, numerical computation, and approximation theory, it will also lead to a better understanding of the geometric aspects of discrete dynamics. The theoretical research efforts will be focused on novel mathematical representations of motion in spacetime, with which variational spatial meshing tools and time integration schemes will be developed. These theoretical developments will provide crucial computational foundations to a seemingly-diverse series of applications that will all benefit from improved numerics brought on by these structure-preserving computations.

Research Challenges:

  1. Mixing numerical benefits of variational integrators (VI) and discrete differential geometry (DDG): To remedy the lack of a unified treatment of VI and DDG, and to offer spatiotemporal structure preservation, we seek novel spatial and temporal motion discretization methods to facilitate the combination of the two areas.
  2. Diverse goals of animation and simulation. Simulation normally requires accuracy, while animations in interactive software requires efficiency. Despite the aims at different aspects of motion and dynamics, we will develop a series of seemingly diverse applications based on the common numerical foundations.

 

Current Results:

  1. Develop novel motion description for fluid with fixed boundaries.
  2. Develop fundamental spatial description for surfaces, and apply it in mesh deformation.
  3. Develop Eulerian discretization of Lie-derivatives for differential forms, which are present in various PDEs.
  4. Develop real-time Lagrangian physically-based simulation for water drop and solid surface interaction.
  5. Develop 3D guidance vector field design method, applicable to various FEM problems.
  6. Develop hexahedralization method, applicable for the discretization of simulation domains as well as 3D objects.
  7. Develop solid-fluid interaction for efficient shallow water simulation, for interactive simulation in graphics.
  8. Develop topological features in 3D surfaces, applicable to simplification and feature detection during simulation.
  9. Develop 3D data structure, for efficient representation of geometric shapes with a small memory footprint.
  10. Develop tools for molecular surface geometric modeling and simulation.
  11. Develop spetral discrete exterior calculus for modeling and simulation.
  1. Develop spectral model-reduced variational fluid simulator.
  2. Develop tensor analysis on meshes.

 

Publication:

(Note: preprint/postprint pdf files may differ in layout from the copyrighted versions)

  1. Power Coordinates: A Geometric Construction of Barycentric Coordinates on Convex Polytopes, Max Budninskiy, Beibei Liu, Yiying Tong, and Mathieu Desbrun, ACM Transactions on Graphics (SIGGRAPH Asia) 2016
  2. Optimal Voronoi Tessellations with Hessian-based Anisotropy, Budninskiy, Liu, de Goes, Tong, Alliez, and Desbrun, ACM Transactions on Graphics (SIGGRAPH Asia), 2016
  3. Discrete connection and covariant derivative for vector field analysis and design, Liu, Tong, de Goes, and Desbrun, ACM Transactions on Graphics (TOG), 2016
  4. Model-reduced variational fluid simulation, Beibei Liu, Gemma Mason, Julian Hodgson, Yiying Tong, and Mathieu Desbrun, ACM Transactions on Graphics (SIGGRAPH Asia), 2015
  5. T Jiang, X Fang, J Huang, H Bao, Y Tong, M Desbrun, "Frame Field Generation through Metric Customization", ACM ToG (SIGGRAPH) 34 (4), 2015
  6. K Xia, X Feng, Y Tong, GW Wei, "Persistent homology for the quantitative prediction of fullerene stability", Journal of computational chemistry 36 (6), 408-422, 2015
  7. F de Goes, B Liu, M Budninskiy, Y Tong, M Desbrun, "Discrete 2-Tensor Fields on Triangulations", Computer Graphics Forum (SGP) 33 (5), 13-24, 2014
  8. J Huang, T Jiang, Z Shi, Y Tong, H Bao, M Desbrun, "l1-Based Construction of Polycube Maps from Complex Shapes", ACM Transactions on Graphics (TOG) 33 (3), 25, 2014
  9. Z Pan, J Huang, Y Tong, C Zheng, H Bao, "Interactive localized liquid motion editing", ACM Transactions on Graphics (TOG) 32 (6), 184, Nov 2013
  10. Jiang, T.; Huang, J.; Wang, Y.; Tong, Y.; Bao, H., "Frame Field Singularity Correction for Automatic Hexahedralization," Visualization and Computer Graphics, IEEE Transactions on , vol.PP, no.99, pp.1, (accepted) 2013
  11. K Xia, X Feng, Z Chen, Y Tong, GW Wei , "Multiscale geometric modeling of macromolecules I: Cartesian representation". Journal of computational physics 257, 912-936, Jan 2014
  12. X Feng, K Xia, Z Chen, Y Tong, GW Wei , "Multiscale geometric modeling of macromolecules II: Lagrangian representation". Journal of computational chemistry 34 (24), 2100-2120, Sept 2013
  13. Beibei Liu, Yanlin Weng, Jiannan Wang, and Yiying Tong. "Orientation field guided texture synthesis". Journal of Computer Science and Technology (CVM), 28(5):827–835, Sept 2013.
  14. Xin Feng and Yiying Tong. "Choking loops on surfaces" IEEE Trans. on Vis. and Comp. Graph., Aug 2013.
  15. Xin Feng, Yuanzhen Wang, Yanlin Weng, and Yiying Tong. "Compact combinatorial maps: A volume mesh data structure." Graph. Mod. (75), May 2013
  16. Jeffrey R. Van Voorst, Yiying Tong, and Leslie A. Kuhn. "ArtSurf: a method for deformable
    partial matching of protein small-molecule binding sites    ." In ACM International Conference on
    Bioinformatics, Computational Biology and Biomedicine, 2012.
  17. Xin Feng, Kelin Xia, Yiying Tong, and Guo-WeiWei. "Geometric modeling of subcellular structures,
    organelles, and multiprotein complexes    " Int. J. for Num. Meth. in Biomed. Eng., 2012.
  18. Yuanzhen Wang, Beibei Liu, Yiying Tong "Linear Surface Reconstruction from Discrete Fundamental Forms on Triangle Meshes" Computer Graphics Forum , 2012
  19. Zherong Pan, Jin Huang, Yiying Tong, and Hujun Bao. "Wake synthesis for shallow water equation" Comp. Graph. Forum (Pacific Graphics), 2012.
  20. Yizhong Zhang, Huamin Wang, Shuai Wang, Yiying Tong, Kun Zhou. A Deformable Surface Model for Real-Time Water Drop Animation, IEEE Transactions on Visualization & Computer Graphics, 2011. pdf
  21. Jin Huang, Yiying Tong, Hongyu Wei and Hujun Bao. Boundary Aligned Smooth 3D Cross-Frame Field. ACM Transactions on Graphics (SIGGRAPH Asia), 20 (6) , 143:1--143:8 , Dec 2011. pdf
  22. Dmitry Pavlov, Patrick Mullen, Yiying Tong, Eva Kanso, Jerrold E. Marsden, and Mathieu Desbrun. Structure-preserving discretization of incompressible fluids. Physica D: Nonlinear Phenomena, March 2011. pdf
  23. Patrick Mullen, Alexander McKenzie, Dmitry Pavlov, Luke Durant, Yiying Tong, Eva Kanso, Jerrold E. Marsden, and Mathieu Desbrun. Discrete Lie advection of differential forms. Foundations of Computational Mathematics, Volume 11, Number 2, 131-149, 2011. pdf
  24. Jin Huang, Yiying Tong, Kun Zhou, Hujun Bao, and Mathieu Desbrun. Interactive shape interpolation through controllable dynamic deformation. IEEE Trans. on Visualization and Computer Graphics, 17(7),  pp. 983-992, July. 2011. pdf

 

Presentation:

  1. Geometric Integrators for Incompressible Fluids, Mechanical Engineering Seminars, MSU, April 19, 2011.
  2. Introduction to Discrete Exterior Calculus, Zhejinag University, May 2011.
  3. Discrete Fundamental Forms and Mesh Deformation, Discrete Differential Geometry Workshop @ SoCG, June 2012
  1. A Discrete Version of the Fundamental Theorem of Surfaces, CVM, Tsinghua University, Nov 2012
  2. Applications of Differential Geometry and Topology in Computer Graphics, Frontiers of Information Science and Technology Workshop, Shanghai, Dec 2012
  3. Tunnels, Handles and Bottlenecks, CTW: Mathematical Challenges in Biomolecular/Biomedical Imaging and Visualization, OSU, Feb 2013
  4. Bottlenecks of 3D Domains, Workshop on Persistent Homology for Biosciences, East Lansing, October 2014
  5. Spectral Discrete Exterior Calculus, Workshop on Discrete Differential Geometry, Oberwolfach, Germany, Mar 2015
  6. Vector field processing on triangle meshes, do Goes, Desbrun, and Tong,

SIGGRAPH Asia 2015 Courses

  1. Vector field processing on triangle meshes, de Goes, Desbrun, and Tong, ACM SIGGRAPH 2016 Courses

 

 

 

Download Software and Educational Material:

  1. We are developing a package for mesh deformation.

a. A guide to install CGAL library that we use on Windows. Downlaod

b. An MFC-based code to run CGAL. Download

c. Compact 3D Data Structure. Download

d. A viewer for the above Data Structure. Download

e. A shader based OpenGL base code for MFC. Download.

f. A textured shaded cube based on the above code. Download.

g. A fingerprint synthesis tool based on orientation field guided texture synthesis. Send request to ytong@msu.edu
h. Robust molecular surface generation based on regular grid data. (code by Beibei and Rundong, tested and maintained by Dr. Guowei Wei's group)

i. Power coordinates: linear accurate non-negative interpolation basis on convex polytopes. (code by Beibei Liu and Max Budninskiy)

  1. We are developing a package for physically-based simulation.

a. A simple circulation preserving fluid simulation java applet based on the implementation by Alex McKensie. Download

b. A step-by-step tutorial for 2D stable fluids based on Jos Stam's paper. Link

c. A step-by-step tutorial for rigid body simulation for a cube. Link (tutorial base code: courtesy of Dr. Charles B Owen.)

d. Simple rigid body simulation on WebGL. Link (step by step construction http://www.cse.msu.edu/~ytong/WebGL/)

 

Broader Impacts

 

We are exploring the application of the motion descriptions and integrators on molecular surface matching and reduction of biomolecular dynamical processes involving large molecules immersed in fluid environments.

 

Point of Contact:  Yiying Tong (ytong@msu.edu)

 

Last update: 10/05/2016

 

Acknowledgement:
 This material is based upon work supported by the National Science Foundation IIS-0953096.
 

Disclaimer:
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.