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.