Went through and updated notes related to the cloth simulator and
the modifiers.
Had a discussion with @ZedDB on whether to make the remeshing step a
separate modifier or to integrate it directly with the cloth
modifier. Came to the conclusion that creating a new modifier and
having it work well with the cloth modifier (or any future modifier
that depends on this new modifier) might take up too much time and
may not be possible to complete within the time limits of GSoC. Thus
the remeshing step will be directly integrated with the cloth
modifier.
Converted the cloth modifier from an only deform (deformVerts)
modifier to a non constructive (modifyMesh) modifier (still need
to add back support for Dynamic Meshes and Hair simulation).
Started work on a better test suite than that made in 2019.
Plan for following week
Work on the new Mesh structure needed for the remeshing step.
Created a new container (with respective tests), a generational
arena. Each element has an associated “generation” so indexing is
done via a special structure Index which contains the location of
the element as well as the generation when the Index was generated
aka when an element in inserted. Deleting an element involves
marking the element in the array as empty, updating a list which
stores the next free location and incrementing the generation. When
inserting an element, it checks if any free locations exist and
makes the necessary changes to the array and the list of free
locations. With a generational arena, inserting and deleting
elements is O(1), and elements are accessed via Index avoiding the
“ABA problem” (in multi-threaded and single-threaded workloads).
For the mesh structure, generational arena allows for adding
references to other elements by storing Index instead of working
with pointers. This leads to less error prone code, allows for
faster debugging, all while maintaining run time speed similar to
that of using raw pointers.
Created the basic classes needed for the mesh structure based on
“Adjacency and incidence framework: a data structure for efficient
and fast management of multiresolution meshes” by Frutuoso
G. M. Silva and Abel J. P. Gomes (GRAPHITE '03) with some
changes. Documentation for this is ongoing.
Plan for following week
Continue work on the mesh structure.
Add a conversion to and from Blender’s DNA Mesh.
Start work on mesh operations like- split edge, collapse edge,
flip edge.
The new mesh structure is now complete. The mesh operations can now
be worked on.
Added a new method to interface with other mesh
structures/files. This makes it easier for conversion between
different mesh structures due to the simplicity of the MeshIO
structure.
Added support for loading from and saving to Wavefront OBJ for
easier debugging.
Test cases for each of the above.
Created notes about DNA Mesh.
Plan for following week
Continue work on the mesh structure.
Add a conversion to and from Blender’s DNA Mesh.
Start work on mesh operations like- split edge, collapse edge,
flip edge.
MeshIO now supports reading from and writing to DNA Mesh.
Adding tests for this was challenging.
Creating a DNA Mesh is not possible without initializing idtype using BKE_idtype_init() (there should actually be a
check for this, at least in debug mode).
BM_mesh_bm_to_me() and BKE_mesh_from_bmesh_eval_nomain() can
be used to convert BMesh to DNA Mesh. The CustomData
blocks stored in the BMesh are copied over but for some
reason, BMesh does not update the blocks corresponding to mvert, mloop, mpoly, etc. during the operations on BMesh
(for which I had used BMO_op_callf()). This leads to the newly
formed DNA Mesh to have incorrect values in mvert, mloop, mpoly, etc. One way to fix this is to create a copy of the BMesh, which internally initializes the blocks correctly, and
using the copy to convert to DNA Mesh. This method is not
ideal but since this is only in the test suite, it should be
good enough.
Mesh and MeshIO now support loose edges.
The cloth modifier now creates and returns a new Mesh only if
needed.
Started work on the mesh operations.
MeshDiff class will be returned for every operation
In the future, adaptive remesh is going to need to know which
elements were updated (added or deleted) during the operation,
thus each operation should return the updated elements via the MeshDiff class.
Plan for following week
Continue work on mesh operations like- split edge, collapse edge,
flip edge.
Hi, @ish_bosamiya
I’m trying to know more about this project and I’m very surprised! This is very exciting, thank you for bringing this to blender.
I’m still trying to understand this project but is this quoted text related to the cloth tearing effect?
EDIT
I just saw in the proposal under benefits that you mention Adaptive Cloth Tearing for this year.
Thank you so much! This is very exciting!
Is the branch compileable and ready for test?
Added support to add new elements (Node, Vert, Edge, Face) with
interpolated values
Added support to delete elements
Deletes the element and updates the elements that refer to this
element
First version worked but if the deletion of the elements was not
thought through at each step, it could every easily lead to
crashes.
A second, significantly better version ensures that deletion of
the elements is allowed to be done in a safe manner to reduce
potential crashes.
Fixed a critical bug in the generational arena
the begin() function of the arena, before the fix, could give an
element that doesn’t exist leading to a crash.
In a new modifier, created some GUI options to help test the mesh
operations more easily.
For those who are compiling this branch, checkout the Adaptive Remesh modifier.
Side note, this will not be a modifier available in master, this
is only for my personal testing. (Check week 01 report for reasons
why).
Split edge done
This mesh operation splits the given edge and ensures
triangulation of the faces around the edge remains after the
operation as well.
This is done by creating a new vert and node by interpolating the
edge verts and nodes. Then new triangulated faces and edges are
created and the correct references between the various elements
affected by this operation are created.
Since Edge stores Vert and not Node, this operation will
split the edge/face in UV space but not in the world space. For
this, an option across_seams, if true, will consider edge nodes
instead of edge verts only which is often the desired result.
De-duplication of elements
DNA Mesh stores UVs per loop which can lead to duplication of
the UVs. If the UVs are not de-duplicated correctly, it can lead
to extra elements in Mesh so mesh operations may not work as
expected.
Handle gaps created in the Arena of nodes, verts during the mesh
operations
Certain mesh operations can lead to gaps in the Arena, this
leads to wrong indexing of the elements when converting Mesh to MeshIO. For this, a Map of the generational arena Index to
positional index needs to be created during the conversion
process.
Collapse edge
This mesh operation collapses the given edge and ensures
triangulation of the faces around the edge remains after the
operation as well.
Ran into trouble with the first version of the delete elements
implementation thus the second version of the delete elements was
born.
Currently there is a bug where collapsing the edge from v1 to v2
leads to a crash because the faces that remain have only 1 vert
but collapsing from v2 to v1 works perfectly.
Plan for following week
Continue work on mesh operations like- collapse edge, flip edge.
It is nice to see the community is excited about this project as I am
The mesh operations will definitely help with the cloth tearing functionality but this is currently out of scope as I have mentioned in my project proposal. Currently, these mesh operations are for adding adaptive remeshing support which will help with getting higher quality simulations without the expense of simulating a very dense mesh and having to manually tweak the mesh topology to prevent that stair stepping effect and other artifacts.
Yes, the branch should be compile but as of now, it is purely in the development stage so no features to test. Hopefully within the next 2-3 weeks, you should have something fun to test.
Rewrote from scratch to allow collapsing of edges across seams.
Flip edge
This mesh operation flips an edge to the other verts of the quad
formed by the triangles. The operation is not allowed if the edge
is on a seam or boundary.
The operation is done by deleting and adding new elements instead
of just adjusting the references of the elements since the
remeshing operations will need to know which elements were
affected by the operation. This does not have any negative hit on
performance since the Mesh utilizes generational arenas. So after
deletion of an element, a new element is added at the same
location but with a different generation not requiring any
reallocation of memory.
Fix rare bug in split edge
An edge reference is broken rarely due to a reallocation of memory
which can lead to access of memory which is no longer valid.
float2x2
Created this new class based on float4x4.
This is needed by the “Sizing” field of the verts.
Static remeshing
Started work on static remeshing which will then be extended to
dynamic remeshing.
Created the necessary structures which will be used in the future.
All the work this week has been related to static remeshing.
The remeshing algorithm happens in 2 stages, splitting of all edges
that exceed the edge size criterion and then collapse all edges that
don’t meet the size requirement. During this, some faces may be
formed that “too scalene” and thus edges of such triangles must be
flipped to maintain better structure of the mesh.
Implementation of the above as of now
Find the maximally independent set over all edges of the mesh that
can be split without affecting other selected edges.
Split edges that are part of this set and update the set, continue
to do this until the set has no more edges that can be split.
The split edge operation returns all the newly added faces, so use
that as the active set of faces for the flip edges operation
described below.
Flip edges is done on a set of “active” faces. All the edges of
the faces are considered for the set formation. An edge is added
to the set if it is “flippable” with an anisotropic criterion and
doesn’t affect flip operation of the already selected edges.
Added UI elements to the cloth modifier to test out the static
remeshing feature in it’s current state.
Testing only the remeshing operation was difficult through the
cloth simulator since applying the modifier uses the cached mesh
and in this case, the cache isn’t updated to support remeshing
yet. For this, abstracted the static remeshing implementation so
that the cloth information is not strictly necessary. This allows
the static remeshing implementation to be called from the only for
testing Adaptive Remesh modifier in which applying the modifier
retains the modified mesh.
Creating a tool to aid with finding the source of bugs in the
remeshing implementation. This will aid in visual analysis of the
mesh to find any hidden bugs as well.
The attached video is only the split edges algorithm running, this
leads to those “too scalene” triangles. The flip edges algorithm is
implemented but has bugs so it is difficult to show it.
Using msgpack, a binary serialization format, serialized the Mesh structure to pass it along to the debug tool for further
visualizations and analysis.
msgpack-c is a header only msgpack serialization and
deserialization library for c++. Added this library to Blender.
Wrote the packer implementation for the various structures
required by Mesh during serialization.
Dumping the msgpack file where appropriate, currently after each
edge operation.
Debug tool
Wrote a debug tool in Rust that helps visualize the various
aspects of the Mesh structure. Earlier, I would look at the
printed output of the Mesh structure and try to visualize
mentally or if it is more complex, draw it on paper. Now that the
meshes have become more complex, it became extremely difficult and
time consuming to do this. It made a lot of sense to add
visualizations but couldn’t find a good way to do this in Blender
directly (GPU immediate mode or writing a python add-on that
renders on top of the view-port could have been done but this
would have taken longer to develop) and thus this tool was born.
Majority of the time this week has been spent on this and it is
already very useful. The visualizations make it easy to see the
references between the different elements of the mesh so finding
bugs has become much easier.
Found bugs in the collapse edge operation, the flip edges routine
run after splitting the edges of the mesh during static remeshing,
etc.
See the attached video for the tool’s usage.
Node: Displays itself, all the verts it references, and a
connecting line between them.
Vert: Displays itself, all the edges it references, and the one
node that it refers to.
Edge: Displays itself, and all the faces it references.
Face: Displays itself. The only references stored are the verts,
which need not be displayed separately.
The debug tool helped me find bugs in the collapse edge
algorithm. Fixed these.
Fixed a bug in functions that link/delink the faces and edges. It
is possible to have a face without any verts just prior to its
deletion.
Added a check to see if the edge is collapsible. This helps
prevent certain run time bugs that can lead to some very weird
mesh results. Best to avoid them.
Added an extra check when testing if the edge is flippable. It is
possible for an edge to already exist where the new edge would be
formed. This can (and almost always will) lead to formation of
duplicate faces which is not ideal. So do not allow the edge to be
flipped if there is already an existing edge where the new edge
would be formed.
No longer finding the maximally independent set of splittable
edges. [1] says that 2 splittable edges are independent if they
don’t share any verts. This condition is true but not
necessary. It is possible to have 2 edges that share a vertex that
when split do not affect any neighbouring elements of the other
edge. Symmetrical remeshing is preferable but considering what [1]
says, it leads to asymmetrical remeshing. A solution to this is to
sort all splittable edges with respect to their size and test to
see if the edge still exists in the mesh before attempting to
split it.
When testing if the edge is flippable (anisotropic aware), [1]
says that some calculated value must be less than 0 for it to be
flippable. This can lead to flipping and reflipping of the new
edge which can go on forever. To reduce this problem, a subsequent
paper, [2], says that the value should be less than some other
calculated value. This too has its own problems. When calculating
this value, it is necessary to consider the orientation of the
triangles when deciding between the other verts (those not
included by the edge). A simple modification to the calculation
(by taking the absolute value for 2 of the terms) is enough to not
worry about the orientation of the triangles and still have the
benefit of not flipping and reflipping the edge. See in code
comments for more details.
Corrected the orientation of the triangles in the split edge
function.
Implemented majority of the collapse edges algorithm.
The basic algorithm is as follows, initially consider all the
faces of the mesh as the set of active faces. Iterate over these
and test if any of the edges of the face are collapsible, if
they are, collapse the edge, run flip edges on the newly created
faces. Add all affected (newly added faces from collapsing and
flipping) to a new set of active faces. After iterating over all
the active faces, assign the new active faces to the old active
faces. Do this until no active faces remain.
Ensure collapsing an edge doesn’t introduce edges that violate
the edge size criterion.
Two parts need to be implemented- checking for the aspect ratio
of the newly formed triangles; preserving elements that were on
a seam or boundary in the initial state of the mesh.
My mentor, Sebastian Parborg, told me to mention the following in
the weekly report. The initial plan (in the proposal) was to only
refactor certain parts of the GSoC 2019 project code for stability
improvements but due to changes (improvements wrt the C++
containers, C++ classes for vectors and matrices, etc.) in Blender
just adapting the code for this would make it hard to maintain the
code in the future so this project has turned into a complete
rewrite. Due to this, the project has taken longer to complete than
initially expected.
Debug tool
Added some features to help with development of the above.
Attached video of statically remeshing a plane and a video of
how the remeshing process takes place.
Plan for following week
Final finishing touches to static remeshing.
Update the cloth simulator’s cloth object when the mesh changes.
Hope to start work on dynamic remeshing.
References
[1] “Adaptive Anisotropic Remeshing for Cloth Simulation” by Rahul
Narain, Armin Samii and James F. O’Brien (SIGGRAPH 2012)
[2] “Folding and Crumpling Adaptive Sheets” by Rahul Narain, Tobias
Pfaff, James F.O’Brien (SIGGRAPH 2013).
Verts that lie on a seam or boundary should not be collapsed
into another vertex (actually any operation should not delete this Vert but as of right now only collapsing of an edge can lead to
deletion of a Vert). This ensures that the very basic shape of
the mesh is preserved instead of reducing the mesh to just a bunch
of points in space.
When the AdaptiveMesh is first created, the above mentioned Verts are marked for preserve.
Computing the face normals after creating the Mesh.
Many operations rely on accurate face normals so calculating the
face normals at the start of the remeshing operation instead of
relying on the provided face normals.
It might make sense to make this a user defined option in the
future.
Flipping an edge should not create any Face(s) that are inverted.
In some rare cases, flipping an edge can lead to inverted Face(s), this can lead to unexpected results. Making sure that
this doesn’t happen by adding this check in the anisotropic aware
edge flip test.
Computing ExtraData and some other info for newly added elements.
Any mesh modifying operation returns a MeshDiff which contains
all the newly added elements, it is not possible for the operation
itself to compute all necessary information so it was up to the
caller to handle this. It is easy to mess up, so created an easy
to call function that updates all necessary information for all
the newly added elements.
Collapsing an edge should not create any Face(s) that are
inverted.
Similar to above mentioned (flipping an edge).
Update the cloth object with changes in the mesh.
Remeshing leads to lots of changes that need to be reflected in
the cloth object for the simulation to proceed after remeshing.
The cloth modifier now stores the previous frame mesh that is used
instead of the mesh provided by the modifier stack when remeshing
is turned on.
Certain features of the cloth modifier like dynamic base mesh are
temporarily disabled when remeshing is active.
Aspect ratio check when collapsing an edge.
An edge collapse should not lead to triangles whose aspect ratio
is too small.
There are many ways to define the aspect ratio of a triangle and
it is difficult to decide which one to use. [1] does not provide
any information about which aspect ratio test it has used. [1]
does cite [2] which contains many different ways to calculate the
aspect ratio of a triangle. In the end decided to use “the measure
associated with interpolation error in the usual (weaker) bounds
given by approximation theory”.
Fixed bugs in the collapse edge function.
In a certain edge case, it is possible to create loose verts and
loose edges. If any edge of v2 has only one face and this face
contains v1, then the face would have been deleted but the edge
between v2 and ov would have remained, leading to a loose
edge. At the same time, it is possible for ov to not be
connected to any other element which would make it a loose
vert. Fixed this.
Debug tool.
Added many more features to the debug tool to aid with the above
mentioned features and bug fixes.
Some notable features include
Selecting an element when the “blender element index” is known.
Display the aspect ratio of triangles calculated using different
methods to help decide which method will be most appropriate.
Visualize and display the indices of loose Nodes, Verts, Faces. Loose Edges were already handled.
There are 2 bugs that I have found during testing.
Access of a Node that no longer exists in the Mesh during
static remeshing of Suzanne when the minimum edge size is set to
0.005 or lower.
Cloth that has remeshing enabled has weird collisions. After a few
frames after a collision, the mesh passes through the collision
object.
Started work on dynamic remeshing.
Week 10 was supposed to be the last week of GSoC, it is slightly
disappointing that I could not complete what I had planned to do but
I am happy with how much I have done so far. I ran into many
unexpected challenges (I guess one GSoC was not enough for me to
learn that these sort of large projects come with many unexpected
challenges). I even wrote a custom tool to help me with these
challenges . The plan now is to try to complete this project in
the next 2-4 weeks, so more weekly reports to come.
Attached is a video of a simple plane with pinning enabled that
collides with a sphere demonstrating the cloth object update and the
above mentioned bug (collision related).
Plan for following week
Fix the above mentioned bugs.
Continue work on dynamic remeshing.
References
[1] “Adaptive Anisotropic Remeshing for Cloth Simulation” by Rahul
Narain, Armin Samii and James F. O’Brien (SIGGRAPH 2012)
[2] “What Is a Good Linear Finite Element? Interpolation,
Conditioning, Anisotropy, and Quality Measures” by Jonathan Richard
Shewchuk
This week has only been about debugging. The overall design of the
cloth simulator really does not like mesh connectivity changes, so
finding what parts to fix and fixing them has been extremely time
consuming and difficult.
Bugs fixed
The spring count stored per vertex would increment every frame
even though it should stay fixed. When building the structural
springs, the avg spring length is reset before the calculation but
the spring count was not. Fixed this.
Not only would the originally pinned vertices be pinned but many
more new vertices around existing pinned vertices would also be
pinned. Initially I thought that the new nodes didn’t interpolate
the cloth vertex flags correctly but this cannot be the issue
because all new vertices always had the pinning related flag set
to false. For sanity sake, I added the correct interpolation of
the flags but this didn’t fix the bug as expected. The simulation
does not only consider the pin flag of the cloth vertex for
pinning but also the goal and this is not expressed anywhere
clearly. So now, all new vertices added have their goal set to
zero, fixing the bug.
Sewing edges are just loose edges in the mesh which are activated
when sewing is enabled in the simulation settings. When remeshing,
finding where to add new sewing edges is an interesting
challenge. There are two approaches that I figured out, one is
currently implemented and the other’s implementation is ongoing.
The first approach is done after splitting an edge and considering
the new vert created in the process as the starting point. For the
new vert, need to find an incident edge that has a loose edge
attached to it. For this loose edge, another edge (lets call it
“opposite edge”) must be incident on it such that it too has a
loose edge incident on it at the other vert of the edge. Finally
if the second loose edge has an edge incident on it that connects
to the new vert from the split operation, we can split “opposite
edge” and create the sewing edge between the 2 newly created
verts.
Here vert is the vert during the split, e2 and e4 are the
loose edges which are connected by the “opposite edge” e3.
During the implementation of the first approach, I had to make
significant changes to the split edges and flip edges functions to
support adding of extra elements in between the two stages. Both
now store more information about the MeshDiff for their operations
by appending many diffs together. Without this, certain elements
would not be considered for further analysis leading to results
that are not ideal.
The first approach has some limitations (which will be obvious
from the attached screenshots). After the first stage of splitting
of the edges, new edges are formed such that the above mentioned
criterion is met in cases where it is not wanted, so it adds many
extra sewing edges and thus making it nearly impossible for the
artist to specify which parts of the mesh should be sewn
accurately. It is almost as though the sewing edges initially
specified act as regions of the cloth (with something like a
spherical gradient) that must be sewn together instead of just
being sewing edges. The second approach should help fix this.
The second approach is done by initially marking all the edges
that are between two (or more) sewing edges and if these sewing
edges are connected by another edge as well. When an edge is
split, and it was an edge marked for this, then the new edges
should also be marked. After which a similar approach is taken as
the first approach but with some changes, the main change is that
the opposite edge is considered only if it is marked. This ensures
that the sewing edges are added between edges that were supposed
to be sewn instead of the region surrounding the initial sewing
edge.
As of right now, marking of the edges has been
implemented. Still need to figure out a way to correctly mark
edges once they are split. After which I will use these markings
when adding the sewing edges.
Debug tool
Implemented visualizations for the sewing related parts of the
remeshing.
The second approach mentioned in week 12’s report works
Added an option to the split edge function to copy the extra data
to the edge that is split, this does not copy the extra data to
the other edges added to ensure triangulation even after the
split.
The sewing edges are added only if the starting vert is between 2
or more edges that are between sewing edge and the opposite edge
is also between sewing edges.
When sewing is on, verts of loose edges are marked for
preserve. Even the verts of the sewing edges added by the
remeshing step are marked for preserve.
Added an option to force split the opposite edge even if it does
not meet the size requirement. This means that an edge and it’s
opposite edge don’t need to have the same length in UV space. This
can sometimes lead to results that are not expected but useful to
have so it must be used with caution.
Resolved unused parameter warnings in release mode.
Bug fix
During collapse edge operation, n2 was not updated for v1. A
simple solution that is extremely difficult to debug. This
particular part of the collapse edge function is run rarely and
the bug is triggered only during a subsequent operation which
makes this particular bug even harder to find. One way to trigger
this bug is to static remesh Suzanne (Blender monkey) at 0.005 or
lower minimum size. This leads to a crash due to a bad optional
access of a node. The vert refers to the node but the node doesn’t
refer to the vert. So once this sort of situation is created, when
that vert’s nodes need to be used, it leads to a bad optional
access.
Dynamic Remeshing
A lot of progress
Dynamic remeshing is now an option in the cloth modifier and the
adaptive remesh modifier.
Storing extra data for the faces of the mesh as well. Currently
stores the UV area of the face.
float2x2
New constructors
Transpose and inverse
Eigendecomposition
float3x2 and float2x3
New constructors
Transpose
Created a function to calculate the Jacobian of the 3 given float3s with respect to the UV coordinates of the given face.
Vert Sizing is calculated as the area weighted average of the Sizing of the adjacent faces.
Created a function to calculate the Sizing of the faces and add
the required constraints through eigendecomposition to the Sizing calculated. The constraints are with respect to the
minimum and maximum edge length and the minimum aspect ratio.
Created the GUI elements to control the constraints as well as the
maximum change in vertex normal (used when calculating the Sizing of the face).
Dynamic remeshing now refines the mesh based on the curvature of
the mesh.
Debug tool
Added some more information to the error message that may be
produced while reading the mesh file produced by Blender.
Added FaceData structure to reflect similar change on Blender’s
side.
The video demonstrates the sewing feature. The screenshot
demonstrates the dynamic remeshing functionality with respect to the
curvature of the mesh. Note how the mesh is more refined as the
curvature of the mesh increases.
