International Journal of Shape Modeling c ○ World Scientific Publishing Company REPAIRING NON-MANIFOLD TRIANGLE MESHES USING SIMULATED ANNEALING

In the field of reverse engineering one often faces the problem of repairing triangulations with holes, intersecting triangles, Möbius-band-like structures or other artifacts. In this paper we present a novel approach for generating manifold triangle meshes from such incomplete or imperfect triangulations. Even for heavily damaged triangulations, representing closed surfaces with arbitrary genus, our algorithm results in correct manifold triangle meshes. The algorithm is based on a randomized optimization technique from probability calculus called simulated annealing. Keywords: CAD-repair; repairing triangulations; simulated annealing. 1991 Mathematics Subject Classification: 52B70, 60J05 1