Content-Aware Quad Meshing

Quadrilateral meshes are preferred over triangular meshes in the animation and CAD industry, mostly because they fit well the role of control grids for higher-level digital representations of smooth surfaces, such as subdivision surfaces and NURBS. Nonetheless, most software and hardware designed for 3D visualization and also most acquisition technology are optimized to generate highly accurate triangular meshes. Due to their different properties, triangular and quadrilateral meshes have led each to different types of applications, even in different scientific disciplines. While algorithms for analysis and processing of geometric data, operating on each of these two representations, have been developed more or less independently, researches have been putting efforts into the design of methods to convert from one to the other. Such methods can be divided into two main categories: automatic and user-assisted. Currently, though, no automatic method is able to produce quadrilateral meshes that can be directly employed in the animation pipeline. This is mainly because of the weak or non-existent connection between any surface geometry and its ideal, application-dependent quad mesh. For example, if the mesh was intended to be used for animation, its connectivity should be tailored to its articulation and optimized to reduce skinning deformation artifacts. It is not possible to extract this kind of information merely from the geometry of a static mesh. In this thesis we investigate the problem of converting a dense, triangular mesh into a coarse, highly structured, quadrilateral mesh, suitable to flow into the standard pipeline of production in the animation industry. We discuss what properties are required and what are the most commonly used methods that can be employed for this goal. Based on such properties, we develop some novel solutions. In particular, we present three different methods. The first one generates meshes with structurally sound patch layout. This means that a high level layout of the surface patches is the objective. The layout of the patches should resemble the layout of the logical parts of an object. The second method introduces a way to drive the quadrangulation with the object deformations expected in an animation sequence. We show that such knowledge is necessary but not always available or complete. Finally, the last method overcomes the shortcomings of the previous ones by allowing the user to sketch the high-level patch layout connectivity in an intuitive and interactive manner. We employed a data-driven approach, which provides precise control over every single aspect of the mesh, without the drawbacks of the classical, manual methods, but leveraging the expertise contained implicitly into other, well-designed, quadrilateral meshes.