Connectivity Editing for Quadrilateral Meshes

Chi-Han Peng, Eugene Zhang, Yoshihiro Kobayashi, Peter Wonka

ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH Asia 2011

Paper	Additional Material	Video	Presentation (Slides+Videos)

We introduce connectivity editing operations to control irregular vertices in quadrilateral meshes. This can lead to improved results in the design of a glass structure: (a) top: the original mesh with irregular vertices as colored dots, (a) bottom: a stripe pattern applied to the mesh, (b) a rendering of the design as glass construction. In (c) and (d) we show the edited mesh. The glass panels on the roof are generated from the edges in the meshes.

Abstract

We propose new connectivity editing operations for quadrilateral meshes with the unique ability to explicitly control the location, orientation, type, and number of the irregular vertices (valence not equal to four) in the mesh while preserving sharp edges. We provide theoretical analysis on what editing operations are possible and impossible and introduce three fundamental operations to move and re-orient a pair of irregular vertices. We argue that our editing operations are fundamental, because they only change the quad mesh in the smallest possible region and involve the fewest irregular vertices (i.e., two). The irregular vertex movement operations are supplemented by operations for the splitting, merging, canceling, and aligning of irregular vertices. We explain how the proposed highlevel operations are realized through graph-level editing operations such as quad collapses, edge flips, and edge splits. The utility of these mesh editing operations are demonstrated by improving the connectivity of quad meshes generated from state-of-art quadrangulation techniques.

Moving a pair of possibly non-adjacent irregular vertices (valence 3 and 5)

Moving a 3-5 pair. The four moving directions (red arrows) for 3-5 pairs with aligned (top row) and mis-aligned (bottom row) separatrices. Each green line denotes a shortest path between the pair. The blue faces denote the nearest unchanged quad strips that enclose the affected region. The yellow and red faces are generated or deleted depending on which direction the 3-5 pair moves, while red faces denote the ones that are immediately to be created or deleted.

Parameterization of all possible requadrangulations in a convex region enclosing a pair of irregular vertices

All configurations shown below are generated by our editing framework. Note that moving from one configuration to an adjacent configuration is achieved by a pair-wise movement.

All possible configurations of a region that contains a 3-3 pair. Each configuration is labeled by its parameterization (m, n) and represented by a node positioned at (m,n) in a 2D coordinate system rotated by 45 degrees. Every node has at most four neighbors, indicating four possibilities of movement given a configuration. Note that each pair of nodes (x,0) and (0,x) on the boundaries (not including the valence 2 case) represent the same degenerate case parameterized differently, thus each boundary configuration can also have at most four neighbors. Note that the grids of configurations with even (red) and odd (blue) L (side length of the enclosing region) are disconnected, i.e., it is impossible to requadrangulate a configuration with even L to any configuration with odd L and vice versa. Note that the grids of configurations with odd and even L are dual to each other, i.e., each face corresponds to a vertex and each pair of adjacent faces corresponds to an edge.

All possible configurations within a regular hexagon of side length six (left) and five (middle) that contains a 5-5 pair. Each configuration is labeled by its parameterization (m, n, p). For brevity we show all parameterizations in the right. Note that the grids of configurations with odd and even L are dual to each other, i.e., each face corresponds to a vertex and each pair of adjacent faces corresponds to an edge.

All possible configurations in a region that contains a 3-5 pair. Each configuration is labeled by its parameterization (m, n). Notice they correspond to translations over a regular 2D grid parameterized by the locations of the red and yellow stars. Every node has at most four neighbors, indicating four possible moving directions given a configuration.

Application: Connectivity editing

Using our editing framework to improve a remeshed fandisk model from Wave-Based Anisotropic Quadrangulation [Zhang et al. 2010]. (left) Original mesh with an ill-shaped upper part caused by a mis-aligned 3-3 pair. (1) The misplaced valence 3 vertex is moved to proper location by an edge flip. (2) The created 3-5 pair is moved downward to cancel with the valence 5 vertex by a 3-5 pair cancellation. (right) Mesh improved by our editing framework. Now the upper part has a nice structure and the face strips flow consistently through the front surface.

Future work: Progressive irregular vertices cancellation

(a) Bunny model produced by a mesh simplification algorithm [Tarini et al. 2010], in which 956 of the total 3006 vertices are irregular. (b) and (c) Intermediate results with 400 and 48 irregular vertices. (d) Maximally reduced form with only eight v3 irregular vertices. The smaller figures show the same models with a checkerboard pattern by greedy coloring (so that adjecent quad faces have different colors).