Unraveling Beziér Splines
by Justin Reynen

Introduction

There's no doubt that you've by now heard of these great new technologies that deal with curves, and curved surfaces. Quadratic Bézier patches, cubic Bézier curves, non-uniform rational B-Splines (NURBS), and have been trying to make sense of all this madness. Maybe even trying to add one of these technologies into a game or demo that your making.

This is article is a great start to unraveling that mystery.

In this article, I will explain to you the mathematics behind these Bézier curves, code that will draw a quadratic bézier spline (the simplest flavor of spline), and some techniques you can use to derive ways of making cubic, quartic, quintic, or whatever degree of bézier curve that you feel that you need.

Mathematics Behind Bézier Splines

Ok, the first thing that we're going to go over is Bernsteins Basis Functions. Ok, I'm going to throw out a formula here, but don't fret. Just look over it and you'll find that it's really quite simple.

1 = t + (1 - t)

T can be any number and this equation would still be true. But for our case, we're only interested in numbers between 0 and 1.

Ok, so now we know Bernsteins basis function. But remember how I said functions, plural! Well, the next step in getting our splines working, is that we have to pick what kind of splines we want in our little demo. For starters, we'll pick quadratic Bézier splines, because they're the easiest to get going.

Ok, so now we know that we want quadratic bézier splines. We have to derive some functions from our almighty basis function. So here we go.

For quadratic Bézier splines, we must square each side of Bernsteins basis function. For cubic Bézier splines, we would cube each side, and so on. So Bernsteins basis, with both sides squared will look like this:

1^2 = (t + (1 - t))^2

1 = t^2 + 2*t*(1-t) + (1-t)*(1-t)

You'll notice that a lot of this I didn't simplify, that's because it's easier to understand and code if you leave it this way.

Ok, now we have our 3 functions, which we derived from our basis. But where you ask. Well, right in front of you! Our functions are each of the terms to the right side of the equation. We'll call our functions Bx(t). It should be noted that the code is in bold.

#define	B1(t)		(t*t)
#define	B2(t)		(2*t*(1-t))
#define	B3(t)		((1-t)*(1-t))

You should notice here that in a quadratic bézier curve, their are 3 functions, in a cubic bézier spline, there are 4, and so on. In the zip file associated with this article, I've already derived the 4 functions for a cubic, and the 5 functions for a quartic, for you, so you don't have to do the math! Look in "Functions.txt".

Ok, now that we've gotten pass the simple math behind bézier curves, lets talk about programming with them!!

Programming with Bézier Splines

Ok, so we have our basis function's. Now it's time to put them to good use.

I think that now would be a really good time to mention that along with these functions, you should also have 3 control points, which we'll call Cx. You can save these control points in a structure that looks like this:

typedef struct sCPoint
{
	int x;
	int y;
}  C_POINT;

NOTE: We will be working with bézier splines in 2d only, but if you wanted 3d bézier splines you would simply add a z component to this structure.

And of course you would have 3 of them, so an array of control points would be appropriate.

C_POINT controlP[3];

Ok, now were going to get into the actual drawing of bézier splines on the screen. Right now, our curve is only imaginary, and only exists as math equations. What we have to do is go along our curve, using the equations that we got, and put dots along our curve path, to make it appear on the screen.

Which brings us to the last thing that I want to talk about; Detail Biases. Basically what a detail bias is, is a number that tells us how far we want to move along our curve each time we want to put a pixel along it's path. Detail biases are always decimals, and are most easily thought of as percentages. A detail bias of 0.5 would say "Ok, start at the beginning of our curve, put a point there, move 50% along our curve and put a point there, then move 50% more and put a point there (at the end of our curve).", this would put a point at the start of our curve, in the exact middle, and at the very end. We would need a counter to keep track of how much of the curve we've rendered, and we would increase this counter by 0.5 each time we put a point until it reaches 1, at which point we would stop. The smaller your detail bias, the more points you'll have on your curve, and the more solid it will look. Ok, without further adieu, the code to render a quadratic bézier spline. It should be noted that the macros Bx() where already defined up top, as were the controlP structures.

//Note: it is assumed that each controlP has already been filled out with
//an x and y coordinate.

double count = 0;  //used as our counter
double detailBias; //how many points should we put on our curve.

