I started with the first algorithm in my proposal, namely the zippering gaps algorithm. This algorithm is meant for gaps within a certain tolerance. This will be decided appropriately. For those greater than that there is the stitching algorithm.
How this algorithm works is we first identify a boundary (free-edges) chain. We obtain free edge chains from the mesh until there’s just one left, in which case it’s the boundary of the mesh. So, given a start and an end half-edge we implement the zipper gaps algorithm.
We look for a feature pair for each vertex on the boundary chain, and calculate the error measure. We maintain a priority queue that will pop the feature pair with the least error measure. The feature for a vertex can either be a vertex or an edge. This depends on the closest edge. The distance from a vertex to a closest edge will be the perpendicular distance if an orthogonal projection is possible, else it’ll be the shortest between the vertex and the closer endpoint. This way we either set the feature_edge or the feature_vertex, but not both, for a vertex. This closest edge cannot have a bounded face incident on it – meaning it’s not a free-edge. It cannot be incident on the current vertex being considered. Also, the line joining the vertex to the closest edge (be it the orthogonal projection or the closer end point) cannot cross any face other than the unbounded face – meaning it should be a valid diagonal.
While zippering the gap, we pop the feature pair with the minimum error measure. Only if this measure is within the tolerance for gaps, we continue. Else we break out of the loop, since every error measure after this will only be greater. We stitch/ fill those defects.
Since the feature vertex of a vertex on the free-edge chain could be a vertex on the free-edge chain itself, its coordinates could possibly change. And hence, the error measure too. Thus every time we pop a new vertex, we need to go through all the elements of the priority queue and:
- Check if there are any invalid features and recalculate the features for those vertices
- Check if the distance measure is up to date.
We pop the feature pair with the minimum error measure. If the feature is a vertex, we move both the vertices to the mid point of the line joining those two. If the feature is an edge, we introduce a new vertex on the orthogonal projection of the vertex on the edge and split the face incident on that edge. We update the vertex, edge, and face records accordingly for both cases.
As and when we update the DCEL, we update the native structure too. This is important to keep all data consistent, that is there must be a synchronization between the two structures.