Control It

SCIENCE CHINA

Information Sciences

. RESEARCH PAPERS . September 2010 Vol. 53 No. 9: 1765 1773

doi: 10.1007/s11432-010-4049-y

Interpolating triangular meshes by Loop

subdivision scheme

DENG ChongYang1 & WANG GuoZhao2

1Institute of Applied Mathematics and Engineering Computations, Hangzhou Dianzi University,

Hangzhou 310018, China;

2Department of Mathematics, Zhejiang University, Hangzhou 310027, China

Received February 24, 2009; accepted August 18, 2009

Abstract Using the limit point formula of the Loop subdivision scheme, we propose a very simple and e cient

method for constructing interpolation surface of triangular meshes by Loop subdivision scheme. The excellent

properties of the method are: (1) Locality: the perturbation of a given vertex only in uences the surface shape

near this vertex. (2) E ciency: the locations of new points can be computed with explicit formulae. (3) Easiness

in implementation: only the geometric rule of the rst step should be modi ed. (4) Freedom: for each edge,

there is one degree of freedom to adjust the shape of the interpolation surface. (5) Easiness in generalization: it

is easy to generalize our method to other approximation subdivision schemes with explicit formulae to compute

limit point.

Keywords computer aided geometric design, subdivision surface, approximating subdivision scheme, Loop

surface, surface interpolating

Citation Deng C Y, Wang G Z. Interpolating triangular meshes by Loop subdivision scheme. Sci China Inf Sci,

2010, 53: 1765 1773, doi: 10.1007/s11432-010-4049-y

1 Introduction

Due to the fact that surface modeling by iterated subdivision has such advantageous properties as nu-

merical stability, code simplicity, easiness in handling arbitrary topology, subdivision surfaces have been

used widely in the elds of geometric modeling, computer graphics, etc. Some movie productions and

game engines, such as 3DMax, Maya, Renderman and Softimage, have the function of modeling surface

by subdivision schemes [1].

Subdivision surfaces can be classi ed into approximating surfaces, interpolating surfaces based on the

criterion whether initial control points should be interpolated or not in the nal surfaces. The most

popular approximating schemes include Catmull-Clark scheme [2], which is based on the tensor product

bi-cubic spline and is designed for quadrilateral mesh, Loop scheme [3], which is based on the three-

directional box spline and is designed for triangular mesh. These two schemes produce surfaces that are

C 2 continuous everywhere except at extraordinary vertices, where they are C 1 continuous. The limit

surfaces of the approximating subdivision scheme in ect the shape of the initial meshes well, so that one

can estimate the shapes of the limit surfaces from the initial control meshes, but the control meshes of

Corresponding author (email: ***@***.***.**, *******@***.***)

c Science China Press and Springer-Verlag Berlin Heidelberg 2010 info.scichina.com www.springerlink.com

DENG ChongYang, et al. Sci China Inf Sci

1766 September 2010 Vol. 53 No. 9

approximating subdivision schemes will shrink with subdivision re nements [4]. Butter y scheme, which

was rst proposed by Dyn et al. [5] and then was improved by Zorin et al. [6], and Kobbelt scheme [7]

are two well-known interpolating schemes. These two schemes extend the 4-point subdivision for curve to

triangular mesh and quadrilateral mesh, respectively. Compared with approximating subdivision schemes,

the control mesh of interpolating subdivisions does not shrink with subdivision re nements, but their

limit surfaces are only C 1 continuous for each vertex and have unwanted folds and artifacts [6] (also see

Figure 4(c), Figure 5(c), Figure 7(b) in section 4 of this paper). So it is di cult to estimate the shapes

of the limit surfaces for interpolating subdivision schemes based on the initial meshes.

To interpolate an initial mesh with more pleasing surfaces, many methods of interpolating meshes by

approximating subdivision schemes are proposed. Hoppe et al. [8] presented a modi cation of the Loop

schemes to force the limit surface to go through a particular set of control points. Nasri [9] presented

a modi cation for the Doo-Sabin algorithm to make it interpolate initial control points and Brunet

[10] introduced a set of shape handles associated to the vertices for shape control in Nasri s approach.

Halstead et al. [11] proposed an interpolation scheme of using Catmull-Clark surfaces, which minimizes

a certain fairness measure. Both Nasri s method and Halstead et al. s method had to construct a linear

constraint on the control points of the initial mesh for each interpolating vertex and thus established a

system of linear equations. The initial control mesh for the subdivision surface was obtained by solving

the equations. However, it is unclear under what conditions the linear system is solvable [6]. As pointed

out by Halstead [11], it is possible for the linear system to be singular or ill-conditioned. Recently, based

on Catmull-Clark subdivision scheme, Zheng and Cai [12] proposed a two-phase subdivision scheme to

interpolate arbitrary topology meshes. They used a set of new rules for the rst subdivision iteration to

obtain a new meshes, whose limit surface of Catmull-Clark re nements interpolates the initial vertices.

The features of their method are that the system of linear equations is diagonally dominant, so it is

guaranteed to always work and the system of linear equations can be solved by more e ective iterative

methods.

In the above-mentioned methods, the number of vertices to be interpolated is equal to that of the

vertices of the new initial mesh solved by the system of equations. So there is no freedom to adjust

the shape of the interpolation surface and such methods are global schemes. To make the interpolation

method a local scheme, we adopt the method of introducing additional degrees of freedom to construct

interpolation surface by Loop subdivision scheme. By this new method, the control vertices can be

obtained directly with no need to solve any initial or intermediate large systems. For convenience, in this

paper we restrict our discussion to closed meshes. Extension to open meshes is straightforward.

The advantages of our method over existing methods for surface interpolation by approximating sub-

division scheme lies in ve aspects:

(1) Locality: the perturbation of a given vertex only in uences the surface shape near this vertex.

(2) Simplicity: we use only simple geometric rules to construct smooth surface interpolating given

vertices.

(3) Easiness in implementation: only the geometric rule of the rst subdivision step is modi ed and

the other steps are the same as Loop subdivision scheme.

(4) Freedom: for each edge and face of the initial mesh, there is one degree of freedom for adjusting

the shape of the limit surface.

(5) Easiness in generalization: it is easy to generalize our method to other approximation subdivision

schemes with explicit formulae to compute limit vertex.

2 Loop subdivision scheme and the formula of the limit point

The closed mesh we consider is a polyhedron-like con guration of faces, edges and vertices such that each

vertex corresponds to a point in a 3D space, and each edge is a line segment bounded by two vertices.

Each face is a triangle bounded by three vertices, or three edges. We also require that each edge should

be shared exactly by two faces.

DENG ChongYang, et al. Sci China Inf Sci 1767

September 2010 Vol. 53 No. 9

2.1 Loop subdivision scheme

Given an initial triangular mesh, the process for each re nement iteration of Loop subdivision scheme

goes in the following steps:

(1) For each vertex p, compute a new vertex point as a linear combination of the points within the

neighborhood of the vertex (Figure 1(a)). Speci cally,

p = (1 k )p + (p1 + p2 + + pk ), (1)

where k is the valence of the vertex p, and {pi }k=1 are vertices sharing edge with p. The coe cient is

i

de ned as 3, k = 3,

16

= (2)

3, k > 3.

8k

= 83 (k > 3) of eq. (2) is proposed by Warren [13]. The original formula proposed by

Remark. k

Loop is = k [ 8 ( 3 + 1 cos 2k )2 ](k > 3)[3]. When k = 6, i.e. p is a regular vertex, the value of derived

15

8 4

1

from both the two formulas are equal to 16 . When k is not equal to 6, i.e. p is an irregular vertex, in

general the values of derived from the two formulas are not equal. But the two formulas can ensure

that the limit surfaces are C 1 at the irregular vertices. In this paper we select the Warren s formula due

to the fact that it is simpler than that of Loop.

(2) For each edge p1 p2, compute a new edge point as follows (Figure 1(b)):

1

p= (3p1 + 3p2 + p3 + p4 ), (3)

8

where p3 p4 are two vertices of the two triangles sharing edge p1 p2 (di erent from p1, p2 ).

(3) Create new edges by connecting each new vertex point to the new edge points surrounding it, and

create a new edge by connecting three new edge points of every triangle (Figure 1(c)).

(4) Create a new face for every three points connected by three new edge (Figure 1(c)).

Steps (1) and (2) de ne the new geometry. We call them geometry rules and denote them by G. Steps

(3) and (4) de ne the connectivity of the new points. We call them topology rules and denote them by T .

