Volume 33 (2014), Number 5

Eurographics Symposium on Geometry Processing 2014
Thomas Funkhouser and Shi-Min Hu(Guest Editors)

Pattern-Based Quadrangulation for N-Sided Patches
Kenshi Takayama

Daniele Panozzo

Olga Sorkine-Hornung

ETH Zurich, Switzerland

Figure 1: (Left) Quadrangulations of N-sided patches using our algorithm, where 2 ≤ N ≤ 6. Our algorithm is guaranteed tosuccessfully quadrangulate N-sided patches with arbitrary numbers of edge subdivisions specified at the patch boundary. (Right)
Integration of our algorithm into the UI framework of Takayama et al. [TPSHSH13b] to efficiently retopologize triangle meshes.
Abstract
We propose an algorithm to quadrangulate an N-sided patch (2 ≤ N ≤ 6) with prescribed numbers of edge
subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved
using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting
all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but
it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We
demonstrate the effectiveness of our algorithm by integrating it into a sketch-based quad remeshing system. A
reference C++ implementation of our algorithm is provided as a supplementary material.
Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Computational Geometry
and Object Modeling—Geometric algorithms, languages, and systems

1. Introduction
Converting a triangle mesh into a coarse quad mesh with a desired mesh connectivity is an important step in many production pipelines, especially in the context of movies and video
games. The process is often called retopology. Algorithms forc 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John
Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

automatic generation of quad meshes incorporating sparseuser constraints such as alignment of edges [BZK09, ILS∗ 11]
and singularities [MPKZ10] have been studied extensively [BLP∗ 13]. Other works [BLK11, TPP∗ 11] considered the problem of altering the connectivity of existingK. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches
𝑙2 =1
𝑙3 =1
𝑙2 =1

𝑙1 =2

𝑙3 =1

𝑙2 =2

𝑙1 =2
𝑙4 =1

𝑙0 =5

𝑙0 =8

𝑙1 =3
𝑙0 =9

Figure 2: Examples of input and output of our quadrangulation algorithm. Points with blue and yellow fill represent singularities
with valence 3 and 5, respectively. Some of the edge loops are highlighted in green.

quad meshes to align singularities, thus defining a coarse
quad layout. The direct generation of these layouts fromthe input surface geometry has also been recently considered [CBK12, BCE∗ 13]. Such approaches are implemented
in several commercial 3D modeling tools [Pil13, Pix13].
However, most of these methods involve global optimization processes that are computationally expensive. Tweaking
their parameters is a time-consuming task, since for eachparameter change the entire quadrangulation has to be regenerated. Furthermore, there is no direct intuitive connection
between the user constraints and the resulting mesh topology; a local change in the user constraints might generate a
globally different connectivity of quadrilaterals.
For these reasons, many artists today still use rather basic
manual modeling tools for coarse quad remeshing that are
not much different from placing vertices and faces individually [Pil13, Pix13]. Although these tools provide complete
control over the retopology process, they are difficult to use,even for experienced artists, and require time-consuming
manual work. For example, it is highly nontrivial to manuallydesign a pure quad mesh that bridges a gap between two
partially quadrangulated regions of a surface.
To alleviate this difficulty, Takayama et al. proposed aninteractive tool for manual quad remeshing [TPSHSH13b].
Their key idea is to represent a quad mesh as a set of N-sided
patches containing multiple quads inside. The user is allowed
to freely sketch patch boundaries and specify any numberof edge subdivisions at each patch boundary. The system
immediately quadrangulates each patch while inserting singularities inside patches as needed. The quadrangulation of an
N-sided patch with prescribed numbers of edge subdivisions
at the patch boundary is thus fundamental to this system.
While there already exist a few algorithms to solve thisproblem [SWZ04, NSY09, YNB∗ 13, ZHLB13, dOMM13,PBJW14], none of them provide guarantee to succeed forarbitrary cases; in particular, these algorithms do not seem tobe able to handle very asymmetric cases where some sidesof the patch are subdivided many times while other sides are
not subdivided at all (see Figure 2 for some examples). Thisis rather a serious shortcoming, since the ability to handle
arbitrary cases is a necessary requirement in order to ensure

