An Algorithm Recreating 3D Triangle Mesh Faces from Its Edges

Marek Zábran

Supervisor(s): Libor Váša

University of West Bohemia

Abstract: 3D triangle meshes are usually represented by a set of points with geometrical coordinates and a set of faces represented by triplets of these points. Multiple algorithms reconstructing a set of faces from a set of points and a set of edges were proposed in the literature, however, none of these can effectively reconstruct the set of faces using only the set of edges. In this paper, such an algorithm is presented, which recreates a set of non-oriented triangle faces from only the set of its edges. The input is expected to be a closed 3D edge-manifold triangle mesh of any genus. The algorithm is simple, purely topological and runs in O(n). We present several practical examples demonstrating that it is capable of reconstructing faces even from fairly large input data, as well as input data that is prone to errors in reconstruction due to a high occurrence of possible inner faces.
Keywords: 3D Reconstruction, Computational Geometry
Full text:
Year: 2018