Curves
Intuitively, think of a curve as something you can draw with a (thin) pen. The curve is the set of points 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 (if you are a mathematician) you could imagine the pen moving in some other kind of space.
Mathematically, definitions of curve generally fall into two categories.
The continuous image of some interval.(Source: carl)
A continuous map from a one-dimensional space to an n-dimensional space.(Source: mathworld-curve)
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 former meaning.
A curve is an infinitely large set of points. The points in a curve have a property that any point has 2 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).
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 “names” or representations to all curves so that we can represent them 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 doesn’t 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:
Implicit 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:
Explicit or Parametric curve representations provide a mapping from a free parameter to the set of points on the curve. That is, this free parameter (a single number) provides an index to the points on the curve. The parametric form of a curve defines a function 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 from the time that we began drawing the curve to the time that we finish. The parametric function of this curve would tells us where the pen was at any instant in time:
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 reason, mathematicians are typically 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 actually curve itself. So when someone says “an implicit curve” they are either referring to the curve that can be represented by some implicit function, or 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 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 of 1 can be written in implicit form as:
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 computer graphics since they are easier to work with. Our focus will be on parametric representations of curves.
Parameterizations, and Re-Parameterizations
A parametric curve refers to the curve that is specified by a specific parametric function over some particular interval. To be more precise, a parametric curve has a given function that is a mapping from a range or interval of the parameters. It is often convenient to have the parameter range over the unit interval from 0 to 1. When the free parameter ranges over the unit interval, we often denote it as
If we consider the parametric curve to be a line drawn with a pen, we can define the beginning of time (when ) to be 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 ( is the end of the curve). To use a different unit for time (for example one second), we scale or shift time into the unit interval. 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 ?”
If we are given a function that specifies a curve over its interval, we can easily define a new function that specified the same curve over the unit interval. We can first define
We have defined a curve by the existence of some parameterization. However, if one parameterization exists, infinitely many other ones exist (because we can always re-parameterize). Being able to have multiple parameterizations of a curve is useful because it allows us to create parameterizations that are convenient. However, it can 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 parameter (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 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:
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. The given function is sometimes referred to as the natural parameterization. Usually, the natural parameterization is created in a way that is convenient (or natural) for specifying the curve, so we don’t 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 half-way 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 distance along the curve (known as the arc length) to positions. We often use the variable to denote an arc length parameter.
Technically, a parameterization is an arc length parameterization if the magnitude of its tangent (that is, the derivative of the parameterization with respect to the parameter) has constant magnitude. In an equation,
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 , you can compute (the arc length distance along the curve from the point to the point ) as:
Using the arc-length parameterization requires being able to solve Equation Equation 9 for given . 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 to denote free parameters that range over the unit interval, to denote arc-length free parameters, and to represent parameters that aren’t one of the other two.
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 specify their shape can be hard. The main strategy that we use to create complex curves is divide-and-conquer: we break the curve into a number of simpler smaller pieces, each of which has a simple description.
Figure 1:
A: a curve that can be easily represented as two lines; B: a curve that can be easily represented as a line and a circular arc; C: approximating curve B with 5 line segmentsFor example, consider the curves in Figure Figure 1. The first two curves are easily specified in terms of two pieces. In the case of curve B, we need two different kinds of pieces: a line segment and a circle.
To create a parametric representation of a compound curve (like B), we need to have our parametric function switch between the functions that represent the pieces. If we always define our parametric functions over the range then curve A or B might be defined as:
We need to be careful in defining the functions and to make sure that the pieces of the curve fit together. If then our curve pieces will not connect, and will not form a single continuous curve.
To represent curve B in Figure Figure 1 well, we needed to use two different types of pieces: a line segment and a circular arc. For simplicity’s sake, we may prefer to use a single type of pieces. If we try to represent curve B with only one type of piece (line segments), we cannot exactly recreate the curve (unless we use an infinite number of pieces). While the new curve made of line segments (as in Figure Figure 1 C) may not be exactly the same shape as B, it might be close enough for our uses. In such a case, we might prefer the simplicity of using the simpler line segment pieces to having a curve that more accurately represents the shape.
Also, notice that as we use an increasing number of pieces, we can get a better approximation. In the limit (using an infinite number of pieces) we can exactly represent the original shape.
One advantage to using a piecewise representation is that it allows us to make a tradeoff between:
- how well our represented curve approximates the real shape we are trying to represent;
- how complicated the pieces that we use are;
- how many pieces we use.
So if we’re trying to represent a complicated shape, we might decide that a crude approximation is acceptable, and use a small number of simple pieces. To improve the approximation we can choose between using more pieces and using more complicated pieces.
In computer graphics practice, we tend to prefer using relatively simple curve pieces (either line segments or cubic polynomial segments).
Splines
Before computers, when a draftsman wanted to draw a smooth curve one tool they employed was a stiff piece of metal that they would bend into the desired shape for tracing. Because the metal would bend, not fold, it would always have a smooth shape. The stiffness meant that the metal would bend as little as possible to make the desired shape. This stiff piece of metal was called a spline.
Mathematicians found that they could represent the curves created by a draftsman’s spline with piecewise polynomial functions. Initially, they used the term spline to mean a smooth, piecewise polynomial function. More recently, the term spline has been used to describe any piecewise polynomial function. We prefer this definition.
For us, a spline is a piecewise polynomial function. Such functions are very useful for representing curves.
Exercises
- Devise an arc-length parameterization for the curve represented
by the parametric function:(11)