J. Scott Drader, Math 308, Fall 2003
Bezier curves have proven to be a very useful method of modeling surfaces in many applications. We will assume the reader is familiar with Bezier curves, Bernstein polynomials, and the DeCasteljau algorithm. We only review the definition and properties of Bezier curves, rather than derive them (section 1). We will focus on two surface representations based on Bezier curves (section 2); tensor product surfaces (section 3), and Bezier triangles (section 4). We will discuss the properties they inherit from Bezier curves, as well as methods for subdividing and rendering them. Finally we mention some other more complex representations not dealt with here and why they are desirable (section 5).
The final section details the provided libraries that were used to produce the images shown. The libraries provide methods for Bezier curves in 2D and 3D, as well for tensor product surfaces and Bezier triangles. The 3d portion the library is built on top of ps3d.inc.
Bezier curves can be described on a highlevel by their geometric interpretation, and indeed this is the property that makes them so elegant. A Bezier curve is a function defined over a single parameter that interpolates a sequence of points. As the parameter changes, the path of the line created goes from the first point in the sequence to the last, moving a long curve that is influenced intuitively by the intermediate control points.
Recall that Bezier curves use the Bernstein polynomials as basis functions. The number of points that are interpolated determine the degree of the curve (and the degree of the polynomial that interpolates them). The equation of the curve is
Bezier curves have several key properties (inherent from the Bernstein polynomials) that are important to the properties curves and 3D surfaces based on them. As we are concerned with 3D surfaces we only state the properties and do not prove them.
The curve interpolates its first and last control point.
The entire curve lies within the convex hull of the control points.
It is invariant under affine transformations (i.e. transforming the curve is only a matter of transforming the control points)
The curve is tangent to its control polygon at the endpoints.
The curve can be evaluated and/or subdivided recursively by the DeCasteljau algorithm.
A degree 3 (cubic) Bezier curve and its control
polygon.
There are several methods of drawing Bezier curves. The most obvious method is to directly evaluate the polynomial at fixed intervals of t to produce a set of points on the curve, which can be joined to form an approximation of the curve. Although this method works, it is inefficient. The above method can be sped up by using the recursive DeCasteljau algorithm to evaluate the curve for values of t. The best method however is recursively subdividing the curve by repeated applications of DeCasteljau.
The DeCasteljau has the property that evaluation of the curve for a value of t produces control points for 2 smaller curves, one from 0 to t and the 2^{nd} from t to 1. Hence applying it at t = 1/2 splits the curve into a left and right curve. By recursively splitting the original curve, the polygon formed by assembling the control points of the subcurves quickly converges to the final curve.
After 2 subdivisions, the curve is already closely approximated
by the control polygons of the 4 resultant curves.
Just as we can use a parameterization in one variable to define a curve, we can use a parameterization in 2 variables to define a surface in 3D. Tensor product surfaces (or rectangular Bezier patches) are the 2variable extension of Bezier curves. Instead of interpolating a sequence of points, they can be thought as a way to interpolate a sequence of Bezier curves, or a rectangular mesh of control points. The formula is
where b_{i,j} is the i,j^{th} control point in the control mesh (i.e. b is the 2D mesh of control points, which we will refer to as the control net). Holding the parameter s constant and traversing the surface for 0 < t < 1 traces a Bezier curve that lies on the surface, and vice versa.
The properties of tensor product surfaces are natural extensions of those for Bezier curves. They are listed below, and numbered such that they correspond to the above list of properties of Bezier curves.
The patch interpolates the corner vertices of its control net.
The surface lies within the convex hull of its control points.
It is invariant under affine transformations (i.e. transforming the surface is only a matter of transforming the control net).
At its corners, the surface is tangent to the vectors formed by the corner control point and the nearest control points on the adjacent edges.
The patch can be evaluated and/or subdivided recursively by applying the DeCasteljau algorithm once in each parameter direction.
A rectangular patch (degree 2 in s and 3 in t) and its control polygon.
Rendering of tensor product surfaces is also analogous to the curve case, with the exception that everything has to be done twice, once in each parameter. We again have direct computation of the polynomial and direct computation with DeCasteljau's algorithm as options, but subdivision is attractive again. Just as a Bezier curve can be split into 2 separate but equivalent curves by a single application of the DeCasteljau algorithm, a rectangular patch surface can be split into 4 smaller but equivalent patches (a split in each parameter direction). The parameter which is chosen first does not affect the result. Rendering via subdivision is also fairly similar to the Bezier curve case. The obvious difference is that it is no longer a matter of simply connecting control points, and normal vectors are required for realistic shading.
There is more than one way to obtain a triangulation of the surface after having subdivided a patch into several subpatches. One way is to render each subpatch by creating a triangulation of its control mesh, and computing normals based on the vertices of the each resulting triangle. This method is fine when only a wireframe approximation of the surface is needed, or when normals only need to be provided
pertriangle rather than pervertex.
A second and arguably more "correct" way is to render each subpatch as two triangles (composed of the 4 corner control points of the subpatch). Note that this scheme does not make use of the interior control points patches, and hence would typically require an extra subdivision or two to obtain an equivalently dense triangle mesh. The reason it is often the favorable method is because exact normal vectors can be obtained at all vertices used in the triangulation (see property 4 above) which is ideal for renderers requiring pervertex normals.
The triangulation and normals after 2 subdivisions
Refinement of a rectangular patch through subdivision
Bezier triangles are not as simple as tensor product patches. Rather than using s and t as parameters as in the tensor patch case, points on the curve are parameterized with Barycentric coordinates. Given a parameter domain bounded by v_{1}, v_{2}, and v_{3}, a point x inside the domain can be described as a weighting of the v_{i} :
Given this parameterization, the basis functions required are the 3dimensional Bernstein polynomials, which are defined as

