Robust and Controllable Quadrangulation ofTriangular and Rectangular Regions

1pattern 3

Alexander Sorkine-Hornung
Disney Research Zurichpattern 4

pattern 2

ternpattern 2

Daniele Panozzo
ETH Zurich

Olga Sorkine-Hornung
ETH Zurichpattern 3

patpattern 1

Kenshi Takayama
ETH Zurich[Nasri et al. 2009]

Figure 1: Basic topological patterns used for quadrangulating rectangular and triangular regions. Vertices with a red circle represent corners.
Vertices with orange and blue fill represent irregular vertices with valence three and five, respectively. pX and pY represent a regular grid ofquadrilaterals padded to the corresponding side of the rectangle (only shown with pattern 1 for brevity). pB , pR , and pL are similarly definedfor the triangle. α and β represent the number of times an edge flow is inserted at these locations. Compared to the patterns proposed by Nasriet al. [2009], all of our patterns have at least one side that has only one edge, which is important for guaranteeing valid quadrangulation of
the region even when the specified number of edge subdivisions is very small and extreme.

Keywords: quad mesh, subdivision surfaces, filling N -sided regions

1Introduction

Remeshing an input 3D surface geometry into a coarse quad meshwith a desired mesh topology is an important process in many production pipelines, especially in the context of producing movies
and video games. Algorithms for automatically generating quad
meshes incorporating sparse user constraints have been studied extensively [Bommes et al. 2013]. However, they are not yet able
to provide the user with direct and explicit controllability over theresulting mesh topology; the link between the user constraints andthe resulting mesh topology is indirect, forcing the user to run thealgorithm multiple times with different constraints and parameters
to obtain the desired result. The process is tedious since the quadrangulation algorithm is not interactive. These algorithms also tend
to perform poorly when coarse mesh resolutions are requested.
For these reasons, many artists today still use rather basic manualmodeling tools for coarse quad remeshing that are not much different
from placing vertices and faces individually [3D-Coat 2013; ZBrush2013]. Although these tools provide complete control over theretopology process, they are slow and difficult to use, even forexperienced artists. For example, it is highly non-trivial to manuallydesign a pure quad mesh that bridges the gap between two partiallyquadrangulated regions of a surface.
Recently, a novel interactive system for manual quad remeshing has
been proposed [Takayama et al. 2013]. The key idea is to represent
a quad mesh as a set of N -sided patches containing multiple quads
inside. The user is allowed to sketch patch boundaries freely andto specify any number of edge subdivision at each patch boundary.
The system inserts singularities (i.e., vertices shared by more or lessthan four quads) inside each patch as needed. It is thus important
to design an algorithm that allows quadrangulating a polygon withprescribed edge subdivisions.
This problem has already been studied in the literature [Schaeferet al. 2004; Nasri et al. 2009], among which Nasri et al.’s algorithm
is the most relevant to us. While being applicable to general N -sided
regions, their algorithm does not support arbitrary numbers of edge

subdivision at the region boundary. For example, their algorithm
fails when one side of the region is given 10 and all the other sides
are given 2 as the number of edge subdivision (for any N ).
We therefore propose a novel algorithm for quadrangulating rectangular and triangular regions that is provably guaranteed to generate
valid quad mesh topology for any even number of edge subdivisionat the region boundary.

2Algorithm

Before describing our algorithm in detail, it is important to exclude
unfeasible boundary configurations.
Proposition 1. The number of boundary edges of any quad mesh iseven.

Proof. Denote a quad mesh as M , the number of its faces asnF (M ), and the number of its boundary edges as nE (M ), respectively. The proposition is proved by induction. When nF (M ) = 1(i.e., M consists of a single quad), clearly nE (M ) = 4 and thepreposition holds. Assume that the proposition holds for any quadmesh M s.t. nF (M ) = k for some integer k. For a quad meshM 0 s.t. nF (M 0 ) = k + 1, there exists a quad mesh M s.t.
nF (M ) = k and a quad f where M 0 can be obtained by attachingf to the boundary of M . Denoting the number of edges sharedby f and M (i.e., they become internal edges in M 0 ) as a, clearlynE (M 0 ) = nE (M ) + 4 − 2a. nE (M ) is even according to theassumption, thus nE (M 0 ) is also even. Therefore, the proposition
holds for any quad mesh M 0 s.t. nF (M 0 ) = k +1, and by induction,
the proposition holds for any quad mesh.

In the following, we assume that the sum of the numbers of edge
subdivisions specified at the boundary of the region is even and callthis valid input. Apart from this restriction, it is possible to arbitrarily vary the edge subdivision, including extremely asymmetricsubdivision counts, and our algorithm will efficiently generate acorresponding quad mesh connectivity.

