Handle self-bordering Voronoi regions
-
Iterate along a Voronoi regions border and count the neighboring patches. If this number is lower than the valence of the meta vertex corresponding to the Voronoi region it has more than one border, so it self-borders as well. -
Either remesh when such patches are found or: -
Connect the meta vertex to itself once per border pair so that the connecting edge separates those borders.
Follow the tree spanned by the Voronoi region in a fixed order, eg. always taking the left-next halfedge. Whenever you reach a vertex that borders another Voronoi region compare if it borders a different Voronoi region than the previous Vertex, if so mark both. This way the faces comprised of one vertex from another region and two vertices from the same region bordering each other can be found. Use those faces to add faces to the meta mesh as well and the resulting mesh should be correct.
Related work: https://www.cs.cmu.edu/~kmcrane/Projects/LoopsOnSurfaces/ Google scholar: Erickson and Whittlesey homotopy basis
Edited by Jan Schnathmeier