Automatic Polygonal Mesh Healing
The first part of the project was to come up with the methodology of the portable module for the mesh healing that can be used by not just BRL-CAD. After discussions with the BRL-CAD and OpenSCAD mentors, it was decided that there’d be an abstract class that would behave as a geometry storage structure, directly accessing the native structures, and a geometry processing structure – Doubly Connected Edge List that would help with the healing operations.
Coming up with this idea took a long time as it needed clarity on the kind of operations that would be performed. Discussions with the organization helped tremendously.
The next step was implementing the zippering module. This module would take care of gaps and T-joints.
Fig: Gap in a mesh
A priority queue was used to maintain which vertex would be healed next in a given free edge (an edge with just a single face incident on it) chain.
Initially the unbounded face was given the index equal to the number of faces in the mesh. But as the mesh would keep changing, this proved cumbersome, hence it was set to zero.
The main challenge of this module was a routine, that aims to find the closest edge to a vertex, which is valid. A valid edge has a lot of properties that include:
- Not being incident on the vertex for which closest edge is being calculated
- Not disrupting any of the existing orientations of the other triangles
- Not intersecting the interiors of the edges of other triangles, etc.
Any small mishap in the function, and you would get a distorted mesh as a result. This routine needed a lot of time and precision. As the weeks progressed, new validity conditions kept coming up and they had to be added.
Checking and setting references properly in the DCEL proved quite tougher than expected. They had been overlooked initially as they seemed quite trivial. But when invalid memory reads started occurring, those were taken care of.
A lot of memory issues arose that took quite some time to resolve. The function signatures initially made the caller responsible for the deallocation of memory. They were changed and made better by performing the deallocation inside the function itself.
The routines had to be modified very frequently. This would happen when some degenerate case popped up that would put the DCEL out of place and hence make the algorithm hang.
Special cases needed to be identified and handled separately. One such instance is a square hole. For more information, check the Week 9 entry in the blog. Initially, the intersection of lines was checked by checking for the intersection the lines projected onto the x-y plane, but that proved erroneous. So intersections were checked in 3-D and they were checked for co-planarity as well (essentially taking care of skewed lines).
One issue is the consistency of the orientation of the triangles. The origin needs to be inside the object for the orientation of all the triangles to be consistent. As my mentor, Daniel had suggested, initially while setting the DCEL, it can be done by starting with a triangle and moving on to neighbouring ones while just flipping the common edges. He also added that this will have issues when there are more than one connected components. Also, the orientation routine in the function is used in other places as well, like finding if two lines intersect, etc. Those will have issues too, then.
Code yet to be merged. The stitching, overlaps, holes modules are left to be implemented.
- Project proposal: GSoC ’16 Project Proposal
- The complete algorithms for all the modules can be found at: Project plan
- My weekly blog outlining my approaches and the challenges faced: Rakshika Bagavathy – Google Summer of Code ’16
- My daily development logs: Development Logs
- Ticket thread of patches I maintained on Sourceforge (includes the latest one): Zippering module
- Public folder of all the patches: Patches
- Folder with screenshots of the results obtained: Results’ screenshots
- Final patch: Zipper Module Patch
- Mail to the BRL-CAD mailing list: Mail to the organization