Efficient topology construction from triangle soup

Triangular mesh is one of the most popular shape representations in computer graphics and the CAD/CAM/ CAE area. In this paper we present a memory and time efficient topology construction algorithm from triangle soup, which is a set of triangles without connectivity information. The proposed algorithm consists of the following steps: (1) vertex merging, (2) internal edge linking, (3) multi-disk vertex splitting, and (4) boundary gap stitching. Typical triangle soup comes in the form of an STL file, and topology construction work encounters non-manifold cases for various causes, which should be converted to 2-manifold models for many downstream processes such as rapid prototyping and tool path generation. The proposed algorithm uses a light-weight vertex-based data structure (adapted from a 'corner table' structure), and does not need to construct a full non-manifold topology information. The efficiency of the proposed algorithm is shown by empirical tests on practical examples.