PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
Comput Aided Geom Des. Author manuscript; available in PMC 2011 January 5.
Published in final edited form as:
Comput Aided Geom Des. 2011 January 1; 28(1): 38–49.
doi:  10.1016/j.cagd.2010.09.008
PMCID: PMC3016058
NIHMSID: NIHMS249988

Regularization of B-Spline Objects*

Abstract

By a d-dimensional B-spline object (denoted as An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg), we mean a B-spline curve (d = 1), a B-spline surface (d = 2) or a B-spline volume (d = 3). By regularization of a B-spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg we mean the process of relocating the control points of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg such that they approximate an isometric map of its definition domain in certain directions and is shape preserving. In this paper we develop an efficient regularization method for An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg, d = 1, 2, 3 based on solving weak form L2-gradient flows constructed from the minimization of certain regularizing energy functionals. These flows are integrated via the finite element method using B-spline basis functions. Our experimental results demonstrate that our new regularization method is very effective.

Keywords: Spline objects, Regularization, L2-gradient flow, Finite element method

1 Introduction

In this paper we use the term a d-dimensional B-spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg to imply a B-spline curve (An external file that holds a picture, illustration, etc.
Object name is nihms249988ig2.jpg), a B-spline surface (An external file that holds a picture, illustration, etc.
Object name is nihms249988ig3.jpg) or a B-spline volume (An external file that holds a picture, illustration, etc.
Object name is nihms249988ig4.jpg). Since B-spline basis functions are linearly independent, many people believe that the parametric B-spline representation of a B-spline object is unique. However, this is not true. Two different sets of control points may represent the same An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg. To see this explicitly, let us consider a Bézier curve x(t)=i=0npiBin(t)R2, which is a special case of a B-spline curve, on the interval [0, 1]. Let t = t(s) = αs(1 − s)+ s2, s [set membership] [0, 1], α [set membership] [0, 2]. Then t(0) = 0, t(1) = 1 with t(s) increasing. Substituting t(s) into x(t), we obtain another representation y(s) := x(t(s)) for the same curve. In this new representation, there is a free parameter α [set membership] [0, 2], which shows that the representation is not unique. Though the changing of α does not change the shape of the curve An external file that holds a picture, illustration, etc.
Object name is nihms249988ig2.jpg, whenever y(s) is sampled on a uniform grid of the interval [0, 1], different αs yield very different distributions of points on the curve. For the plane Bézier curve

x(t)=[0,1]TB13(t)+[2,1]TB23(t)+[2,0]TB33(t),t[0,1],
(1.1)

Fig 1.1 shows the distributions of the sampling points for three different αs, where the sub-figures (a), (b) and (c) are generated using α values 0, 1 and 2, respectively. It is easy to observe that different αs yield different distributions of the sampling points.

Fig 1.1
(a), (b) and (c) are the sampling points of the curve y(S) = x(t(s)) defined by (1.1) at the equal-spaced parameter values on [0, 1], using α values 0, 1 and 2, respectively.

The aim of “regularization of a An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg” is to relocate the control points of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg such that the object shape is not changed and a uniform sampling on the parameter domain leads to an An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg approximate uniform sampling. The main idea of the regularization is to construct several L2-gradient flows that move the control points of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg in the tangential directions. The foundation of our regularization method is based on a result of Epstein and Gage (see [6]), which states that the tangential motion of a manifold does not change its shape.

The regularization of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg is an interesting problem that has not been directly studied in the past. A direct application of the regularization is to generate a high quality discrete approximation (quality mesh) of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg. Another application perhaps is in the area of computer aided manufacturing (CAM). Quite often, the machine parts to be manufactured are represented by B-splines in a CAM system. When a machine part is manufactured using cutting tools, one often requires the surface motion of the tools or the curve motion relative the tools, be at a uniform rate with respect to the domain parameters.

