GSoC 2022 : Soft body simulations using XPBD (Weekly Reports)

Hello everyone,

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)

22 Likes

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.

1 Like

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.

1 Like

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 ?

1 Like

Closing this thread to limit this to the weekly reports. @arcticblazer Feel free to open a second thread for feedback if you like.

4 Likes

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
8 Likes

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.

10 Likes

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.

10 Likes