GSoC 2020: Soft Body Sim - Weekly Reports

Work will be committed to the soc-2020-soft-body branch in the extern/softbody and intern/softbody directories if you want to check it out.

This thread is for weekly reports. Please post comments to the discussions and suggestions thread.

14 Likes

Week 1

  • First pass at implementing the solver and API
  • Edits to the current softbody simulation code to call new solver and return results
  • Not fully functional at the moment: details below

Blender does not have any support for tetrahedral meshes. In order to verify the solver/API are working, I generate an extremely simple “lattice” around the input surface mesh. This is nothing more than embedding the surface vertices in a few tets that fill the entire space. This helped me verify I was indeed updating the vertices in the solver correctly, mapping them back to the surface vertices, and passing that information to Blender to view the results in the viewport. However this rudimentary lattice does not produce any interesting dynamics, and it is not stored in the cache. Of course this is only temporary, and expanding/improving the input is the focus of next week.

Next week:

  • Add a mesh operator to tetrahedralize the mesh using TetGen.
  • Some viewport functionality to see/inspect the tetmesh
9 Likes

Week 2

  • Added tetrahedralization mesh operator in remesh. You can view the interior by entering edit and deleting vertices. Attached is an image of the ico-sphere in wire frame showing the internal elements.
  • The solver code calls the remesher operator on initialization and stores the tets internally.
  • Set up the solver to interface with the point cache. I think this will still need some improvement, as there are some unnecessary copies going on which will slow down high resolution sims. You can now bake the sim, or backtrack/restart at different spots between initialization and the last frame.
  • Added CPU threading to a few places within the solver.

Next week:

  • Improve the lattice/cage generation which embeds the surface mesh. This is an alternative to the tet-mesher.
  • Improve API between Blender and the solver to avoid unnecessary copies.
10 Likes

Week 3

  • Improved API between solver and Blender to reduce redundant copies. Also fixed a bug where some vertices (that are a part of the tet mesh and not surface mesh) were not being cached properly. Still some issues related to starting/restarting sims and the model xform, but I’ll work those out soon.
  • Updated lattice generation. Right now it is a grid of variable length that fully encloses the surface mesh, each grid cell makes up 5 tets. This can be improved in the future to by subdividing certain grid cells.
    • Before implementing cell subdivision, we’ll want to review metrics for determining if a grid cell should be subdivided. There is related literature on this.
    • Using a grid/lattice this way has some benefit. In particular it allows animators/users to directly increase resolution in areas of interest (e.g. surface of the mesh), and reduce resolution where it is less important (e.g. interior of the mesh). Though if there are any animators reading this that have other thoughts and opinions, I would be happy to hear them!
  • Implemented a basic AABB tree with a generic interface for traversal. It is currently being used in the lattice generation to remove unnecessary cells, and will also be used in collision detection. I’ll be making use of the kernels in BLI_math_geom.h for a lot of this.
  • Attached is an example of the Suzanne colliding with a ground plane. The lattice is not visible. Not that interesting or a good stress test, but shows that things are behaving as expected.

Next week

  • Self collisions and collisions with other objects in the scene.
  • Interface with “goal positions” to allow scripted motion.
  • Some more interesting test cases.

13 Likes

I’ve added a new page to keep track of longer-term next steps: link to roadmap. There is a growing and never-ending list of to-do’s, so I’ll keep them in one place.

Quick note: if you have questions regarding details of this project or solver, please feel free to post it in the discussion or message me directly. All questions from all experience levels are okay! I don’t go deep in the weeds with these updates or the proposal, so I’d be happy to clear up any confusion.

