Introduction

The usage of piecewise polynomials for the representation of curves and surfaces is very common in modern CAD systems since a lot of requirements like interpolation and approximation are simple and even numerically stable to deal with. However, the designer is not satisfied in every case with the resulting curves or surfaces obtained from such applications since the results might be non-smooth or even unfair meaning that any subjective fairing criterion is offered.

Unfortunately, in the literature about fairing a lot of different subjective fairing criteria can be found even for the much simpler case of polynomial spline curves. The two most common definitions for planar curves are the following:

(C1): A (spline) curve is fair if it minimizes the integral of the squared curvature $\kappa^2(s)$ with respect to the arc length (i.e. strain energy of a thin elastic beam); see (Mehlum, 1974).
(C2): A (spline) curve is fair if the plot of the curvature $\kappa(s)$ is continuous, has the appropriate sign, and is as close as possible to a piecewise monotone function with as few as possible monotone pieces; see (Su and Liu, 1989) and (Sapidis and Farin, 1990).

Now in practice these two fairing criteria are not suitable for piecewise polynomials since they lead to non-linear problems whereby explicit solutions cannot be found in general. Therefore, very time-consuming numerical tools are necessary to obtain approximative solutions; see (Moreton, 1993) for criterion (C1) and some similar integral minimization problems.

Therefore, in most known fairing algorithms the criterion (C1) is linearized by the assumption that the actual parameter of the spline curve ${\mbox{\bf x}}$ nearly represents the arc length, meaning that $\, \vert{\mbox{\bf x}}'(t)\vert \,$ is nearly constant. Then the much simpler integral

$\begin{displaymath} E_2 = \int_a^b \left( {\mbox{\bf x}}''(t) \right)^2 \; dt \end{displaymath}$

(1)

is minimized instead. Doing so, (1) yields a quadratic minimization problem with a unique solution if linear function spaces, like piecewise polynomials, are used.

Nevertheless, it should be kept in mind that the usage of (1) can produce strange results if the actual parametrization is far from satisfying $\, \vert{\mbox{\bf x}}'(t)\vert \,$ to be constant. Here, in (Lee, 1990) some exemplary effects are pointed out for spline curves with singularities (see also Section 3.5).

Let us now come back to the problem stated originally. To avoid unfair effects, which can originate from e.g. digitizing errors, two different principles are used in general. The first one consists of incorporating the fairness criterion (1) already into the interpolation or approximation process; see (Hosaka, 1969), (Nowacki, 1990) and (Hagen and Schulze, 1992) for examples and more details. These global methods yield good results although the maximal pointwise error usually cannot be controlled without dealing with non-linear constraints.

The second way to obtain smooth spline curves is the separation of the construction and the fairing process. Therefore, the problem of fairing a given spline must be solved. Here, again two principles exist: global one-step algorithms as described in (Kallay, 1993) or local algorithms which have to be executed iteratively; see Section 4 for details.

In the case of B-spline curves of order , which are always notified in the present paper by

$\begin{displaymath} {\mbox{\bf x}}(t) = \sum_{i=0}^{n} {\mbox{\bf d}}_i \cdot N_{i,k}(t) \;\;\;,\;\;\; t \in [t_{k-1},t_{n+1}] \end{displaymath}$

(2)

with general knot sequence $T=(t_j)_{j=0}^{n+k}$ and control points ${\mbox{\bf d}}_i \in \ifmmode{I\hskip -3pt R} \else{\hbox{$I\hskip -3pt R$}}\fi ^s$ , a first attempt for local fairing using a rather simplified version of criterion (C2) was given by Kjellander (1983) in the cubic case

although this method still contains a global part. Later on, Sapidis and Farin (1990) (see also (Farin et al., 1987)) modified Kjellander's method to be really local. The main part of their algorithm is a knot removal - knot reinsertion step which is explained in more detail in Section 2.

Recently, Farin (1992) developed another local fairing method for cubic B-splines whereby the main part is a degree reduction - degree reelevation step. This method is not considered here although it yields good results, too.

In the present paper we state an alternative local fairing method which is orientated according to criterion (C1) instead of criterion (C2).

We locally minimize the linearized energy integral (1) by modifying only one control point in a local step and keeping all others fixed. This idea is also used successfully in a recent paper of Eck and Jaspert (1994) where polygons are faired by minimizing discretized fairness criteria.

Furthermore, we also consider the integral over the third instead of the second derivative as described in (Meier, 1987) and (Hagen and Schulze, 1990). This criterion, by the way, is equivalent to the integral over $\, (\kappa')^2 + \kappa^2 (\kappa^2 + \tau^2) \,$ if the underlying curve is parametrized with respect to the arc length. Here $\, \tau \,$ represents the torsion of the curve. Therefore, also the variation of the curvature is minimized in some sense as done in (Moreton, 1993), too.

In Section 3 this iterative fairing method which is valid for B-spline curves of general order with general knot vectors in general dimension is described together with some simple modifications and extensions. It is especially outlined how to satisfy a uniform prescribed bound of the deviation which is important for applications.

Further, in Section 4 a general discussion follows where the local and global methods are compared in more detail. In addition, some considerations about local and global convergence of the iterative algorithm can be found.

Finally, some concluding remarks and future research directions are contained in Section 5.