the flexibility of an artist using the sketch-based retopology
tool [TPSHSH13b].
Takayama et al. [TPSHSH13a] proposed a robust algorithm for quadrangulating 3-sided and 4-sided patches with
arbitrary numbers of edge subdivisions at the patch boundary, and integrated it into their sketch-based retopology system [TPSHSH13b]. While their algorithm also uses a patternbased approach similar to ours, it does not generalize wellto patches with more than 4 sides, because it classifies the
input into several cases by directly comparing the numbersof edge subdivisions given to the patch sides, leading to asignificantly large number of cases to be considered alreadyfor 5-sided patches.
In this paper, we propose a more general algorithm for
quadrangulating N-sided patches with 2 ≤ N ≤ 6. Our key
observation is that the initial problem can be reduced into an
equivalent and much smaller problem, which considerably
decreases the number of cases that need to be considered(Section 2.1). Based on this observation, we provide a complete set of topological patterns that covers all possible inputs,
thus ensuring our algorithm’s generality (Section 2.2). We
then show that the problem of determining whether a certain
topological pattern can satisfy a given input can be concisely
formulated as a small integer linear program (Section 2.3).
We also provide simple ways to explore the space of possible
quadrangulations for the given input (Sections 2.4 and 2.5).
As shown in Figure 1, our algorithm can generate quadrangulations for arbitrary input and proves useful when integrated
into the interactive system by Takayama et al. [TPSHSH13b].
A reference C++ implementation of our algorithm is provided
as a supplementary material.
2. Algorithm
We consider a tessellation of an N-sided patch into a quadmesh with N corner vertices at the boundary, where 2 ≤N ≤ 6. A side of the patch is defined as the mesh boundary
between two consecutive corner vertices. The valence of aninterior vertex is defined as the number of its adjacent edges.
The valence of a corner boundary vertex is defined as thenumber of its adjacent edges plus two, and the valence ofa non-corner boundary vertex is the number of its adjacentedges plus one. A vertex with valence four is called a regularvertex, while a vertex with other valence is called an irregularc 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches

4

4

5

4

3

1

3

7

7

4

1

1

1
4

11

1

4

1

4

4
1

1

3

12
5

16

1

12

1

12

4

4
5

5

2

3

2

Figure 3: Examples of maximally reducing the input for 3- and 4-sided patches. After each reduction operation, a pair of sides
get smaller numbers of edge subdivisions, shown in red.

vertex or a singularity. An edge flow or an edge loop is asequence of edges that starts from and ends at a singularity
or a patch boundary and goes through regular vertices suchthat every pair of consecutive edges does not belong to thesame quad.
The input to our algorithm is the number of edge subdivisions for each side (l0 , · · · , lN−1 ) ∈ ZN
+ where li corresponds
to the i-th side, and the output is a quad mesh that satisfies
the input with as few singularities as possible. In this paper,
the side indices are always taken modulo N. Figure 2 shows
examples of input and output for the quadrangulation of 3-,4-, and 5-sided patches.
Note that it is impossible to quadrangulate the input if thesum of the provided numbers of edge subdivisions, ∑N−1
i=0 li ,is odd. To see this, consider an arbitrary quad mesh patchwith F faces, Eb boundary edges, and Ei internal edges. Since
every quad has four edges and every internal edge is sharedby two quads, these numbers are related as 4F = Eb + 2Ei ,meaning that Eb must always be even.
Therefore, we assume in this paper that ∑N−1
i=0 li is even.
Apart from this restriction, it is possible to arbitrarily vary
the numbers of edge subdivisions li , and our algorithm will
efficiently generate a corresponding quad mesh connectivity.
Our algorithm only determines the topological information,i.e., the mesh connectivity. For visualization purposes in thispaper, we use 2D mesh vertex positions {vi } ⊂ R2 obtainedby the uniform Laplacian smoothing:argmin ∑(i, j)∈E kvi − v j k2

(1)

i∈C

(2)

{vi }

subject tovi = wi ,where E is the set of edges of the mesh, C is the set of boundary vertices, and wi ∈ R2 is the predefined 2D boundary
position to which the i-th boundary vertex is fixed. In actual
retopology scenarios, these 2D vertex positions are mapped
to 3D surface positions using the parameterization.
c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

