This document is organized as follows:
Complex object shapes in the real world necessitate the use of curved surfaces in 3D rendered environments. This need introduces the broad area of surface modeling in computer graphics, including common representations of 3D surfaces in the form of Hermite and Bezier curves. With these curve representations, you can scale the visual quality of geometry, also known as the Level of Detail (LOD). Smooth curves and surfaces are the building blocks for solving this tough problem of LOD in the realm of computer graphics.
The goal of this project is to teach others about Bezier curves and how to construct a practical tool to manipulate Bezier curves. Basically, the application will have a 4x4 grid of points, representing the Bezier control points, that can be modified to alter the shape of the surface. The user can rotate around the surface in free-form and can switch back and forth between rendered and point mode to see the effects of their control points. Branching out from our tutorial, we will discuss how this tool can be used in conjunction with another application to take individual curved surface patches and form a complete mesh. We will be covering briefly how Bezier curves work, the mathematics behind them, and then provide an in-depth look at how we created our tool.
A few years back, consumer-level 3D acceleration was unheard of. Now, even the previously non-accelerated graphics machines on the low end have slowly been replaced with computers that can run 3D graphics using an accelerated chipset. However, graphics adapter manufacturers continue to create faster and faster chipsets, making products from 6 months ago seem slow. In order to support high-end consumers, and at the same time not abandon the low-end consumers, a new trend has been born in the industry: scalable geometry. Scalable geometry is any kind of geometry that can be adapted to run with decreased visual quality on slower machines or with increased visual quality on faster machines.
Curved surfaces are one of the most popular ways of implementing scalable geometry. Games applying curved surfaces look fantastic. UNREAL's characters looked smooth whether they are a hundred yards away, or coming down on top of you. QUAKE 3: ARENA screen shots show organic levels with stunning smooth, curved walls and tubes. There are a number of benefits to using curved surfaces. Implementations can be very fast, and the space required to store the curved surfaces is generally much smaller than the space required to store either a number of LOD models or a very high detail model.
The industry demands tools that can make creation and manipulation of curves more intuitive. A Bezier curve is a good starting point, because it can be represented and understood with a fair degree of ease. To be more specific, we choose cubic Bezier curves and bicubic Bezier patches for the reason of simplicity.
A cubic Bezier curve is simply described by four ordered control points, p0, p1, p2, and p3. It is easy enough to say that the curve should "bend towards" the points. It has three general properties:
1. The curve interpolates the endpoints: we want the curve to start at p0 and end at p3.
2. The control points have local control: we'd like the curve near
a control point to move when we move the control point, but have the rest of
the curve not move as much.
3. The curve stays within the convex hull of the control points. It can be culled
against quickly for visibility culling or hit testing.
A set of functions, called the Bernstein basis functions, satisfy the three general properties of cubic Bezier curves.
If we were considering general Bezier curves, we'd have to calculate n choose i. Since we are only considering cubic curves, though, n = 3, and i is in the range [0,3]. Then, we further note the n choose i is the ith element of the nth row of Pascal's traingle, {1,3,3,1}. This value is hardcoded rather than computed in the demo program.
Since a Bezier curve was a function of one variable, f(u), it's logical that a surface would be a function of two variables, f(u,v). Following this logic, since a Bezier curve had a one-dimentional array of control points, it makes sense that a patch would have a two-dimensional array of control points. The phrase "bicubic" means that the surface is a cubic function in two variables - it is cubic along u and also along v. Since a cubic Bezier curve has a 1x4 array of control points, bicubic Beizer patch has a 4x4 array of control points.
To extend the original Bernstein basis function into two dimension, we evaluate the influence of all 16 control points:
The extension from Bezier curves to patches still satisfies the three properties:
1. The patch interpolates p00, p03, p30, and p33 as endpoints.
2. Control points have local control: moving a point over the center
of the patch will most strongly affect the surface near that point.
3. The patch remains within the convex hull of its control points.
Rendering a Bezier patch is more complicated than rendering a Bezier curve, even when doing it in the simplest possible way. With a Bezier curve, we could just evaluate strips of points and render a line of strips. With a patch, we need to evaluate strips of points and render triangle strips. Also, with a patch we have to worry about lighting. Even with the simplest lighting method, we need to light each vertex, which means we need each of the vertex's normal. So for every (u,v) pair, we need to solve the point on the surface, and then solve for its normal.
To find the normal of a point on the surface, we can take the derivative of the surface with respect to either u or v, which yields the tangent vectors to the surface in the direction of either u or v. If we find both of these tangents, we know that they both lie in the plane tangent to the surface. Their cross product yields the surface normal after we normalize it. This renders the Bezier patches without optimization.
To find df(u,v)/du.
The same holds for df(u,v)/dv.
So, now that we have a basic understanding of Bezier curves and patches, let us take a closer look at how to construct a practical tool to create Bezier surfaces. By constructing a tool, we can use what we have just learned and see how to deform surfaces visually by modifying the surfaces' control points. First, we must start with a codebase that can render curved surfaces and then we can add the tool's functions.
Since our tutorial is based on a two-part article published in Game Developer Magazine, we are fortunate to have code samples from which to construct our tool. The author of the article, Brian Sharp, provides many different curved surface demos. In selecting from the six demos, we decide upon Bezsurf because it contains:
Next, we must decide on the design of the tool.
In the design phase we decide that we would like for our tool to be able to:
By default, Bezsurf generates a random surface, but we would also like to generate a flat surface. After sifting through bezsurf.cpp we find a function called genPatch() which generates the control points for the surface. The lines marked in yellow are of interest to us:
void genPatch()
{
// Empty the patch so we can start over.
bezierPatch.clearControlPoints();
// Seed the random number generator to change the points each time we run.
srand( timeGetTime() );
std::vector< std::vector< CurvePoint > > pts;
for ( int x = 0; x < numPoints; x++ )
{
pts.push_back( std::vector< CurvePoint >() );
}
// Get random values for each of the x, y, and z values of each control point.
for ( int i = 0; i < numPoints; i++ )
{
for ( int j = 0; j < numPoints; j++ )
{
// We want a reasonable distribution from around -7 to 7.
float x = ( (float)( i - (float)numPoints * 0.5 ) / (float)numPoints ) * 14;
float y = ( (float)( j - (float)numPoints * 0.5 ) / (float)numPoints ) * 14;
float z = 0;
// Move them around a little (but not enough that they can intrude into other points' space).
// x += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f / (float)numPoints;
// y += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f / (float)numPoints;
z += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f;
pts[ i ].push_back( CurvePoint( x, y, z ) );
}
}
bezierPatch.setControlPoints( pts );
UniformPatchTessellator lightmapper;
long startTime = timeGetTime();
bezierPatch.generateLightmap( &lightmapper, 4 );
long endTime = timeGetTime();
std::cout << "Lightmapping took " << (endTime - startTime) << std::endl;
}
We can see that the control points are cleared at the beginning of the function and then set later on within the nested for loops. We do not want to modify the x and y positioning because the existing code is already spacing out the points equally within the xy plane. Although z is set to zero initially, which is what we want, later it is set to a random value. This is where we need to modify the code.
To allow for the creation of a flat surface we need two pieces: a flag for controlling the random z point calculations and a hook into the keyboard handler to set this flag. First, we add the keyboard control code to the keyboard handler, appKey():
//ADDITION: Flat Control Grid case 'z': case 'Z': zeroFlag = true; genPatch(); break;
The zeroFlag variable is a global variable in this case. Next, we modify genPatch() to utilize the flag:
void genPatch()
{
// Empty the patch so we can start over.
bezierPatch.clearControlPoints();
// Seed the random number generator to change the points each time we run.
srand( timeGetTime() );
std::vector< std::vector< CurvePoint > > pts;
for ( int x = 0; x < numPoints; x++ )
{
pts.push_back( std::vector< CurvePoint >() );
}
// Get random values for each of the x, y, and z values of each control point.
for ( int i = 0; i < numPoints; i++ )
{
for ( int j = 0; j < numPoints; j++ )
{
// We want a reasonable distribution from around -7 to 7.
float x = ( (float)( i - (float)numPoints * 0.5 ) / (float)numPoints ) * 14;
float y = ( (float)( j - (float)numPoints * 0.5 ) / (float)numPoints ) * 14;
float z = 0;
// Move them around a little (but not enough that they can intrude into other points' space).
// x += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f / (float)numPoints;
// y += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f / (float)numPoints;
if(!zeroFlag) //ADDITION: Flat control grid condition
z += ( ( (float) rand() / (float) RAND_MAX ) - 0.5f ) * 14.0f;
pts[ i ].push_back( CurvePoint( x, y, z ) );
}
}
zeroFlag = false; //ADDITION: reset flag to default incase it was used
bezierPatch.setControlPoints( pts );
UniformPatchTessellator lightmapper;
long startTime = timeGetTime();
bezierPatch.generateLightmap( &lightmapper, 4 );
long endTime = timeGetTime();
std::cout << "Lightmapping took " << (endTime - startTime) << std::endl;
}
Next, let's add editing capabilities.
Bezsurf can view Bezier surfaces with no problem, but there is no way to edit the control points. So, this is where we make the bulk of our code modifications. Creating an Edit mode toggle in appKey() is as simple as was creating the zeroFlag, but the new flag editMode must do something. For starters, let us have the edit mode switch to wireframe viewing, so that we can see the full surface unoccluded:
//ADDITION: Edit Mode case 'e': case 'E': editMode = !editMode; bezierPatch.setUseLightmap( !bezierPatch.getUseLightmap() ); if (editMode) { lastMode = tessellator->getMode(); tessellator->setMode( GL_LINE ); } else tessellator->setMode(lastMode); registerEditControls(); break;So, now we have a wireframe default view within the Edit mode, but we need a way to cycle through the control points and see which point is selected. We create two functions to accomplish this: an arrow key handler, specialKey(), and a relative control point selector, changeControl(). Basically, the arrow keys can select a control point within the 4x4 grid. For example, if you are at control point (1,1), then hitting the down arrow key would move you to (2,1).
//ADDITION: Edit Mode, Control Point keyboard navigation
void changeControl( int du, int dv )
{
int cont_new_u, cont_new_v;
cont_new_u = cur_cont_u + du;
cont_new_v = cur_cont_v + dv;
if( cont_new_u < numPoints && cont_new_u >= 0 )
cur_cont_u = cont_new_u;
if( cont_new_v < numPoints && cont_new_v >= 0 )
cur_cont_v = cont_new_v;
}
//ADDITION: Arrow keys control active control point in Edit Mode
void specialKey( int keyHit, int x, int y)
{
int u = 0, v = 0;
if( !editMode ) return;
switch ( keyHit )
{
case GLUT_KEY_UP: { v = -1; break; }
case GLUT_KEY_LEFT: { u = 1; break; }
case GLUT_KEY_DOWN: { v = 1; break; }
case GLUT_KEY_RIGHT: { u = -1; break; }
}
changeControl( u , v );
}
Now, we must be able to see which control point is selected. We create a function, drawControlBox() to draw a highlighted square around the selected control point:
//ADDITION: Edit Mode control box drawer
void drawControlBox()
{
float d = 0.25;
const float *p = (bezierPatch.getControlPoint(cur_cont_u,cur_cont_v))->getXYZArray();
const float *c1 = (bezierPatch.getControlPoint(0,0))->getXYZArray();
const float *c2 = (bezierPatch.getControlPoint(0,numPoints-1))->getXYZArray();
const float *c3 = (bezierPatch.getControlPoint(numPoints-1,0))->getXYZArray();
const float *c4 = (bezierPatch.getControlPoint(numPoints-1,numPoints-1))->getXYZArray();
::glDisable( GL_LIGHTING );
::glDisable(GL_TEXTURE_2D);
::glColor3f( .8, 0, .8 );
::glBegin( GL_QUAD_STRIP );
::glVertex3f( p[0]-d , p[1]+d , p[2]+d );
::glVertex3f( p[0]-d , p[1]-d , p[2]+d );
::glVertex3f( p[0]+d , p[1]+d , p[2]+d );
::glVertex3f( p[0]+d , p[1]-d , p[2]+d );
::glVertex3f( p[0]+d , p[1]+d , p[2]-d );
::glVertex3f( p[0]+d , p[1]-d , p[2]-d );
::glVertex3f( p[0]-d , p[1]+d , p[2]-d );
::glVertex3f( p[0]-d , p[1]-d , p[2]-d );
::glVertex3f( p[0]-d , p[1]+d , p[2]+d );
::glVertex3f( p[0]-d , p[1]-d , p[2]+d );
::glEnd();
if( editControlGrid==2 || (editControlGrid !=0 && tessellator->getMode()!=GL_FILL))
drawControlGrid();
::glEnable( GL_LIGHTING );
::glEnable(GL_TEXTURE_2D);
}
Now, we have a window that looks like this:
This is great, but I can't see any of the other control points! We need another toggle in appKey() for turning on a control point grid:
//ADDITION: Control Point Grid case 'g': case 'G': editControlGrid = (editControlGrid+1)%3; break;
and a function that will draw the grid:
//ADDITION: Draws a grid over the control points
void drawControlGrid()
{
::glColor3f( .80,.80,.80 );
for( int y = 0 ; y < numPoints-1 ; y++ )
{
::glBegin( GL_QUAD_STRIP );
for( int x = 0 ; x < numPoints ; x++ )
{
const float *p1 = (bezierPatch.getControlPoint(x,y))->getXYZArray();
const float *p2 = (bezierPatch.getControlPoint(x,y+1))->getXYZArray();
::glVertex3f( p1[0] , p1[1] , p1[2] );
::glVertex3f( p2[0] , p2[1] , p2[2] );
}
::glEnd();
}
::glColor3f( 0,0,.9 );
::glPointSize(4);
::glBegin( GL_POINTS );
for( y = 0 ; y < numPoints ; y++ )
{
for( int x = 0 ; x < numPoints ; x++ )
{
const float *p1 = (bezierPatch.getControlPoint(x,y))->getXYZArray();
::glVertex3f( p1[0] , p1[1] , p1[2] );
}
}
::glEnd();
::glPointSize(2);
}
Now, we have a slick editing interface:
Well, we have come far in developing our tool, but we have yet to modify a single control point! Here, we encounter a problem: How can we use the mouse for moving control points if we are already using it for moving around the surface? Bezsurf uses a class called CameraMover to handle the mouse input and to control the viewport. So, logically let us add our code there. Unfortunately, we cannot because CameraMover was designed to be agnostic to the application. In other words, CameraMover is told each draw cycle to update itself or, more clearly, to update the viewport based on mouse input between the last cycle and the current cycle. Therefore, CameraMover cannot know anything about an Edit mode or control points. In this case, we must add a new class called EditMover and base it off of the CameraMover class. For brevity, we will only include the EditMover::update() function from EditMover.cpp because it is where the control point is actually moved:
void EditMover::update( CurvePoint *c )
{
long curTime = timeGetTime();
if (lastFrameTime == 0)
{
lastFrameTime = curTime;
return;
}
float dt = (curTime - lastFrameTime) / 1000.0f;
// Go forward if the left button is down, backwards if any other mouse button is down.
float direction = mouseButton == GLUT_LEFT_BUTTON ? 1.0f : -1.0f;
bool button1 = mouseDown && mouseButton == GLUT_LEFT_BUTTON;
bool button2 = mouseDown && mouseButton != GLUT_LEFT_BUTTON;
//If holding shift or ctrl, move the control pointS
if( (shift || control) && button1 )
{
if(shift) (*c).setZ((*c).getZ()+0.1*accumY);
else
{
(*c).setX((*c).getX()+0.1*accumX);
(*c).setY((*c).getY()+0.1*-accumY);
}
}
else
{
GlobalCamera::Instance()->getPosition().pitch(0.004 * accumY);
GlobalCamera::Instance()->getPosition().rotateByAngles(0.004 * accumX, 0.0f);
if (mouseDown)
{
GlobalCamera::Instance()->getPosition().translateBy(GlobalCamera::Instance()->getPosition().getOrientation(), direction * dt * 40.0f);
}
}
// Reset these since we've taken them into account now.
accumX = 0;
accumY = 0;
lastFrameTime = curTime;
}
From the highlighted section above we can see that we constrain the control point to movement in the Z direction if the SHIFT key is held down and constrain movement to the XY plane if the CTRL key is held down:
We now have a working tool! Let's move on to some fun stuff.
One of the cool features that was already present in Bezsurf was surface texturing, but it only allowed for one texture. Why limit it texturing to one when we can limit it to five? Okay, so we aren't going to create anything robust, but at least we can throw together a hack to allow for four more textures. Searching through the original bezsurf.cpp we find that the one texture is manually set in appInit():
// Generate a texture for it.
int textureName = loadTexture("texture00.raw");
bezierPatch.setTexture(textureName);
To change this to support five textures, we create a new data structure:
const int numTextures = 5;
char *textures[numTextures] = {
"tex0.raw",
"tex1.raw",
"tex2.raw",
"tex3.raw",
"tex4.raw"};
a new handler in appKey() to cycle through the textures:
//ADDITION: Texture Cycling case 'y': case 'Y': curTexture = (curTexture+1)%numTextures; useTexture(curTexture); break;
and a function for setting the surface's active texture:
//ADDITION: Texture changing
void useTexture( int t )
{
int textureName = loadTexture(textures[t]);
bezierPatch.setTexture(textureName);
}
Anyone with a graphics application that can save raw files can custom texture the surfaces he or she creates. We now have a fully-featured Bezier surface creator tool!
Where do you go from here? Well, a logical step would be adding storing and loading capability to the tool. With your curved surfaces saved to disk, you could create another tool that loads multiple curved surfaces from disk and allows a user to combine the surfaces into a 3D mesh. After creating a 3D mesh, you could export the mesh for final use in a game or other 3D application that supports Bezier curves.
prj4fresh.zip - This is basically the Bezsurf code we started with, but configured to compile under Visual C++ v6.0. It includes all the files you will need including glut.h, glut32.lib, and glut32.dll, which you normally would have to download. Only download this if you want to start from scratch in building your Bezier surface tool.
prj4source.zip - This is the source code for our complete Bezier surface creator tool. All the code snippets presented above have come from this source. If you download this file, then it isn't necessary to download prj4fresh.zip because the code additions have been designate with the comment "//ADDITION: ...".
prj4exec.zip - This is a compiled version of the program that should run on any version of Windows with DirectX support. Having an accelerated graphics card is a plus, but the tool will still run in software emulation mode if you do not have one.
README.txt - The README file that accompanies the executable, but is listed here for completeness.
Sharp, Brian. "Implementing Curved Surface Geometry." Game Developer Magazine June 1999: 42-53.
Sharp, Brian. "Optimizing Curved Surface Geometry." Game Developer Magazine July 1999: 40-48.