double x,y; //used as accumulators to make our code easier to read


detailBias = 1 / 50; //we'll put 51 points on out curve (0.02 detail bias)

do
{
x = controlP[0].x*B1(count) + controlP[1].x*B2(count) + controlP.x[2]*B2(count);
y = controlP[0].y*B1(count) + controlP[1].y*B2(count) + controlP.y[2]*B2(count);

	PutPixel(x,y,RGB(255,255,255));

	count += detailBias;

}while( count <= 1);

Notice how we get our x and y values. We multiply each control point by the coresponding basis function (B1 with control point 1, B2 with control point 2, etc.), and add them all together. We do this for both the x and y coordinates, and if we're working in the third dimension, the z coordinate as well.

Creating Surfaces Out Of These Curves

I'm just going to scratch the surface (pun intended) of how to make curved surfaces out of Bézier curves, because this subject is big enough to fit in an article by it's self, and is beyond the scope of this article. I will only discuss quadratic bézier patches, and I will supply no code for you to look at. I will tell you how to generate points from this surface, which you can then turn into triangles or quads quite easliy.

This image is the basic idea of how a patch, made out of quadratic bézier splines, would look like. It would have 9 control points, and you can think of the surfaces x-axis running along 7,8, and 9. The y would run along 7,4, and 1. To make things simple, we'll say that the detail bias will be 0.25, which we know will generate 5 points along a spline ((1/deatil bias) + 1), but since this is a surface, it will generate 5*5 points, which is 25 points in total. It's nice to think of these points in terms of x and y, so our data structure to hold these data points will be an array that looks like this:

C_POINT points[5][5];

We will also be deriving other control points as we go along, from points on other splines. I'll walk you now, step by step, the process of generating points from this surface. This is probably the most confusing part of this article, and you don't need to know this to get the basic Bézier spline working. It should be noted that when I say evaluate a spline, I mean take it's control points and create points with our equations and our detail bias, which is always 0.25. Ok here we go.

Use points 1,4, and 7 and evaluate them.
Derive 3 new control points by evaluating and taking the first point generated by spline 7,8,9, this will be our first control point, we'll call it f1. Do the same with 4,5,6, which will be f2, and 1,2,3 will be f3.
Evaluate spline f1, f2, and f3, and generate points from this spline.
Do the same as 2, except f1, f2, and f3 will now be the second point generated by 7-8-9, 4-5-6, and 1-2-3 respectfully.
Do steps three and four over and over (just make sure that instead of the second point, it's the third, then the fourth etc.) until you fill up our array.

In Conclusion

I hope that this article gave you a good understanding of what bézier splines are and how you can use them in your games and demos. I also hope that I took out some of the mystery of what these things can do for you. Before I go, I would like to leave you with a few pro's and con's about Bézier splines and curved surfaces.

Pro's:

Curved surfaces can be an excellent add-on to an engine that uses LOD (Level Of Detail) techniques to reduce the amount of poly's rendered. It's easy to bump these surfaces down to only 4 polygons (for quadratics), and you can do this quite easily (by changing the detail bias). It's also easier to make smooth surfaces, and more organic looking environments with curved surfaces. Also, if you plan on adding support for a moving camera, Bézier splines are essential to making the camera path, and animation paths, smooth.

Con's:

The one major con that plagues most engines with curved surfaces in them, is that they take a long time to tesselate (turn into polygons), this doesn't really make that big of a difference if you tesselate them at load time, but if you have to do it frame per frame, you'll probably notice a huge performance hit. That's about the only major beef that most engine developers have with curved surfaces.

Anyhow, I hope that you've learned something new from this article that you didn't know when you started reading it. I also hope to see more uses of Bézier splines/surfaces in game engines, and demos! If you have any questions, suggestions, or comments about this article, or if you just want to talk about coding, feel free to e-mail(mr_oreo@hotmail.com) me, or ICQ(4718529). Thank you.

-=Worlds Sexiest Cookie-=
-=|Mr.Oreo|=-
(Justin Reynen)

Note about the demos: Please read the "readme.txt" which can be found in the zip file associated with this article. Thank you.

Discuss this article in the forums

Date this article was posted to GameDev.net: 1/5/2000
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
NURBS, Splines and Patches