Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC3016058

Formats

Article sections

- Abstract
- 1 Introduction
- 2 B-Spline Objects
- 3 Regularization of B-Spline Objects Using L2-Gradient Flows
- 4 Algorithm Steps and Illustrative Examples
- 5 Conclusions and Extensions
- References

Authors

Related links

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.008PMCID: PMC3016058

NIHMSID: NIHMS249988

See other articles in PMC that cite the published article.

By a d-dimensional B-spline object (denoted as ), 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 we mean the process of relocating the control points of 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 , *d* = 1, 2, 3 based on solving weak form *L*^{2}-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.

In this paper we use the term *a d-dimensional B-spline object* to imply a B-spline curve (), a B-spline surface () or a B-spline volume (). 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 . To see this explicitly, let us consider a Bézier curve
$\mathbf{x}(t)={\sum}_{i=0}^{n}{\mathbf{p}}_{i}{B}_{i}^{n}(t)\in {\mathbb{R}}^{2}$, which is a special case of a B-spline curve, on the interval [0, 1]. Let *t* = *t*(*s*) = *αs*(1 − *s*)+ *s*^{2}, *s* [0, 1], *α* [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 *α* [0, 2], which shows that the representation is not unique. Though the changing of *α* does not change the shape of the curve , 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

$$\mathbf{x}(t)={[0,1]}^{T}{B}_{1}^{3}(t)+{[2,1]}^{T}{B}_{2}^{3}(t)+{[2,0]}^{T}{B}_{3}^{3}(t),\phantom{\rule{0.38889em}{0ex}}t\in [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.

The aim of “regularization of a ” is to relocate the control points of such that the object shape is not changed and a uniform sampling on the parameter domain leads to an approximate uniform sampling. The main idea of the regularization is to construct several *L*^{2}-gradient flows that move the control points of 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 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 . 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 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
${\{{V}_{i}\}}_{i=1}^{N}$ of the sphere *S* from the generators
${\{{\mathbf{p}}_{i}\}}_{i=1}^{N}\subset S$ is called SCVT if and only if **p*** _{i}* is the constrained mass centroid of the Voronoi region

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 . Sections 3 discuss the regularization methods of , *d* = 1, 2, 3, respectively. Several experimental examples to illustrate the dramatic effects of regularization are given in section 4.

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.

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

$${u}_{0}\le \cdots \le {u}_{i}\le {u}_{i+1}\le {u}_{i+2}\le \cdots \le {u}_{m+2k}.$$

*U* = {*u*_{0}, ···, *u _{m}*

$$\{\begin{array}{l}{N}_{i,0}(u)=\{\begin{array}{ll}1,\hfill & \text{for}\phantom{\rule{0.38889em}{0ex}}u\in [{u}_{i},{u}_{i+1}),\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}i=0,1,\cdots ,m+2k-1,\hfill \\ {N}_{i,k}(u)=\frac{u-{u}_{i}}{{u}_{i+k}-{u}_{i}}{N}_{i,k-1}(u)+\frac{{u}_{i+k+1}-u}{{u}_{i+k+1}-{u}_{i+1}}{N}_{i+1,k-1}(u),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}i=0,1,\cdots ,m+k-1,\hfill \\ \text{Assume}\frac{0}{0}=0\hfill \end{array}$$

(2.1)

where *i* is the index of *N _{i,k}*(

$${u}_{0}={u}_{1}=\cdots ={u}_{k}=0,\phantom{\rule{0.38889em}{0ex}}{u}_{k}<{u}_{k+1}<\cdots <{u}_{m+k},\phantom{\rule{0.38889em}{0ex}}{u}_{m+k}=\cdots ={u}_{m+2k}=1.$$

In order to have the B-spline objects to be at least *C*^{1} smooth, we take *k* ≥ 2.

For given positive integers *m*_{1}, *m*_{2}, ···, *m _{d}*,

$${U}^{(l)}=\{{u}_{0}^{(l)},\cdots ,{u}_{{m}_{l}+2k}^{(l)}\},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}l=1,\cdots ,d,$$

the 2d-sided degree *k* spline object is defined as

$${\mathcal{O}}^{d}=\{\mathbf{x}\in {\mathbb{R}}^{n}:\mathbf{x}=\mathbf{x}(\mathbf{u}),\mathbf{u}\in {[0,1]}^{d}\},$$

with

$$\mathbf{x}(\mathbf{u})=\sum _{{i}_{1}=0}^{{m}_{1}+k-1}\cdots \sum _{{i}_{d}=0}^{{m}_{d}+k-1}{\mathbf{p}}_{{i}_{1}\cdots {i}_{d}}\prod _{j=1}^{d}{N}_{{i}_{j},k}({u}^{(j)}),$$

where

$$\mathbf{u}={[{u}^{(1)},\cdots ,{u}^{(d)}]}^{T}\in {[0,1]}^{d}.$$

**p**_{i}_{1···}_{i}_{d} * ^{n}* are called control points of the object

For a fixed **u*** _{l}* [0, 1]

$${\mathbf{u}}_{l}={[{u}^{(1)},\cdots ,{u}^{(l-1)},{u}^{(l+1)},\cdots ,{u}^{(d)}]}^{T}\in {\mathbb{R}}^{d-1}.$$

If ||*D _{l}*

In this paper, our attention is focused on the cases *n* = 3, *d* = 1, 2, 3, where the B-spline objects are space curves , surfaces and volumes in ^{3}, respectively.

In this section, we give a set of *L*^{2}-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.

For a given B-spline object defined by **x**(**u**), let

$${L}^{(l)}({\mathbf{u}}_{l})={\int}_{0}^{1}\left|\right|{D}_{l}\mathbf{x}(\mathbf{u})\left|\right|\text{d}{u}^{(l)},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\mathbf{u}\in {[0,1]}^{d},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}l=1,\cdots ,d.$$

For a fixed **u*** _{l}* [0, 1]

(3.1)

To regularize the B-spline object **x**(**u**), we minimize the energies ^{(}^{l}^{)}() by moving the object point in the *D _{l}*

(3.2)

where *f* is a given *C*^{1} smooth function with respect to its arguments.

Let () be an energy functional defined by (3.2) for the B-spline object . Then the *L*^{2}-gradient flow of () in the direction D_{l}**x** is given by

$${\int}_{{\mathcal{O}}^{d}}\frac{\partial \mathbf{x}}{\partial t}\phi \text{d}V=-{\int}_{{\mathcal{O}}^{d}}\sum _{k=1}^{d}\left[\left(({D}_{kl}\mathbf{x}){({\alpha}_{k}^{d})}^{T}+{({D}_{kl}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}\right)({D}_{l}\mathbf{x})\phi +{({D}_{l}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}({D}_{l}\mathbf{x}){D}_{k}\phi \right]\text{d}V,$$

(3.3)

where I_{n} stands for the *n* × *n* unit matrix, for d = 1, 2, 3,
${\alpha}_{k}^{d}$ are defined by

$$\begin{array}{l}{\alpha}_{1}^{1}={\nabla}_{{D}_{1}\mathbf{x}}f+\frac{{D}_{1}\mathbf{x}}{\left|\right|{D}_{1}\mathbf{x}\left|\right|},\\ {\alpha}_{1}^{2}={\nabla}_{{D}_{1}\mathbf{x}}f+\frac{1}{\sqrt{g}}[{g}_{22}({D}_{1}\mathbf{x}-{g}_{12}{D}_{2}\mathbf{x})],\phantom{\rule{0.38889em}{0ex}}{\alpha}_{2}^{2}={\nabla}_{{D}_{2}\mathbf{x}}f+\frac{1}{\sqrt{g}}[{g}_{11}({D}_{2}\mathbf{x}-{g}_{12}{D}_{1}\mathbf{x}].\\ {\alpha}_{1}^{3}={\nabla}_{{D}_{1}\mathbf{x}}f+{D}_{2}\mathbf{x}\times {D}_{3}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{\alpha}_{2}^{3}={\nabla}_{{D}_{2}\mathbf{x}}f+{D}_{3}\mathbf{x}\times {D}_{1}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{\alpha}_{3}^{3}={\nabla}_{{D}_{3}\mathbf{x}}f+{D}_{1}\mathbf{x}\times {D}_{2}\mathbf{x}.\end{array}$$

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.

To regularize the B-spline object in the *D _{l}*

$$({D}_{kl}\mathbf{x}){({\alpha}_{k}^{d})}^{T}+{({D}_{kl}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}{({D}_{l}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n},$$

(3.4)

in (3.3) are treated as known quantities which are computed from the previous step of the approximation. The term *D _{l}*

For easy of description, we reorder the control points **p**_{i}_{1···}_{i}_{d} of the B-spline object into a 1-dimensional array and represent them as:

$${\mathbf{x}}_{0},\cdots ,{\mathbf{x}}_{{n}_{0}},{\mathbf{x}}_{{n}_{0}+1},\cdots ,{\mathbf{x}}_{{n}_{1}},$$

where **x**_{0}, ···, **x**_{n}_{0} are inner control points, **x**_{n}_{0+1,} ···, **x**_{n}_{1} are boundary control points, and

$${n}_{0}=\prod _{i=1}^{d}({m}_{i}+k-2)-1,\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}{n}_{1}=\prod _{i=1}^{d}({m}_{i}+k)-1.$$

The B-spline basis functions ${\prod}_{j=1}^{d}{N}_{{i}_{j},k}({u}^{(j)})$ are correspondingly reordered and represented as

$${\phi}_{0},\cdots ,{\phi}_{{n}_{0}},{\phi}_{{n}_{0}+1},\cdots ,{\phi}_{{n}_{1}}.$$

Using this ordering of the basis functions and control points, can be represented as

$$\mathbf{x}(\mathbf{u})=\sum _{j=0}^{{n}_{0}}{\mathbf{x}}_{j}{\phi}_{j}(\mathbf{u})+\sum _{j={n}_{0}+1}^{{n}_{1}}{\mathbf{x}}_{j}{\phi}_{j}(\mathbf{u}).$$

(3.5)

Substituting **x**(*u*, *v*) into (3.3), and taking the test function as * _{i}*, for

$$\sum _{j=0}^{{n}_{0}}{m}_{ij}^{(l)}\frac{\text{d}{\mathbf{x}}_{j}(t)}{\text{d}t}+\sum _{j=0}^{{n}_{0}}{q}_{ij}^{(l)}{\mathbf{x}}_{j}=\sum _{j={n}_{0}+1}^{{n}_{1}}{q}_{ij}^{(l)}{\mathbf{x}}_{j},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}i=0,\cdots ,{n}_{0},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}l=1,\cdots ,d,$$

where

$$\begin{array}{l}{m}_{ij}^{(l)}={\int}_{{\mathcal{O}}^{d}}{\phi}_{i}{\phi}_{j}{\text{I}}_{n}\text{d}V,\\ {q}_{ij}^{(l)}={\int}_{{\mathcal{O}}^{d}}\sum _{k=1}^{d}\left[\left(({D}_{kl}\mathbf{x}){({\alpha}_{k}^{d})}^{T}+{({D}_{kl}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}\right)({D}_{l}{\phi}_{j}){\phi}_{i}+{({D}_{l}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}({D}_{l}{\phi}_{j}){D}_{k}{\phi}_{i}\right]\text{d}V,\end{array}$$

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.

$$\sum _{j=0}^{{n}_{0}}\left({m}_{ij}^{(l)}+\tau {q}_{ij}^{(l)}\right){\mathbf{x}}_{j}^{(s)}=\sum _{j=0}^{{n}_{0}}{m}_{ij}^{(l)}{\mathbf{x}}_{j}^{(s-1)}+\sum _{j={n}_{0}+1}^{{n}_{1}}{q}_{ij}^{(l)}{\mathbf{x}}_{j}^{(0)},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}i=0,\cdots ,{n}_{0},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}l=1,\cdots ,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.

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

Let be the B-spline curve to be regularized and defined by $\mathbf{x}(u)={\sum}_{{i}_{1}=0}^{{m}_{1}+k-1}{\mathbf{p}}_{{i}_{1}}{N}_{{i}_{1},k}(u)$.

- Set the temporal step-size
*τ*, and set*s*= 0, ${\mathbf{p}}_{{i}_{1}}^{(0)}={\mathbf{p}}_{{i}_{1}}$. - Check the stopping conditions if
*s*≥ 1$$\begin{array}{l}max\left|\right|{\mathbf{p}}_{{i}_{1}}^{(s)}-{\mathbf{p}}_{{i}_{1}}^{(s-1)}\left|\right|\le {\epsilon}_{1}\tau ,\\ \text{dis}({({\mathcal{O}}^{1})}^{(s)},{({\mathcal{O}}^{1})}^{(s-1)})\ge {\epsilon}_{2},\end{array}$$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, *m*_{1} = 6.

Let be given B-spline surface to be regularized and defined by

$$\mathbf{x}(u,v)=\sum _{{i}_{1}=0}^{{m}_{1}+k-1}\sum _{{i}_{2}=0}^{{m}_{2}+k-1}{\mathbf{p}}_{{i}_{1}{i}_{2}}{N}_{{i}_{1},k}(u){N}_{{i}_{2},k}(v).$$

- Regularize each of the four boundary curves using the curve regularization algorithm.
- Regularize the interior of the surface as follows
- Set the temporal step-size
*τ*, and set*s*= 0, ${\mathbf{p}}_{{i}_{1}{i}_{2}}^{(0)}={\mathbf{p}}_{{i}_{1}{i}_{2}}$. - Check the stopping conditions$$max\left|\right|{\mathbf{p}}_{{i}_{1}{i}_{2}}^{(s)}-{\mathbf{p}}_{{i}_{1}{i}_{2}}^{(s-1)}\left|\right|\phantom{\rule{0.16667em}{0ex}}\le {\epsilon}_{1}\tau ,$$(4.1)$$\text{dis}({({\mathcal{O}}^{2})}^{(s)},{({\mathcal{O}}^{2})}^{(s-1)})\ge {\epsilon}_{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).

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.

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.2–4.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 *m*_{1} = *m*_{2} = 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.

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.

Let be the given B-spline volume to be regularized and defined by

$$\mathbf{x}(u,v,w)=\sum _{{i}_{1}=0}^{{m}_{1}+k-1}\sum _{{i}_{2}=0}^{{m}_{2}+k-1}\sum _{{i}_{3}=0}^{{m}_{3}+k-1}{\mathbf{p}}_{{i}_{1}{i}_{2}{i}_{3}}{N}_{{i}_{1},k}(u){N}_{{i}_{2},k}(v){N}_{{i}_{3},k}(w).$$

- Regularize each of 12 boundary curves of the volume using the curve regularization algorithm.
- Regularize each of 6 boundary faces of the volume using the surface regularization algorithm.
- Regularize the interior of the volume as follows:
- Set the temporal step-size
*τ*, and set*s*= 0, ${\mathbf{p}}_{{i}_{1}{i}_{2}{i}_{3}}^{(0)}={\mathbf{p}}_{{i}_{1}{i}_{2}{i}_{3}}$. - Check the stopping conditions if
*s*≥ 1$$max\left|\right|{\mathbf{p}}_{{i}_{1}{i}_{2}{i}_{3}}^{(s)}-{\mathbf{p}}_{{i}_{1}{i}_{2}{i}_{3}}^{(s-1)}\left|\right|\phantom{\rule{0.16667em}{0ex}}\le {\epsilon}_{1}\tau ,$$(4.3)If this condition is satisfied, stop the iteration, otherwise set*s*to be*s*+ 1, go back to step (b).

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 *m*_{1} = *m*_{2} = *m*_{3} = 6 and *k* = 3. The sampling is on equal-spaced grid of the domain [0, 1]^{3} with sampling rate 16^{3}.

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.

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.

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 *L*^{2}-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.

- 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.
- 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.
- 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.
- 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(
*m*_{1}+*k*− 2)^{2}(*m*_{2}+*k*− 2)^{2}(*m*_{3}+*k*− 2)^{2}3D integrals need to be computed), the computation is intensive if*m*_{1},*m*_{2}··· 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.

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.

We construct an *L*^{2}-gradient flow for a general form energy functional

(A.1)

where *f* is a given *C*^{1} smooth function with respect to its arguments, *J ^{d}* is the metric of the object. For

$$\begin{array}{l}{J}^{1}=\phantom{\rule{0.16667em}{0ex}}\left|\right|{D}_{1}\mathbf{x}\left|\right|,\\ {J}^{2}=\sqrt{g},\phantom{\rule{0.38889em}{0ex}}g={g}_{11}{g}_{22}-{g}_{12}^{2},{g}_{11}={({D}_{1}\mathbf{x})}^{T}{D}_{1}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{g}_{12}={({D}_{1}\mathbf{x})}^{T}{D}_{2}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{g}_{22}={({D}_{2}\mathbf{x})}^{T}{D}_{2}\mathbf{x},\\ {J}^{3}=det[{D}_{1}\mathbf{x},{D}_{2}\mathbf{x},{D}_{3}\mathbf{x}],\end{array}$$

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

$$\underset{\_}{{\mathcal{O}}^{d}}(\mathrm{\Phi},\epsilon )=\{\underset{\_}{\mathbf{x}}(\mathbf{u},\epsilon )=\mathbf{x}+\epsilon \mathrm{\Phi}(\mathbf{u}):\mathbf{u}\in {[0,1]}^{d}\},\phantom{\rule{0.38889em}{0ex}}\mathrm{\Phi}\in {C}_{0}^{1}{({[0,1]}^{d})}^{n}.$$

Then we have

where

(A.2)

Now we compute *δ*(*D _{k}*

$$\underset{\_}{\mathbf{x}}=\mathbf{x}+\epsilon \mathrm{\Phi},$$

(A.3)

$${D}_{k}\underset{\_}{\mathbf{x}}={D}_{k}\mathbf{x}+\epsilon {D}_{k}\mathrm{\Phi},$$

(A.4)

we have

$$\delta ({D}_{k}\mathbf{x})={D}_{k}\mathrm{\Phi},\phantom{\rule{0.38889em}{0ex}}k=1,\cdots ,d,$$

and

$$\begin{array}{l}\delta ({J}^{1})=\frac{{({D}_{1}\mathrm{\Phi})}^{T}{D}_{1}\mathbf{x}}{\left|\right|{D}_{1}\mathbf{x}\left|\right|},\\ \delta ({J}^{2})=\frac{1}{\sqrt{g}}[{g}_{22}{({D}_{1}\mathrm{\Phi})}^{T}{D}_{1}\mathbf{x}+{g}_{11}{({D}_{2}\mathrm{\Phi})}^{T}{D}_{2}\mathbf{x}-{g}_{12}[{({D}_{1}\mathrm{\Phi})}^{T}{D}_{2}\mathbf{x}+{({D}_{2}\mathrm{\Phi})}^{T}{D}_{1}\mathbf{x}]]\\ \delta ({J}^{3})=det[{D}_{1}\mathrm{\Phi},\phantom{\rule{0.38889em}{0ex}}{D}_{2}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{D}_{3}\mathbf{x}]+det[{D}_{1}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{D}_{2}\mathrm{\Phi},\phantom{\rule{0.38889em}{0ex}}{D}_{3}\mathbf{x}]+det[{D}_{1}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{D}_{2}\mathbf{x},\phantom{\rule{0.38889em}{0ex}}{D}_{3}\mathrm{\Phi}]\\ ={({D}_{1}\mathrm{\Phi})}^{T}({D}_{2}\mathbf{x}\times {D}_{3}\mathbf{x})+{({D}_{2}\mathrm{\Phi})}^{T}({D}_{3}\mathbf{x}\times {D}_{1}\mathbf{x})+{({D}_{3}\mathrm{\Phi})}^{T}({D}_{1}\mathbf{x}\times {D}_{2}\mathbf{x}),\end{array}$$

where × denotes cross product of two vectors in ^{3}. Hence *δ*(*J ^{d}*) could be written as

$$\delta ({J}^{2})=\sum _{k=1}^{d}{({D}_{k}\mathrm{\Phi})}^{T}{\beta}_{k}^{d},\phantom{\rule{0.38889em}{0ex}}{\beta}_{k}^{d}\in {\mathbb{R}}^{n}.$$

Substituting these into (A.2), we have

(A.5)

where

$${\alpha}_{k}^{d}={\nabla}_{{D}_{k}\mathbf{x}}f+{\beta}_{k}^{d}\in {\mathbb{R}}^{n},$$

To construct *L*^{2}-gradient flows moving the volume in the tangent *D _{l}*

$$\mathrm{\Phi}=({D}_{l}\mathbf{x}){({D}_{l}\mathbf{x})}^{T}\phi ,\phantom{\rule{0.38889em}{0ex}}\phi \in {C}_{0}^{1}({[0,1]}^{d}).$$

Then

$${D}_{k}\mathrm{\Phi}=({D}_{kl}\mathbf{x}){({D}_{l}\mathbf{x})}^{T}\phi +({D}_{l}\mathbf{x}){({D}_{kl}\mathbf{x})}^{T}\phi +{({D}_{l}\mathbf{x})}^{T}{D}_{k}\phi .$$

Therefore, we construct the following weak form *L*^{2}-gradient flows moving the surface in the *D _{l}*

$${\int}_{{\mathcal{O}}^{d}}\frac{\partial \mathbf{x}}{\partial t}\phi \phantom{\rule{0.16667em}{0ex}}\text{d}V=-{\int}_{{\mathcal{O}}^{d}}\sum _{k=1}^{d}\left[\left(({D}_{kl}\mathbf{x}){({\alpha}_{k}^{d})}^{T}+{({D}_{kl}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}\right)({D}_{l}\mathbf{x})\phi +{({D}_{l}\mathbf{x})}^{T}{\alpha}_{k}^{d}{\text{I}}_{n}({D}_{l}\mathbf{x}){D}_{k}\phi \right]\phantom{\rule{0.16667em}{0ex}}\text{d}V,l=1,\cdots ,d.$$

(A.6)

For the energy functional defined by (3.1), *f* = [||*D _{l}*

$${\nabla}_{{D}_{l}\mathbf{x}}f=2\left[1-\frac{{L}^{l}({\mathbf{u}}_{l})}{\left|\right|{D}_{l}\mathbf{x}(\mathbf{u})\left|\right|}\right]{D}_{l}\mathbf{x}(\mathbf{u}),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}{\nabla}_{{D}_{k}\mathbf{x}}f=\mathbf{0},\phantom{\rule{0.38889em}{0ex}}\text{for}\phantom{\rule{0.38889em}{0ex}}k\ne l.$$

^{*}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.

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]

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |