Thursday, December 5, 2013

Computer Graphics - a Quick Look at de Casteljau and Hermite Curves

A while ago I delved into the world of curves. By default CamanJS provided just Bézier variant (four control points). This was just unacceptable. I wanted to achieve two things. Provide means to generate curves with an arbitrary amount of control points. And better yet, provide access to Hermite curve variant. Hermites allow you to define curves in which the curve goes through certain control points.

If that went over your head, it's okay. You will see these types of curves in computer graphics a lot. In short they are parametric. They allow you to define a complex curvature just by using a couple of control points. This makes them a very powerful design tool. Incidentally some of the fundamental math was developed for designing cars. That probably explains why the 60s era Citroëns were so beautiful.

de Casteljau's Curve

Bézier curve is defined as a polynomial. The thing is as you want more control points per curve the equations just keep getting more difficult. This isn't particularly nice. On the other hand it is fast to solve Béziers in simple cases.

de Casteljau's solution is quite different. It is something you might discover intuitively just by drawing on a paper. Draw two lines so you end up with something like a V. Pick a point from both segments that is in the same place relatively speaking. Draw a line between those points. Repeat this process long enough. In the end the intersections of the lines added should give you something resembling a curve.

It is possible to generalize this process to arbitrary amount of control points. The idea is that as you add segments to the control curve, each iteration of this process gives you another curve with less control points. This way the problem can be reduced to the basic case I just described. First you just solve a curve you can solve and then solve that.

I have prepared a tiny demo for you that illustrates the idea. It might be easier to understand what's going on after you step through the code.

JS Bin

Hermite Curve

The problem with both Bézier and de Casteljau's curves is that it can be a little bit difficult to control the curvature. There are times when you want the curve to go through certain points. This is where hermite curves or cubic hermite splines come in. If you have used applications like Photoshop or GIMP, you have likely used these curves when modifying color levels or something similar.

As I don't understand the math fully I won't even bother trying to explain it. Suffice to say that it has something to do with tangents. Somehow the larger curve is split up into smaller segments with three control points per each. The curvature is then calculated for each segment taking this information into count.

I have prepared a demo you can study below.

JS Bin


I hope this little post gave you some idea what's going on behind the scenes when you are dealing with curves. In case you are interested in the topic and want to understand the math better you should check out Pomax's guide on Béziers. There are some nice interactive demos to run.