Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Using NURBS Surfaces in Real-Time Applications
View All     RSS
July 12, 2020
arrowPress Releases
July 12, 2020
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Using NURBS Surfaces in Real-Time Applications


November 17, 1999 Article Start Previous Page 3 of 5 Next
 

Parametric Surfaces

Now that we know how to describe parametric curves using a set of control points (which is what P0, P1, P2, and P3 were in the previous example), we can begin to understand parametric surfaces. The control points that we're going to use for parametric surfaces will be 3-dimensional points. Let's construct an example using the points shown in Figure 6.

Figure 6. A parametric surface.

Starting with16 points labeled P0,0 through P3,3, we want to "blend" these points together to form a surface. This process is actually quite easy. To generate a surface point that we'll call S, start with two knot vectors, U and V, to create two sets of b-spline basis functions, Bi,p(u) and Bj,q(v). Here p and q tell us the degrees of the surface (for example: linear, quadratic, cubic) in each direction. Now, we can define the function for the surface that corresponds to the function for a curve shown in Equation 3:

Simple enough? Let's look at it in greater depth just to be sure that the process is clear. To calculate a surface point, S(u,v), we loop over all the control points (with the two summation signs in the equation) and scale each control point, Pi,j, by the appropriate blending functions evaluated at u and v. Keep in mind that for a surface with many control points, some of the blending functions will be equal to zero over large regions of the surface. In particular, for a surface of degree n x m, at most (n+1)*(m+1) blending functions will be non-zero at a given (u,v) parameter value.

Figure 7. The generated surface.

We can generate different surfaces by using different knot vectors and changing the degrees of the blending functions (p and q). For example, if you generate a surface that is 3rd degree in both dimensions with knot vectors U = {0,0,0,0,1,1,1,1} and V = {0,0,0,0,1,1,1,1], the result would look like the image in Figure 7 if we use the control point mesh from Figure 6.

If you're wondering why we chose these particular knot vectors, the reason is simple. By having the repeated knot values at the beginning and end of the vectors, the resulting surface interpolates (in other words it passes through) the corner and edge control points. In contrast, the surface drawn does not pass through the middle control points, although it does approach them.

Before getting to the sample code, let's cover one more thing. The basis functions that we've described have an interesting property (actually it's by design). If you expand them for a given degree, n, and a fixed knot vector, you end up with a polynomial equation of the form: A0 + A1u + A2u^2 + A3u^3 + … + Anu^n where AI are coefficients that are determined exclusively by the knot vector and degree. Polynomials are good functions used for approximating (or, in some cases, representing exactly) other functions. However, there are some three dimensional surfaces that can't easily be approximated using polynomials as bases; specifically, the conics: spheres, cylinders, cones, and so on. To more easily and accurately represent these surfaces, you can use a ratio of polynomials. For two polynomial equations, F and G, a rational polynomial R would be defined by:


Using the b-spline functions from Equation 1, we can define a "rational" parametric surface by adding to the control points a fourth component (the first three are x, y, and z) that "weights" each control point. We'll call the fourth component w. In this manner, the equation for the surface becomes:



In case you were wondering, this is the equation for a rational b-spline surface. If the knot vector used for the basis functions is a non-uniform knot vector, then this is the equation for a non-uniform rational b-spline surface: a NURBS surface! Equation 4 is the equation for a generalized parametric surface. Other common parametric surfaces are just subsets of these surfaces. Specifically, a non-rational, uniform or non-uniform, b-spline surface is one where the weights, wi,j, are all equal to 1. This causes the division to accomplish nothing (and hence we don't have to evaluate the denominator at all). Also, you may have heard of a Bézier surface which is a non-rational b-spline surface with a uniform knot vector that is all zeros followed by all ones. So, for a 3rd degree Bézier surface, the knot vector would be U = {0,0,0,0,1,1,1,1}.

Rational parametric surfaces offer one more nicety that isn't available for non-rational surfaces. Any affine transformation (translation, rotation, scale, shear, and perspective projection) can be applied to the control points of a rational parametric surface and then the surface points generated in the transformed space will be correct. This means that if you have a small number of control points then you can transform the control points and generate a large number of surface points without having to transform all the generated surface points. Using non-rational surfaces, you would at least have to perform the projection transformation of the generated surface points.

Implementing a NURBS Surface Renderer

At this point, we can take Equation 4 and write some code to do a straight forward implementation of this. This would not be too difficult, but there are some optimizations that we can make first so that our implementation will perform better and after all, it's real-time performance that we want. First, let's discuss "tessellation". Tessellation is the process of taking the continuous, mathematical equation of a surface and approximating it with polygons (we'll use triangles). This process can be accomplished in a number of ways with the potential for vastly different visual results.

For simplicity, we're going to use what's called uniform tessellation. Uniform tessellation means we step equally between the minimum and maximum values for the parameters over which the surface is valid. For example, assume that the surface is valid for the ranges u E [0,3] and v E [2,3]. What we can do is divide these into some number of subdivisions and then just loop over these values calculating surface points that will be used as vertices of triangles. If we decide to use 20 subdivisions, we would calculate S(u,v) at u=0, u=0.15, u=0.30, …, u=3 for each v=2, v=2.05, v=2.10, v=2.15, …, v=3. So, we'd end up generating 441 points (21 times 21 because we include the end points) that we could then connect into triangles and render using a 3D API, such as OpenGL* or Direct3D*.

To speed up the calculation of S(u,v), we can calculate Bi,p(u) and Bj,q(v) at the subdivision points and store these in an array. This calculation can be performed once, so that it will not have to be performed in the inner loop of calculating surface points. Instead, a lookup of the pre-computed values and a multiplication is the only task that would be required. If at some point we change the number of subdivisions we want, we can just recalculate the stored arrays of basis functions evaluated at the new subdivisions.


Article Start Previous Page 3 of 5 Next

Related Jobs

Remedy Entertainment
Remedy Entertainment — Espoo, Finland
[07.10.20]

Programmer (Character Technology team)
Square Enix Co., Ltd.
Square Enix Co., Ltd. — Tokyo, Japan
[07.10.20]

Experienced Game Developer
Klang Games GmbH
Klang Games GmbH — Berlin, Germany
[07.09.20]

AI Engineer (f/m/d)
Remedy Entertainment
Remedy Entertainment — Helsinki, Finland
[07.08.20]

Technical Director





Loading Comments

loader image