Publications

Nowadays, digital 3D models are in widespread and ubiquitous use, and each specific application dealing with 3D geometry has its own quality requirements that restrict the class of acceptable and supported models. This article analyzes typical defects that make a 3D model unsuitable for key application contexts, and surveys existing algorithms that process, repair, and improve its structure, geometry, and topology to make it appropriate to case-by-case requirements. The analysis is focused on polygon meshes, which constitute by far the most common 3D object representation. In particular, this article provides a structured overview of mesh repairing techniques from the point of view of the application context. Different types of mesh defects are classified according to the upstream application that produced the mesh, whereas mesh quality requirements are grouped by representative sets of downstream applications where the mesh is to be used. The numerous mesh repair methods that have been proposed during the last two decades are analyzed and classified in terms of their capabilities, properties, and guarantees. Based on these classifications, guidelines can be derived to support the identification of repairing algorithms best-suited to bridge the compatibility gap between the quality provided by the upstream process and the quality required by the downstream applications in a given geometry processing scenario.

Digital 3D models are key components in many industrial and scientific sectors. In numerous domains polygon meshes have become a de facto standard for model representation. In practice meshes often have a number of defects and flaws that make them incompatible with quality requirements of specific applications. Hence, repairing such defects in order to achieve compatibility is a highly important task – in academic as well as industrial applications. In this tutorial we first systematically analyze typical application contexts together with their requirements and issues, as well as the various types of defects that typically play a role. Subsequently, we consider existing techniques to process, repair, and improve the structure, geometry, and topology of imperfect meshes, aiming at making them appropriate to case-by-case requirements. We present seminal works and key algorithms, discuss extensions and improvements, and analyze the respective advantages and disadvantages depending on the application context. Furthermore, we outline directions where further research is particularly important or promising.

There are two major approaches for converting a tessellated CAD model that contains inconsistencies like cracks or intersections into a manifold and closed triangle mesh. Surface oriented algorithms try to fix the inconsistencies by perturbing the input only slightly, but they often cannot handle special cases. Volumetric algorithms on the other hand produce guaranteed manifold meshes but mostly destroy the structure of the input tessellation due to global resampling. In this paper we combine the advantages of both approaches: We exploit the topological simplicity of a voxel grid to reconstruct a cleaned up surface in the vicinity of intersections and cracks, but keep the input tessellation in regions that are away from these inconsistencies. We are thus able to preserve any characteristic structure (i.e. iso-parameter or curvature lines) that might be present in the input tessellation. Our algorithm closes gaps up to a user-defined maximum diameter, resolves intersections, handles incompatible patch orientations and produces a feature-sensitive, manifold output that stays within a prescribed error-tolerance to the input model.

We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry as well as gaps and holes up to a user-defined maximum size. Moreover, the output mesh always stays within a prescribed tolerance to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 4096^3 on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.