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.
[size="5"]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)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)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))Ok, now that we've gotten pass the simple math behind b?zier curves, lets talk about programming with them!!
[size="5"]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;And of course you would have 3 of them, so an array of control points would be appropriate.
C_POINT controlP[3];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);[size="5"]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];- 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.
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.
This helped me out a lot!