2.1

2.2

Topological patterns

The basic idea is to use topological patterns to generate the patch
connectivity given the constraints. We devise four patterns for rectangular patches and three for triangular ones (Fig. 1). Let us denotethe desired number of edge subdivisions per side by B, T, R, L (forBottom, Top, etc.) for 4-sided regions and B, R, L for 3-sided regions. The relation between these numbers determines which pattern
will be used to construct the connectivity.
Each pattern is a “minimal” instance of a certain graph configuration,from which an infinite family of patch connectivities can be produced by varying the parameters, which are the number of edge flow
insertions α and β, and the number of outer paddings: horizontal
and vertical paddings for 4-sided patches (called pX and pY ) andtriangle paddings for 3-sided patches (pB , pR , pL ). See Figure 2for an illustration. A single outer padding step adds an edge loop
parallel to the patch side, while insertion of inner edge flows can be
performed in certain directions, as shown in Figures 1 and 2 by theblue and purple arrows. For rectangular patches, the outer padding
can be performed on both opposing sides (top-bottom, left-right),
which effectively translates the irregular vertices in parallel (Figure 3, top). In addition, with patterns 3 and 4 for rectangular regions
and patterns 2 and 3 for triangular regions, the padding can be split
and inserted in the middle of the patch, which effectively makes thedistance between irregular vertices larger (Figure 3, bottom). Most
importantly, any variation of these parameters does not change thenumber of irregular vertices – it is fixed per pattern.

Pattern selection

Here we describe how a pattern is selected based on the specified
number of edge subdivisions for each side of the boundary. For
rectangular regions, we denote the differences between the numbersof edge subdivisions between opposing sides by dX = B − T anddY = R − L. Without loss of generality, we assume an order ofsides such that dX ≥ dY . An appropriate pattern is selected basedon the configuration of dX and dY as follows. For simple cases
where dX = dY = 0 and dX = dY > 0, the regular grid andpattern 1 are selected, respectively. For cases where dX > dY , wefirst check if the specified number of edge subdivisions is extreme(B > R + T + L). If this is not the case, pattern 2 is selected.
Otherwise, patterns 3 and 4 are selected if dY = 0 and dY > 0,respectively. For triangular regions, similarly to the above, weassume an order of sides such that B ≥ R ≥ L. We first check if
the specified number of edge subdivisions is extreme (B > R + L).
If this is not the case, pattern 1 is selected. Otherwise, patterns 2 and3 are selected if R = L and R > L, respectively.

2.3

Parameter calculation

Once an appropriate pattern is selected, the next step is to calculate
its parameters such that it satisfies the specified number of boundaryedge subdivisions.
Rectangular region, pattern 1.

It is clear from the pattern that:

R=L+1+α(1)which gives:
α = R − L − 1.
(2)
The padding parameter can be derived as: pX = T − 1 andpY = L − 1.
valence 5valence 3

Rectangular region, pattern 2.

valence 3
corner

It is clear from the pattern that:

R
B

=
=

L+α−βT +2+α+β(3)
(4)

=
=

(B − T + R − L − 2)/2
(B − T − R + L − 2)/2.

(5)
(6)

which gives:
Figure 2: Using a patch pattern (here, pattern 2, cf. Fig. 1) togenerate a quad-only tessellation. Patch corners are circles with redboundary.
In contrast to the patterns proposed by Nasri et al. [2009], all ourpatterns have at least one side that has only one edge, which is important when dealing with a very small number of edge subdivisions.
Note that while patterns 1 and 2 for rectangular regions and thepattern 1 for triangular regions can be derived from Nasri et al.’spatterns, the other patterns are novel and necessary to support anarbitrary number of edge subdivisions.

αβThe padding parameter can be derived as: pX = T − 1 andpY = R − 1 − α.
Rectangular region, pattern 3.

It is clear from the pattern that:

B = T + 2 + 2α(7)which gives:
α = (B − T − 2)/2.
(8)
The padding parameter can be derived as: pX = T − 1 andpY = R − 1.
Rectangular region, pattern 4.

R
B

==

It is clear from the pattern that:

L+1+α
T + 3 + α + 2β,(9)
(10)

R−L−1
(B − T − 3 − α)/2.

(11)
(12)

which gives:
Figure 3: Moving irregular vertices by changing the distribution ofpadding added to the opposing sides (top), or to the middle of thepattern (bottom).

αβ

=
=

The padding parameter can be derived as: pX = T − 1 and pY =L − 1.

Triangular region, pattern 1.

BRL

==
=

It is clear from the pattern that:2 + pR + pL
1 + pL + pB
1 + pB + pR

