Gameplay Programming Tips: Hermite Curves1
Matt posted in Gameplay Programming on September 12th, 2008
Creating motion is an important thing in games. Very few games consist of only completely static objects, so odds are as a gameplay programmer, you are going to spend a lot of time defining the motion of objects. One interesting problem you will probably face as a gameplay programmer is when you want a nice smooth curve and you only know a start position, start direction, end position and end direction. Although you may think this may not be enough information to formulate a path (and strictly speaking it isn’t, but I’ll get to that later), there is a simple, elegant and efficient way to compute that using Hermite Curves. In order to follow this math, you need knowledge of basic linear algebra (matrix multiplication, transposing and inversion) and basic calculus (differentiating).
Firstly, the basic equation for a cubic is In order to simplify the math, we can write the equation as where and .
As well, using simple calculus, you can get the derivative of x with respect to time.
Now, let’s start defining more equations based on what we know.
These equations can be written as where and .
Premultiplying by the inverse of , we get . Since is known, plugging that into the previous equation we get . is also known as the Hermite Basis Matrix, and is easy to calculate.
So now, you can find out your cubic equation with a matrix multiply. However, In order to make this work better with a math library that doesn’t support column vectors, note that . If that statement is a little confusing, let’s do the math:
If you noticed the only difference between those two quantities is the first has brackets around it, you’d be right. The fact that one solution is a 1×1 matrix and the other is a regular scalar value doesn’t make any difference for our purposes. So, using some more basic linear algebra: . This is a better format anyway because now we are multiplying a row vector by a 4×4 matrix, which should be something easily computable with standard math libraries. So finally, let’s say .
You can find the cubic equation coefficients easily because
This is an efficient way to evaluate a cubic when you have a vector processor that supports a dot instruction. You can store as a vector intrinsic, and when you want to evaluate it, you compute and dot it with . As well, (your cubic equation coefficients) can be found with just by multiplying the known quantities () with a constant matrix, so that is easy to do as well. Isn’t that elegant?
Although we solved the equations for , but the same math applies to and . Basically each component will have an independent cubic equation that is solved by multiplying by this equation.
Now back to what I said earlier. Just the direction is not enough information. The values in are the tangent, which has a direction and magnitude. The tangent is the derivative of the curve at the point, which is the rate of change. For a position function, the rate of change is the velocity. However, we have a cubic function with a parametric
Although we solved the equations for parameter, which isn’t the same as time in seconds or whatever your unit is. You can convert it to whatever units you’d like by using dimensional analysis. Yes, that High School chemistry knowledge comes in handy in game development after all.
So, if you know what speed you want the particle to start out at and end at, you can solve for the exact cubic. However, your cubic solution may not look how you expect because there is one solution with the limited information and there’s no guarantee that it will be visually appealing. Usually I tweak the start and exit speeds to find something that looks good with values in the ranges that I’d expect to encounter.
Another thing to note is that your object moving along the curve will not move at a constant speed. The curve’s tangent magnitude varies significantly. If you want to move at a constant speed along the path that this generates, you would need to solve the equation for the arc length evaluated from to . Unfortunately, finding the general equation for arc length for a cubic is extremely complicated, so this probably isn’t a good approach for real time applications. You can either iteratively estimate it or estimate it by dividing your desired world space speed by the magnitude of the tangent vector. However, in many situations, the cubic path works just fine.
There are other curve methods that you can use to interpolate between two points that may suite your needs better for whatever particular problem you are trying to solve. The secret to gameplay programming is try as many different things as you have time for and see which one works the best. For a reference on Hermite curves and some other curve methods, check out this webpage.