Cutting and stitching: converting sets of polygons to manifoldsurfaces

摘要

Many real-world polygonal surfaces contain topologicalnsingularities that represent a challenge for processes such asnsimplification, compression, and smoothing. We present an algorithm thatnremoves singularities from nonmanifold sets of polygons to createnmanifold (optionally oriented) polygonal surfaces. We identify singularnvertices and edges, multiply singular vertices, and cut through singularnedges. In an optional stitching operation, we maintain the surface as anmanifold while joining boundary edges. We present two different edgenstitching strategies, called pinching and snapping. Our algorithmnmanipulates the surface topology and ignores physical coordinates.nExcept for the optional stitching, the algorithm has a linear complexitynand requires no floating point operations. In addition to introducingnnew algorithms, we expose the complexity (and pitfalls) associated withnstitching. Finally, several real-world examples are studied