We arrive at the regularization problem of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg as a result of solving geometric partial differential equations (GPDE) while constructing B-spline GPDE surfaces (see [19]). Certain GPDEs, such as quasi-surface flow (see [20]), contain tangential motion, which cause the evolved surface drift in the tangent directions, yielding an un-isometric surface. Even though the used GPDEs contain no tangential motion, the un-isometric property of the initial surface is inherited during the evolution that follows. Therefore, it becomes necessary to combine a regularization step in the process of surface evolution, especially when the surfaces are being generated for the aforementioned applications.

For the triangular mesh fairing, the regularization problem has been considered in the past in computer graphics literature (see [11, 12, 17, 20]). In these papers, a tangential displacement is imposed at each of the vertices to move it towards its geometric or mass center of the surrounding vertices. In Du et al’s publications [4, 5], Spherical Centroidal Voronoi Tessellation (SCVT) have been introduced. A Voronoi tessellation {Vi}i=1N of the sphere S from the generators {pi}i=1NS is called SCVT if and only if pi is the constrained mass centroid of the Voronoi region Vi for i = 1, ··· N. Recently, a superlinear convergent Centroidal Voronoi Tessellation method for volume has also been presented by Liu, Wang et al. [8]. In [18], a sequence of spherical triangulations are constructed which are optimal in certain sense, leading to smaller truncation error of the discrete Laplace-Beltrami operator.

Another subarea of research that is related to but different from the mesh regularization is mesh re-parametrization, which computes a bijective mapping between a triangular surface mesh and another surface with the same or similar topology. There are several excellent surveys [7, 9, 16] on this topic. For volume data re-parameterization, Martin et al [10] present a method based on discrete volumetric harmonic functions to parameterize a volumetric model in a way that it can be used to fit a single trivariate B-spline to data. We could not find any other prior work that directly addressed the regularization of parametric Bernstein-Bézier or B-spline surfaces.

The rest of our paper is organized as follows: Section 2 introduces some background material on An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg. Sections 3 discuss the regularization methods of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg, d = 1, 2, 3, respectively. Several experimental examples to illustrate the dramatic effects of An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg regularization are given in section 4.

2 B-Spline Objects

B-spline representations of curves and surfaces are well-known (see [1, 2, 3, 13, 15]). For easy of understanding and sake of completeness in this paper, we briefly introduce their definition and establish notation, necessary for subsequent use. There are several equivalent approaches to define B-spline functions, including divided differences of truncated power function (see [2, 15]), the blossoming method (see [13]) and the recursive formulas (see [1, 3]). We adopt the approach of recursive formulas which additionally facilitates ease of computer programming.

Definition

Given a positive integer m, nonnegative integer k and a knot sequence

u0uiui+1ui+2um+2k.

U = {u0, ···, um+2k} is referred to as a knot vector. Then B-splines basis functions are defined as follows

