Useful functions for game designers - Lagrange Interpolation

In science, technology and engineering it is very common to have to interpolate between data points. One of the many ways to do this is through Lagrange interpolation. In this video I'll go through how it works and if you go to desmos.com you can follow right along.
========== Social Media Links ==========
Twitter: @The_ArtOfCode
Facebook: / theartofcode
Patreon: / theartofcode
ShaderToy: www.shadertoy....
PayPal Donation: paypal.me/thea...
========== If you want to follow along ==========
Starting point:
www.desmos.com
End Point:
www.desmos.com...
========== Other videos to watch ==========
Check out my video about linear interpolation:
• Interpolation for Dumm...
Or using smooth minimums:
• Function Smoothing Exp...
Or using Hermite interpolation (smoothstep):
• Smoothstep: The most u...

[@Anskair]

I never knew you can name a point in desmos and then address their x/y components. Mind-blowing!

[@llamallama1509]

I've been experimenting with this on Desmos and although I really am not the best at mathematics, this seems like something I can get my head around. Thank you for teaching me something new

[@seanloughran6714]

Man, you explained that so well and took out all the mystery and explained it so well.

[@kolosso305]

Some are saying this function isn't as good as bezier, and that may be true for most cases, but I just enjoyed seeing the problem from a new perspective. That alone is an invaluable tool to have

[@TheArtofCodeIsCool]

Yeah I should have mentioned that this might not be the best for your particular situation. There are many different ways to interpolate so just see this as another tool in your toolbox.

[@braveitor]

Excellent! This is how this topic should be taught in schools. Much more comprehensive and useful!

[@TheArtofCodeIsCool]

I'm glad you think so and I agree!

[@user-ns1jz9ir6z]

I couldn't imagine that it's so simple. Grazie!

[@TheArtofCodeIsCool]

You are welcome!

[@boggo3848]

It's so cool to see the final result hit all those points!

[@CynicatPro]

Yooo i've been looking for how this curve worked for ages and could never find the name! I've been wanting this for simple curve editing for literal years at this point X3

[@moodeex3766]

Incredibly insightful! 🙏

[@purplehierophant]

A great video, reminds you to think mathematically, very didactic because it shows you the function and construction rather than presenting it as a back box just to plug in

[@sagielevy]

I just used this algorithm to rotate a camera to look at different targets along a spline. I remembered you taught this algorithm somewhere in the back of my head. Thank you!

[@pawspaws101]

Beautiful stuff! I've been using interpolation for awhile, and it works by 'majic' just looking at the formula but this has explained the formula so visually I know understand more about why it works! Thankyou!!!

[@spherolly2374]

Thank you very much, that is great tutorial and very useful in gamedev indeed! Currently I'm making fully procedural character animation system at my job which uses math functions instead of baked animation curves, I've also used Desmos a lot for finding functions formulas from shapes of curves, because I forgot all math long time ago :) I hope you will continue make more desmos-functions tutorials!

[@spherolly2374]

@@stysner4580In a nutshell, we describe trajectories of character's joints with parametric functions. You can think of it like 'rules of motion' for character in certain conditions. For example, when bipedal character is moving (walking) it's pelvis goes up and down, you can represent that motion with a sine wave function and adjust amplitude of that motion based on character's velocity.

[@pockets111222333]

Great video, explanation was really clear and easy to follow!

[@RavenAmetr]

Excellent tutorial! Would like to see more of such things!

[@Only1Guitar]

Brilliant explanation! I'm going to use this for realtime audio sample rate conversion.

[@arildboes]

Nice. Great video. very usefull to me, with the good breakdown

[@shau4744]

I enjoyed that, great explanation especially as I'm not too good at maths.

[@kdblender8528]

Amazing, Love this tut !!

[@user-xm5px6zf8c]

purely substantial content,

[@0briang0]

That is so beautiful. Thanks for making this video

[@NexysStormcloud]

simple and usefull

[@sanderbos4243]

Beautiful explanation, thank you so much!

[@johncreativeproducts5688]

Awesome video man! Thanks so much!

[@goranbla]

I liked your content so far, but this one I love 👍 thank you, learned a thing or two (three, four) 😅

[@hippotizer]

Really beautiful, thanks a lot for sharing

[@aayushparashar4143]

Really like these type of videos, and the one you did on the smooth step function.Would love to see an implementation of chaos game on desmos!!!

[@TheArtofCodeIsCool]

Not sure what you mean by chaos game?

[@aayushparashar4143]

@@TheArtofCodeIsCool making serpinski triangle by choosing a random vertex and and interpolating to it 50% and then repeating.

[@TheArtofCodeIsCool]

@@aayushparashar4143 you got a link for this?

[@aayushparashar4143]

