Math Magician – Lerp, Slerp, and Nlerp

原文出处

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, Spherical 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.

---

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. (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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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 also 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! (This link is really old by now, though…)

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