Cutting and stitching: converting sets of polygons to manifold surfaces

TitleCutting and stitching: converting sets of polygons to manifold surfaces
Publication TypeJournal Article
Year of Publication2001
AuthorsGueziec, A., G. Taubin, F. Lazarus, and B. Hom
JournalVisualization and Computer Graphics, IEEE Transactions on
Keywordscompression computational complexity computational geometry edge stitching linear complexity manifold surfaces pinching polygonal surfaces rendering rendering (computer graphics) simplification smoothing snapping solid modelling surface topology topologic

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied