October 4, 2016

The most boring article about curves you'll ever read

I'm using Paint.net as my main painting program. It may not be as good as Photoshop, but it's free and far better than what is delivered with Windows. If you want to make a curve in Paint.net you have two options: Cubic Spline or B├ęzier Curve. Both curve types are almost the same, but just almost. But have you ever wondered how the computer is creating those curves? The answer is interpolation.

This summer I read a book called Essential Mathematics for Games and Interactive Applications and it included an entire chapter on interpolation. If you want to connect two points with a curve you need to do what the game Mafia did: learn interpolation:


If you want to build curvy roads you have to do what the game Cities: Skylines did: learn interpolation:


Interpolation is actually a big topic within math. You can define interpolation as "a method of constructing new data points within the range of a discrete set of known data points." The easiest form of interpolation is linear interpolation, where you follow a straight line from A to B (the known data points).

But curves are more interesting than straight lines. I recently had the need to connect two points with a curve, so I was forced to learn everything about interpolation. If you want to connect two points with a curve you have two main options:
  1. Generate a Catmull-Rom spline. You should use this alternative if you want to control the shape of the curve by moving the points that make up the curve. I suspect that this is the method Paint.net is using to generate a cubic spline because a Catmull-Rom spline is a cubic spline. 
  2. Generate a Bezier Curve. You should use this alternative if you want to control the shape of the curve even though the points that make up the curve are fixed. If you use this curve you get two handles that you can move around to determine the shape. This curve type was developed to make aerodynamic car bodies.   

Both of these curve types are actually quite easy to generate. To generate the Bezier curve you just have to make a few linear interpolations between the end points and control points. The problem is to move along the curves. What's happening when you generate these curves is that the derivative is not constant, with the result that the step size is not constant. You move along the curves with a parameter called t. This t is between 0 and 1, where t is 0 at the start of the curve and t is 1 at the end. But because the derivative is not always constant, 0.5 is not necessarily at the middle of the curve. This is the result if you have a Bezier curve (you can see that the lines at the beginning of the curve are longer than the lines as the end of the curve):

 
To solve this problem you have to go to your bookshelf, find the book you used when you studied numerical methods, dust it off, and repeat both Simpson's rule and Newton's method. It was about 12 years since I used that book, so it was really dusty. Anyway, if you use those methods, you will be able to generate a Bezier curve with constant steps (to generate a Catmull-Rom spline with constant steps you follow the same procedure):


If all this sounds complicated, I've written a tutorial on how to do it: Everything about interpolation in Unity with C# code.

No comments:

Post a Comment