Converting Sets of Polygons to Manifold Surfaces by Cutting and Stitching

Many real-world polygonal surfaces contain topological singu-laries that represent a challenge for processes such as simplifica-tion, compression, smoothing, etc. We present an algorithm for removing such singularities, thus converting non-manifold sets of polygons to manifold polygonal surfaces (orientable if necessary). We identify singular vertices and edges, multipry singular ver-tices, and cut through singular edges. In an optional stitching phase, we join surface boundary edges that were cut, or whose endpoints are sufficiently close, while guaranteeing that the surface is a mani-fold. We study two different stitching strategies called “edge pinch-ing ” and “edge snapping”; when snapping, special care is required to avoid re-creating singularities. The algorithm manipulates the polygon vertex indices (surface topology) and essentially ignores vertex coordinates (surface geom-etry). Except for the optional stitching, the algorithm has a linear complexity in the number of vertices edges and faces, and require no floating point operation