Farin G. Curves and Surfaces for CAGD. A Practical Guide
Подождите немного. Документ загружается.
422 Chapter 23 Shape
The data point x(Uj) is potentially in error; so why not move x{Uj) to a more
favorable position? It seems that a more favorable position should be such that
the spline curve through the new data no longer exhibits a slope discontinuity.
We now make the following observation: if a spline curve is three (instead
of just two) times differentiable at a point x(^y), then certainly its curvature is
differentiable at
UJ;
that is, it does not have a slope discontinuity there (assuming
that the tangent vector does not vanish at
Uj),
Moreover, the two cubic segments
corresponding to the intervals (t/y_i,
Uj)
and
(wy,
Uj_^i)
are now part of one cubic
segment: the knot
Uj
is only a pseudoknot, which could be removed from the
knot sequence without changing the curve.
We will thus try to remove the "offending knot"
Uj
from the knot sequence,
thereby fairing the curve, and then reinsert the knot in order to keep a spline curve
with the same number of intervals as the initial one. We discussed knot insertion
in Chapter 8. The inverse process, knot removal^ has no unique solution. Several
possibilities are discussed in Eck and Hadenfeld
[185],
Farin et al.
[214],
and
Farin and Sapidis
[215], [533].
We present here a simple yet effective solution to
the knot removal problem. Let the offending knot
Uj
be associated with the vertex
Aj,^ We now formulate our knot removal problem: to what position dy must we
move dy such that the resulting new curve becomes three times differentiable at
Uj}
After some calculation (equating the left and the right third derivative of the
new spline curve), we verify that the new vertex dy is given by
^ (Wy+2 -
^;)1/
+ {Uj - Uj_2)Tj
where the auxiliary points
ly,
ry
are given by
J _ (^y+i - ^y-3)dy-i - (^;+i - ^;)dy_2
and
^i
=
(Wy+3 - ^;-l)dy+i - {Uj - Wy_i)dy+2
^/+3 - ^j
The geometry underlying these equations is illustrated in Figure 23.2.
The faired curve now differs from the old curve between x(Uj_2) and
x(wy_^2)—
thus this fairing procedure is local.
4 This is a slight deviation from the notation of Chapter 8.
23.2 Curve and Surface Smoothing 423
Figure 23.2 Knot removal: if
dy
is moved to dy, the
nevv^
curve is three times differentiable at
Uj.
h max: 0.010
min: -0.564
Figure 23.3 Curve smoothing: an initial curve and B-spline polygon with its curvature plot.
Figures 23.3 and 23.4 illustrate an application of this algorithm, although
it is not used locally, but for all knots. Note that the initial and the smoothed
curves look almost identical, and only their curvature plots reveal significant
shape differences. The initial curve has an inflection point, which is not visible
424 Chapter 23 Shape
}>
max: 0.000
min: -0.507
Figure 23.4 Curve smoothing: the smoothed curve and its curvature plot.
without the use of curvature plots. The faired curve does not have this shape
defect any more.
In practice, the improved vertex dy may be farther aw^ay from the original
vertex
dy
than a prescribed tolerance allows. In that case, we restrict a realistic d;
to be in the direction toward the optimal dy, but within tolerance to the old dy.
Other methods for curve fairing exist. We mention Kjellander's method
[358],
which moves a data point to a more favorable location and then interpolates
the changed data set with a C^ cubic spline. This method is global. A method
that fairs only data points, not spline curves, is presented by Renz
[507].
This
method computes second divided differences, smoothes them, and "integrates"
back up. Methods that aim at the smoothing of single Bezier curves are discussed
by Hoschek
[333], [335].
Variations on the described method are given in
[215].
23.3 Surface Interrogation 425
A method that tries to reduce the degrees of each cubic segment to quadratic is
given in
[200].
25.5 Surface Interrogation
Curvature plots are useful for curves; it is reasonable, therefore, to investigate the
analogous concepts for surfaces. Several authors have done this, including Beck et
al.
[49], Farouki
[219],
Dill
[169],
Munchmeyer
[435], [434],
and Forrest
[242].
An interesting early example is on page 197 of Hilbert and Cohn-Vossen
[323].
Surfaces have tv^o major kinds of curvature: Gaussian and mean; see Section
19.6.
Both kinds can be used for the detection of surface imperfections. Another
type of curvature can be useful, too: absolute curvature
K^\^^.
It is defined by
'^abs=kll + k2l5
where KI and KI are the maximal and minimal normal curvatures at the point
under consideration.
Gaussian curvature does not offer much information about generalized cylin-
ders of the form
c(w, v) = {l
—
u)x(v) + u[x(v) + v].
Even if the generating curve x(v) is highly curved, we still have K = 0 for these
surfaces. A similar statement can be made about the mean curvature H, which
is always zero for minimal surfaces, no matter how complicated.
Color Plates IV and V illustrate the use of curvatures in nonengineering
applications. Plate IV shows the digitized model of
a
bone (digitized as a mesh and
locally fitted with Bezier patches) and a color coding of the absolute curvature:
where the curvature is high, the surface is "painted" red, and where it is low,
it is "painted" blue. This process is referred to as texture mapping in computer
graphics.
Color Plate V shows an application in archeology: a digitized vessel (Native
American) is represented as a triangle mesh (left, with original texture). A cross
section is computed, fitted with a B-spline curve, and its curvature is displayed
(middle). Finally, Gaussian curvature is used as a texture map (right).
Another method for surface interrogation is the use of reflection
lines^
first de-
scribed in Klass
[360].
Poeschl [486] introduced a simplified method, isophotes.
Reflection lines are a standard surface interrogation tool in the styling shop of
a car manufacturer. They are the pattern that is formed on the polished car sur-
face by the mirror images of a number of parallel fluorescent strip lights. If the
426 Chapter 23 Shape
Figure 23.5 Isophotes: a line light source (top) is reflected by a surface.
Figure 23.6 Isophotes: left, a surface with "perfect" isophotes; right, after a perturbation was applied
to the surface.
mirror images are "nice," then the corresponding surface is deemed acceptable.
Whereas reflection lines depend on the position of an observer, isophotes consider
only the angle formed between surface normals and light source. The principle
is illustrated in Figure 23.5.
Reflection lines and isophotes can easily be simulated on a raster graphics
device (mark points whose normal points to one of the light sources). With some
more effort, they can also be computed on a hne drawing device (see Klass [360]).
Figure 23.6 shows a surface with several isophotes and the effect that a small
perturbation can have on them.
Reflection lines and curvature "paintings" have different usages: reflection
lines are not as fine-tuned as curvatures; they are prone to miss local shape defects
of a surface.^ On the other hand, curvatures of a surface may look perfect, yet it
might not have a "pleasant" overall shape—reflection lines have a better chance
of flagging global imperfections.
This is because reflection lines may be viewed as a first-order interrogation tool (involving
only first derivatives), whereas curvature plots are second-order interrogation tools.
23.4 Implementation 427
Once imperfections are detected in a tensor product B-spline surface, we would
want methods to remove them without time-consuming interactive adjustment
of control polygons. One such method is to apply the curve-smoothing method
from Section 23.2 in a tensor product way: smooth all control net rows, then all
control net columns. The resulting surface is usually smoother than the original
surface. Figure 23.6 is an example of this method: the right figure is a B-spline
surface; four iterations of the program f ai r_surf produced the figure on the left.
More involved methods for surface fairing exist; they aim for the enforcement
of convexity constraints in tensor product spline surfaces. We mention Andersson
et al. [8], Jones
[348],
and Kaufmann and Klass
[354].
25.4 Implementation
The routine curvatures may be used to generate curvature values of a rational
Bezier curve. It writes the values into a file that might be read by another program
that generates a curvature plot.
To compute the curvature at the parameter value ^, the curve is subdivided
using the (rational) de Casteljau algorithm. Of the two subpolygons that are
generated, the larger one is selected, and its beginning curvature is computed.
Since the subdivision routine rat__subdiv orders both subpolygons beginning at
the subdivision point, only one curvature routine curvature_0 is needed.
void curvatures(coeffx,coeffy,weight,degree,dense)
/* writes signed curvatures of a rational Bezier curve into
a file,
input:
coeffx, coeffy:
2D
Bezier polygon
weight: the weights
degree: the degree
dense: how many curvature values
to
compute
output:
written into file outfile
V
The routine curvature^O is a simple application of (10.10):
float curvature_0(bez_x,bez_y,weight,degree)
/*
computes curvature
of
rational Bezier curve
at
t=0
Input: bez_x, bez_y, weight: control polygon and weights
degree: degree
of
curve
V
428 Chapter 23 Shape
The following area routine is included for completeness:
float area(pl,p2,p3)
/* find area
of
triangle pl,p2,p3
*/
Note,
however, that area returns a negative value if the input points are
ordered clockwise!
The following routine generates the "raw data" that are needed to create the
curvature plot of a rational B-spline curve. Of course, we may simply set all
weights to unity for the polynomial case.
void bspl_kappas(bspl_x,bspl_y,bspl_w,knot,l,dense)
/* writes curvatures
of
cubic rational B-spline curve into
a file,
input:
bspl_x,bspl_y:
2D rat.
B-spline polygon
bspl_w:
the
B-spline weights
knot:
the
knot sequence
dense:
how
many curvature values
to
compute
per
interval
1:
no. of
intervals
output:
written into file outfile
V
The preceding programs are used by the main program pi ot_b_kappa.
c
in order
to produce Postscript output for a curvature plot.
Now the programs to fair curves and surfaces. First, the curve case:
void fair_bspline(bspl,knot,l,from,to)
/* Fairs
a
cubic rational B-spline curve
by
knot removal/reinsertion.
Input:
bspl:
cubic B-spline control polygon
(one
coord.)
knot: knot sequence
1:
no. of
intervals
from,
to:
from where
to
where
to
fair
Output: same
as
input,
but
hopefully fairer.
V
Second, the surface case:
void fair_surf(bspl,lu,lv,knot_u, knot_v)
/* Fairs B-spline control
net.
23.5 Problems 429
Input: bspl: B-spline control
net
(one coordinate only)
lu,lv: no.
of
intervals
in u- and
v-directi on
knots_u, knots_v: knot vectors
in u- and
v-directi on
Output:
as
input
Note:
Has to be
called once
for
each x-,y-,z- coordinate.
25.5 Problems
1 Show that a planar cubic curve may have tv^o points of inflection, that is,
points v^here curvature changes sign.
2 Show^ that a true space cubic cannot have any points v^ith zero curvature.
PI The routine curvatures produces a file that contains pairs
^/,/c^;
that is, it
can be used to plot curvature versus parameter. Modify the program so it
can be used to produce plots of curvature versus arc length.
P2 Write a program to compute the torsion of a Bezier or a spline curve. Then
produce torsion plots as an additional interrogation tool for space curves.
P3 Compute the curvatures of isoparametric curves of a spline surface, color
code them, and use them as an interrogation tool.
P4 Produce a uniform B-spline surface that interpolates the four boundary data
sets from car.dat. Test if that surface is fair (using P3 if you v^ant); if not,
improve its shape by using fai
r_surf.
This Page Intentionally Left Blank
Evaluation of
Some Methods
In this chapter, we will examine some of the many methods that have been
presented. We will try to point out the relative strengths and weaknesses of each,
a task that is necessarily influenced by personal experience and opinion.
24.1 Bezier Curves or B-Spline Curves?
Taken at face value, this is a meaningless question: Bezier curves are a special
case of B-spline curves. Any system that contains B-splines in their full generality,
allowing for multiple knots, is capable of representing a Bezier curve or, for that
matter, a piecewise Bezier curve.
In fact, several systems use both concepts simultaneously. A curve may be
stored as an array holding B-spline control vertices, knots, and knot multiplici-
ties.
For evaluation purposes, the curve may then be converted to the piecewise
Bezier form.
24.2 Spline Curves or B-Spline Curves?
This question is often asked, yet it does not make much sense. B-splines form a
basis for all splines, so any spline curve can be written as a B-spline curve. What
is often meant is the following: if we want to design a curve, should we pass an
interpolating spline curve through data points, or should we design a curve by
interactively manipulating a B-spline polygon.'' Now the question has become one
concerning curve generation methods rather than curve representation methods.
431