@@TheArtofCodeIsCool yeah definitely, ( kzbin.info/www/bejne/f3jPeKmJjdCFfas ).This is a short 3 minute video visually explaining chaos game!!!

[@TheArtofCodeIsCool]

@@aayushparashar4143 thanks I'll have a look

[@DragonSight_]

Very clear instructions!! Definitely would love more maths in this format.

[@alejmc]

Didn’t know Deimos, didn’t know Lagrange curves interpolations (only by name, for physics related solvers I think it was), by the end of this video it was all perfectly clear and useful. Glad to have learned something new, thanks a lot. Question, if time permits, adding more points means adding increasing the complexity of each separate curve… now, to be honest, for the most part the amount of points in general are constrained in my experience (when referring to gameplay anything). In your camera flying over landmarks idea, I don’t really see more than 5 waypoints being shown at any single time. However, supposing that we want 100 points, would something like evaluating four points at a time be stitch-able? I.e. the curve from p1 to p2 uses [p0 p1 p2] from p2 to p3 uses [p1 p2 p3], so on and so forth.

[@vladshcherbakov3112]

Thanks, this is really useful. I remember I learned about this in a numerical analysis class years ago, but then totally forgot about it.

[@onlyeyeno]

Thanks for another absolute top notch tutorial. Getting a notification about a new video from You always raises my spirits :) Best regards. P.S. I guess it might be obvious to anyone who is more "accomplished at maths" than me (which doesn't really take much) but this "method" can "simply" be amended following the same "pattern" to accommodate arbitrarily many points, "as per Your needs" :) D.S.

[@TheArtofCodeIsCool]

I'm glad you get something out of my video, and yes, you can extend this to arbitrarily many points.

[@Trooperos90]

This is so beautiful

[@TheCookingPixel]

These are very important, please continue..thank you.

[@sasjadevries]

17:19 Wow, if you change the order of points, then the line adapts automatically to the new order. That does answer my question on why someone would use this interpolation over something like a spline.

[@Krunklehorn]

Very cool alternative to the usual recommendation of "Just construct a bezier." I'd be interested to see some examples for case study of where this would come in handy, especially in scenarios where the direction of movement between each point is either not provided or not important.

[@TheArtofCodeIsCool]

A Bezier might be more controllable in many cases. You could see this more a technique to fit a polynomial to a bunch of points.

[@brandonlewis2599]

Yeah, desmos is pretty cool. Been using it for a while.

[@Bleenderhead]

I get the impression that this is extremely numerically unstable with large number of control points. You'd have an nth degree polynomial with N control points, so every point on the curve is evaluated by taking a huge product, then dividing it by the result of another huge product. The "correct" curve could also vary wildly in between control points in order to ensure that it passes through them all, and another problem is that moving any control point changes the curve everywhere. For a camera path, surely something with more predictable behavior like a catmul-rom spline would be preferable; splines have a locality property that ensure that moving a point will only affect the nearby parts of the curve, which is more desirable for artists.

[@TheArtofCodeIsCool]

You make a bunch of valid points. Perhaps I should have been more clear that this is just one of many ways to interpolate and it might not be the best solution to your particular problem. See as just another tool in your toolbox.

[@jeffcummings3842]

Wave Function Collapse is an interesting topic to make a video ... or two !!

[@idirbelaid1924]

omg, fantastic !! keep them coming bro !!

[@TheArtofCodeIsCool]

More to come!

[@jeffcummings3842]

Wow, amazing! Thanks for the great explanation. You'll make a video game creator out of me yet!

[@tobberh]

Very useful!!!

[@gnorts_mr_alien]

wow such teaching

[@user-iy8ek4ki1r]

Very nice!!

[@MrYefh]

I'm so glad you're back :)

[@BoyceBailey]

loved this. I'm looking forward to watching examples of all the others. Does anyone have examples of making this work in Unity?

[@ezequielleonzybert]

thanks

[@realcygnus]

Nifty

[@unveil7762]

Wow … thaz cool!!!

[@agrandcanyonoffucksgiven2776]

The mathematician who this is named for, has an interesting history during the french revolution.

[@TheArtofCodeIsCool]

Oww yeah? Do tell!

[@FalkBay]

I really like this, I have to try it out by myself. Which is the time complexity? looks like O(n²) to me.

[@TheArtofCodeIsCool]

Since every new point requires a new polynomial and also a new term in all the polynomials, its O (n^2) indeed

[@brice.v]

Fantastic :) how does it scale up with the number of points? Does this mean it's always o(n) or is there some properties of this curve I can use? Should I just for example do pieces of 4 points and lerp the first and last segments or something? Thanks, great content as always!

[@CodAv123]

Implemented as a general-purpose algorithm, it has an n² complexity. So twice the number of points means four times the work to be done. Not great, but could be worse.

[@EntresDee]

@@CodAv123 But can't get much worse regarding runtime complexity.

[@carbunclegrim3419]

cool!!

[@adarshsinha1237]

Super informative video! Out of curiosity, would there be a direct mathematical way to make it so that if there was a point here that you wanted to AVOID, you could get the resulting line to bend around it? (eg. in a flowchart or a graph where nodes are connected by seemingly nicely curving arrows if the nodes are moved around, but if 1 node is placed in the middle of an existing curve/edge, that curve bends around it)?

[@vzzzk]

Just spawn a few points on some equal distance around a point you want to avoid. And use Lagrange on these new points ;)

[@adarshsinha1237]

@@vzzzk Aha that's a great idea, literally thinking outside the box. Thank you! I shall try that out.

[@forasago]

The most straight forward way would not be to create multiple points but just one: Keep the X and invent a new "false" Y. It's that simple. Now you just have to come up with a rule for how you falsify the Y coordinate. The simplest option would be multiplying with -1, that way you've reflected the point past the X-axis. Or you can add/subtract a constant value for a consistent pattern. Or you can add/subtract a random value to avoid a pattern.

[@MartinToernby]

​@@forasago That would not work when y = 0, also going totally off in the opposite direction, may not be desirable. But yeah - Adarsh Sinha may need to clearify the desired effect. I'm more impressed with Антон Тятенков 's approach. Adding 3 points around point B, with a predefined Offset of whatever you like may do the trick - middle point with same x as B, but y at Offset, left point: going towards A at distance Offset, right point: going towards point C at a distance of Offset. And then take into account if A and B or B and C are closer than Offset - then just use half the distance between A and B instead of Offset. Longest reply in world for someone posting an idea .. : )

[@NoTengoIdeaGuey]

I wish i was taught math like this in high school. All i got was some poor underpaid lady hurriedly explaining the "rules" of math from a textbook, and then endless homework to test if i learned the rules or not. Needless to say i did poorly and always thought i was just "bad at math".

[@sotrh7974]

Would using a bezier curve be more performant?

[@davidmurphy563]

And, two minutes in, I'm pausing to watch a children's video on what a polynomial is... Still, got it now. Let's see if I can follow this. EDIT: ok, my jaw is on the floor with y = (x + z) * (x - z)... You can make pretty much any graph you need. Ugh, I was messing around with graphs on desmos for ages last weekend to make a robot that faces the player with torque forces without overshooting and this would have done it in a heartbeat. And you can just add up these terms you say? Wow. Maths is magic. EDIT EDIT: 5:20 Ok, it's clear what you're doing. Let me see if I can pause the video and do the rest myself. EDIT EDIT EDIT: Nope, wasn't able to make the leap from zeroing to normalisation with my thick brain. Managed to pause and get it working at 11:16 so I'm calling that a win. I'm not as clear on the normalisation as I'd like to be... I guess if there were only two points C and A then dividing by (c.x-a.x), that's the length, makes sense sorta but we need to scale so that the y fits, not the x. Let's say that gives 10. Now, if we have another component, (b.x-a.x) let's say this is 5. So, b is 5 away from a on the x. C is 10 away. Now you multiply them?! What? That gives 50... Nope, no idea why that works. I'll have to think about this some more.

[@TheArtofCodeIsCool]

For every point the curve goes through we make a basis polynomial which is a function that goes through the desired height at the point in question, and through 0 at every other point. So the basis func for point b would be: (x-a.x)(x-c.x) because that goes through 0 at a and c. Because at a the first term is zero, making the whole thing 0, and at c the 2nd term is 0, making the whole thing 0. Great! But what happens at point b? We want it to go through b.y In order to do that, we first normalize the func so it goes through 1 at b.x so in other words we want (x-a.x)(x-c.x) to be 1 if we fill in b.x. So lets fill this in -> (b.x-a.x)(b.x-c.x). hmm well we dont really know what that is. How can we make it 1? How can we make any number (except 0) into a 1? By dividing it by itself! So if we make it so that the func divides by itself when we plug b.x into it, we are good. hence ((x-a.x)(x-c.x)) / ((b.x-a.x)(b.x-c.x)) go ahead, plug b.x into this formula and what you get is an expression divided by itself, which yields one. Make sense?

[@davidmurphy563]