{Ni,0(u)={1,foru[ui,ui+1),0,otherwise,i=0,1,,m+2k1,Ni,k(u)=uuiui+kuiNi,k1(u)+ui+k+1uui+k+1ui+1Ni+1,k1(u),i=0,1,,m+k1,Assume00=0
(2.1)

where i is the index of Ni,k(u), k is the degree. In this paper, we assume that

u0=u1==uk=0,uk<uk+1<<um+k,um+k==um+2k=1.

In order to have the B-spline objects to be at least C1 smooth, we take k ≥ 2.

B-Spline objects

For given positive integers m1, m2, ···, md, nd, a nonnegative integer k, and knot vectors

U(l)={u0(l),,uml+2k(l)},l=1,,d,

the 2d-sided degree k spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg is defined as

Od={xRn:x=x(u),u[0,1]d},

with

x(u)=i1=0m1+k1id=0md+k1pi1idj=1dNij,k(u(j)),

where

u=[u(1),,u(d)]T[0,1]d.

pi1···id Rn are called control points of the object x(u). If il = 0 or ml + k − 1, l = 1, ···, d, pi1···id are called boundary control points. Other control points are called inner control points. Let Dl=u(l) be the first order partial derivative operators, Dij = DiDj the second order partial derivative operators. Then Dlx(u) are tangential vectors of x(u) in the directions u(l), l = 1, ···, d. All the vectors perpendicular to the tangent vectors Dlx(u) form a normal space.

For a fixed ul [set membership] [0, 1]d−1, let L(l)(ul) be the arc length of the space curve x(u) over [0, 1], where

ul=[u(1),,u(l1),u(l+1),,u(d)]TRd1.

If ||Dlx(u)|| = L(l)(ul), ∀ul [set membership] [0, 1]d−1, then we say the object is isometric in the u(l) direction.

In this paper, our attention is focused on the cases n = 3, d = 1, 2, 3, where the B-spline objects An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg are space curves An external file that holds a picture, illustration, etc.
Object name is nihms249988ig2.jpg, surfaces An external file that holds a picture, illustration, etc.
Object name is nihms249988ig3.jpg and volumes An external file that holds a picture, illustration, etc.
Object name is nihms249988ig4.jpg in R3, respectively.

3 Regularization of B-Spline Objects Using L2-Gradient Flows

In this section, we give a set of L2-gradient flows, and a method for discretization, and finally the solution via a linear system solver. The full derivation of these flows from an energy functional is given in the appendix.

3.1 L2-Gradient Flows

For a given B-spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg defined by x(u), let

L(l)(ul)=01||Dlx(u)||du(l),u[0,1]d,l=1,,d.

For a fixed ul [set membership] [0, 1]d−1, L(l)(ul) is the arc length of the space curve x(u), u(l) [set membership] [0, 1], in the[u(l) direction. Let

equation image
(3.1)

To regularize the B-spline object x(u), we minimize the energies x2130(l)(An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg) by moving the object point in the Dlx directions, respectively. This goal is achieved by solving d L2-gradient flows derived from (3.1). Consider the general form energy functional

equation image
(3.2)

where f is a given C1 smooth function with respect to its arguments.

Theorem 3.1

Let x2130(An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg) be an energy functional defined by (3.2) for the B-spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg. Then the L2-gradient flow of x2130(An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg) in the direction Dlx is given by

OdxtφdV=Odk=1d[((Dklx)(αkd)T+(Dklx)TαkdIn)(Dlx)φ+(Dlx)TαkdIn(Dlx)Dkφ]dV,
(3.3)

where In stands for the n × n unit matrix, for d = 1, 2, 3, αkd are defined by

α11=D1xf+D1x||D1x||,α12=D1xf+1g[g22(D1xg12D2x)],α22=D2xf+1g[g11(D2xg12D1x].α13=D1xf+D2x×D3x,α23=D2xf+D3x×D1x,α33=D3xf+D1x×D2x.

Taking l = 1, ···, d in (3.3), we obtain a sequence of flows. For n = 3 and d = 1, 2, 3, these flows are for B-spline curves, surfaces and volumes, respectively.

3.2 Numerical Solutions

To regularize the B-spline object An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg in the Dlx directions, we solve (3.3) interchangeably using finite element method in the spacial discretization and semi-implicit Euler scheme in temporal discretization. More specifically, the terms

(Dklx)(αkd)T+(Dklx)TαkdIn,(Dlx)TαkdIn,
(3.4)

in (3.3) are treated as known quantities which are computed from the previous step of the approximation. The term Dlx is treated as the unknowns.

For easy of description, we reorder the control points pi1···id of the B-spline object into a 1-dimensional array and represent them as:

x0,,xn0,xn0+1,,xn1,

where x0, ···, xn0 are inner control points, xn0+1, ···, xn1 are boundary control points, and

n0=i=1d(mi+k2)1,n1=i=1d(mi+k)1.

The B-spline basis functions j=1dNij,k(u(j)) are correspondingly reordered and represented as

φ0,,φn0,φn0+1,,φn1.

Using this ordering of the basis functions and control points, An external file that holds a picture, illustration, etc.
Object name is nihms249988ig1.jpg can be represented as

x(u)=j=0n0xjφj(u)+j=n0+1n1xjφj(u).
(3.5)

Substituting x(u, v) into (3.3), and taking the test function [var phi] as [var phi]i, for i = 0, ···, n0, we can discretize (3.3) as a set of linear systems of ordinary differential equations (ODE) with the inner control points xi, i = 0, ···, n0, as unknowns.

j=0n0mij(l)dxj(t)dt+j=0n0qij(l)xj=j=n0+1n1qij(l)xj,i=0,,n0,l=1,,d,

where

mij(l)=OdφiφjIndV,qij(l)=Odk=1d[((Dklx)(αkd)T+(Dklx)TαkdIn)(Dlφj)φi+(Dlx)TαkdIn(Dlφj)Dkφi]dV,

For the temporal discretization of these ODE systems, we use a forward Euler scheme which finally leads to a set of linear systems of algebraic equations.

j=0n0(mij(l)+τqij(l))xj(s)=j=0n0mij(l)xj(s1)+j=n0+1n1qij(l)xj(0),i=0,,n0,l=1,,d,
(3.6)

where τ is a temporal step-size. Solving these linear systems via GMRES (see [14]) for l = 1, ···, d, we obtained the new inner control points.

4 Algorithm Steps and Illustrative Examples

This section outline the steps of regularization algorithms for B-spline curves, surfaces and volumes. Illustrative examples are also given.

4.1 Curve Regularization

Let An external file that holds a picture, illustration, etc.
Object name is nihms249988ig2.jpg be the B-spline curve to be regularized and defined by x(u)=i1=0m1+k1pi1Ni1,k(u).

Algorithm 4.1. Curve Regularization

  1. Set the temporal step-size τ, and set s = 0, pi1(0)=pi1.
  2. For n = 3 and d = 1, form the linear system (3.6) and solve it.
  3. Check the stopping conditions if s ≥ 1
    max||pi1(s)pi1(s1)||ε1τ,dis((O1)(s),(O1)(s1))ε2,
    where dis(·, ·) stands for the Hausdorff distance between two curves. If one of the two conditions is satisfied, stop the iteration, otherwise set s to be s + 1, go back to the previous step.

Figure 4.1 shows an regularization example of a B-spline curve, which is defined on the equal-spaced knots with k = 3, m1 = 6.

Fig 4.1
(a) and (b) are control polygons as well as the sampled curves of a spline curve before and after regularization. The larger and smaller diamonds represent the control points and sampled curve points, respectively.

4.2 Surface Regularization

Let An external file that holds a picture, illustration, etc.
Object name is nihms249988ig3.jpg be given B-spline surface to be regularized and defined by

x(u,v)=i1=0m1+k1i2=0m2+k1pi1i2Ni1,k(u)Ni2,k(v).

Algorithm 4.2. Surface Regularization

  1. Regularize each of the four boundary curves using the curve regularization algorithm.
  2. Regularize the interior of the surface as follows
    1. Set the temporal step-size τ, and set s = 0, pi1i2(0)=pi1i2.
    2. For n = 3 and d = 2, form the systems (3.6) and solve them for l = 1, 2.
    3. Check the stopping conditions
      max||pi1i2(s)pi1i2(s1)||ε1τ,
      (4.1)
      dis((O2)(s),(O2)(s1))ε2,
      (4.2)
      where dis(·, ·) stands for Hausdorff distance between two surfaces. If one of the two conditions is satisfied, stop the iteration, otherwise set s to be s + 1, go back to step (b).

Remark 4.1

Though the tangential motion does not change the shape of the surface, but since the PDEs to be solved are nonlinear, the semi-implicit discretization yields a certain amount of normal motion. This motion is small relative to the tangential motion. However the accumulation over long time evolution could make it significant. The stopping condition (4.2) is used to control this movement within a given allowable bound.

Remark 4.2

If a B-spline surface representation is not unique, then there are degrees of freedom to relocate the control points to regularize the surface. If the B-spline surface representation is unique, then there will essentially be no freedom for the tangential motion. However we can still regularize the surface within a given error bound ε2.

Next we give a few examples to illustrate that the surface regularization method proposed is efficient and gives good results. Fig 4.24.4 show the regularization effects for B-spline surfaces with different shaped boundaries. The B-spline basis are defined on the equal-spaced knots with k = 3 and m1 = m2 = 6. Sub-figures (a) and (b) show the control meshes of the spline surfaces on the domain [0, 1]2 without and with using the regularization step, respectively. Sub-figures (c) and (d) show the uniform sampling of the spline surfaces on the domain [0, 1]2 without and with using the regularization step, respectively. It is easy to observe that the surface shapes are unchanged after the regularization, but the quality of the sampling surface meshes are significantly improved.

Fig 4.2
Convex B-spline surface: (a) Control mesh of a spline surface without regularization. (b) Control mesh of the same spline surface after regularization. (c) Spline surface mesh without regularization. (d) Spline surface mesh after regularization.
Fig 4.4
(a) Control mesh of a spline surface without regularization. (b) Control mesh of the same spline surface after regularization. (c) Spline surface mesh without regularization. (d) Spline surface mesh after regularization.

4.3 Volume Regularization

Let An external file that holds a picture, illustration, etc.
Object name is nihms249988ig4.jpg be the given B-spline volume to be regularized and defined by

x(u,v,w)=i1=0m1+k1i2=0m2+k1i3=0m3+k1pi1i2i3Ni1,k(u)Ni2,k(v)Ni3,k(w).

Algorithm 4.3. Volume Regularization

  1. Regularize each of 12 boundary curves of the volume using the curve regularization algorithm.
  2. Regularize each of 6 boundary faces of the volume using the surface regularization algorithm.
  3. Regularize the interior of the volume as follows:
    1. Set the temporal step-size τ, and set s = 0, pi1i2i3(0)=pi1i2i3.
    2. For n = 3 and d = 3, form the systems (3.6) and then solve them for l = 1, 2, 3.
    3. Check the stopping conditions if s ≥ 1
      max||pi1i2i3(s)pi1i2i3(s1)||ε1τ,
      (4.3)
      If this condition is satisfied, stop the iteration, otherwise set s to be s + 1, go back to step (b).

Remark 4.3

Since the tangential space for the B-spline volume is three dimensional, the normal space is null. Hence there is no normal motion problem as mentioned in Remark 4.1. For this reason, we do not need the control of normal motion. We further point out that the regularization for B-spline volume could always be performed. This is different from the cases of curves and surfaces.

Now we present a few test examples to illustrate the regular effect of B-spline volumes. To see the insides of the sampled volumes, we use both spacing and cutoff mesh display techniques. Figure 4.5 shows the regularization of a cube, where the initial inner control points are not regularly distributed. The left figure shows this irregularities. The right figure is the result after regularization. Figure 4.6 and Figure 4.7 show the regularizing results for a volume with curved boundary faces. These figures clearly exhibit the regularization effects. In these examples, the B-spline volume are defined on equal-spaced knots with m1 = m2 = m3 = 6 and k = 3. The sampling is on equal-spaced grid of the domain [0, 1]3 with sampling rate 163.

Fig 4.5
Regularization of a cube: (a) Sampling of the initial B-spline volume with irregularly distributed control points. (b) Sampling of the B-spline volume after the regularization.
Fig 4.6
Regularizing a B-spline volume with curved boundary faces: (a) Sampling of the initial B-spline volume. (b) Sampling of the B-spline volume after the regularization.
Fig 4.7
Regularizing a B-spline volume with curved boundary faces: (a) Sampling of the initial B-spline volume. (b) Sampling of the B-spline volume after the regularization.

5 Conclusions and Extensions

We have presented a novel and efficient regularization technique for multi-dimensional B-spline objects. Our new technique consists of first devising appropriate energy functionals, then constructing variational L2-gradient regularized flows, and finally solving the flows using the finite element method. Our regularization method can be used to generate uniform polygonal approximations for curves, near regular and quality quadrilateral surface meshes for surfaces and near regular and quality hexahedral volumetric meshes for volumes. The implementation results show that the proposed method is effective and yields our desired results. This research could be extended in several directions. Here we list a few possibilities.

  1. Apply the regularizing method to generate regular curve, surface and volume meshes. This could be done by first interpolating the mesh with the B-spline objects, and then regularizing the B-spline objects and finally resampling them to obtain the regularized meshes. We are planing to regularize the meshes from segmentation of virus image data.
  2. Application of the regularization method for B-spline objects could be applied to other type objects, such as Bézier objects, NURBS objects as well as subdivision objects (subdivision curves, surfaces and volumes) and so on.
  3. The regularizing energies used could be replaced with other type functionals to meet different requirement, such as the energy functional measuring the angle distribution of the tangent vectors aiming at to achieve unform distribution of angles. Since the flows for surface and volume are derived for the general form functionals, these extensions are straightforward.
  4. The spatial discretization of the above described flows by the finite element method we use, involves integral computations for forming the coefficient matrices of the ODE systems. For high dimension problem, such as volume regularization (9(m1 + k − 2)2(m2 + k − 2)2(m3 + k − 2)2 3D integrals need to be computed), the computation is intensive if m1, m2 ··· are large. To obtain a more efficient evolution process, one may use divided difference method to solve the flows. In order to do that the weak form flows need to be reformulated into non-weak forms using Green’s formulas.
Fig 4.3
(a) Control mesh of a spline surface without regularization. (b) Control mesh of the same spline surface after regularization. (c) Spline surface mesh without regularization. (d) Spline surface mesh after regularization.

Acknowledgments

Work in this paper was completed when Guoliang Xu was visiting Chandrajit Bajaj at UT-CVC. His visit was additionally supported by the J. T. Oden Faculty Fellowship Research Program at ICES.

A The Derivation of L2-gradient Flows

We construct an L2-gradient flow for a general form energy functional

equation image
(A.1)

where f is a given C1 smooth function with respect to its arguments, Jd is the metric of the object. For n = 3 and d = 1, 2, 3,

J1=||D1x||,J2=g,g=g11g22g122,g11=(D1x)TD1x,g12=(D1x)TD2x,g22=(D2x)TD2x,J3=det[D1x,D2x,D3x],

and det[·] stands for the determinant of a matrix. Let

Od_(Φ,ε)={x_(u,ε)=x+εΦ(u):u[0,1]d},ΦC01([0,1]d)n.

Then we have

equation image

where

equation image
(A.2)

Now we compute δ(Dkx) and δ(Jd) in (A.2). It follows from

x_=x+εΦ,
(A.3)

Dkx_=Dkx+εDkΦ,
(A.4)

we have

δ(Dkx)=DkΦ,k=1,,d,

and

δ(J1)=(D1Φ)TD1x||D1x||,δ(J2)=1g[g22(D1Φ)TD1x+g11(D2Φ)TD2xg12[(D1Φ)TD2x+(D2Φ)TD1x]]δ(J3)=det[D1Φ,D2x,D3x]+det[D1x,D2Φ,D3x]+det[D1x,D2x,D3Φ]=(D1Φ)T(D2x×D3x)+(D2Φ)T(D3x×D1x)+(D3Φ)T(D1x×D2x),

where × denotes cross product of two vectors in R3. Hence δ(Jd) could be written as

δ(J2)=k=1d(DkΦ)Tβkd,βkdRn.

Substituting these into (A.2), we have

equation image
(A.5)

where

αkd=Dkxf+βkdRn,

To construct L2-gradient flows moving the volume in the tangent Dlx direction, l = 1, ···, d, we take

Φ=(Dlx)(Dlx)Tφ,φC01([0,1]d).

Then

DkΦ=(Dklx)(Dlx)Tφ+(Dlx)(Dklx)Tφ+(Dlx)TDkφ.

Therefore, we construct the following weak form L2-gradient flows moving the surface in the Dlx direction

OdxtφdV=Odk=1d[((Dklx)(αkd)T+(Dklx)TαkdIn)(Dlx)φ+(Dlx)TαkdIn(Dlx)Dkφ]dV,l=1,,d.
(A.6)

For the energy functional defined by (3.1), f = [||Dlx(u)|| − Ll(ul)]2, it is easy to derive that

Dlxf=2[1Ll(ul)||Dlx(u)||]Dlx(u),Dkxf=0,forkl.

Footnotes

*G. Xu was supported in part by NSFC grant 60773165 and National Key Basic Research Project of China (2004CB318000). C. Bajaj was supported in part by NSF grants CNS-0540033 and NIH contracts R01-EB00487, R01GM074258, R01-GM07308.

References

1. Cox MG. The numerical evaluation of B-splines. Jour Inst Math Applic. 1972;10:134–149.
2. Curry HB, Schoenberg IJ. On spline distribution and their limits: the Pólya distribution functions. Bull Amer Math Soc. 1947;53:109.
3. de Boor C. On calculating with B-splines. Journal of Approximation Theory. 1972;6:50–62.
4. Du Q, Gunzburger MD, Ju L. Constrained centroidal Voronoi tessellations for surfaces. SIAM J Sci Comput. 2003;24(5):1488–1506.
5. Du Q, Gunzburger MD, Ju L. Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere. Computer methods in applied mechanics and engineering. 2003;192:3933–3957.
6. Epstein CL, Gage M. The curve shortening flow. In: Chorin A, Majda A, editors. Wave Motion: Theory, Modeling, and Computation. Springer-Verlag; New York: 1987. pp. 15–59.
7. Lévy B. Technical Report. ALICE; 2007. Parameterization and deformation anylysis on a manifold. http://alice.loria.fr/publications.
8. Liu Y, Wang W, Levy B, Yan D, Sun F. Computing Centroidal Voronoi Tessellation with Superlinear Convergence. 2008
9. Floater M, Hormann K. Advances in Mutiresolution for Geometry Modelling, Mathematics and Visualization. Springer; 2005. Surface parameterization: a turorial and survey; pp. 157–186.
10. Martin T, Cohen E, Kirby M. ACM Symposium on Solid and Physical Modeling. Stony Brook; New York: 2008. Volumetric parameterization and trivariate b-spline fitting using harmonic functions; pp. 269–280. ACM.
11. Ohtake Y, Belyaev AG, Bogaevski IA. Polyhedral surafce smoothing with simultaneous mesh regularization. Geometric Modeling and Processing Proceedings; 2000. pp. 229–237.
12. Ohtake Y, Belyaev AG, Bogaevski IA. Mesh regularization and adaptive smoothing. Computer-Aided Design. 2001;33:789–800.
13. Ramshaw L. Report 19, Digital. System Research Center; Palo Alto, CA: 1987. Blossoming; a connect-the-dots approach to spline.
14. Saad Y. Iterative Methods for Sparse Linear Systems. 2. SIAM; Philadelphia, PA: 2003.
15. Schoenberg IJ. Contributions to the problem of approximation of equidistance data by analytic functions. Quart Appl Math. 1946;4:45–99.
16. Sheffer A, Praun E, Rose K. Mesh parameterization methods and their applications. Foundations and Trends in Computer and Vision. 2006;2(2):105–171.
17. Wood ZJ, Breen D, Desbrun M. Semi-regular mesh extraction from volumes. IEEE Visualization Proceedings of the conference on Visualization ’00; Salt Lake City, Utah, United States. 2000. pp. 275–282.
18. Xu G. Discrete Laplace-Beltrami Operator on Sphere and Optimal Spherical Triangulations. International Journal of Computational Geometry & Applications. 2006;16(1):75–93.
19. Xu G. Geometric Partial Differential Equation Methods in Computational Geometry. Scientific Publishing Press; 2009.
20. Xu G, Pan Q, Bajaj C. Discrete surface modelling using partial differential equations. Computer Aided Geometric Design. 2006;23(2):125–145. [PMC free article] [PubMed]