Every beginner game programmer becomes familiar with the concept of needing to move from a value between point A to point B. It comes up all the time in game programming, especially as you sit there trying to figure out how to do something as simple as move a box across the screen. It is then that they learn about the linear interpolation (abbreviated to "lerp") as a way to smoothly fade between two values, finding any point between them with a simple [0,1] t value. The formula is simple:
Lerp(t) = (1 - t) * StartPoint + t * EndPoint
And before you know it, those beginner programmers are Lerping all over the place, using it to help overcome all sorts of challenged in game development from moving an object in 3D space to fading between two audio clips. In reality, this is actually just accomplishing one thing- it is just a straight line segment, reworked into a form that makes it easy to sample any point on that line. Anyone that's taken high school level math knows that there is more to life than just straight lines. What if we need a curve?
So let's consider how we might go about making this curve. An approach that I've seen many beginner programmers, including myself, to try to get around the problem by stringing several lines together as an approximation. This might be alright in some situations, but it fails in many. For one, it requires the placement of a lot of points and then storage of that data, which can be painful. Secondly, and perhaps more importantly, it will suffer from being jagged. Maybe at a certain distance we will have enough points that it will appear smooth enough, but when examined closely enough the lack of smoothness will always become apparent (unless the number of points approach infinity).
Enter: Bezier Curves
Moving to a more complex equation can allow us to overcome these difficulties. We know we can create curved functions with polynomial equations, but does this actually help us? We can write these as parametric equations much like the linear interpolation equation shown above, but we don't want to write a new equation each time we want to generate a curve. We want to generate different curves between points, not just the same curve between them each time. Before this was not an issue, as we only ever used a straight line. What we can do is store additional data that factors into our equation with additional data points beyond just the start and end points of the curve. This is where quadratic and cubic bezier curves come into play.
If you're new to bezier curves, you may find them a little intimidating due to the implication that there is some more complex math happening. I used to think they were outside my league of math just because Adobe has released entire applications based around drawing with bezier curves. Little did I know that I already used the 1st-degree, linear bezier equation all the time. Here it is:
LinearBezier(t) = (t - 1) * StartPoint + t * EndPoint
As you can probably tell, the linear bezier is actually just the linear interpolation equation. Higher degree bezier curves introduce control points into their equations and the math only gets a little bit worse, but the similarities are still very visible to our friend linear interpolation.
These 2nd and 3rd degree bezier curves can be defined as:
QuadraticBezier(t) = (1 – t)^2 * StartPoint + 2(1 – t) * t * ControlPoint + t^2 * EndPoint
CubicBezier(t) = (1 – t)^3 * StartPoint + 3(1 – t)^2 * t * ControlPoint1
+ 3(1 – t) * t^2 * ControlPoint2 + t^3 * EndPoint
Let's look at what happened. Our computations are a bit more expensive, but can now craft more intricate curves. These equations allow for the manipulation of continuously defined curves between the start point and end point by adjusting our control points. Take a look at a couple of shots showing examples of these:
- A Quadratic Bezier Curve
- A Cubic Bezier Curve
The interface for modifying these curves is quite simply the same as the start and end points of a line, being that a control point is just another point in the same vector space as our start and end points. Increasingly complex curves can be generated with higher degree bezier curves, but we don't actually want that because the computation becomes increasingly expensive and the increases in control points can become cumbersome. This is where turning to piecewise equations becomes a good solution.
B-Splines
Quadratic and cubic bezier curves do offer a lot more flexibility, but they also offer something else, the ability to be chained together without losing continuity, forming a piecewise function for your curve. So instead of using higher degree equations to create more intricate curves, we can create a series of cubic bezier curves and restrict them a bit to meet continuity requirements. Just as a refresher, a function meets different levels of continuity based depending on how many derivatives of the function are continuously defined. The previously mentioned chain of straight lines only has a continuity of C0, meaning that all points along the spline are defined, but because it lacks C1 continuity, the first derivative is not continuously defined. The more derivatives that are continuously defined, the smoother our curve will be, but it will also result in less and less control over the spline as a consequence.
Now that we have moved to a chain of cubic bezier curves, we can easily obtain C1 continuity by requiring that the line formed between an end point and the second control point, is the equal and opposite of the start control point on the curve that is being transitioned to. This looks like this:
- Piecewise Bezier with C1 Continuity
However, even with that restriction we can still have relatively sharp corners occur. If we require a smoother curve, we can convert our piecewise curve to a B-spline. This will allow us to achieve C2 continuity, meaning that the second derivative is continuously defined. Our bezier control points are now moved to being controlled by a new set of points known as deBoor points. A cubic bezier curve that always has C2 continuity will be defined by these deBoor points. Perhaps the biggest drawback is that the start and endpoints of a segment are no longer directly controllable either, but it is still relatively easy to work with from just the control points. Here are the equations for the generating the cubic bezier from the deBoor points, note that I name the variables based off of examining a particular segment in the spline:
CubicControlPoint1 = (2 * deBoorStartPoint + deBoorEndPoint) / 3
CubicControlPoint2 = (2 * deBoorEndPoint + deBoorStartPoint) / 3
CubicStartPoint = (deBoorPreviousStartPoint + 4 * deBoorStartPoint + deBoorEndPoint) / 6
CubicEndPoint = (deBoorStartPoint + 4 * deBoorEndPoint + deBoorNextEndPoint) / 6
We can then build our cubic bezier with these values. These relationships are a lot easier to visualize in a picture:
- A B-spline defined with deBoor Points
As you can probably see, these are a bit more mathematically involved than just a bezier curve. They are still relatively easy to manipulate through the deBoor points, and they have the added benefit of not requiring any additional data beyond that of a bezier curve and any bezier code that you currently have can be fit to work as a B-spline. This is exactly what I did when I most recently used B-splines to obtain C2 continuity on a project, I took advantage of the fact that the deBoor points could control the cubic curve entirely tool-side, while my in-game bezier code functioned exactly the same.
Conclusion
As you can see, math is fun and can lead to better better solutions to the engineering challenges in game development. Bezier curves naturally extend into many areas, and many useful uses have been cooked up for them. For a really great example of bezier curves at work, check out this article from GPU Gems 3 about rendering vector graphics on the GPU:http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html. Keep in mind that all this awesomeness comes with the cautionary wisdom that moving to higher degree curves is not always worth the increased computational complexity. As always, make sure you evaluate what the right tool is to get the job done.