2.1. Reducing the input
It is challenging to consider all possible input configurations,since their number increases exponentially as we increase N.
Our key observation is that the problem can be reduced to an
equivalent, easier subproblem by trimming the patch. This
operation drastically reduces the number of cases we need toconsider to ensure our algorithm’s generality.
Assume an input (l0 , · · · , lN−1 ) where lk−1 and lk+1
are both greater than 1 for some k, and let us define d =min(lk−1 , lk+1 ) − 1. Then, the quadrangulation of the original input can be achieved by first quadrangulating another,0
smaller input (l00 , · · · , lN−1
) where(li − d if i = k ± 1
li0 =liotherwise,
and then attaching a d-by-lk regular grid to the k-th side of theresulting intermediate quadrangulation. We call this operation
trimming, and its inverse padding. The trimming operation
can be repeated until no more trimming is possible, obtaining a maximally reduced input. Figure 3 shows examples ofmaximally reducing the input for 3- and 4-sided patches.
Maximally reduced input can be classified into a small
number of cases for N ≤ 6, as shown in Table 1, where α andβ represent arbitrary numbers greater than 1. The requirement
for an input to be maximally reduced is that for all k, atleast one of lk−1 and lk+1 must be 1. Note that the cases areclassified modulo rotations and inversions, e.g., (α, 1, 1) ≡(1, α, 1) ≡ (1, 1, α). Doublets, i.e., patches with N = 2, arehandled separately (Section 2.6).
2.2. Topological patterns
Figure 4 shows a complete set of topological patterns thatcovers all cases of maximally reduced input. The blue andpurple arrows with associated symbols x and y shown on topof some patterns are parameters of these patterns, indicating

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches
3-sided

4-sided

𝑥
𝑥

𝑥

2

4+2𝑥

pattern 0

pattern 1

pattern 05-sided2+𝑥 1+𝑦

𝑥
𝑥

1+𝑥

𝑥

1+𝑥

𝑦

2+𝑥

3+𝑥+𝑦

3+2𝑥

4+2𝑥+𝑦pattern 2

pattern 3

pattern 4

1+𝑥

𝑦
𝑥

2+𝑦

2+𝑦

1+𝑦

𝑥

𝑦

𝑥

pattern 1
6-sided

𝑥

𝑦

2+𝑥

𝑥

𝑥
𝑦

2

2+𝑥

4+2𝑥

5+2𝑥+𝑦1+𝑥

2+𝑥

3+2𝑥+𝑦4+2𝑥+𝑦pattern 0

pattern 1

pattern 2

pattern 3

pattern 0

pattern 1

pattern 2

pattern 3

2+𝑦Figure 4: A complete set of topological patterns that covers all cases of maximally reduced input. Vertices with red borders
represent patch corners. The number of edge subdivisions is depicted for each patch side if it is not 1.

N

Input

Condition

Pattern3(α, 1, 1)

α=2
α = 4 + 2x

01

4

(1, 1, 1, 1)(α, 1, 1, 1)(α, β, 1, 1)

5(α, 1, 1, 1, 1)(α, β, 1, 1, 1)

6(1, 1, 1, 1, 1, 1)(α, 1, 1, 1, 1, 1)(α, β, 1, 1, 1, 1)(α, 1, 1, β, 1, 1)

α = 3 + 2xα=βα = β + 2 + 2x

0
2 (x = 0), 3
1
4

α=2
α = 4 + 2xα = β+1α = β + 3 + 2x

0
2
1
3

α = 3 + 2xα=βα = β + 2 + 2xα=βα = β + 2 + 2x

0 (x = 0)
2 (y = 0)1
302

Table 1: Exhaustive set of rules that covers all valid
maximally-reduced inputs (3 ≤ N ≤ 6). For each input, thecorresponding conditions cover all the valid values of α andβ under the assumption that the total number of edge subdivisions is even.
insertion of edge flows at these locations x and y times (x ≥ 0
and y ≥ 0). Figure 5 shows examples of inserting edge flows
into some patterns.

example, let us consider the input of the form (α, 1, 1). Only
inputs with α being even can be quadrangulated, since thesum of the numbers of edge subdivisions has to be even. We
now consider two cases. For the case where α = 2, we apply
pattern 0 directly. For all the other cases where α = 4 + 2x,
we apply pattern 1. We consider all the other forms of input
in a similar manner. In some cases, different patterns canbe applied to the same input; we discuss how to select apattern with minimal number of singularities and how to let
the user choose other feasible patterns in Sections 2.3 and
2.5, respectively.
Strategy for designing patterns. We designed the patterns
such that a minimal number of singularities of valence 3 or
5 are introduced. We first considered the case with one sidehaving arbitrary number of edge subdivisions, and all theother sides having only one edge, i.e., (α, 1, · · · , 1). Then we
considered the case with two adjacent sides having arbitrary
numbers of edge subdivisions, and all the other sides having
only one edge, i.e., (α, β, 1, · · · , 1). While some of the patterns seem to have similar topological structures in common,
we have not yet found a way to automatically generate thesepatterns for a given N; we designed them manually using theconnectivity editing operators [PZKW11].
2.3. Pattern selection formulated as ILP

Figure 5: Examples of inserting edge flows into some patterns.

So far we have shown that it is possible to quadrangulate
N-sided patches with arbitrary numbers of edge subdivisions
by first maximally reducing the input and then choosing oneof the proposed patterns. However, as shown in Figure 6,
this procedure may lead to the selection of an unnecessarily
complex pattern with more singularities than needed. To select the pattern with a minimal number of singularities, welook for all feasible patterns and pick the one with the fewest
singularities.

Table 1 shows that any possible maximally reduced input
can be quadrangulated using at least one of the patterns. As an

We observe that each pattern defines a simple linear relation between the input (l0 , · · · , lN−1 ) and the parameters, i.e.,
the amount of padding of the i-th side pi and the number of

𝑥

𝑥=3

𝑥

𝑥=1
𝑦=2

𝑦

4-sided, pattern 1

6-sided, pattern 3

c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches
1
7

7

1

1

6
4

pattern 1

4

Outputwith pattern 1

Outputwith pattern 0

Figure 6: An example of quadrangulating a 3-sided patch where maximally reducing the input leads to the selection of pattern 1
which is more complex than pattern 0 satisfying the same input.

edge flow insertions x and y; see Figure 7 for some examples.
This relation can be written in matrix form as
Ax = b,(3)

where A is an N × M matrix (constant per pattern) with
M being the number of the pattern’s parameters, x an Mdimensional vector representing the pattern’s parameters (unknown), and b an N-dimensional vector determined by the
input (l0 , · · · , lN−1 ) and the pattern. An important requirement is that each parameter xi ∈ x must be a non-negative
integer. A pattern is then feasible if Eq. (3) has non-negative
integer solutions. This can be formulated as an integer linear
program (ILP):>

maximizec x(4)subject to

Ax = b(5)x ≥ 0, x ∈ ZM

(6)

where c is an M-dimensional vector representing the objective we wish to maximize, which will be discussed later. The
existence of solutions to this ILP means that the pattern is feasible for the input. Since the number of variables M is small(at most 10 in our case), it can be solved very quickly. To
account for the permuted versions of the input (Section 2.1),
we test if the pattern is feasible for all the permuted versionsof the input. We further perform this test sequentially for eachof the patterns in the ascending order of index (i.e., patterns
with fewer singularities are tested first), and as soon as afeasible solution is found, we use the corresponding pattern,parameter, and permutation to generate the quadrangulationaccordingly. Our pattern design (Section 2.2) ensures that atleast one solution will be found during this process.
The ILP often has multiple solutions since N ≤ M. Thismeans that there are multiple parameters for the same patternsatisfying the input. In the next section, we show how tointeractively explore the solution space.
2.4. Adjusting pattern parameters
As shown in Figure 8, some patterns accommodate additionaledge flows other than those depicted in Figure 4. These aretreated as additional variables in the ILP. Since the difference between the number of variables and the number of
constraints M − N is always less than 5, the space of feasible
solutions is at most 4-dimensional.
c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

The default parameters are computed by maximizing thesum of the paddings ∑N−1
i=0 pi . This is achieved by setting
c j = 1 if the corresponding variable represents padding, andc j = 0 elsewhere. To let the user freely and intuitively explore
the space of feasible solutions, we propose a simple userinterface where the user can adjust a certain parameter while
keeping changes to other parameters minimal (Figure 9 top).
Let us denote the current and new sought parameters as x̃
and x, respectively, and suppose we want to increase the k-th
parameter xk . First, we specify an additional constraint as
xk ≥ x̃k + 1.

(7)Then, we conceptually set the objective as
M−1minimize∑ |x j − x̃ j |.

(8)

j=0

To handle this form of objective in ILP, we follow the conventional approach: we introduce auxiliary variables y =(y0 , · · · , yM−1 ), set the objective as
M−1minimize∑ y j,(9)j=0

and specify additional constraints as
y j ≥ −(x j − x̃ j )(10)

y j ≥ x j − x̃ j

(11)

for all j ∈ {0, · · · , M − 1}. This doubles the number of variables in the ILP, but it is still small and can be solved quickly.
When the space of feasible solutions becomes empty due tothe additional constraint (7), the system tells the user that therequested parameter adjustment is impossible.
Notice that the coefficient matrix for pattern 4 for 4-sided
patches shown in Figure 7 contains two pairs of columns thatare identical: the first and the third columns (corresponding
to p0 and p2 ), and the second and the fourth columns (corresponding to p1 and p3 ). These parameters with the identicalcolumns in the coefficient matrix affect the number of edge
subdivisions at the patch boundary in the same manner. Adjusting these parameters while keeping their sum constant canbe seen as topologically translating singularities (Figure 9
middle). By mapping the user’s dragging of the mouse to theadjustment of these parameters, we provide an intuitive interface for translating singularities. The number of additional

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches
3-sided, pattern 03-sided, pattern 1

4-sided, pattern 4𝑙2

5-sided, pattern 3
𝑙3

𝑝2
𝑙2

𝑝1

𝑝2

𝑙2

𝑙1

𝑝0
𝑙0

𝑙0 = 2 + 𝑝1 + 𝑝2
𝑙1 = 1 + 𝑝2 + 𝑝0
𝑙2 = 1 + 𝑝0 + 𝑝1

0 1 1
1 0 1
1 1 0

𝑝1

𝑝2 𝑥

𝑙1

𝑙3

𝑝0

𝑦
𝑝0

𝑙0

𝑙0

𝑝0
𝑙0 − 2
𝑝1 = 𝑙1 − 1
𝑝2
𝑙2 − 1

0 1 1
1 0 1
1 1 0

2
0
0

𝑙1

𝑝1

0
1
0
1

𝑙0 − 4= 𝑙1 − 1𝑙2 − 1

1
0
1
0

0
1
0
1

1
0
1
0

2
0
0
0

1
1
0
0

𝑝4

𝑙4

𝑥

𝑝2

𝑦

𝑝1
𝑝0

𝑙1

𝑙0

𝑙0 = 5 + 𝑝1 + 𝑝4 + 2𝑥 + 𝑦
𝑙1 = 2 + 𝑝2 + 𝑝0 + 𝑦
𝑙2 = 1 + 𝑝3 + 𝑝1
𝑙3 = 1 + 𝑝4 + 𝑝2
𝑙4 = 1 + 𝑝0 + 𝑝3

𝑙0 = 4 + 𝑝1 + 𝑝3 + 2𝑥 + 𝑦
𝑙1 = 2 + 𝑝0 + 𝑝2 + 𝑦𝑙2 = 1 + 𝑝1 + 𝑝3
𝑙3 = 1 + 𝑝0 + 𝑝2

𝑙0 = 4 + 𝑝1 + 𝑝2 + 2𝑥
𝑙1 = 1 + 𝑝2 + 𝑝0
𝑙2 = 1 + 𝑝0 + 𝑝1
𝑝0
𝑝1
𝑝2
𝑥

𝑝3

𝑥

𝑝3

𝑙2

𝑝0
𝑝1
𝑝2
𝑝3
𝑥
𝑦

=

𝑙0 − 4𝑙1 − 2𝑙2 − 1𝑙3 − 1

0
1
0
0
1

1
0
1
0
0

0
1
0
1
0

0
0
1
0
1

1
0
0
1
0

2
0
0
0
0

1
1
0
0
0

𝑝0
𝑝1
𝑝2
𝑝3
𝑝4
𝑥
𝑦

=

𝑙0 − 5𝑙1 − 2𝑙2 − 1𝑙3 − 1𝑙4 − 1Figure 7: Linear relations between the input and the parameters for four patterns.

edge flows, qi , introduced in Figure 8, is indexed in such a
way that its corresponding column in the coefficient matrix
is identical to that of the padding parameter pi , enabling asimilar operation of topologically translating singularities(Figure 9 bottom).
𝑞1

𝑞1

𝑞2

𝑞4

𝑞4

decrease 𝑥

𝑞4

𝑞1

𝑝1 =2
𝑝3 =1

𝑤

translate

𝑝1 =1
𝑝3 =2

𝑧
𝑞3

𝑞0

Figure 8: Additional edge flows for some patterns which aretreated as additional variables in ILP.

2.5. Switching between patterns
As mentioned in Section 2.2, different patterns may satisfy
the same input (Figure 10 left). Furthermore, the same pattern with different permutations may satisfy the same input(Figure 10 middle). We can offer the user further flexibility
by allowing her to switch among these feasible patterns andpermutations. In addition, we can add more patterns to the algorithm that are redundant for ensuring the algorithm’s gener-

𝑝2 =1
𝑞2 =2

𝑝1 =0
𝑝3 =3
translatetranslate

𝑦
𝑞3

𝑥=2

translate

𝑞0

𝑧

𝑥=1

𝑥=0

𝑞1

𝑞1

increase 𝑥

𝑝2 =2
𝑞2 =1

𝑝2 =3
𝑞2 =0

Figure 9: A simple user interface for adjusting parameters.
(Top) The user can increase or decrease a selected parameter. (Middle and bottom) Exchanging values between certain
pairs of parameters amount to topologically translating singularities.
ality, but useful for providing the user with more options; forexample, Figure 10 right shows pattern 2 for 3-sided patches(as proposed by Takayama et al. [TPSHSH13a]) which canbe optionally chosen by the user.
2.6. 2-sided patches
The maximally reduced input for doublets (2-sided
patches) can only take the𝑦𝑥𝑥pattern 0𝑦pattern 1

c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches
45form (A, 1). Due to our assumption of valid input, A must be odd, i.e., A = 3 + 2x,
which is covered by pattern 0 (see inset). An exceptional
singular case that cannot be handled by pattern 0 is the inputof (2, 2), which is covered by pattern 1.
3. Results
We implemented our algorithm using OpenMesh [BSBK02]
for handling the mesh connectivities and lp_solve [BDE∗ 10]
for solving the ILP. Note that the maximal reduction procedure described in Section 2.1 is only used to prove thegenerality of our algorithm. A reference C++ implementation of our algorithm is provided as a supplementary material.
Figure 1 (left) shows a few examples of quadrangulations
generated by our algorithm. The computation time for generating a mesh connectivity of this level of density is at mostaround 30 ms on an Intel Core i7 2.67GHz CPU, where thesteps of the ILP solve and the Laplacian energy minimization are equally dominant. Figure 1 (right) shows two results
created using our algorithm integrated into Takayama et al.’ssystem [TPSHSH13b]. The modeling sessions took about 70
and 40 minutes for the Bear and the Humanoid models, respectively. While the design process is inherently artistic andexploratory, making quantitative comparisons difficult, existing manual retopology tools [Pil13, Pix13] tend to requireroughly twice or more time to achieve similar results.
Comparisons. Figure 11 shows comparisons between
Yasseen et al.’s results (top row), reported in Fig. 9 of their paper [YNB∗ 13] and our results (bottom row). Our results havefewer singularities (left) or the same number of singularities
with a different layout (middle). On the top right example,
the sum of the input numbers of edge subdivisions is odd, andtheir algorithm necessarily introduces a triangular element tohandle this invalid input. If we change the input slightly byincrementing the number of edge subdivisions at the top rightside, our method produces a topologically similar result using
pattern 3 for 5-sided patches (bottom right). Most importantly,
our method is guaranteed to generate quadrangulations withknown number of singularities (determined by the predefinedpatterns) for arbitrary input. To the best of our knowledge,
this guarantee was never provided by any previous algorithm.
c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.

4

12

15

3-sided,pattern 2

Figure 10: Switching patterns and permutations. We canallow the user to choose (left) different patterns and (middle)
different permutations within the same pattern. (Right) We
can also incorporate additional patterns into the algorithm
to provide the user with more options.

5

3

6

6

3

8
4

5

4
4

5

4

13

15
3
6

6

4

8

3
4

Figure 11: Comparisons between Yasseen et al.’s results [YNB∗ 13] (top row) and ours (bottom row).
Our algorithm, as opposed to previous ones [YNB∗ 13,
PBJW14], allows singularities on the patch boundary. While
this might be problematic for some applications, it is a key
feature for our main target application of sketch-based quadmeshing, since we want to always generate a quad mesh forevery valid input specified by the user, including the caseswith no subdivision on some sides of the polygon.
4. Limitations and future work
Our method generates only a subset
of possible quadrangulations satisfying
the same input because of the use ofpredefined patterns. If the user wants acertain quadrangulation which cannot
be represented by any of these patterns (e.g., as in the inset
showing a 2-sided case), she has to manually split the polygon into separate parts. Enlarging the solution space of our
method by creating more complex patterns is left as future
work.
Designing patterns for cases with N ≥ 7 is another subject
for future work. All possible cases of maximally reduced
input for N ∈ {7, 8} are as follows:
N

Maximally-reduced input

7(α, 1, 1, 1, 1, 1, 1), (α, β, 1, 1, 1, 1, 1),(α, 1, 1, β, 1, 1, 1), (α, β, 1, 1, γ, 1, 1)

8(1, 1, 1, 1, 1, 1, 1, 1), (α, 1, 1, 1, 1, 1, 1, 1),(α, β, 1, 1, 1, 1, 1, 1), (α, 1, 1, β, 1, 1, 1, 1),(α, 1, 1, 1, β, 1, 1, 1), (α, β, 1, 1, γ, 1, 1, 1)Some of these cases involve three sides having more than oneedge subdivisions (i.e., α, β, and γ) which may complicate
the pattern design and drastically increase the number of patterns required. We have not yet attempted to manually design
patterns for these cases, because the practical relevance did
not seem worth the effort. An automatic algorithm for generating the minimal set of required patterns for arbitrary N is
an interesting direction for future work.

K. Takayama et al. / Pattern-Based Quadrangulation for N-Sided Patches

Sophisticated geometric optimization could be utilized tofurther enhance the usability of our algorithm. For example,
the uniform Laplacian smoothing used in our implementation
causes flipped quadrilaterals when the shape of the patch is
not convex. This issue would be solved by using one of therecent bijective mapping techniques [SHF13]. We could also
take the geometric features of the 3D shape being retopologized into account, or consider the geometric qualities of theresulting quad mesh when choosing the best quadrangulationin the feasible set, similar to Peng et al.’s approach [PBJW14].

[BLP∗ 13] B OMMES D., L EVY B., P IETRONI N., P UPPO E.,S ILVA C., TARINI M., Z ORIN D.: Quad-mesh generation andprocessing: A survey. Comput. Graph. Forum 32, 6 (2013). 1

Lastly, generalization of our approach to hexahedral meshgenerations is an interesting and challenging direction for
future work. This is highly relevant especially in the context
of finite element analysis. One possible approach would be
to let the user decompose the model’s volume into a setof volumetric patches of different types, such as cuboids,
triangle prisms and triangular pyramids. The user would thenbe able to specify the number of edge subdivisions along eachridge line of the patches, based on which the system would
hexahedralize the interior of each patch. Figure 12 showsa few topological patterns for such volumetric patches. It
seems highly challenging to find a complete set of topologicalpatterns that cover all possible configurations.

[dOMM13] DE O LIVEIRA M IRANDA A., M ARTHA L.: Quadrilateral mesh generation using hierarchical templates. In Proc. IMR(2013). 2[BSBK02] B OTSCH M., S TEINBERG S., B ISCHOFF S., KOBBELT
L.: OpenMesh: A generic and efficient polygon mesh data structure. In OpenSG Symposium 2002 (2002). 7[BZK09] B OMMES D., Z IMMER H., KOBBELT L.: Mixed-integer
quadrangulation. ACM Trans. Graph. 28, 3 (2009). 1[CBK12] C AMPEN M., B OMMES D., KOBBELT L.: Dual loops
meshing: quality quad layouts on manifolds. ACM Trans. Graph.
31, 4 (2012). 2[ILS∗ 11] II J. D., L IZIER M., S IQUEIRA M., S ILVA C., N ONATO
L.: Template-based quadrilateral meshing. Computers & Graphics
35, 3 (2011). 1[MPKZ10] M YLES A., P IETRONI N., KOVACS D., Z ORIN D.:
Feature-aligned t-meshes. ACM Trans. Graph. 29, 4 (2010). 1[NSY09] NASRI A., S ABIN M., YASSEEN Z.: Filling N-sided
regions by quad meshes for subdivision surfaces. Comput. Graph.
Forum 28, 6 (2009). 2[PBJW14] P ENG C.-H., BARTON M., J IANG C., W ONKA P.:
Exploring quadrangulations. ACM Trans. Graph. 33, 1 (2014). 2,
7, 8[Pil13] P ILGWAY: 3D-Coat, 2013.
3d-coat.com/. 2, 7

Version V3, http://[Pix13] P IXOLOGIC: ZBrush, 2013. Version 4.4, http://www.
pixologic.com/zbrush/. 2, 7
[PZKW11] P ENG C.-H., Z HANG E., KOBAYASHI Y., W ONKA
P.: Connectivity editing for quadrilateral meshes. ACM Trans.
Graph. 30, 6 (2011). 4

Figure 12: An incomplete set of topological patterns forvolumetric hexahedral mesh generation.

Acknowledgements
The authors wish to thank Alexander Sorkine-Hornung and
Maurizio Nitti for helpful discussion and feedback. The Bearmodel is courtesy of Takeo Igarashi. The Humanoid model
is courtesy of the AIM@SHAPE Shape Repository. This
work was supported in part by the ERC grant iModel (StG2012-306877). Kenshi Takayama’s stay at ETH Zurich until
April 2014 was funded by JSPS Postdoctoral Fellowships for
Research Abroad.

References[BCE∗ 13] B OMMES D., C AMPEN M., E BKE H.-C., A LLIEZ P.,
KOBBELT L.: Integer-grid maps for reliable quad meshing. ACM
Trans. Graph. 32, 4 (2013). 2[BDE∗ 10]B ERKELAAR M., D IRKS J., E IKLAND K., N OTE BAERT P., E BERT J.: lp_solve, 2010. Version 5.5.2.0, http:[SHF13] S CHNEIDER T., H ORMANN K., F LOATER M.: Bijective
composite mean value mappings. Comput. Graph. Forum 32, 5(2013). 8[SWZ04] S CHAEFER S., WARREN J., Z ORIN D.: Lofting curve
networks using subdivision surfaces. In Proc. SGP (2004). 2[TPP∗ 11] TARINI M., P UPPO E., PANOZZO D., P IETRONI N.,
C IGNONI P.: Simple quad domains for field aligned meshparametrization. ACM Trans. Graph. 30, 6 (2011). 1[TPSHSH13a] TAKAYAMA K., PANOZZO D., S ORKINE H ORNUNG A., S ORKINE -H ORNUNG O.:
Robust andcontrollable quadrangulation of triangular and rectangularregions. Tech. rep., ETH Zurich, 2013. 2, 6
[TPSHSH13b] TAKAYAMA K., PANOZZO D., S ORKINE H ORNUNG A., S ORKINE -H ORNUNG O.:
Sketch-based
generation and editing of quad meshes. ACM Trans. Graph. 32, 4(2013). 1, 2, 7
[YNB∗ 13] YASSEEN Z., NASRI A., B OUKARAM W., VOLINO
P., M AGNENAT-T HALMANN N.: Sketch-based garment design
with quad meshes. Computer Aided Design 45, 2 (2013). 2, 7
[ZHLB13] Z HANG M., H UANG J., L IU X., BAO H.: A divideand-conquer approach to quad remeshing. IEEE TVCG 19, 6(2013). 2//lpsolve.sourceforge.net/5.5/. 7[BLK11] B OMMES D., L EMPFER T., KOBBELT L.: Global structure optimization of quadrilateral meshes. Comput. Graph. Forum30, 2 (2011). 1

c 2014 The Author(s)Computer Graphics Forum c 2014 The Eurographics Association and John Wiley & Sons Ltd.