PARAMETRIC SURFACES
While working at the Renault corporation in the 1950s and 1960s, Pierre Bézier developed software systems for designing automobile bodies. His programs utilized mathematical systems of equations developed earlier by Paul de Casteljau, who was working for the competing Citroën automobile manufacturer [BE72, DC63]. The de Casteljau equations describe curves using just a few scalar parameters, and are accompanied by a clever recursive algorithm dubbed “de Casteljau’s algorithm” for generating the curves to arbitrary precision. Now known as “Bézier curves” and “Bézier surfaces,” these methods are commonly used to efficiently model many kinds of curved 3D objects.
11.1QUADRATIC BÉZIER CURVES
A quadratic Bézier curve is defined by a set of parametric equations that specify a particular curved shape using three control points, each of which is a point in 2D space.1 Consider, for example, the set of three points [p0, p1, p2] shown in Figure 11.1.
Figure 11.1
Control points for a Bézier curve.
By introducing a parameter t, we can build a system of parametric equations that define a curve. The t represents a fraction of the distance along the line segment connecting one control point to the next control point. Values for t are within the range [0..1] for points along the segment. Figure 11.2 shows one such value, t = 0.75, applied to the lines connecting p0-p1 and p1-p2 respectively. Doing this defines two new points p01(t) and p12(t) along the two original lines. We repeat this process for the line segment connecting the two new points p01(t) and p12(t), producing point P(t) where t = 0.75 along the line p01(t)-p12(t). P(t) is one of the points on the resulting curve, and for this reason it is denoted with a capital P.
Figure 11.2
Points at parametric position t = 0.75.
Figure 11.3
Building a quadratic Bézier curve.
Collecting many points P(t) for various values of t generates a curve, as shown in Figure 11.3. The more parameter values for t that are sampled, the more points P(t) are generated, and the smoother the resulting curve.
The analytic definition for a quadratic Bézier curve can now be derived. First, we note that an arbitrary point p on the line segment pa-pb connecting two points pa and pb can be represented in terms of the parameter t as follows:
Using this, we find the points p01 and p12 (points on p0-p1 and p1-p2 respectively) as follows:
Similarly, a point on the connecting line segment between these points would be:
Substituting the definitions of p12 and p01 gives:
Factoring and combining terms then gives:
or,
where:
Thus, we find any point on the curve by a weighted sum of the control points. The weighting function B is often called a “blending function” (although the name “B” actually derives from Sergei Bernstein [BE16], who first characterized this family of polynomials). Note that the blending functions are all quadratic in form, which is why the resulting curve is called a quadratic Bézier curve.
11.2CUBIC BÉZIER CURVES
We now extend our model to four control points, resulting in a cubic Bézier curve as shown in Figure 11.4. Cubic Bézier curves are capable of defining a much richer set of shapes than are quadratic curves, which are limited to concave shapes.
Figure 11.4
Building a cubic Bézier curve.
As for the quadratic case, we can derive an analytic definition for cubic Bézier curves:
A point on the curve would then be:
Substituting the definitions of p12-23 and p01-12 and collecting terms yields:
where:
There are many different techniques for rendering Bézier curves. One approach is to iterate through successive values of t, starting at 0.0 and ending at 1.0, using a fixed increment. For instance, if the increment is 0.1, then we could use a loop with t values 0.0, 0.1, 0.2, 0.3, and so on. For each value of t, the corresponding point on the Bézier curve would be computed, and a series of line segments connecting the successive points would be drawn, as described in the algorithm in Figure 11.5.
Another approach is to use de Casteljau’s algorithm to recursively subdivide the curve in half, where t=½ at each recursive step. Figure 11.6 shows the left side subdivision into new cubic control points (q0,q1,q2,q3) shown in green, as derived by de Casteljau (a full derivation can be found in [AS14]).
The algorithm is shown in Figure 11.7. It subdivides the curve segments in half repeatedly, until each curve segment is sufficiently straight enough that further subdivision produces no tangible benefit. In the limiting case (as the control points are generated closer and closer together), the curve segment itself is effectively the same as a straight line between the first and last control points (q0 and q3). Determining whether a curve segment is “straight enough” can therefore be done by comparing the distance from the first control point to the last control point, versus the sum of the lengths of the three lines connecting the four control points:
Figure 11.5
Iterative algorithm for rendering Bézier curves.
D1 = | p0-p1 | + | p1-p2 | + | p2-p3 |
D2 = | p0-p3 |
Then, if D1-D2 is less than a sufficiently small tolerance, there is no point in further subdivision.
Figure 11.6
Subdividing a cubic Bézier curve.
An interesting property of the de Casteljau algorithm is that it is possible to generate all of the points on the curve without actually using the previously described blending functions. Also, note that the center point at p(½) is “shared”; that is, it is both the rightmost control point in the left subdivision, and the leftmost control point in the right subdivision. It can be computed either using the blending functions at t=½, or by using the formula (q2 + r1)/2, as derived by de Casteljau.
Figure 11.7
Recursive subdivision algorithm for Bézier curves.
As a side note, we point out that the subdivide() function shown in Figure 11.7 assumes that the incoming parameters p, q, and r are “reference” parameters, and hence the computations in the function modify the actual parameters in the calls from the drawBezierCurve() function listed above it.
11.3QUADRATIC BÉZIER SURFACES
Whereas Bézier curves define curved lines (in 2D or 3D space), Bézier surfaces define curved surfaces in 3D space. Extending the concepts we saw in curves to surfaces requires extending our system of parametric equations from one parameter to two parameters. For Bézier curves, we called that parameter t. For Bézier surfaces, we will refer to the parameters as u and v. Whereas our curves were composed of points P(t), our surfaces will comprise points P(u,v), as shown in Figure 11.8.
Figure 11.8
Parametric surface.
For quadratic Bézier surfaces, there are three control points on each axis u and v, for a total of nine control points. Figure 11.9 shows an example of a set of nine control points (typically called a control point “mesh”) in blue, and the associated corresponding curved surface (in red).
Figure 11.9
Quadratic Bézier control mesh and corresponding surface.
The nine control points in the mesh are labeled pij, where i and j represent the indices in the u and v directions respectively. Each set of three adjacent control points, such as (p00, p01, p02), defines a Bézier curve. Points P(u,v) on the surface are then defined as a sum of two blending functions, one in the u direction and one in the v direction. The form of the two blending functions for building Bézier surfaces then follows from the methodology given previously for Bézier curves:
The points P(u,v) comprising the Bézier surface are then generated by summing the product of each control point pij and the ith and jth blending functions evaluated at parametric values u and v respectively:
The set of generated points that comprise a Bézier surface is sometimes called a patch. The term “patch” can sometimes be confusing, as we will see later when we study tessellation shaders (useful for actually implementing Bézier surfaces). There, it is the grid of control points that is typically called a “patch.”
11.4CUBIC BÉZIER SURFACES
Moving from quadratic to cubic surfaces requires utilizing a larger mesh—4x4 rather than 3x3. Figure 11.10 shows an example of a 16-control-point mesh (in blue), and the corresponding curved surface (in red).
Figure 11.10
Cubic Bézier control mesh and corresponding surface.
As before, we can derive the formula for points P(u,v) on the surface by combining the associated blending functions for cubic Bézier curves:
where:
Rendering Bézier surfaces can also be done with recursive subdivision [AS14], by alternately splitting the surface in half along each dimension, as shown in Figure 11.11. Each subdivision produces four new control point meshes, each containing sixteen points which define one quadrant of the surface.
Figure 11.11
Recursive subdivision for Bézier surfaces.
When rendering Bézier curves, we stopped subdividing when the curve was “straight enough.” For Bézier surfaces, we stop recursing when the surface is “flat enough.” One way of doing this is to ensure that all of the recursively generated points in a sub-quadrant control mesh are within some small allowable distance from a plane defined by three of the four corner points of that mesh. The distance d between a point (x,y,z) and a plane (A,B,C,D) is:
If d is less than some sufficiently small tolerance, then we stop subdividing, and simply use the four corner control points of the sub-quadrant mesh to draw two triangles.
The tessellation stage of the OpenGL pipeline offers an attractive alternative approach for rendering Bézier surfaces based on the iterative algorithm in Figure 11.5 for Bezier curves. The strategy is to have the tessellator generate a large grid of vertices, and then use the blending functions to reposition those vertices onto the Bézier surface as specified by the cubic Bézier control points. We implement this in Chapter 12.
SUPPLEMENTAL NOTES
This chapter focused on the mathematical fundamentals of parametric Bézier curves and surfaces. We have deferred presenting an implementation of any of them in OpenGL, because an appropriate vehicle for this is the tessellation stage, which is covered in the next chapter. We also skipped some of the derivations, such as for the recursive subdivision algorithm.
In 3D graphics, there are many advantages to using Bézier curves for modeling objects. First, those objects can, in theory, be scaled arbitrarily and still retain smooth surfaces without “pixelating.” Second, many objects made up of complex curves can be stored much more efficiently as sets of Bézier control points, rather than storing thousands of vertices.
Bézier curves have many real-world applications besides computer graphics and automobiles. They can also be found in the design of bridges, such as in the Chords Bridge in Jerusalem [CB16]. Similar techniques are used for building TrueType fonts, which as a result can be scaled to any arbitrary size, or zoomed in to any degree of closeness, while always retaining smooth edges.
Exercises
11.1Quadratic Bézier curves are limited to defining curves that are wholly “concave” or “convex.” Describe (or draw) an example of a curve that bends in a manner that is neither wholly concave nor convex, and thus could not possibly be approximated by a quadratic Bézier curve.
11.2Using a pen or pencil, draw an arbitrary set of four points on a piece of paper, number them from 1 to 4 in any order, and then try to draw an approximation of the cubic Bézier curve defined by those four ordered control points. Then rearrange the numbering of the control points (i.e., their order, but without changing their positions) and redraw the new resulting cubic Bézier curve. There are numerous online tools for drawing Bézier curves you can use to check your approximation.
References
[AS14] |
E. Angel and D. Shreiner, Interactive Computer Graphics: A Top-Down Approach with WebGL, 7th ed. (Pearson, 2014). |
[BE16] |
S. Bernstein, Wikipedia, accessed October 2018, https://en.wikipedia.org/wiki/Sergei_Natanovich_Bernstein |
[BE72] |
P. Bézier, Numerical Control: Mathematics and Applications (John Wiley & Sons, 1972). |
[CB16] |
Chords Bridge, Wikipedia, accessed October 2018, https://en.wikipedia.org/wiki/Chords_Bridge |
[DC63] |
P. de Casteljau, Courbes et surfaces à pôles, technical report (A. Citroën, 1963). |
1Of course, a curve can exist in 3D space. However, a quadratic curve lies entirely within a 2D plane.
