From irregular meshes to structured models

Abstract

Surface manipulation and representation is becoming increasingly important, with applications ranging from special effects for films and video-games to physical simulation on the hulls of airplanes. Much research has been done to understand surfaces and to provide practical and theoretical tools suitable for acquiring, designing, modeling and rendering them. This thesis contributes to fill the gap that exists between acquisition of surfaces from 3D scanners and their use in modeling. The problem has been studied from different perspectives, and our contributions span the entire modeling pipeline, from decimation and parametrization to interactive modeling. First and foremost, we propose an automatic approach that converts a surface - represented as a triangle mesh - to a base domain for the definition of a higher order surface. This allows us to have the advantages of a structured base domain, without the need of defining it by hand. The algorithm performs a series of local operations on the provided triangulation to transform it into a coarse quad mesh, minimizing in a greedy way a functional that keeps the newly computed smooth surface as close as possible to the original triangle mesh.The same problem is also approached from a different angle, by proposing an algorithm that computes a global parametrization of the surface, using an automatically costructed abstract mesh as domain. The problems are related because whenever a global parametrization of a surface is known, it is possible to produce a quad mesh by imposing a regular grid over the parametrization domain, which is usually a plane or a collection of planes, and mapping it to the surface using the parametrization itself. It is then possible to use surface fitting methods to convert the quad mesh to a base domain for a high-order surface. Our contribution is an algorithm that is able to start from a cross-field defined on a surface, simplify its topology and then use it to compute a global parametrization that is especially suitable for re-meshing purposes. It is also possible to use it for other usual applications of a parametrization, like texturing or non-photorealistic rendering. Since most objects in the real-world are symmetric, we studied robust methods to extract the symmetry map from acquired models. For extrinsic symmetries, we propose a simple and fully automatic method based on invariants usually used for image analysis. For intrinsic symmetries, we introduce a novel topological definition of symmetry and a novel algorithm that starting from a few correspondences is able to extract a high-quality symmetry map for the entire shape. The extracted symmetric map is then used to produce symmetric remeshing of existing models, as well as symmetric non-photorealistic rendering and parametrization.We also introduce an innovative parametrization algorithm for the special case of mapping a rectangular subset of the plane to another subset of different size. This case is of special interest for the task of interactive image retargeting, where the aspect ratio of an image is changed without distorting the content in interesting areas. Our algorithm searches for the parametrization function in the restricted subset of axis-aligned deformations, by minimizing a convex functional. This allows us to achieve robustness and real-time performances even on mobile devices with low processing power. A user-study with 305 participants shows that our method produces high-quality results.Starting from a structured model, we consider the problem of refining it in an adaptive way. We present a way to encode an arbitrary subdivision hierarchy in an implicit way, requiring an amount of additional space that is negligible with respect to the size of the mesh. The core idea is general, and we present two different instantiations, one for triangle and one for quad meshes. In both cases, we discuss how they can be implemented on top of well-known data structures and we introduce the concept of topological angles, that allows to efficiently navigate in the implicit hierarchy. Our adaptive framework can be used to define adaptive subdivision surfaces and for generating semi-regular remeshing of a given surface.Finally, we extend common geometric modeling algorithms to prevent intersections. We show that it is possible to extend them to produce interesting deformations, which depend on the modeling algorithm used, to avoid self-intersections during interactive modeling. Self-intersections are a common problem, since they usually represent unrealistic scenarios and if a mesh contains intersections it is hard to run any kind of physical simulation on it. It is thus impossible to realistically model clothes or hair on self-intersecting meshes, and the manual cleaning of these models is time-consuming and error-prone. Our proposal allows us to produce models with the guarantee that self-intersections cannot appear and can be easily integrated into existing modeling software systems.