Continued Development on Adaptive Cloth Simulator for Blender: Final Report

Summary:

A lot of development on the Adaptive Cloth Simulator has been done in the past 10 weeks. It is close to ready to merge with master. A larger portion of the 10 weeks was spent on implementing a new mesh structure which aids with speed and maintainability. The later portion of GSoC was spent on adding static remeshing support. There were many unexpected challenges along the way. After my GSoC 2019 project, there have been many changes in Blender (improvements wrt the C++ containers, C++ classes for vectors and matrices, etc.), so it was not possible to only refactor my GSoC 2019 project for stability as initially planned. It turned into a complete rewrite due to which it has taken longer than expected. Even though this was not part of the plan, this is definitely for the better when it comes to performance and future maintainability of the code.

There are some minor bugs to be fixed and one feature that remains to be implemented (dynamic remeshing support, an extension to the already implemented static remeshing in the cloth simulator).

During these 10 weeks, I also implemented a specialized tool (Mesh Analyzer) to aid me in development. Many features were added to this tool as needed during the development process.

I would like to thank Sebastian Parborg and Sebastián Barschkis for their mentorship :)

Details:

New mesh structure:

Implementing a new mesh structure was an important step towards stabilizing this project for master. It is primarily based on Adjacency and Incidence Framework (AIF) [8] but with modifications that are made for speed and usability for this project.

There are 4 components of the mesh- nodes, verts, edges and faces. Nodes store the 3D coordinates of the mesh and a node also stores references to all the verts that refer to this node. Verts store the 2D (UV) coordinates of the mesh and a vert also stores references to all the edges that refer to this vert. Each vert also stores a reference to a single node. The edges are considered to be the glue between the faces and verts, each edge stores references to all the faces that are adjacent to this edge and also stores the verts that form this edge. Each face stores references to all the verts that form this face.

I implemented a container called generational arena which is extremely fast for data whose order doesn't matter but still needs an index based access of the elements. Inserting and deleting elements is O(1) and the elements are accessed via a generational index which stores the position of the element and the generation when the element was added to the arena. This has the benefit of avoiding the "ABA problem" in multi-threaded and single-threaded workloads. The above mentioned mesh structure stores the nodes, verts, edges and faces in generational arenas and the references between the elements is stored using generational indices. This has allowed the mesh structure to be pointer free while having similar performance to a structure that relies on pointers. This also means that invalid references are caught early with more information than a structure relying on pointers.

Many functions were implemented to access different elements of the mesh through other elements. These were then used to implement the 3 main operations on the mesh- split edge, collapse edge, flip edge. These operations are later used for implementing the remeshing stage of the cloth simulator.

Changes to the cloth modifier:

With the addition of remeshing, the cloth modifier is no longer a deform type (deformVerts) modifier but is converted to a non deform type (modifyMesh) modifier. The modifier now also stores the previous frame mesh, so when remeshing is enabled and the previous frame mesh is available and valid, it uses this mesh instead of the mesh provided to the modifier.

Certain features of the cloth simulation like dynamic vertex groups, or dynamic base mesh are disabled when remeshing is active since such features cannot be supported when the mesh is constantly changing.

The function that does the remeshing operation is called at the end of the simulation step (do_step_cloth()).

Mesh Analyzer

The new mesh structure stores many internal references between elements and visualizing these references is extremely useful. So I built a specialized tool to aid with this and more. Any element in the mesh can be selected and the tool visualizes all the other elements that the selected element refers to. This helped solve bugs in the operations that change the mesh structure. It was especially useful in debugging the collapse edge function of the mesh.

Since Mesh Analyzer is a standalone tool, the mesh in Blender is serialized to msgpack, a compact binary file format and stored to disk. These files are deserialized by Mesh Analyzer for further analysis and visualizations.

In many parts of the Adaptive Cloth implementation, visualizations and analysis of the mesh prove to be helpful. While testing if an edge is flippable, there are various criteria that must be considered, one of which is anisotropic aware. The criterion needed to be modified (which are not in line with the research paper followed) and for this, analyzing this part separately was beneficial. Another such instance was when calculating the aspect ratio of the triangles (faces) of the mesh. While integrating with the cloth modifier, parts of the simulation did not work as expected. To solve this, I implemented a feature that provides real-time information (both as visuals and text) about the simulation data.

Static remeshing

Each vert in the mesh is assigned a certain "sizing" in the remeshing process. Dynamic remeshing involves calculating this "sizing" on the fly and static remeshing sets a fixed "sizing". With the "sizing" information available at every vert, the size for all the edges of the mesh is determined. The basic idea of remeshing is to split all edges that exceed the size of one and collapse all edges that are less than the size of one. Edges of newly created faces are flipped if they don't meet the anisotropic aware criterion. This is implemented by utilizing the split edge, collapse edge and flip edge operations implemented in the mesh structure.

There are 2 parts to highlight for which the implementation differs from what is proposed by the research paper [6]:

The research paper [6] proposes that when splitting all the edges, a maximally independent set of splittable edges must be found by selecting a splittable edge only if its verts were not already selected by a previously selected splittable edge. Although this is a valid way to find a set of splittable edges, it doesn't work well in practice. It is possible to have 2 edges that share a vertex and when split, do not affect the other edge. When the proposed is implemented, it leads to, in some sense, asymmetrical remeshing which is not the intended result. A simple approach to solve this problem is to consider all the splittable edges and sort them based on their edge size such that the largest edge is split preferably. For each edge in this set, consider this edge for further processing only if the edge still exists in the mesh. This leads to much better mesh results in practice.

The research paper [6] proposes an anisotropic aware criterion to test if an edge is flippable. The proposed criterion in practice leads to infinite flipping of an edge where the criterion is met for the selected edge and the edge that would be formed after the flip. In the process of finding the solution to this problem, I found a subsequent paper [7] that attempts to solve this problem by adding an extra metric that it must satisfy but this too has its own drawback, it requires the verts to be chosen in a specific order which cannot be guaranteed always. The final solution implemented is a slight modification of what is proposed in the subsequent paper. The Mesh Analyzer was extremely useful for finding the solution.