This thread is to post my weekly reports, I’m super excited about the project and will keep this updated with all progress. Goes without saying, would love all feedback and suggestions anyone might have!
As a first update, I’m working on building the tetrahedralizer as a modifier for the first step since that will enable me to decouple the 2 processes (soft body sim and tetrahedralization)
Please do share all thoughts and feedback that I can work on here, would love to know your thoughts.
Hi, @arcticblazer As a blender physics player I’m really excited about this project. I wish you all the best for this Gsoc project!
I would love to test and play with your implementation and help with direct feedback.
I don’t know much about XPBD, but the tetrahedralizer sounds like something I’ve been thinking about a lot when planning my physics engine in my dreams. So I’ll be very interested to see what you do.
Hello i wish you a good GSOC make the best ! And i have suggest for you why not implement a tétrahedral topo in the Triangulate modifier ?
Closing this thread to limit this to the weekly reports. @arcticblazer Feel free to open a second thread for feedback if you like.
Week 1 - Was a slow week,
- Understood half-edge data-structure and correspondingly the code for bmesh and modifiers.
- Spent time understanding Delaunay Triangulization
- Started coding the same
Week 2 -
Hello everyone, I was hoping that I would have a working demo/code for the tetrahedralization but I haven’t been putting as much as time as is required and I’ll be taking more care of that. I’ll try to update the same in a day or 2 as soon as I have some working code.
After that the goal for the week would be to make documentation for the same explaining the process employed for the process.
Week 3 -
Hey everyone, I’ll start by explaining the basic steps and approach employed for building the tetrahedralizer since I hadn’t covered it last week. In Delaunay Tetrahedralization, each vertex is added in an incremental manner and with each addition, new tetrahedrons are formed such that all tets satisfy the Delaunay condition : “No point lies inside the circumsphere of any tethrahedron”
We start with a big tet that encompasses all points of our object and add points one by one. The first part is finding the tetrahedron which contains the new point. For this, a ray is cast from the center of the current tetrahedron to the point to be added and we move to neighboring tet in the direction of ray. For this, it is integral to store neighbors of each face for every tet.
For the actual tetrahedralization, we need to find all tets that violate the Delaunay condition. We then delete all these tets and make new tets centered at the new point. For doing so, “boundary faces” need to be extracted. To extract these boundary faces, we are iterating over all faces of a violating tet and store faces that are the common to violating and non-violating tets.
Finally with the new tets formed, neighbors for these new tets need to be computed which is being done in a brute force manner where at each step, for all the new tets added, each face is checked against each new tet. Since the number of new tets added in an iteration generally does not exceed 16 tets , this is reasonably efficient.
The tet information is stored as an array of constituting verts. Since we have to add new verts that fill up the volume and the tets have to be stored as a quad face, they’re constructed in an empty bmesh which is then converted to a mesh.
Over the past week a lot of work was done on the code. Currently I’m still debugging the code since the it is still breaking. There were a lot of different bugs that caused various errors that took time to figure. One of the more intricate bugs I encountered was - Wrong ordering of verts of the new tets formed which caused normals to point inwards instead of outwards affecting code for finding containing tet.
The bug I’m currently solving is one where neighbor of a tet is pointing to a deleted tet which ideally should never happen.
Week 4 -
Hey everyone, super excited that I finally have something to show!
About what all was done in the previous week
- Added support for viewing each face of tet separately for better visualization. The tets are scaled down by a factor so that the quality of tetrahedralization can be evaluated. (In code that is enabled by the variable oneFacePerTet)
- Added BVH tree building and ray casting to remove exterior tets, we check if the center of the tet lies inside the surface mesh before adding it in the final result
- Floating point error handling was added which solved some of the errors and the code seems to be more stable yet not entirely. It is still breaking in some cases which is exactly what I’m also working on right now.
I also wanted to specify some terminology for those wanting to look at the code:
- Violating tet - one which fails the Delaunay condition (a point lies inside the circumsphere of the tet)
- Boundary face - for a violating tet, a boundary face is one that is shared by a non-violating tet. The idea is that all violating tets when put together will form a convex structure and we connect the faces of this structure to the new point when forming tets.
As it stands, the code is still not entirely stable and in my testing is breaking when internal resolution is added. Even in the cases that internal resolution is not breaking the code, the result seems to be inaccurate which is what I’m looking into right now.
Now that I have some working code as well (pushed the latest code to my branch, please use Weld modifier to try out the tetrahedralization, it’s just used as a placeholder since it wasn’t in the original plan to build it as a standalone tool which would require some time. I can certainly do that once the objectives of the project are completed since most of the code would remain the same), I’m also opening up the discussion forum(link in first post) for any suggestions or feedback or observations you might have to share, would love to hear from everyone!
Week 5 -
Hey everyone, super happy to inform that I’m done with this part of the project. Over the week, I spent time in debugging the cause of instability. It was because of how neighbors were being set for the new tets that were formed which would cause issues at a later stage.
A brief rundown of things done:
- Changed the way neighbors are set making the code stable
- Investigated the need for floating point error correction and removed the unnecessarily high blanket correction epsilon
- Added a small bit about evaluating quality of tets formed to remove the planar tets (co-planar tets forming a tet) from the final result
Since the code is not at all straightforward and has a lot of intricate details to it’s working, I’m working on commenting it well. Will finish that and finally start work on the simulation system.
Week 6 -
Over the past week, I cleaned the tetrahedralization code and added all documentation for the same.
The rest of the time was spent in understanding the current flow for soft body simulations and starting work on the same. Since I’m attempting to rewrite the flow from scratch if possible, it has been kinda slow. Right now I’m still working on getting the basic data population flow in place before I move to writing code for simulation.
Week 7 -
So understanding how data flow worked in an attempt to write new and clean code for softbody required a lot more effort than I earlier expected. A lot of time was spent on understanding how the current RNA-DNA system worked. It made me realise that the system is not very obvious and an all encompassing document about the same could help a lot. I’ll try to make one properly after the project but for now, just posting what I learnt about the same:
- In general
DNA_*.h files hold data that we wish to write to disk when saving a file. In case of simulations, we wish to store the simulation settings, thus they’re defined in the DNA files.
- Since these settings are also taken as input from user, they’re connected to the UI which is defined in
properties_*.py using RNA code.
- These RNA codes for each modifier are however not written individually and are auto-generated from using their respective
- The code in
RNA_*.c file consists of 2 parts, Runtime functions and UI connector functions. The runtime functions are generally for get()/set() while the UI connector functions define the function, associate it to the respective variable in the DNA struct and set the range and default values for these properties.
- The code for reading and writing data to disk can be found in
blenkernal/intern/*.c for the respective data structure
While there are a lot more specifics that I can add, I’ve tried to cover the basic flow to the best of understanding as of now. I also understand that most of what I’ve understood here is specific to softbodies and this flow may not necessarily be entirely the same for others (I’d however love for it to be more in sync with what might be the norm now)
I hope that with this effort I’ll be able to clean out the simulation code a lot. Over the next week I want to establish the basic stack for simulation that I can keep adding to.
Week 8 -
Hey everyone, I made quite some strides this week. Finally got the basic flow of code to work, setting the basic stack in place. In addition I also implemented distance and volume preservation constraints.
For now to test the simulations, an imaginary ground at z=0 was implemented.
As the next step, I will be implementing self collision and eventually collision with other objects.
Finally here are some demos to show the progress (the structures look weird since the tets have been stored as quads as of now):
Week 9 -
Hello everyone, over the last week, a few small additions were worked on in addition to testing out how the simulation reacted to different stiffness constant.
Amongst the small additions -
- Point cache system was added
- A few controls were added to the simulation UI to help in testing
The computation of unique edges was made more efficient which helped increase the rendering speed of ~4800 tets with substep_count = 50 from 1.5fps to 12fps
Since Matthias was able to get the simulations running with much higher compliance (inverse stiffness) values than I was, some time was spent on understanding why that was the case which led to changing how masses are allotted to each vertex. Instead of giving defined values to vertices, the mass was given based on the volume of tets it was a part of. This led to generally higher values of mass as well which allowed for higher compliance values as was seen in the demo shown by Matthias Muller.
Week 10 -
Hey everyone, the past week was spent working on implementing self collisions in the system.
It’s for most parts brute forced for now where the first part is to check if any vertex is inside a tet, where for each vertex we are iterate over each tet and check if the vertex is inside the tet.
Once the tet has been recognized, we need to find the intersecting face of the tet. To do this, a ray is cast from the previous point to the current point and distance of faces from previous point along that ray is found, the min distance face being the intersecting face.
Once the intersecting face (triangle is identified), we move both the violating point as well as the intersecting triangle in opposite direction such that the momentum is conserved.
I’m still working on the same and will report back with the progress
Week 11 -
Hello everyone, the earlier approach was completed but it suffered from objects getting crumbled when collisions occurred. After much analysis it was realised the issue could have been because all points were being checked for collisions instead of just surface points which caused a logical error in how intersecting faces for collisions are found.
To solve this we are now extracting just surface points and tets and performing collision detection and correction using those. This hasn’t worked yet and it was seen that the objects are passing through (essentially collisions are not being detected) and I’m working on the same to understand why that is happening.
Week 12 -
Over the past week I recognized that the bug in the code was because of how we find the triangle intersected by a colliding point. To perform this, we were casting a ray from the previous position of the point to the current position and checking which face is closest along that ray from the previous point. The issue with this approach is that in not so rare cases, the previous position of the point can be inside the colliding tetrahedral in which case we get the wrong intersecting surface and the objects get thrown in random directions. Other ways to detect the intersecting surface were tested but to not much avail yet.
I am also in the process of moving country to start a new role and because of that I wasn’t able to put in as much time as I wanted to.
Week 13 -
Hey everyone, this week was primarily spent finalizing code and making the final report.
I want to start by thanking everyone here for being so supportive throughout the journey. It is really motivating to see how excited everyone is about my work.
I understand that a lot of work still needs to be done to make this solver usable by everyone and I really look forward to the day I will be able to merge this to master. I never saw GSoC as the project rather always saw it as just a small part of it. I started working on the project and understanding the code before GSoC and I only look forward to continuing the same and finishing what was started, and then more.
Lastly while I have said this a few times I don’t think I can thank my mentor, Sebastian enough for being extremely helpful. He gave me the space to work and was always there to help me whenever and for however long I needed it and I’m extremely grateful for that.