My Paper

Eurographics Symposium on Geometry Processing (2006) Konrad Polthier, Alla Sheffer (Editors)

Designing Quadrangulations with Discrete Harmonic Forms

Y. Tong1 P. Alliez2

1 Caltech

D. Cohen-Steiner2

2 INRIA

M. Desbrun1

Sophia-Antipolis, France

Abstract We introduce a framework for quadrangle meshing of discrete manifolds. Based on discrete differential forms, our method hinges on extending the discrete Laplacian operator (used extensively in modeling and animation) to allow for line singularities and singularities with fractional indices. When assembled into a singularity graph, these line singularities are shown to considerably increase the design flexibility of quad meshing. In particular, control over edge alignments and mesh sizing are unique features of our novel approach. Another appeal of our method is its robustness and scalability from a numerical viewpoint: we simply solve a sparse linear system to generate a pair of piecewise-smooth scalar fields whose isocontours form a pure quadrangle tiling, with no T-junctions.

1. Introduction

Partitioning a surface into quadrilateral regions is a common requirement in computer graphics, computer aided geometric design and reverse engineering. Such quad tilings are amenable to a variety of subsequent applications due to their tensor-product nature, such as B-spline fitting, simulation with finite elements or finite differences, texture atlasing, and addition of highly detailed modulation maps. Quad meshes are particularly useful in modeling as they aptly capture the symmetries of natural or man-made geometry, allowing artists to design simple surfaces using a quite intuitive placement of quad elements. Automatically converting a triangulated surface (issued from a 3D scanner for instance) into a quad mesh is, however, challenging. Stringent topological conditions make quadrangulating a domain or a surface a rather constrained and global problem [Ede00]. Application-dependent meshing requirements such...