---

Abstract

We present a framework for exploring topologically unique quadrangulations of an input shape. First, the input shape is segmented into surface patches. Second, different topologies are enumerated and explored in each patch. This is realized by an efficient subdivision-based quadrangulation algorithm that can exhaustively enumerate all mesh topologies within a patch. To help users navigate the potentially huge collection of variations, we propose tools to preview and arrange the results. Furthermore, the requirement that all patches need to be jointly quadrangulatable is formulated as a linear integer program. Finally, we apply the framework to shape-space exploration, remeshing, and design to underline the importance of topology exploration.

---

Framework Overview

Overview of our quadrangulation framework. (a) A control graph is generated by segmenting the underlying input mesh into a collection of surface patches; (b) the numbers of vertices on each edge can be computed by integer programming such that all patches are quadrangulatable by the minimum number of irregular vertices. Exhaustive enumerations of all topologies with the minimal number of irregular vertices for every patch are shown; (c) by picking one desired topology for each patch (marked), a full requadrangulation of the mesh can be generated.

---

Subdivision-based Quadrangulation of Patches

Overall, our quadrangulation algorithm hierarchically subdivides a patch into smaller sub-patches until every sub-patch has become a simple patch that can be quadrangulated with a closed-form solution. Simple patches consist of:

1) Simple Convex Patches

A simple convex patch is either a parallelogram (a), triangle (b) , or pentagon (c). Here we show the subdivision steps to quadrangulate them. The topological position of the irregular vertex (v3 or v5) is uniquely obtained by solving a linear system.

2) Simple Concave Patches

A simple concave patch is a single-boundary loop, (topologically) concave patch that can be embedded in a simple convex one with the same TVD (Total Valence Deficit). The embedding is realized by a novel cave-filling algorithm.
In short, the algorithm iteratively removes general caves of a patch by iteratively applying simple cave-filling operations, shown above. Green faces denote the latest simple cave being filled.

Quadrangulating general (non-simple) patches:

For non-simple patches, they are subdivided into simple ones in a divide-and-conquer sense. Here, (a) a non-simple patch with TVD = 0 is subdivided into a triangle and a pentagon; (b) a non-simple patch with TVD = 1 is subdivided into a triangle and a general 4-gon; (c) a non-simple patch with TVD = -1 is subdivided into a pentagon and a general 4-gon; (d) a patch with TVD = 5 is subdivided into two sub-patches of TVD = 3 (left) and 2 (right); (e) a patch's two boundary loops are combined into one by making a cut connecting the outer and inner boundary loops. The subdivisions/cuts are shown in red.

---

Theorems for Efficient Enumerations of Quadrangulations

The following novel theorems are useful for pinpointing the feasible ranges of subdivision steps for enumerating quadrangulations:

THEOREM 1: Under the assumption that a patch is convex, TVD < -1, and the sum of the lengths of boundaries is even. Then, the patch is quadrangulatable without inner v3-v5 pairs ↔ the sum of the lengths of the longest consecutive pair of sides ≤ the sum of the lengths of all other sides minus 2|TVD|.

THEOREM 2: When quadrangulated with two v3s and no v5, the maximal number of quads in a 2-sided patch (TVD=2) with side lengths b0 and b1 is ⌊b0/2⌋⌈b1/2⌉ + ⌈b0/2⌉⌊b1/2⌋.

THEOREM 3: When quadrangulated with three v3s and no v5, the maximal number of quads in a 1-sided patch (TVD=3) with side length b0 is
(b0b0)/4 - 1.

---

Enumerating Quadrangulations Example

Given a boundary specification of a patch (left, the back of the Fandisk model), our framework exhaustively enumerates all possible quadrangulations of the patch interior with the minimal amount of irregular vertices (two v5, one v3) in just 1.02 seconds on a 2.1GHZ quad core CPU, 8GB RAM machine. The results are sorted (from top-left to bottom-right) in descending geometry quality. Results of which the two v5 are collocated as a v6 are marked in grey.

---

Results and Applications

Shape-space exploration on different topologies. The cap of an elliptic paraboloid is PQ meshed using twenty different topological patterns (top row) and planarity-preserving shape-space exploration is applied on each topology such that the boundary is fixed while the interior vertices are allowed to move. The best eight eigendirections are sampled for each topology. The results (clockwise) are ranked in decreasing fashion according to planarity (a), circularity (b) and fairness (c). The color shows the affiliation with the topological pattern.

Exploring alternative requadrangulations of an architectural tower model. Left: the input tower model with a large number of irregular vertices and small faces due to the computation of intersections by a professional modeling package. Second left to right: five requadrangulations explored with our enumeration framework. The first and second both consider the hyperboloid-shaped facade on the front as an 8-sided patch, while the former favors uniform quad size and the latter favors alignment of irregular vertices. The third alternatively considers the front facade as a 4-sided patch, and four v3s are removed. The fourth no longer preserves the sharp feature on the right, and the two adjacent patches are merged. It has fewer irregular vertices at the cost of less sharp feature fidelity. The fifth discards all sharp features on the front in exchange for even fewer irregular vertices.

Coarse requadrangulations of the Fandisk model. Left: the input mesh from [Bommes et al. 2009]. Second left to right: coarser requadrangulations with exact sharp feature fidelity. Note that for the one with 232 quads, we allow irregular vertices to appear on the patch boundaries and achieve a more regular flow of mesh lines.

Requadrangulations of a single curved patch with two inner holes. Left: a standard requadrangulation with four v5. Middle: an alternative in which the interior meshing is completely regular by moving the v5 to the boundaries (two v5 are collocated as a v6). Right: another alternative that favors uniform quad size at the cost of additional irregular vertices. The arrangement of irregular vertices significantly influences the overall grid layout as observed from the zebra pattern rendering.

Quadrangulations of font interiors. We choose Georgia (Bold, Italy) as a challenging example for its curved, asymmetric outlines. Left: a quadrangulation with regular interiors. However, some parts such as the left of the letter d can never be uniformly quadrangulated without irregular vertices. Right: an alternative that favors uniform quad size at the cost of additional irregular vertices. Bottom left: 2- coloring of the quads is possible because the meshing is regular (quads are merged when necessary). Bottom right: a third color is necessary for quads adjacent to the v3 and v5 vertices.

---

Acknowledgements

We thank Helmut Pottmann and the anonymous reviewers for insightful comments, Alexander Schiftner and authors of [Bommes et al. 2009] and [Zhang et al. 2010] for providing datasets, Dongming Yan for an implementation of [Cohen-Steiner et al. 2004], Yoshihiro Kobayashi and Christopher Grasso for renderings, and Virginia Unkefer for the proofreading. This research was supported by the National Science Foundation and KAUST.