(13)
(14)
(15)

Extending this approach to higher number of polygonal sides(N ≥ 5) is left for future work, as the number of possible cases
to be considered grows in a combinatorial manner. In practice,
the user can easily fill pentagonal or other polygonal regions bycombining rectangular and triangular patches.

3which gives:pBpRpL(R + L − B)/2
(B + L − R − 2)/2
(B + R − L − 2)/2.

=
=
=

(16)
(17)
(18)

In this section, we prove that our algorithm can quadrangulate triangular and rectangular regions with arbitrary number of edge subdivisions specified at the region boundary.

3.1
Triangular region, pattern 2.

B
R
L

=
=
=

=
=
=

4 + pR + pL + 2α
1 + pB + pL
1 + pB + pR

(R + L − B + 2 + 2α)/2(B + L − R − 4 − 2α)/2(B + R − L − 4 − 2α)/2,(19)
(20)
(21)

(22)
(23)
(24)

where α is a user-specified parameter chosen from the range[(B − L − R − 2)/2, (B − 4)/2].
Triangular region, pattern 3.

===We use the same notation as in Section 2.2: dX = B − T, dY =R − L and assume dX ≥ dY ≥ 0.
If dX = 0, the region can be trivially quadrangulated with a regulargrid.
In the following, we consider the condition for a pattern to be able torealize a valid quadrangulation given (B, R, T, L) as input, which
we call realizability condition hereafter. In general, a pattern’s
realizability condition is derived by restricting its parameters to benon-negative.
Assuming dX = dY > 0, consider the realizability condition ofpattern 1:
αpX
pY

It is clear from the pattern that:L = 1 + pR + pB , R = 2 + pL + pB , B = 3 + pR + pL + 2α,(25)which gives:
pL
pR
pB

Patterns for rectangular region

It is clear from the pattern that:which gives:
pBpR
pL

Proof of algorithm generality(R + B − L − 4 − 2α)/2(L + B − R − 2 − 2α)/2(L + R − B + 2α)/2,

(26)
(27)
(28)

(29)
(30)
(31)

Assuming dX > dY , consider the realizability condition of pattern 2:
αβ

2.4

pX
pY

Note that a quad mesh generated using our algorithm is not the only
choice that satisfies certain number of boundary edge subdivisions.
For example, Nasri et al. [2009] also considered extreme cases andproposed to attach two of their patterns side by side for rectangularregions, leading to a quad mesh topology different from ours for thesame input (4). Compared to their method, our patterns ensure that
irregular vertices are connected by the same edge flow, as much aspossible, often resulting in more desirable meshing. If a different
configuration is needed, the user can always split a single patch into
two and adjust the topology as desired.

R−L−1≥0T −1≥0
L − 1 ≥ 0.

The first condition always holds under the assumption: R − L =dY ≥ 1 > 0. The second and third conditions obviously hold.
Therefore pattern 1 covers all cases where dX = dY > 0.

where α is a user-specified parameter chosen from the range[(B − L − R)/2, (L + B − R − 2)/2].

Discussion

=
=
=

=
=
=
=

(B − T + R − L − 2)/2 ≥ 0(B − T − R + L − 2)/2 ≥ 0
T −1≥0R − 1 − α ≥ 0.

(32)
(33)
(34)
(35)

Note that dX >= dY + 2 because otherwise (if dX = dY + 1)
the sum of (B, R, T, L) would become odd, which violates ourassumption. This ensures that the first and second conditions always
hold. The third condition also obviously holds. The fourth condition
gives:B ≤R+T +L(36)which is the realizability condition of pattern 2. Therefore pattern 2
covers all cases where dX > dY as long as its realizability condition
holds: B ≤ R + T + L. Note that Nasri et al. [2009] also mention
this condition.
In the following, we assume dX > dY and B > R + T + L.
Assuming dY = 0, consider the realizability condition of pattern 3:
α[Nasri et al. 2009]

Ours (pattern 4)

Figure 4: Quadrangulations of a rectangular region in extreme
cases using the pattern of [Nasri et al. 2009] (left) and our pattern 4(right). Note that our pattern ensures that irregular vertices areconnected by the same edge flow as much as possible.

pXpY

===

(B − T − 2)/2 ≥ 0
T −1≥0R − 1 ≥ 0.

(37)
(38)
(39)

The first condition always holds because dX ≥ dY + 2 ≥ 2 asshown previously. The second and third conditions obviously hold.
Therefore pattern 3 covers all cases where dX > dY = 0.

Assuming dY > 0, which is the last remaining case, consider therealizability condition of pattern 4:
αβpXpY====R−L−1≥0(B − T − 3 − α)/2 ≥ 0
T −1≥0L − 1 ≥ 0.