Week 4
There was a request for more interesting demos (also GSoC first eval coming up :wink:), so I added one similar to the horse in the original paper. Some notes on the attached video:

  • Armadillo surface has about 346K faces, 173K vertices. The deformation lattice is extremely low resolution (~400 tets and ~200 vertices), and that has some obvious artifacts in a few places like the legs shearing/flattening at the second cylinder bounce. It looks surprisingly okay despite the low res lattice.
  • The interface for lattice gen is a bit clunky. You can expect improvements on that in the future. Admittedly I don’t have any experience with embedded defo, so I’m looking forward to experimenting :slightly_smiling_face:.
  • The whole simulation took ~4 minutes and nearly all of the solver time was spent on collision detection, which is performed on the surface mesh and resolved on the lattice. Collision detection is performed per-vertex and every solver iteration, and I was using 50 iters per-timestep (1/24 s). So that’s a lot of queries.
  • While the cylinders are stationary, the code does support moving obstacles.

To get the dillo-drop-demo up and running:

  • Added mesh-obstacle collision detection. I wanted to use Blender’s built in CCD for mesh-obstacle collisions, but that was tricky because collision detection happens within the solver iterations. There are workarounds, of course, but I need to implement self-collision regardless. Considering that, it made sense to roll my own collision detection code.
  • Fix some bugs in the solver code (oops). This took up more time than I hoped.

Next week

  • Scale up/improve lattice generation.
  • Revise linear solver and constraint formulation. I’m not confident the current constrained linsolver will scale well to larger res.
  • Self collisions.
33 Likes

WOW! I just can’t believe what I’m seeing here… Thanks by the efforts to bring this so useful feature @mattoverby
Is it possible to test the current implementation?
I would like to contribute making videos examples to demonstrate the usage or even for documentation if you need…

Would it make sense to look at SDF based collision detection now that Blender has OpenVDB support ? Thats one way Houdini solves collisions is volume based sampling. Might be worth looking…

Yes, I commit all of my code to the soc-2020-soft-body branch. However, the interface is a bit clunky right now as I am focused on building the solver. If you would like to try it anyway, all collision obstacles must be joined into the same object (right click -> join) before begin made a collision object. Baking/cache and all that should work normally. If you do happen to make any neat demos I would be happy to see them :slight_smile:

It absolutely would. In fact my first pass at collision detection was using SDFGen. That worked okay and I had plans to revisit that. I have never used OpenVDB but that seems like a good option.

1 Like

Week 5

Two updates: lattice generation and constraint formulation/linear solver. There is a lot of text below, but it is mostly background information for those wanting to learn more about the project. As always, feel free to message me with questions/suggestions.

Lattice generation:
Recap: A high resolution surface is “embedded” in a low-resolution deforming lattice. Dynamics are computed on the lattice and the embedded surface is updated accordingly. This sacrifices some fidelity in dynamics, but significantly improves run time and usability.

I reimplemented the lattice generation to allow better control on resolution and get smaller tets/more vertices on the surface than the interior, which gives us better-looking dynamics. It’s built in a top-down manner by subdividing boxes into 8 smaller boxes until a specified resolution. A box is only split if it contains the embedded surface. While it does what I wanted, it’s unfortunately a bit slow (e.g. it takes a second or two to generate the Armadillo from last week’s update). So, I still don’t like it, and will continue to make changes in the future. Attached is an image of the embedded surface rendered outside of Blender.

Constraint formulation and linear solver:
Recap for those who have not read the TVCG paper or are not familiar with projective dynamics or ADMM-PD: the solver works through alternating mimizations of the sum of elastic energies (local step) and momentum potential (global step). The former is parallelizable and the latter is a linear solve, in which the factorization can be precomputed assuming no change in topology. This provides some benefits over classic descent-type solvers in terms of robustness, rapid early-iteration convergence, and being linesearch-free. In the TVCG paper we found that resolving certain constraints (collisions, pins, attachment/slide) during the global step is much more effective than the local step. This update refers to different ways to solve the resulting constrained linear system but is a slight departure from the methods in the linked TVCG paper.

