Math Magician – Lerp, Slerp, and Nlerp

Illustration of linear interpolation on a data...

Illustration of linear interpolation on a data set. The same data set is used for other interpolation methods in the interpolation article. (Photo credit: Wikipedia)

Man, I wish I had this blog going through school, because this place has become my online notebook. Game development is like riding a bike – but math, for me, can have a hard time stickin’. I’ve been working in databases so long that I have a lot of bit-shifting down, but my matrix and vector math is starting to lack. So, a creative way for me to remember all these algorithms is to try to explain them. Today, I’m going through Linear Interpolation, Sphereical Linear Interpolation, and Normalized Linear Interpolation.

The Code

I’m starting off with the code to show the similarities and differences with each. One thing similar right off the bat is the parameter list: each function takes the same 3 – A start, an end, and a percent. The start and end can be Vectors, Matrices, or Quaternions. For now, lets use Vectors. The percent is a scalar value between 0 and 1. If percent == 0, then the functions will return start, if percent == 1, the functions return end, and if percent == 0.5, it returns a nice average midpoint between the 2 vectors.

English: Illustration of linear interpolation.

English: Illustration of linear interpolation. (Photo credit: Wikipedia)

Lerp: The basic Linear Interpolation function. Lets break this down, right to left. First, we have end - start, which will pretty much return a vector the same distance as start and end, but represented as if it’s start vector was {0, 0, 0}. We multiply that vector by percent, which will give us a vector only percent as long (so if percent is 0.5, the vector now is only half as long as it was). We then add start back to it to return it to its normal position. Done.

Vector3 Lerp(Vector3 start, Vector3 end, float percent)
{
     return (start + percent*(end - start));
}

Lerp is useful for: Transitions from place to place over time, implementing a Health Bar, etc. Pretty much going from point A to point B.

Oblique vector rectifies to Slerp factor.

Oblique vector rectifies to Slerp factor. (Photo credit: Wikipedia)

Slerp: Slerp is a very powerful function. It’s become very popular in the game industry for it’s ease of use and significant result, however, people tend to ignore its drawbacks. Slerp travels the torque-minimal path, which means it travels along the straightest path the rounded surface of a sphere, which is a major plus and part of the reason it’s so powerful, as well as the fact that it maintains constant velocity. But Slerp is non-commutative, meaning the order of how the vectors/matrices/quaternions are passed in will affect the result. A call to Slerp(A, B, delta) will yield a different result as compared to Slerp(B, A, delta). Also, Slerp is computationally expensive because of the use of mathematical functions like Sin(), Cos() and Acos().

// Special Thanks to Johnathan, Shaun and Geof!
Vector3 Slerp(Vector3 start, Vector3 end, float percent)
{
     // Dot product - the cosine of the angle between 2 vectors.
     float dot = Vector3.Dot(start, end);     
     // Clamp it to be in the range of Acos()
     // This may be unnecessary, but floating point
     // precision can be a fickle mistress.
     Mathf.Clamp(dot, -1.0f, 1.0f);
     // Acos(dot) returns the angle between start and end,
     // And multiplying that by percent returns the angle between
     // start and the final result.
     float theta = Mathf.Acos(dot)*percent;
     Vector3 RelativeVec = end - start*dot;
     RelativeVec.Normalize();     // Orthonormal basis
     // The final result.
     return ((start*Mathf.Cos(theta)) + (RelativeVec*Mathf.Sin(theta)));
}

Slerp is useful for: Rotation, mostly.

Nlerp: Nlerp is our solution to Slerp’s computational cost. Nlerp also handles rotation and is much less computationally expensive, however it, too has it’s drawbacks. Both travel a torque-minimal path, but Nlerp is commutative where Slerp is not, and Nlerp aslo does not maintain a constant velocity, which, in some cases, may be a desired effect. Implementing Nlerp in place of some Slerp calls may produce the same effect and even save on some FPS. However, with every optimization, using this improperly may cause undesired effects. Nlerp should be used more, but it doesn’t mean cut out Slerp all together. Nlerp is very easy, too. Just normalize the result from Lerp()!

Vector3 Nlerp(Vector3 start, Vector3 end, float percent)
{
     return Lerp(start,end,percent).normalized();
}

Nlerp is useful for: Animation (in regards to rotation and such), optimized rotation.

The trouble with Lerp, Slerp and Nlerp to most people is that they don’t truly understand the functions. Most people will post “Hey, I have a problem with this” and someone will say use one form of Linear Interpolation, and just patch it in. It’ll work, but will they understand why it works? Could it be improved? I would recommend taking some time and reading articles on the different Linear Interpolations – there are more out there I didn’t mention, and all with different purposes.

That’s all for now. I’ll find more math to put up in the weeks to come. Till then, take care!

This post is dedicated to the staff at ZeeGee Games. I may have lost the battle, but I will not lose the war! I will be a Game Dev Jedi!

Also, if you’re part of the IGDA, Vote For Grant!

References:
The Inner Product – Understanding Slerp, Then Not Using It, by Jonathan Blow
GameDev.Net – Nlerp/Slerp with 2 vectors. [Solved], Post by ChaosPhoenix, Reply from jyk

About these ads

Tags: , , , , , ,

About KeithM

Lead Programmer at CSS, Inc. and Indie Game Dev from New Jersey. Loves playing games, and loves making them, too.

12 responses to “Math Magician – Lerp, Slerp, and Nlerp”

  1. Shaun says :

    Thanks for the slerp code!

    I noticed you have a clamp after the dot product. That should not be needed because dot should always return a number between -1 and 1

    One thing I learned when implementing this was that you don’t need acos() when you know for a fact that your two input vectors are right angles. For example, in the case where your vector was derived from a cross product. This is because the dot product of right angles == 0, and acos(0) == 1.5708… or PI * 0.5, which when compiled as a constant would be much faster. Also in the case of right angles, you could do without the relative vector since it would be the end vector.

    Thanks again!

  2. Geof says :

    Great post, very informative, don’t forget to bin off that clamp!!

    • KeithM says :

      Consider it done! Sorry for being so late to do so!

      • Jonathan Blow says :

        Whoa, don’t get so antsy! The above posters are wrong. It is quite frequent for vector dot product routines to return values outside of [-1, 1] due to floating point error (or just that one of the input vectors got to be a little bit non-unit some other way) and then acos will throw an exception. You want to always *always* clamp before an inverse trig routine…

      • Jonathan Blow says :

        I mean, let me put it this way: due to limited numerical precision, it is actually impossible for your Vector3 to be exactly 1 unit long except in special cases. So… you do think it’s going to be less than 1 unit long or greater than 1 unit long? Or either, quasi-randomly?

      • KeithM says :

        You do bring up a valid point, and I have learned a few lessons from floating point precision. I’ll put it back in for, if nothing else, a paranoid check.

        Thank you all for your input on this!

      • KeithM says :

        Also, just as an aside, I just realized who you are. I’m not going to completely nerd-out like I am doing in real life right now, but thank you for coming here and commenting. I feel like my blog has now some credibility, and it’s thanks to you and all the other successful Indie devs out there that make me feel like I have a chance in the daunting world of Video Games.

        Thank you, sir.

  3. Alban says :

    I do not really understand the argument of non-commutativity of Slerp. If I consider the Lerp interpolation, it leads to similar behaviour: Lerp(Q1,Q2,percent) is also different from Lerp(Q2,Q1,percent).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 400 other followers

%d bloggers like this: