i
i
i
i
i
i
i
i
15
Michael Gleicher
Curves
15.1 Curves
Intuitively, think of a curve as something you can draw with a pen. The curve is
the set of points that the pen traces over an interval of time. While we usually
think of a pen writing on paper (e.g., a curve that is in a 2D space), the pen could
move in 3D to generate a space curve, or you could imagine the pen moving in
some other kind of space.
Mathematically, definitions of curve can be seen in at least two ways:
1. The continuous image of some interval in an n-dimensional space.
2. A continuousmap from a one-dimensionalspace to an n-dimensionalspace.
Both of these definitions start with the idea of an interval range (the time over
which the pen traces the curve). However, there is a significant difference: in
the first definition, the curve is the set of points the pen traces (the image), while
in the second definition, the curve is the mapping between time and that set of
points. For this chapter, we use the first definition.
A curve is an infinitely large set of points. The points in a curve have the
property that any point has two neighbors, except for a small number of points
that have one neighbor (these are the endpoints). Some curves have no endpoints,
either because they are infinite (like a line) or they are closed (loop around and
connect to themselves).
339
i
i
i
i
i
i
i
i
340 15. Curves
Because the “pen” of the curve is thin (infinitesimally), it is difficult to create
filled regions. While space-filling curves are possible (by having them fold over
themselves infinitely many times), we do not consider such mathematical oddities
here. Generally, we think of curves as the outlines of things, not the “insides.”
The problem that we need to address is how to specify a curve—to give a
name or representation to a curve so that we can represent it on a computer. For
some curves, the problem of naming them is easy since they have known shapes:
line segments, circles, elliptical arcs, etc. A general curve that does not have a
“named” shape is sometimes called a free-form curve. Because a free-form curve
can take on just about any shape, they are much harder to specify.
There are three main ways to specify curves mathematically:
1. Im plicit curve representations define the set of points on a curve by giving a
procedure that can test to see if a point in on the curve. Usually, an implicit
curve representation is defined by an implicit function of the form
f(x, y)=0,
so that the curve is the set of points for which this equation is true. Note that
the implicit function f is a scalar function (it returns a single real number).
2. Parametric curve representations provide a mapping from a free parameter
to the set of points on the curve. That is, this free parameter provides an
index to the points on the curve. The parametric form of a curve is a func-
tion that assigns positions to values of the free parameter. Intuitively, if you
think of a curve as something you can draw with a pen on a piece of paper,
the free parameter is time, ranging over the interval from the time that we
began drawing the curve to the time that we finish. The parametric function
of this curve tells us where the pen is at any instant in time:
(x, y)=f(t).
Note that the parametric function is a vector-valued function. This example
is a 2D curve, so the output of the function is a 2-vector; in 3D it would be
a 3-vector.
3. Generative or procedural curve representations provide procedures that can
generate the points on the curve that do not fall into the first two categories.
Examples of generative curve descriptions include subdivision schemes and
fractals.
Remember that a curve is a set of points. These representations give us ways
to specify those sets. Any curve has many possible representations. For this
i
i
i
i
i
i
i
i
15.1. Curves 341
reason, mathematicians typically are careful to distinguish between a curve and
its representations. In computer graphics we are often sloppy, since we usually
only refer to the representation, not the actual curve itself. So when someone says
“an implicit curve,” they are either referring to the curve that is represented by
some implicit function or to the implicit function that is one of the representations
of some curve. Such distinctions are not usually important, unless we need to
consider different representations of the same curve. We will consider different
curve representations in this chapter, so we will be more careful. When we use a
term like “polynomial curve,” we will mean the curve that can be represented by
the polynomial.
By the definition given at the beginning of the chapter, for something to be a
curve it must have a parametric representation. However, many curves have other
representations. For example, a circle in 2D with its center at the origin and radius
equal to 1 can be written in implicit form as
f(x, y)=x
2
+ y
2
− 1=0,
or in parametric form as
(x, y)=f(t)=(cost, sin t),t∈ [0, 2π).
The parametric form need not be the most convenient representation for a given
curve. In fact, it is possible to have curves with simple implicit or generative
representations for which it is difficult to find a parametric representation.
Different representations of curves have advantages and disadvantages. For
example, parametric curves are much easier to draw, because we can sample the
free parameter. Generally, parametric forms are the most commonly used in com-
puter graphics since they are easier to work with. Our focus will be on parametric
representations of curves.
15.1.1 Parameterizations and Re-Parameterizations
A parametric curve refers to the curve that is given by a specific parametric func-
tion over some particular interval. To be more precise, a parametric curve has a
given function that is a mapping from an interval of the parameters. It is often
convenient to have the parameter run over the unit interval from 0 to 1. When the
free parameter varies over the unit interval, we often denote the parameter as u.
If we view the parametric curve to be a line drawn with a pen, we can consider
u =0as the time when the pen is first set down on the paper and the unit of time
to be the amount of time it takes to draw the curve (u =1is the end of the curve).
i
i
i
i
i
i
i
i
342 15. Curves
The curve can be specified by a function that maps time (in these unit coordinates)
to positions. Basically, the specification of the curve is a function that can answer
the question, “Where is the pen at time u?”
If we are given a function f (t) that specifies a curve over interval [a, b],we
can easily define a new function f
2
(u) that specifies the same curve over the unit
interval. We can first define
g(u)=a +(b −a)u,
and then
f
2
(u)=f(g(u)).
The two functions, f and f
2
both represent the same curve; however, they pro-
vide different parameterizations of the curve. The process of creating a new pa-
rameterization for an existing curve is called re-parameterization,andthemap-
ping from old parameters to the new ones (g, in this example) is called the re-
parameterization function.
If we have defined a curve by some parameterization, infinitely many oth-
ers exist (because we can always re-parameterize). Being able to have multiple
parameterizations of a curve is useful, because it allows us to create parameteriza-
tions that are convenient. However, it can also be problematic, because it makes
it difficult to compare two functions to see if they represent the same curve.
The essence of this problem is more general: the existence of the free parame-
ter (or the element of time) adds an invisible, potentially unknown element to our
representation of the curves. When we look at the curve after it is drawn, we don’t
necessarily know the timing. The pen might have moved at a constant speed over
the entire time interval, or it might have started slowly and sped up. For example,
while u =0.5 is halfway through the parameter space, it may not be half-way
along the curve if the motion of the pen starts slowly and speeds up at the end.
Consider the following representations of a very simple curve:
(x, y)=f(u)= (u, u),
(x, y)=f(u)= (u
2
,u
2
),
(x, y)=f(u)= (u
5
,u
5
).
All three functions represent the same curve on the unit interval; however when
u is not 0 or 1, f (u) refers to a different point depending on the representation of
the curve.
If we are given a parameterization of a curve, we can use it directly as our
specification of the curve, or we can develop a more convenient parameterization.
Usually, the natural parameterization is created in a way that is convenient (or
i
i
i
i
i
i
i
i
15.1. Curves 343
natural) for specifying the curve, so we don’t have to know about how the speed
changes along the curve.
If we know that the pen moves at a constant velocity, then the values of the
free parameters have more meaning. Halfway through parameter space is halfway
along the curve. Rather than measuring time, the parameter can be thought to
measure length along the curve. Such parameterizations are called arc-length
parameterizations because they define curves by functions that map from the dis-
tance along the curve (known as the arc length) to positions. We often use the
variable s to denote an arc length parameter.
Technically, a parameterization is an arc-length parameterization if the mag-
nitude of its tangent (that is, the derivative of the parameterization with respect to
the parameter) has constant magnitude. Expressed as an equation,
df(s)
ds
2
= c.
Computing the length along a curve can be tricky. In general, it is defined by
the integral of the magnitude of the derivative (intuitively, the magnitude of the
derivative is the velocity of the pen as it moves along the curve). So, given a value
for the parameter v, you can compute s (the arc-length distance along the curve
from the point f(0) to the point f(v))as
s =
v
0
df(t)
dt
2
dt, (15.1)
where f(t) is a function that defines the curve with a natural parameterization.
Using the arc-length parameterization requires being able to solve Equation
(15.1) for t,givens. For many of the kinds of curves we examine, it cannot be
done in a closed-form (simple) manner and must be done numerically.
Generally, we use the variable u to denote free parameters that range over the
unit interval, s to denote arc-length free parameters, and t to represent parameters
that aren’t one of the other two.
15.1.2 Piecewise Parametric Representations
For some curves, defining a parametric function that represents their shape is easy.
For example, lines, circles, and ellipses all have simple functions that define the
points they contain in terms of a parameter. For many curves, finding a function
that specifies their shape can be hard. The main strategy that we use to create com-
plex curves is divide-and-conquer: we break the curve into a number of simpler
smaller pieces, each of which has a simple description.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.