(40)
(41)
(42)
(43)

The first condition holds from the assumption. The second condition
holds because B−T −3−α = dX −3−dY +1 = dX −dY −2 ≥ 0
as shown previously. The third and fourth conditions obviously hold.
Therefore pattern 4 covers all cases where dX > dY > 0.

3.2

Patterns for triangular region

Assuming R > L, which is the last remaining case, consider the realizability condition of pattern 3. Similar to the above, its realizability
condition is parameterized by α:
pL
pR
pB

===

(R + B − L − 4 − 2α)/2(L + B − R − 2 − 2α)/2(L + R − B + 2α)/2.

(52)
(53)
(54)

This condition gives one lower bound and two upper bounds forα. In order for α to exist that satisfies this condition, the following
condition must hold:max(B −L−R, 0) ≤ min(B +R−L−4, B +L−R−2). (55)
For the right hand side, we have

As in Section 2.2, we assume B ≥ R ≥ L. The proof is similar tothe above section.

B+R−L−4≥=B + (L + 1) − (R − 1) − 4
B + L − R − 2.

(56)
(57)

Consider the realizability condition of pattern 1:pB
pR
pL

===

(R + L − B)/2 ≥ 0(B + L − R − 2)/2 ≥ 0(B + R − L − 2)/2 ≥ 0.

(44)
(45)
(46)

We show that this condition always holds when B = R. The first
condition holds obviously. The second condition holds because Lcannot be smaller than 2 (otherwise the sum of (B, R, L) wouldbecome odd). The third condition holds because B cannot be smaller
than 2. Therefore pattern 1 covers all cases where B = R ≥ L.
In the following, we assume B > R (or equivalently B ≥ R + 1)
and consider the realizability condition of pattern 1. The second
condition holds because B + L − R − 2 ≥ (R + 1) + L − R − 2 =L − 1 ≥ 0. The third condition holds because B cannot be smaller
than 2. The first condition gives:

Finally we show that the condition holds:
min(B + R − L − 4, B + L − R − 2) = B + L − R − 2≥ B + L − R − 2L
=B−L−R= max(B − L − R, 0).
Therefore pattern 3 covers all cases where B > R + L and R > L.

References
3D-C OAT, 2013. Pilgway. Version V3, http://3d-coat.
com/.

(47)

B OMMES , D., L EVY, B., P IETRONI , N., P UPPO , E., S ILVA , C.,
TARINI , M., AND Z ORIN , D. 2013. Quad-mesh generation andprocessing: A survey. Comput. Graph. Forum XX, X.

which is the realizability condition of pattern 1. Therefore pattern
1 covers all cases as long as its realizability condition holds: B ≤R + L. Note that Nasri et al. [2009] also mention this condition.

NASRI , A., S ABIN , M., AND YASSEEN , Z. 2009. Filling n-sided
regions by quad meshes for subdivision surfaces. Comput. Graph.
Forum 28, 6, 1644–1658.

In the following, we assume B > R + L. Note that this means
B ≥ R + L + 2, because otherwise (i.e., B = R + L + 1) the sumof (B, R, L) would become odd.

S CHAEFER , S., WARREN , J., AND Z ORIN , D. 2004. Lofting curvenetworks using subdivision surfaces. In Proc. SGP, 103–114.

B ≤R+L

Further assuming that R = L, consider the realizability conditionof pattern 2. Because pattern 2 has a user-specified parameter α, itsrealizability condition is parameterized by α:pB
pR
pL

=
==

(R + L − B + 2 + 2α)/2 ≥ 0(B + L − R − 4 − 2α)/2 ≥ 0(B + R − L − 4 − 2α)/2 ≥ 0.

(48)
(49)
(50)

This condition gives one lower bound and two upper bounds forα. In order for α that satisfies this condition to exist, the following
condition must hold:max(B−R−L−2, 0) ≤ min(B+R−L−4, B+L−R−4). (51)This condition holds because
max(B−R−L−2, 0) = B − R − L − 2≤B−4= min(B + R − L − 4, B + L − R − 4)
using the fact that B ≥ R + L + 2 and R = L ≥ 1. Therefore
pattern 2 covers all cases where B > R + L and R = L.

TAKAYAMA , K., PANOZZO , D., S ORKINE -H ORNUNG , A., ANDS ORKINE -H ORNUNG , O. 2013. Sketch-based generation andediting of quad meshes. ACM Trans. Graph. 32, 4.
ZB RUSH, 2013. Pixologic, Inc. Version 4.4, http://www.
pixologic.com/zbrush/.