Note: This is an archived version of the Blender Developer Wiki (archived 2024). The current developer documentation is available on developer.blender.org/docs.

User:Mattoverby/GSoC2020/mattoverby final report

Volumetric Soft Body Simulation Blender - GSoC 2020 Final Report

Summary

A volumetric soft body solver was successfully implemented in the Blender code base. The soft body solver differs from the previous Blender implementation in many ways, primarily that it is an implicit (Backward Euler) integrator capable of large time steps, volume preservation, and nonlinear material models. The solver has three mesh modes that change the way it deforms the input surface mesh. Embedded mode computes an invisible low resolution cage and updates the input surface mesh through linear interpolation. TetGen mode tetrahedralizes the input mesh. Cloth mode treats the entire input mesh as a cloth. Several important types of constraints have been implemented, such as collisions with moving obstacles, self intersections, and goal positions for user interaction. Many of the solver parameters are mapped to intuitive options in the Blender user interface. The implementation is conducive to future improvements, such as additional elastic material models, constraints (e.g. surface attachment), and even different third-party solvers.

Divergence from the proposal

The original goal was to produce an optimized soft body solver designed for character animation, i.e. volume preserving skinning under collision. Doing so would have considerably narrowed the allowable types of mesh input, typical constraint scenarios, and tools for user interaction, and more time could have been spent improving the speed, robustness, and interactivity. Instead, the scope was broadened to allow many types of mesh deformation, e.g. cloth simulation, deformable bodies colliding with moving obstacles, meshes with degenerate or thin features, embedded and tetrahedral volumetric meshes, etc… The end result is a solver that fast, robust, and general to a wide range of deformation tasks, but is not optimized for any one specific task. There are some concrete benefits and limitations of the chosen algorithm, listed below.

Pros:

  • Rapid initial convergence provides a reasonable looking solution very quickly
  • Generality to different hyperelastic material models
  • Robust to extreme deformation and volumetric inversions
  • Robust to input mesh quality, e.g. sliver and irregular tetrahedralization, non-closed and non-manifold meshes
  • Discrete online collision detection allows meshes to start in a penetrating state and respond to new collisions detected during the solve
  • Extensible to different applications - while the current implementation is a general solver, it can easily be modified and optimized for specific tasks, e.g. skin slide or tight clothing, character skinning, cloth simulation, static mesh optimization, and more

Cons:

  • Embedded simulation will look more damped and less jiggly than a tet mesh
  • ADMM-PD convergence tails off and has poor angular momentum conservation, it may take a long time to find an exact solution
  • Discrete collision detection results in tunneling or poorly defined constraints for large time steps and thin features
  • Collisions are nodal, so edge-edge contact is ignored
  • Penalty constraints may not be fully resolved by the end of the simulated time step

Work Completed

Volumetric mesh generation

Blender does not have a standard format for volumetric (tetrahedral) meshes, which most soft body solvers operate on. The input provided by Blender to the soft body solver is a triangle mesh, which may be non-closed and non-manifold. As a result, robustly supporting different types of mesh input and simulation scenarios ballooned into the most time consuming goal of the project.

If the mesh is closed it can be tetrahedralized by TetGen. However, TetGen may still fail under various circumstances in which case an error message will alert the user and the solver will not attempt to deform the vertices. In most cases the quality of the tetmesh has an impact on the quality of the dynamics. To allow the user to investigate the quality of the tetmesh, there is now a tetmesh remesh operation. The user can run TetGen, slice the mesh, and see the resulting interior.

Tetmesh.png

Alternatively, the triangle mesh may be embedded in an invisible cage, or lattice. This can be useful when the resolution of the surface mesh is high, but the amount of deformation it will undergo is minimal. This lattice is constructed to fully enclose the input triangle mesh using a tetrahedralized regular grid. The grid cells that contain surface triangles are subdivided down to a user-specified amount. The goal is to allow more tetrahedra on the surface than the interior, which can improve visual quality while keeping the solver degrees of freedom low. The lattice is deformed by the solver, in which the surface vertices are updated through barycentric weights. Both self collisions and collisions with other obstacles are detected on the embedded mesh, but resolved on the lattice through stiff penalty springs. Like TetGen, a remesher operation is available to inspect the generated lattice.

Monkeylattice.png

For example, the default monkey mesh in blender is non-closed. As a result, TetGen does not produce a mesh with appropriate surface features, but the embedded lattice is usable.

