Programming & Using Splines - Part#1

hello this week we're going to start taking a look at splines and how you as a coder can use them to enrich your applications and games in short splines are a way of algorithmically representing a curve and even though you might not think you need curves in your application you'll be surprised just how useful they can be for example if you're making a game why do your game objects need to move in straight lines they can look a lot more fluid and natural if they follow a curvature what if you're interpolating between two points again don't use a straight line use a spline you've probably already encountered splines and don't really realize it so here in humble paint this is a spline and we can position the curvature and you probably experienced the frustration of trying to curve it just how you wanted it always seems to have a mind of its own we see from the paint example that we'll have two control points and a third one which is used as an indication of where the curvature should tend towards and if we were trying to represent a longer path using more points in this fashion we have to pretty much guess where those control points need to be we'll also face issues about what happens when you try to join two splines if we have a look at the Wikipedia article for splines we'll see that it's actually quite mathematical and this can make it inaccessible for the one loan coders out there who just want to get some curvature into their application that said the maps behind these things is quite fantastic and we'll be looking at some of it when it comes to programming we rarely like guesswork so deciding where to put these control points is not ideal so we'll not use that type of spline instead the type of spline I'm going to be explaining in this video you can use multiple control points and the path is guaranteed to go through all of them and to use this I'm going to use a type of slime called a cat mole realm spline and an interesting fact there is the mr. cat mole in the cat Milgram here is one of the founders concurrent president of Pixar so this guy knows his stuff when it comes to computer graphics in its most basic form a capital R arm spline contains four points which are denoted here with the red blue orange and green dots justice gathers going with some of the notation we usually refer to as p0 p1 p2 and p3 a camel runs flying will only generate a curve between p1 and p2 and it uses p0 + p3 as a guide to what angle the curve should be going through the points p1 and p2 to find a point along the spline we usually use a value T which begins at zero for point 1 and ends at 1 4 point 2 so we're accessing the curve segment in normalized space and the nice thing about Catmull ROM splines is the points can be multi-dimensional so even though it traditionally would have X&Y we could have more dimensions afterwards and the mathematics doesn't change just scales up so I'm going to try and start explaining how a spline works without getting involved with the mathematics just yet and I find it useful to think about the points as being the center of influential circles that guide our point T so simply put as we approach p2 we're more influenced by p2 and we become less influenced by P 1 because we're further away so of course if the point lies directly in the middle of p1 and p2 were equally influenced by both the points and if the point on the curve are interested in happens to lie on one of our control points were 100% influenced by that control point and nothing comes from the other control point so what a points p 0 and P 3/4 then well if we just had the point P 1 and P 2 influencing the curve we would get a straight line which you don't need me to tell you isn't a curve so in a similar way to the circles of influence from P 1 and P 2 p 0 and P 3 also are influencing our point on the curve but in a much more mild way so whereas we saw P 1 and P 2 attract our target points p 0 and P 3 repel the target point and we can see in this example that the curve pushes upwards using the desmos comm graphing calculator we can have a look at the maths behind the spline consider the x axis along the bottom to represent our variable T in normalized space so it goes from 0 to 1 and if we remember for our point that was blue which is a p1 we want to have a full influence when we're on the point and we want to have no influence at all when we're on the other extreme of the curve in this case p2 so in this way consider the y-axis to be the amount of influence the point has on our point T going around the curve segment naturally then it follows that our orange point which was p2 has an opposite looking curve so it is not influenced at all by p1 but as we increase our T point along the curve segment it becomes fully influenced by the time it gets to point 2 let's consider p0 now this one looks a little strange positive influence in the Y Direction is attraction ie we bend the curve towards the point so p0 the red point here goes negative which pushes the point away as I showed with the arrows before and likewise we have a mirror image curve for p3 the final point all of these functions are cubics so this is a cubic spline if you've ever tried to use the pen tool in Photoshop you'll know why this is important at each spline control point we can specify a gradient but the curve doesn't necessarily go through the points this makes this tool incredibly frustrating to use but it does highlight one of the limitations of the Catmull arm spline that we cannot specify the gradient through a point the gradient is always calculated by the position of its neighboring points these equations are only valid for one component of our point vector so in 2d space we'd have to calculate all of these for X and all of these for y to give us the XY point on the curve segment I think it's time to start putting these into practice so I've created a new console project and I'm going to use our old friend the OLC console game engine so we can visualize the splines as most of my viewers will know by now the OLC console game engine just simply wraps up the console in a way that it repeatedly displays information to the screen and it also accepts some user input and we need to override two functions in this class the unuse are create and on user update functions I'm going to create a console application that's 160 characters wide by 80 characters high and each character in the console is going to be 10 by 10 pixels let's start by creating a structure that represents a 2d point so I'm just going to have an X and a y coordinate I'm going to create another structure now to represent the spline and the spline is going to consist of a vector of points let's start by getting some of the visualization out of the way in my game engine class I'm going to need a spline object which I'm going to call path and in the unusal create function I'm going to populate that path with points so these are coordinates of console characters on the screen and they represent the control points in the spline there's only four of them now let's try to draw these to the screen first thing I'm going to do is clear the screen which I'm doing by drawing space to all characters then I want to iterate through all of the points and draw them to do this I'm going to use the fill function to draw one pixel either side what one character either side of all of the control points it's going to use the solid character and it's going to call them red this will give me a 3x3 block to represent a control point and in the middle of that 3 by 3 block I'm going to draw the index of that control point so we can see which ones which let's take a look perfect I want to move the control points around the screen so I'm going to create a variable that represents a point that's selected for movement we'll initialize it to 0 so let's handle a little bit of input from the user if the user presses the X key I want to increment my selected point variable but I'm also going to make sure that it doesn't go out to bounce so if it does it rotates it back round to 0 again I'm going to do the opposite with the Zed key which this time decrements the variable now I want to move the selected point around depending on the arrow keys so I'm going to check if an arrow key is held down in this case left and if it is I'm going to move the selected point x position by some value in this case I'm picking 30 because it will be a fast movement and if I modulate that with the elapsed time it'll be smooth depending on the performance of the system and likewise I can do the same for the other arrow keys I think it's important that we highlight the currently selected control point so I'm going to use exactly the same code as I've done here except instead of coloring it in red I'm going to color it in yellow and obviously I'm going to use the selected point variable instead of the eye in the loop let's take a look so we can see the zero control point is currently highlighted and I can use the arrow keys to move it around and if I use the Z and X keys I can move any control point that I want so how do we draw the curve I'm going to create a function called get spline point which takes in a value T and returns an XY coordinate for now I'm just going to hard-code that is zero zero drawing the spline is a little tricky and I want to make sure I'm drawing it behind the control points remember we're using the curve to generate an XY position based on a normalize coordinate so we're going to issue a 0 to a 1 and it will return an XY for that point on the curve so let's create a little for loop which iterates from 0 to 1 and I'm going to nibble at it in very small steps and we'll see that this is actually one of the downsides of using splines for each value of T I'm going to call our spline point function which should return the XY coordinate and I'm just going to draw a pixel at that XY coordinate but of course at the moment it'll only draw something at 0 0 because we need to fill in I'll get spline point function we've only been given the value of T so we need to create some indices based around that value T we know for example if T was say not 0.3 then P 1 would be the floor of T which in this case would be 0 from there we know that P 2 is P 1 plus 1 we know that P 3 is P 1 plus 2 and we know that p 0 is P 1 take 1 so let's do exactly that I'm just going to cast to an integer to do our floor equation and of course because I code these things live I've immediately noticed a mistake it's p 0 1 2 3 we can now start to implement our equations so I know that I'm going to be using T squared and T cubed a lot so I'm going to cash these I'm just going to take the equations exactly as I had them in the desmos graphing calculator to give me four values which are influential field values to calculate the result we do it one axis of the time so I'm going to look at the x axis first we need to take the point that we're interested in so in this case the first one is p0 and we're only looking at the x-coordinates at the moment and we've multiplied that by our first field of influence which was the red line the red point and then take the next point along and use our second field of influence and so on so the four influential fields are multiplied by their respective point locations in the x-axis I can cut and paste this to do the y-axis and just change the X components to Y components instead of returning zero zero will return txt y there is one final thing to do if we examine these equations we see that the influence on the y axis lies between 0 & 2 we want this to be between 0 & 1 so we will have all of the values let's take a look well there's certainly something on the screen let's see if it's behaving so I'm going to move this control point down we can see it does start to repel some of the curve let's move this control point over a little bit okay I'll bring this one round too so we'll make it look like we had in the diagram before however there's some reason it's a dashed line why is this well that's because we nibble through the zero to the one in a small increment and if we're only incrementing in naught point naught 5 that means really we can only have 20 pixels between the two control points and if they're 40 pixels apart we'll skip every other pixel so we need to make this smaller let's have a look that's better that one curve segment on its own isn't very impressive so let's add a lot more points so here I've added a point every 10 pixels in a straight line we've now got more than one curve segment so we need to adjust our drawing routine accordingly now I take the number of points in our path and I'm going to use that to calculate Mike T note that I'm subtracting a value from them I don't want to draw the two control points at the end of the spline let's take a look hmm something doesn't look quite right here oh dear let's see why this might be well our T is going to go above 1 so we need to modify our get spline point function to accommodate this and this is quite simple because we've already got the floor of our tea to give us our first control point we just want what's left over so our control points will represent one two three and four and any remainder that comes in is what we're going to use to index into the normalize point of the curve segment this looks a little better let's move some points around very nice and so you can see with more control points we can have quite elaborate curves let's just take a minute to look at an interesting property of this here I've laid out the points in what appears to be a loop and in fact if I take the two end points which in this case will be one and eight and overlap them that would actually make a loop but it's a loop with a bit of a kink in it around the point eight but I can get rid of that by using the two original end points and overlapping those with the two neighboring points which gives us a nice perfectly curved loop and so if we wanted our splines to be loops we could just manipulate the indices when we're trying to calculate our spline point and therefore we know that our loop goes through all the control points if we want our spline to be looped we have to treat it differently I'm going to modify our spline point function if it's not looped we just do what we did before which will give us a curvy path but the ends won't join but if it is looped we can take our T variable calculate the indices in a similar way to before but this time wrap the indices around all of the points in the vector so let's say I'm approaching the point towards the end of the vector I can use the modulus function to wrap it round to the staff and likewise if I go below zero I can't use the modulus function for that but I can do a little trickery here to give me the point at the other side of the vector you should also modify our drawing function now to go through all of the points but we must tell our spline function that it is loops now let's take a look well it looks like a straight line again but as I start to move the points around we can see they're certainly joined nice now we have a facility where we could control an AI character let's say for example a spaceship to follow a path around space and it will look very natural it won't have to move at right angles or turn at fixed intervals and the path can be modified in real time so with a simple bit of mathematics we can generate a very natural-looking behavior but what if we wanted our spaceship to follow the path precisely for example in this instance our spaceship is only getting an x and y coordinate will always point in the same direction regardless of where it's up to on the path instead what we would prefer is that the spaceship carry on pointing in the direction of the path depending on where it is and we can do this by extracting the gradient at any point a crude way of guessing the gradient at a point will be to take it to control points and create a straight line between them and that would give us an approximate gradient maybe but a better way is to modify our spline equations to give us a precise gradient in a similar way that we calculate the position unfortunately this is very simple indeed if you remember before we were calculating our Q values which were the influential field so we have something like minus T cubed plus 2t squared take 1 all we need to do is differentiate this equation which becomes minus 3t squared plus 4t take 1 and we can do that for all of our equations so I'm going to take our entire point function here and duplicate it I'm going to call this one get spline gradient and everything else can remain the same but I'm going to change these equations I'll just cut and paste the others in there we go so let's hack something in to demonstrate that we can extract the gradient the agents location is going to be represented by a variable called F marker so we need to have some keys so we can increment and decrement this variable I'm going to use the a and s keys to change it but I want to make sure that I keep control of this variable so I'm also going to put some boundary checks in so if the marker value goes larger than the number of points in the path then it wraps around like we did before with these E and X keys I'm going to draw on our path where the agent currently stands so to do that I'm going to get the point on the path this assumes we're looping at the moment I'm going to get a point on the path where the marker location is and I'm also going to call I'll get gradient function for the same point to draw the agent I'm going to draw a line which I'm hoping is going to be orthogonal to the path at all points so let's have a look at this the first thing I do is calculate the angle of the gradient returned by the get spline gradient function so this will return an XY vector but I'm going to convert it to radians and I'm going to use the draw line function which is provided by the game engine to calculate two points that are rotated around p1 which is where our agent is on the path by the angle represented by the gradient I'm going to offset these by 5 pixels so I'm going from one point here which you can see is a plus 5 to a minus 5 and this will hopefully give me two points either side of the path I'm going to draw this blue let's not also forget that we're working in loop mode here so let's take a look well I can see the agent is definitely orthogonal to the path let's make it our path a little bit more interesting it's always very satisfying watching the curves sort of unfold themselves and we can see the agent starting to rotate depending on the orientation of the path so if I use the ANS keys we can see the agent follows the path now because I'm incrementing its position along the curve then it wraps around very nice so this video is showing you how to create a path and spline between all the control points and I think it's quite useful for things like a non-player character ai or animations but there is still a few things to work out so as I move my agent around we can see is speed varies and this is because it assumes that the distance between all of the points is the same 0 to 1 we'll come up with a solution for this in part 2 of the splines video all of the code for this video is available on github if you've enjoyed it please give me a big thumbs up have a think about subscribing and I'll definitely see you next time and I'll definitely see you for part 2 of this video so take care

Channel: javidx9

Views: 60,337

Keywords: onelonecoder, one lone coder, splines, catmull-rom, bezier, programming, tutorial, learning, console, command prompt, c++, ai, npc, path following

Id: 9_aJGUTePYo

Length: 23min 56sec (1436 seconds)

Published: Sun Aug 06 2017