Then when a triangular mesh is subdivided by Loop subdivision scheme, it can be seen as the following

re nement steps:

1G 1T 2G 2T 3G 3T, (4)

where kG, kT mean the application of the geometric rule and topology rule to the mesh derived from the

initial mesh subdivided by k 1 steps of Loop subdivision process.

Two examples of Loop surfaces with their initial control meshes are shown in Figures 4(b) and 5(b) in

section 4. From these two examples we can see that the limit surfaces are smooth but shrink from the

initial control meshes.

2.2 Formula of the limit point

For the initial vertex pi, there is a corresponding limit point p . The limit point corresponding to pi can

i

be computed by pi and its 1-neighborhood vertices [14] (Figure 2):

k

p = (1 k )pi + pj, (5)

i

j =1

where is de ned as 1,

k = 3,

1

3 5

= +k = (6)

1

8, k > 3.

2k

DENG ChongYang, et al. Sci China Inf Sci

1768 September 2010 Vol. 53 No. 9

Figure 1 Loop subdivision scheme. (a) New vertex point; (b) new edge point; (c) topology rule.

The neighborhood around vertex pi and the limit point of pi .

Figure 2

3 The interpolation method

Given an initial triangular mesh M 0 with a set of vertices {p0 } and a set of edges {e0 }, the process of

i i

constructing interpolation surface of M 0 by Loop subdivision scheme is as follows:

1G 1T 2G 2T 3G 3T, (7)

where 1G is the new geometric rule of computing new vertex points and new edge points. Comparing

(4) with (7), we can see that in the process of interpolating with Loop subdivision scheme, only the

rst geometric step is modi ed. The other steps are the same as those of Loop scheme, so it is easy to

incorporate our method to the modeling systems.

Denote the triangular mesh subdivided by new geometric rule 1G and topology rule 1T from M 0 as

1 . For a vertex p0 of M 0, let its corresponding vertex at M 1 be p1 . Then if each limit point of p1 is p0,

M i i

i i

the limit surface of M interpolates M . By limit point formula (5), p1 is a linear equation with unknown

1 0

i

p0, so the equation has solution even if the new edge points p1 (j = 1, 2, . . ., k ) are selected arbitrarily. So

i j

in theory, the new edge points of 1G can be selected arbitrarily.

To make the interpolation surface fair and re ect the shape of the initial triangular mesh well, we adopt

the geometric rule of normal based subdivision scheme, which is proposed by Yang [15], to compute the

new edge points of 1G .

DENG ChongYang, et al. Sci China Inf Sci 1769

September 2010 Vol. 53 No. 9

Computation of the new edge point of 1G

3.1

Many current interpolating subdivision schemes are spline based, and new vertices are computed as linear

combinations of old vertices. Because these subdivision surfaces are discrete analogous to spline surfaces

interpolation with uniform parameterizations, the nal surfaces may have undesirable undulations when

the triangle of the original mesh are not regular in size or the mesh has ugly changing local shapes.

To obtain smoother interpolation surfaces, Yang [15] proposed the normal based subdivision scheme

for surface interpolation. Numerical examples show that the surfaces obtained by the normal based

subdivision scheme look more fair and natural than those by some previous methods. In this subsection

we propose a method of computing new edge points for 1G based on the normal based subdivision

scheme. Numerical examples show that by this method the interpolation surfaces are fair.

For each vertex p0 of M 0, rst we estimate its normal vector. Suppose that j (j = 1, 2, . . ., mi ) are

i

the triangles sharing the vertex p0 . For each triangle j, assume that the angle at the vertex p0 is j .

i i

The normal of the triangle is nj . Then the normal at the vertex p0 can be estimated as (see [15])

i

mi

j =1 j nj

ni = . (8)

mi

j =1 i nj

Assume that the two end points of edge e are p0, p0 . We de ne the new edge point of e as (Figure 3)

i j

p0 + p0

i j

+ (di ni + dj nj ),

p=

(9)

2

p0 +p0 p0 +p0

where di = (p0 i 2 j )ni, dj = (p0 i 2 j )nj, is a free parameter for adjusting the shape of the

i j

interpolation surface. In theory, can be selected arbitrarily or we can select di erent values of for

di erent edges. But by our experience, should be constrained within 0

Contact this candidate