@@TheArtofCodeIsCool Let me work through all that slowly in my head. Ok, simplest concrete example imaginable: a = vec2(-0.5, 1.0) b = vec2(0.0, 1.0) c = vec2(0.5, 1.0) _(x-a.x)(x-c.x)_ This much makes perfect sense. It forces zero on the y axis at points *a* and *c* because you're deducting a.x from x, giving zero at that point on the x. With *a* and *c* above then *b* is at the bottom of the curve in the simple example with a y value of -0.25 (-0.5 * 0.5). So far so good. So helpful know, incredibly powerful on its own. The need to normalise this -0.25 value to 1.0 is clear. I've used such a simple example it's obvious *b* normalises dividing it by -0.25. Oh shit. Yeah, just divide it by itself... _hence ((x-a.x)(x-c.x)) / ((b.x-a.x)(b.x-c.x))_ Ohhhhhh. The penny drops. It's a self-division at the x coordinate of *b*! x = 0 in the case of my symmetrical example. So, -0.25/-0.25 = 1. I was thinking it was something complicated... And then you just scale it. Easy. Got it now. Thank you so much for replying with such a comprehensive and helpful answer after having to trawl through to my ramblings. Ok, now I want to do it in 3d. Make a rollercoaster maybe. Bet you could do it with 2 functions and loop through an array of vecs...

[@bl4ck0p]

do you have to use a white background

[@Haykke]

Is it possible to make a mesh gradient on shadertoy?

[@nicholasmaniccia1005]

This is fucking nuts.

[@victorl2886]

Hi Martijn, what was your original resources of learning all those techniques? Thanks!

[@TheArtofCodeIsCool]

I get my ideas from books, KZbin, shadertoy and, most of all, playing with this kind of stuff a lot.

[@supersaiyan9616]

does it works in 3 dimensional coordinates as we have another dimension

[@TheArtofCodeIsCool]

That's a great question. I suppose there are multiple ways of trying to extend things to 3d. How about treating x as time, as opposed to a physical dimension, and instead of just adding a the l-functions to get a final y value, you multiply every l-function by a location vector and the add all location vectors?

[@supersaiyan9616]

@@TheArtofCodeIsCool I'm not so great in maths like you. So I don't know that will work or not?. Thanks for your reply. ❤

[@manzoo_3096]

oh. i love you

[@syntax_error6882]

your name its .. the wizard if you have one minute i've this spiral but a strange line : float l = length(uv); float r = atan(uv.y , uv.x ) * 3.14159 ; // of course glsl atan(x, y) float t = iTime *10.; float c = 1. - sin(l* 70.+r+t); vec3 rgb = vec3(c); did you have some exercices to understand math stuff imply here ? anyway thanks for the channel

[@TheArtofCodeIsCool]

You have a line because your atan function returns a number between -PI and PI, so you shouldn't multiply that by PI again.

[@syntax_error6882]

@@TheArtofCodeIsCool great thanks

[@wizardOfRobots]

very nice! what happens when two points have the same x value?

[@TheArtofCodeIsCool]

if they have the same x and same y, then all is fine. If they don't have the same y I imagine you get a division by zero, which is never too good ;)

[@CodAv123]

Yes, if x is the same, but y is different, the graph would need to have infinite steepness. This could be mitigated by simply not allowing the same x coordinate for any two points. Even a very small difference would work, but the graph would then make a huge detour in +/- y direction, way outside your screen/map limits.

[@NikolaNevenov86]

just a silly question....the "l"s is the y coordinate for every x?

[@TheArtofCodeIsCool]

We make a basis-polynomial for each point that I call l1, l2, l3 etc. Which is a function that contributes the y-coordinate for that point. Is that what you mean?

[@NikolaNevenov86]

@@TheArtofCodeIsCool yes thank you

[@ricurse]

Is this also used for generating roads / tracks in e.g those top down Rollercoaster type of games?

[@TheArtofCodeIsCool]

Not sure, but its possible.

I am not sure about this but bezier curves are used for that purpose most certainly...

[@CoolJosh3k]

Neat, but you didn’t show how to generalise it for n points.

[@TheArtofCodeIsCool]

For that, you'd have to look at the thumbnail of the video ;)

[@CoolJosh3k]

@@TheArtofCodeIsCool I hope to see more than 2 parts. There are plenty of things like this.

[@botteu]

It must be nice to know math.

[@TheArtofCodeIsCool]

Most useful math isn't anything more than highschool-level stuff. Just follow along and you'll get there!

[@ivankramarenko]

so many calcs. How can u reduce?

[@TheArtofCodeIsCool]

You can't with this kind of interpolation. Computers are blazing fast though. They can do this 100.000 times a second without breaking sweat.

[@LeutnantJoker]

@@TheArtofCodeIsCool or as they say: profile first, then worry about performance

[@alejmc]

@@LeutnantJoker exactly! Premature optimization is most likely an enemy than an ally at this stage.

[@letsadoptloli2014]

Curve comes shitty (with big amplitude) realy fast with adding new points, because of degree of polynom

[@gower1973]

The reason you got confused over the colours was because the colours for the variables didn't match the formulas

[@TheArtofCodeIsCool]

Yeah everything is on the fly some sometimes stuff like that happens ;)