and this gives us the final equation for the curve:
The properties we are interested in are virtually identical to those listed above for tensor product surfaces, with the notable difference that the DeCasteljau algorithm has a slightly different form with the Barycentric parameterization.
The DeCasteljau algorithm in this case subdivides the control mesh into 3 submeshes as follows:
Unlike with Bezier curves or tensor product patches however, repeated applications of this subdivision scheme do not produce a triangulation that approaches the original surface since the edges of the patch are not refined. A more complex algorithm that splits the mesh into the configuration below is possible.
The naive algorithm to do so requires 12 calls to the DeCasteljau algorithm, but it can be done in 4 calls by using a clever sequence of splits.
The triangulation and normals of a cubic Bezier triangle after 2 subdivisions
Refinement of a triangular patch through subdivision
An often desirable but difficult to deal with task that we have not discussed involves joining curves or patches into more complex curves or patches. Typical reasons for combining several curves or patches include the desire to assemble more complex surfaces, and the desire to achieve more locality of control (i.e. a control point affects only the part of the curve closest to it). The fundamental problem that arises in attempting to to achieve either of these ideals is linking the curves or patches in a continuous fashion.
Constraints placed on neighboring curves or patches of the type we have discussed can be fairly easily derived for each of the the representations via their polar forms, but this is beyond our scope, and provides a good starting point for further reading. Representations that we have not mentioned that begin to deal with these problems by implicitly enforcing the continuity constraints include BSplines, rational curves, NUBS (NonUniform BSplines) and NURBS (NonUniform Rational BSplines).
Gallier, J., Curves and Surfaces in Geometric Modelling, Morgan Kaufmann Publishers, Sanfrancisco, CA, 2000.
Heidrich, W., Geometric Modelling, http://www.ugrad.cs.ubc.ca/~cs424/Slides/index.shtml
AkenineMöller, T, Haines, E, Bezier Triangles and NPatches, http://www.gamasutra.com/features/20020715/mollerhaines_01.htm
Kruger, G, Curved Surfaces Using Bezier Patches, http://www.gamasutra.com/features/19990611/bezier_01.htm
surface3d.inc is a library for rendering Bezier curves, tensor product patches, and Bezier triangles in PostScript. Methods are provided for evaluation, subdivision, and rendering. surface3d.inc makes use of ps3d.inc and it is assumed they are in the same directory.
There are 4 main structures used by surface3d.inc. They are detailed below:
Structure Name:  bez3 
Description:  The control polygon for a 3d Bezier curve 
Structure:  [ b_{1} ... b_{n} ]; where the degree of the curve is n 1 
Structure Name:  rpatch 
Description:  The control polygon for a tensor product surface 
Structure:  [[b_{1,1} ... b_{1,m}] ... [b_{n,1} ... b_{n,m}]]; where the patch is degree n 1 in s and m  1 in t 
Structure Name:  tpatch 
Description:  The control polygon for a Bezier triangle 
Structure:  [[b_{1,1}] ... [b_{n,1 }... b_{n,n}]]; where the patch is degree n 1 
Structure Name:  frag 
Description:  A triangular surface fragment. 
Structure:  [[v_{1 } n_{1}] [v_{2 }n_{2}] [v_{3 } n_{3}]]; where v_{i} are the vertices and n_{i} their normal vectors 
bez3 methods:
Method Name:  bez3eval 
Description:  Evaluates a Bezier curve at a given value of t 
Parameter(s):  bez3 t; the Bezier and the parameter value 
Return Value(s):  v; the point 
Method Name:  bez3subdiv 
Description:  Subdivides a Bezier curve at a given value of t. 
Parameter(s):  bez3 t; the Bezier and the parameter value 
Return Value(s):  bezleft bezright; the 2 resultant Beziers 
Method Name:  bez3subdivarr 
Description:  Recursively subdivides an array of Beziers at t = 0.5 
Parameter(s):  bez3arr n; the array of Beziers and the number of subdivisions to perform 
Return Value(s):  bez3arrnew; the new array of Beziers 
Method Name:  bez3buildpatharr 
Description:  Builds a path for an array of Beziers 
Parameter(s):  bez3arr; the array of Beziers 
Return Value(s):  none 
rpatch methods:
Method Name:  rpatcheval 
Description:  Evaluates a rectangular patch for given values of s and t. 
Parameter(s):  rpatch s t; the Bezier and the parameter values 
Return Value(s):  v; the point 
Method Name:  rpatchsubdiv 
Description:  Subdivides a rectangular patch into 4 patches 
Parameter(s):  rpatch; the patch 
Return Value(s):  rpatch1 rpatch2 rpatch3 rpatch4; the 4 resultant patches 
Method Name:  rpatchsubdivarr 
Description:  Recursively subdivides an array of rectangular patches (into 4 patches each) 
Parameter(s):  rpatcharr n; the array of patches and the number of subdivisions to perform 
Return Value(s):  rpatcharrnew; the new array of patches after n subdivisions 
Method Name:  rpatchbuildpatharr 
Description:  Built a path representing the control meshes of an array of patches 
Parameter(s):  rpatcharr; the array of patches 
Return Value(s):  none 
Method Name:  rpatchgetfragmentsarr 
Description:  Returns an array of fragments representing the array of patches 
Parameter(s):  rpatcharr; the array of patches 
Return Value(s):  fragarr; the array of fragments 
tpatch methods:
Method Name:  tpatchrotate 
Description:  Rotates a patch rst to str 
Parameter(s):  rst; the patch 
Return Value(s):  str; the rotated patch 
Method Name:  tpatchtranspose 
Description:  Takes the patch rst and computes its transpose, rts 
Parameter(s):  rst; the patch 
Return Value(s):  rts; the transposed patch 
Method Name:  tpatcheval 
Description:  Evaluates a patch for given Barycentric coordinates 
Parameter(s):  tpatch [alpha beta gamma]; the patch and Barycentric coordinates 
Return Value(s):  v; the point 
Method Name:  tpatchsubdiv3 
Description:  Subdivides a triangular patch into 3 patches for the given Barycentric coordinate 
Parameter(s):  rst [alpha beta gamma]; the patch and Barycentric coordinates 
Return Value(s):  ars ast atr; the 3 resultant patches 
Method Name:  tpatchsubdiv4 
Description:  Subdivides a patch into 4 patches for Barycentric coordinates [1/3 1/3 1/3] 
Parameter(s):  rst; the patch to be subdivided 
Return Value(s):  bas cra cab cbt; the 4 resultant patches 
Method Name:  tpatchsubdivarr 
Description:  Recursively subdivides an array of patches (into 4 patches each) 
Parameter(s):  tpatcharr n; the array of patches and the number of subdivisions to be performed 
Return Value(s):  tpatcharrnew; the new array of patches after n subdivisions 
Method Name:  tpatchgetfragmentsarr 
Description:  Returns an array of fragments representing the array of patches 
Parameter(s):  tpatcharr; the array of patches 
Return Value(s):  fragarr; the array of fragments 
frag methods:
Method Name:  drawfragmentsgouraud 
Description:  Draws an array of fragments with Gouraud shading 
Parameter(s):  fragarr lightsource shadefunc color; the array of fragments, a 4value array reprsenting the light source, a 4value array representing the shading curve, a 3value array representing an RGB color 
Return Value(s):  none 
Method Name:  buildfragmentswireframe 
Description:  Built a path representing the edges of an array of fragments 
Parameter(s):  fragarr; the array of fragments 
Return Value(s):  none 
Method Name:  buildfragmentnormals 
Description:  Built a path representing the normal vectors of an array of fragments 
Parameter(s):  fragarr len; the array of fragments, the length the normals are to be drawn 
Return Value(s):  none 