Non-manifold Surface Conversion Algorithm

In the process of modeling, we often encounter the polygonal surfaces that contain topological singularities. First of all, some modeling operations could lead to non-manifold surfaces unavoidably; secondly, because non-manifold surfaces own more complex topological relations and better description, some modelers may prefer the non-manifold surface. But various algorithms in Computer Graphics are designed to operate exclusively on manifold surfaces, such as simplification, compression and smoothing. So, in order to apply these algorithms to non-manifold surfaces safely, we present an algorithm that converts a non-manifold model N to a manifold model M that is infinitely close to N in the geometric sense.There are many data structures are used to describe surfaces. But some edge-based structures can only represent one manifold surface. So, based on a face-based data structure-DLFL, we present a variation structure of DLFL, which doesn't only provide plenty of topological information, but also can represent all non-manifold surfaces showed on screen. At last, based on this new structure, we state a new method to find out singular vertex, and this algorithm owns a linear complexity.Most algorithms that are used as repairing singular edges could still produce new singular edges after edge stitch. In this case, we refer an improved cutting and stitching method in this paper, which is not only used for cutting operations in any instances, but also can avoid invalid edge stitch.We have re-investigated algorithms for repairing singular vertices. Because these algorithms may only produce a manifold description that disconnected on topology, we have proposed a new method to convert singular vertices to pipe in topology, and got a connected manifold surface. Then, based on the theory of graph rotation system, we have proved that the operation InsertEdge doesn't produce singularities.In the end, several real-world examples are studied, applying Doo-Sabin method to surfaces after repairing. It can validate that whether non-manifold surfaces have converted to manifold or not.