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.

** 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 *as long (so if percent is 0.5, the vector now is only half as long as it was). We then add*

`percent`

`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.

** 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

###### Related Articles

- Trenki’s Programming Page – Vector Math (trenki.net)
- Linear algebra for game developers ~ part 3 (wolfire.com)
- A blog by Pavel Penev – On my quest for mastery (pavelpenev.posterous.com)

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!

Excellent catch! Thanks for the tip – I’ll work that into the code I posted. Thanks a lot!

I will disagree on he clamp not being needed. I work in an environment with a lot of math and vector nodes available. And I have had to do my own implementation of the Angle node, precisely to add a clamp because of floating point errors. Don’t ask me why… yes, the vectors are normalized, but it would just once in a full moon through a FP error, go over 1 or -1 and make arccos trip a -1.#IND.

From my experience I say keep it, but I don’t know if here the same issue will take place.

Cheers

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

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

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…

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?

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!

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.

I will disagree on he clamp not being needed. I work in an environment with a lot of math and vector nodes available. And I have had to do my own implementation of the Angle node, precisely to add a clamp because of floating point errors. Don’t ask me why… yes, the vectors are normalized, but it would just once in a full moon through a FP error, go over 1 or -1 and make arccos trip a -1.#IND.

From my experience I say keep it, but I don’t know if here the same issue will take place.

Cheers

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).

I know this post is a few years old, but, for the Slerp function, the dot product of a vector does not always return a value between -1 and 1. For instance, the dot product of these two vectors and is -353. To get that value between -1 and 1 (the value to use with the arccosine), you would need to divide it by the magnitudes of both vectors.

It seems it didn’t like the brackets around the two vectors: (1, 50, -25) and (12, -7.3, 0)…

If the input vectors are normalized (your vectors are not), the dot product will be -1 to 1. If you need a vector of the same length as the input, you can grab the lengths before you normalize and then multiply that to the slerped vector, probably interpolating the lengths as well if both inputs are different lengths.

Except nowhere in the function does it ensure that the vectors are normalized, so blindly inputting a vector (like the ones that I posted) would produce a bad result.

I personally like that the code is more modular this way. I am generally already working with normalized vectors, so having an extra normalization step in there would be a waste of cycles in many of my cases. If it was always wanted, then you might make a function for it, but it doesn’t make sense to do that if it’s not always what is wanted. Perhaps there could be a comment that the input vectors should be normalized.

Or, if cycles are not and will never be a concern for your application, you could always make a “safe” version that ensures normalization.

great post ! thanks for slerp code, now i can understand it !