Cutting and Stitching: Efficient Conversion of a Non-Manifold Polygonal Surface to a Manifold

We present an algorithm for converting a non-manifold polygonal surface to an immersed manifold polygonal surface, orientable if necessary, so that it can be processed by a variety of algorithms that require that the neighborhood of each vertex be topologically equivalent to a disk. The algorithm manipulates the polygon vertex indices, or surface topology, and essentially ignores the vertex coordinates, or surface geometry. We identify singular edges and vertices and multiply singular vertices, or cut through singular edges. In the optional stitching stage, we join surface boundaries that were cut, or that satisfy a given relation, while guaranteeing that the resulting surface is a manifold. We distinguish between stitching along the same boundary and along different boundaries, and show the difficulties associated with the latter. Cutting and stitching are general tools that are useful independently of converting to a manifold. The conversion has a linear complexity in the number of vertices, edges, faces, and boundary vertices, as we essentially perform one pass on such elements. We store the conversion information by means of a look up table for the vertices that are multiplied, allowing to restore the original topology. Key-words: Manifold, Cutting, Stitching.