Tetremesher.jpg

Blender interface to support alternative soft body solvers

Another challenging part of this project was altering the code base to support new and custom external soft body solvers. Unlike the previous implementation (legacy), most soft body solvers need to store some persistent data between time steps. Often this data can be expensive to compute, e.g. matrix factorizations. This became an issue with the multiple ways soft body data was copied (e.g. copy and paste, duplicate, copy-on-write with parameter change, reading and writing to file.) The soft body code is now structured in a way that a new external soft body solver can more easily be added by following the steps taken with ADMM-PD.

ADMM-PD solver

The ADMM-PD solver was implemented from the ground up over the duration of this summer. There are two primary differences from the original method. First, the mesh is capable of resolving embedded mesh deformation with collisions. Second, the global step is solved with preconditioned conjugate gradients and treats constraints as a quadratic penalty. The final algorithm is a generic-as-possible solver that can be used for a wide range of visual effects tasks. As mentioned previously, the downside to this is that it is not optimized to do any one specific task. It is my hope that when certain tools are needed in the future, the ADMM-PD solver can be retrofitted and utilized with minor changes.

Here’s an example of a simulation produced by Everton Schneider using the ADMM-PD solver:

Hammer.gif

Very briefly, the algorithm is: 

   Generate mesh if first time step
   Initialize constant solver variables
   For i … max iterations
       Minimize elastic energies (local step)
       Detect collisions and generate constraints
       Solve constrained linear system (global step)
       Stop iterating if converged
   End

Here’s where the above algorithm is represented in the code:

  • admmpd_mesh: This file is responsible for generating cloth and volumetric meshes from Blender input. New types of meshes can be added here.
  • admmpd_collision: Given a certain mesh type, this file is responsible for detecting collisions. All collisions (both self intersections and with obstacles) are handled in a discrete manner. That is, at the current state if a surface vertex is penetrating, a constraint is formed to project it to the nearest surface. The benefit of this is that detection is quite fast and robust, and allows the mesh to start the time step in an intersected state. But If the displacements are too large tunneling may occur.
  • admmpd_energy: This houses the elastic energy minimization code, i.e. the ADMM local step. If new energy models (e.g. Stable Neo-Hookean, Mooney-Rivlin, Fung) are desired, they can be added here in the switch statements. All that’s needed to add new material models is the energy density, gradient, and Hessian. The ease at which new models can be added to the solver is one of the benefits to ADMM-PD, in which even barrier or incompressibility terms do not significantly impact solver performance.
  • admmpd_linsolve: This is the linear solve, i.e. ADMM global step. You will find an implementation of preconditioned conjugate gradients (PCG), in which a factorization of the mass weighted Laplacian is used as the preconditioner. This Laplacian remains constant as long as the topology does. However, there is no reason this cannot be changed to a different solver if certain applications justify it (e.g. multi-color Gauss-Seidel, which is commented out because of stability concerns when applied to certain problems.)
  • admmpd_solver: This is the main driver of the algorithm and runs the solver iterations.

Suggested Future Work

Blender tetrahedral mesh object type

Improving tetmesh and lattice generation is necessary for better soft body simulation.

Currently the ADMM-PD solver will accept a surface mesh and attempt to form a lattice or tetmesh with TetGen. One issue to this pipeline is that the surface of the resulting mesh cannot change the surface topology.

A remesher operation is available to inspect the mesh ADMM-PD would create, but the mesh created by the remesher is for visible inspection only. It would be far more versatile and useful to animators to store the output of this remesher data. Then, other non-surface-preserving but more robust tet meshing software (e.g. TetWild) can be used to generate the mesh. This would also allow the user can more easily define the initializer and rest state, which for now is defaulted to whatever the state of the mesh is at frame 1.

Select solver by application

There is no one-size-fits all soft body solver. That is why the current implementation is designed to be as generic-as-possible, so that it can later be retrofitted to specific tasks. A useful feature would be a drop-down button can be used to select versions of the solver by application, e.g. volumetric skinning, contact and friction, etc... These application choices could also be used to select between different solvers that are more suited for a specific task, e.g. IPC for contact and friction.

Improvement to the ADMM-PD solver

Acknowledgements

Thank you Everton Schneider for all the testing animations, and thank you Sebastian Parborg for being my GSoC mentor.

Retrieved from "https://wiki.blender.org/w/index.php?title=User:Mattoverby/GSoC2020/mattoverby_final_report&oldid=18918"