I hoped I would be able to process collisions as temporary pin constraints, i.e. c(x)=x-p, with x being the colliding vertex and p being the point-of-impact. This would allow some convenient speedups in the global step due to the structure of the problem. Unfortunately processing collisions this way has the obvious effect of sticking and loss of tangential sliding motion, more than I hoped or expected. This goes away at smaller time steps and more iterations, but doing so negates the speedups provided by treating collisions as pin constraints. Instead I went back to the usual formulation, c(x) = n^T(x-p), which required a lot of restructuring of the code.

I’ve implemented two solvers, preconditioned conjugate gradients (PCG) which uses the prefactored mass-weighted Laplacian as the preconditioner, and multi-color Gauss-Seidel (MCGS). I plan to support both solvers throughout the project, as both provide different benefits depending on the problem. PCG relies on the prefactored matrix but has faster convergence and is overall better for general problems. MCGS has slower convergence but does not rely on prefactorization (though the cost of graph coloring is non-negligible). There are some hidden benefits to MCGS: If the constraint queries are cheap they can be queried inside the Gauss-Seidel sweeps. This makes it very effective as resolving certain constraints, e.g. pin and attachment/slide (findings of the TVCG paper). That’s why I aim to support both solvers.

Next week

  • Finish MCGS solver (still working out a few bugs).
  • Revise collision detection - it is the primary bottleneck

21 Likes

Hi there, impressive work!

I just read a comment of the user “Lapis Sea” (Blender.Today Q&A #111) talking about IPC. I don’t really know anything about this stuff but maybe you will find it interesting. I’ll copy his comment here:

Lapis Sea

Hi Pablo (the undisputed blender king) and guests!

There came some really cool things out of SIGGRAPH 2020! One of them I took notice in in specific. It is a soft body solver to rule them all. It has an open source C++ implementation under MIT License.

I was wondering if things like this are to be considered for incorporation in to the blender solver family?

2 Likes

Thanks Xnet. The discussion thread might be a better place for this, but I’ll respond here anyway.
Yes, I am familiar with IPC. I don’t see a reason why Blender can’t have multiple soft body solvers and allow the user to choose between them. That’s up the devs in the end.

3 Likes

Week 6

Minor things:

  • I’ve started to tag various commits as “stable”. If you’re interested in trying out the code, these are the ones to clone. The latest is softbody-stable-v2 which has pin constraints and collisions against obstacles.
  • Fixed some bugs in the parallel Monte Carlo graph coloring.
  • Investigated stability issues in the parallel Gauss-Seidel solver. This has to do with the matrix being non-diagonally dominant when constraint stiffness is high. I tried a few approaches to mitigate this (such as building the matrix more carefully) but I’ll need to keep poking at that further before it’s robust. For now we’ll stick with the PCG solver in the global step as the default.

Added goal positions (pin constraints)

  • Added pins/goal positions which are treated like springs based on the vertex group weight. These should behave as they did in the old softbody solver. You can paint on the weight, set the “goal” vertex group in the softbody settings, and let it simulate. For now the stiffness values shown in the softbody options are ignored and only the vertex group weight is used. You should be able to script motion with this, but I don’t know how to do that in the interface, hah!

Here’s an example of a swinging dillo. Reasonably fast when there aren’t collisions. A lot of the overhead is just copying the mesh data from Blender to the solver. But, I think need to do a better job distributing the mass of the mesh to the lattice vertices - the legs don’t flop around as much as I want them to.

Next week

  • Continue revising collisions and/or self collision
  • Better mass distribution from mesh to lattice
18 Likes

FYI new IPC softbody code. Opensource, MIT licence.
https://youtu.be/y96jk-eUCgI — demo
https://github.com/ipc-sim/IPC — code

1 Like

Wow, IPC seems pretty cool, may not be possible to include it under this GSOC, but it seems amazing.

I hope we can end up using the evolution of softbodies here with particle nodes / physics nodes, (IPC or not IPC) to do node controlled simes of noodles and such things :slight_smile: