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.

By: Andre Gueziec, Gabriel Taubin, Francis Lazarus and William Horn

Published in: RC20935 in 1997


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Questions about this service can be mailed to .