[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Hello once again shmup fans.  Strap yourself in for another fun filled exhilarating ride through my brain.  This time we'll be discussing how you can quickly, easily, and efficiently create super smooth curved motion for your scripted game objects and have them follow in real time.  This will let your enemies gracefully swoop in on complex attack vectors and create mind boggling formations with each other as they spin around the screen.  At the end of this tutorial I'll be linking it up with the ideas from the last control schemes tutorial so if you haven’t read that already then please do so now.  So without further ado lets crack on.

When designing motion for our scripted game objects we don’t want to have to manually specify their positions for every single frame, imagine how long it would take to create all that data.  Instead we want to specify only a few key positions for the object and have the computer automatically move the object between those key positions.  This is what is known as interpolation and there are many ways we can do it each having different properties and giving different results.  Therefore we want to choose an interpolation method which has the properties we desire.  For this I'll be considering the two major properties we are concerned about.  The first of these is whether the object is forced to move exactly through the key positions we specified or whether these are merely control points for the motion which is approximated between the points.  There really isn't much difference between the two methods since the same motion can be represented with both systems but personally I prefer the first option since it gives more intuitive control over the motion and allows us to set up exact locations for things such as formations of multiple enemies etc.  Therefore I'll want an interpolation method that satisfies the first option.  The second important property is the continuity of the interpolation, i.e.: how smooth the resulting motion is.  For example consider the simplest type of interpolation we can perform which is to move the object linearly between the key positions (imagine connecting up the key positions with straight lines).  In such a system the position aspect of the object is continuous since there are no sudden teleportations in the position.  The objects velocity is discontinuous however since it suddenly changes direction at the key positions giving rise to jagged line motion.  This interpolation method is known as zero order continuous because none of the derivatives of the motion are continuous (velocity being the first derivative of position).  Now imagine a first order continuous method.  In this scheme the objects position and velocities would change smoothly but the objects acceleration (the second derivative) is allowed to change suddenly at the key positions.  Therefore such an object would move in smooth curves between key positions but the curvature is allowed to change suddenly between pairs of control points.  In a second order continuity method our acceleration is now also continuous and hence the rate of change of curvature must also change smoothly.  As you can see the higher the order of continuity the smoother and smoother our motion is going to become.  The trade off however is that higher order systems are more computationally expensive and become more restricting on the motion we can produce.  The visual improvement you get from using higher order systems drops quickly too so it’s not important to use a high order.

So taking all the above into account, an interpolation method known as Catmull-Rom Splines is widely popular for controlling motion.  This is an exact interpolation method (passes directly through key positions) and is first order continuous giving nice smooth curving motion without being too expensive or restrictive.  Therefore this is the interpolation method I'll be using throughout this tutorial.  So how do we use Catmull-Rom splines?  We will consider the spline in segments with the smallest spline we can use containing one segment.  There is no cap on the number of segments a spline can contain and hence there is no limit to the maximum size restriction for a Catmull-Rom spline.  A spline segment consists of two key positions you want to interpolate between, and the key positions either side of those two key positions:



Therefore the minimum number of key positions a spline must contain is 4 since this equates to one segment.  To create longer splines we simply add more key positions onto the end and shift our segment up one key position at a time, thus a spline with 5 key positions has 2 segments, one with 6 key positions has 3 segments, etc.  This allows us to interpolate between every pair of key positions with the exception of the [0,1] pair and the [n-1,n] pair where 'n' is the total number of key positions.  Therefore when creating a spline you must always add in an extra key position on either end of the desired motion.  So how do we do the actual interpolation to determine points on the spline in-between the key positions?  Imagine a spline segment with key position p0, p1, p2, and p3.  Given the requirements for a segment just discussed this means that for this segment we can interpolate between key positions p1 and p2.  Any point between these two key positions can be described by a value 't' which can take any value between 0 and 1 inclusive where t=0 represents key position p1 and t=1 represents key position p2.  There t=0.5 would reference a point on the spline half way between key positions p1 and p2.  Then for a given value of 't' we are interested in we can calculate the actual x,y coordinates of the point on the spline at that 't' using the following equations:

Code:

x = 0.5 * ((2 * p1x) + (p2x - p0x)*t + (2*p0x - 5*p1x + 4*p2x - p3x)*t*t + (3*p1x + p3x - p0x - 3*p2x)*t*t*t)

y = 0.5 * ((2 * p1y) + (p2y - p0y)*t + (2*p0y - 5*p1y + 4*p2y - p3y)*t*t + (3*p1y + p3y - p0y - 3*p2y)*t*t*t)

So one option for us to move our object along a spline is to increment 't' by a constant amount each frame and calculate the objects position from the new value of 't'.  When 't' becomes greater than 1 we subtract 1 from the 't' value to put it back in range and move our segment one key position along the spline.  This is repeated until the object has reached key position n-1.  This will give us nice smooth motion but there is a problem in that the length of each spline segment isn't necessarily equal to the length of all the other spline segments.  Even if we spaced our key positions so that they all have the same separation the actual length of the interpolation segments will still vary since they curve by different amounts.  In fact due to the mathematics involved you'll find that the speed of our objects will vary even on different portions of the same spline segment.  What this means for us is that varying 't' by a constant value doesn't equate to our object moving with constant speed.  In fact just using the knowledge we currently have its near impossible for us to control the speed of our objects at all which obviously isn't very good for us.  So how do we tackle this problem?

Clearly what we need is some knowledge of the distance our object is covering during interpolation, specifically we need to know about what is called arc length which is the length of a curve if you imagine it stretched out flat.  What we need to do is reparameterise the Catmull-Rom equations so that they become functions of arc length rather than 't' (the parametric variable).  Often these reparameterisations aren't able to be done analytically and we must use numerical methods.  Since we want to keep our spline code efficient we'll be approximating the reparameterisation by using a pre-calculated look up table.  We calculate this table for each spline segment by evaluating the position along that segment for lots of small increments of 't'.  If our 't' slices are small enough then we can approximate the little slices of curves between each evaluated point as straight lines.  What this means is that by adding up the lengths of the straight lines we can get an estimate for the arc length at each value of 't' we evaluated.  This pre-calculated table is then loaded into our game so that we can control our objects by incrementing their arc lengths directly giving us absolute control over object speed.  The current arc length is then looked up on the table and its corresponding 't' value read off and used to calculate the objects actual new position using the Catmull-Rom spline equations given above.

There is one more complication however.  Given a value of arc length for which we want to know our objects position, it’s unlikely that our table will contain this exact value of arc length to read off the exact 't' value.  Instead we must blend between the 't' values for the two nearest arc lengths in the table either side of our actual desired arc length.  This can be done by following this formula where 'a0' and 'a1' are the two closest tabulated values of arc length our actual desired arc length 'a' lies between, and 't0' and 't1' are the corresponding values of 't' for 'a0' and 'a1' respectively:

Code:

t = t0 + ((a - a0) / (a1 - a0)) * (t1 - t0)

So we can now move our object in nice smooth curving motions whilst maintaining absolute control over their velocities.  There's really only one more thing I need to mention.  Imagine now you control a tank style enemy using such a spline.  You'll want the tanks lower body and tank tracks to rotate so that it looks like the tank is actually driving along the path.  We can achieve this if we know the angle the spline motion takes to some reference direction and then combine this with our sprite perspective trick from the previous control schemes tutorial.  What we need to know is the rate at which the curves position is changing at any point which will give us the direction.  For those of you who know anything about calculus this equates to finding the differential of the spline.  Don’t worry I'm not going to start giving you a tutorial on calculus, I'll just spit out the answer.  So the rate of change of x and y, called 'dx' and 'dy' become:

Code:

dx = 0.5 * (p2x - p0x + 2*t*(2*p0x - 5*p1x + 4*p2x - p3x) + 3*t*t*(3*p1x + p3x - p0x - 3*p2x))

dy = 0.5 * (p2y - p0y + 2*t*(2*p0y - 5*p1y + 4*p2y - p3y) + 3*t*t*(3*p1y + p3y - p0y - 3*p2y))

The nice thing about this is that many of the bracketed groups and powers of 't' have already been calculated in the Catmull-Rom spline equations and so we can re-use them.  We can now plug these 'dx' and 'dy' values into the atan2 function just like we did in the progear turrets tutorial in order to calculate the direction our object is facing and hence update its sprite accordingly.  Well that’s basically it.  Welcome to the world of super slinky spline motion, I hope you enjoy it.  Sorry this tutorial is a little stunted compared to usual and things maybe aren't explained in the same level as detail as my usual standard but with taking over the website and trying to organise the next compo my time is a little tight.  As usual if you want to ask questions please do so.

 

Thanks for reading

 

 

Dan.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

[reserved]

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

You can find previous replies to this tutorial posted in the following thread:

http://www.shmup-dev.com/forum/index.php?topic=1172.0

That topic has now been locked.  Please continue any discussions or add any further questions in this thread.  Many thanks.

[Yumil]

Yumil

Yumil

Show Yumil's last posts.

Show general stats for Yumil.

• 
• Full Member
• Score: 2
• Posts: 113

Hi, it's me again.
I've now been playing around with Catmull-Rom splines thanks to your tutorial(BTW, it was the one I could understand the easiest out of what I've found searching the interwebz). Changing the equation to a function of arc length is great...exactly what I wanted, but I do have one question.

Would it be better to just store a table of positions based on a minimum velocity(say 1) and pass that to the game from an editor. I'm just saying that if you have less points to visit than arc length data on the table, wouldnt it be smaller to just pass the points. I'm just thinking that keeping a sufficiently small t increment for your table to make a smooth curve over a large arc for the smaller arcs would lead to a table that is larger than what you need. Also, by making a table of positions over time, it would get rid of the calculation and the table search.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

It seems to me that you're massively over-sampling your splines if you're having problems with table sizes.  The velocity of the objects which follow the splines isn't the factor you should be using to determine your sampling rate.  Instead you should be considering the 'frequency' of the spline, in other words how rapidly it can change direction, or how sharp the curviture is.  For an in depth description on data sampling take a look at http://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem.

Your splines though will likely be made up of only a hand full of points spread out across the length of the screen and so wont contain much high frequency data or rapid curviture, therefore a huge sampling rate isn't really required.  If you really wanted to shave off as much space as possible in your tables, then in your spline tool you could start at a high sampling rate and then repeatedly evaluate each spline segment using lower and lower sampling rates and compare the error between that and the first high sampling rate evalution until it rises above some tollerance level.  You'll then know how small a sampling rate you can use for that segment without the results becoming too erroneous.

Lastly there's not a way you can get rid off the table search, not unless you know how fast your object is moving before hand at the time you make the spline and then stored 60 positions a second for that object (assuming your game runs at 60fps which you would also need to know at the time you make the spline).  Now that would be a very large table.  If you want to reduce table size and make your system more flexible and generic so that you can change your objects velocities if and when you want, and run the game at what ever fps you want, then table searches are innevitable.
.

[Yumil]

Yumil

Yumil

Show Yumil's last posts.

Show general stats for Yumil.

• 
• Full Member
• Score: 2
• Posts: 113

It seems to me that you're massively over-sampling your splines if you're having problems with table sizes.  The velocity of the objects which follow the splines isn't the factor you should be using to determine your sampling rate.  Instead you should be considering the 'frequency' of the spline, in other words how rapidly it can change direction, or how sharp the curviture is.  For an in depth description on data sampling take a look at http://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem.

Thats my problem. I'd been using a much smaller t sample for the table because I was getting huge jumps at the points. I didn't even think of resampling specific areas when the error rate gets too high and just inserting it into the table. Doing that, would probably keep it small, and since its not reliant on the t sample being constant, it'll probably turn out fine.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

I'd been using a much smaller t sample for the table because I was getting huge jumps at the points.

If you're getting sudden jumps at the nodes then it sounds like a bug in your implementation, possibly with how you deal with crossing sectors.  The thing is that using the implementation in the tutorial you should get continuous motion even with no sub-sampling since the sampling rate just determines how accurately you're able to control the object velocity.  If this is a bug when crossing sectors like I suspect, check out the other discussion thread for this tutorial, there's discussion in there with someone who had the same problem.

[Yumil]

Yumil

Yumil

Show Yumil's last posts.

Show general stats for Yumil.

• 
• Full Member
• Score: 2
• Posts: 113

I'd been using a much smaller t sample for the table because I was getting huge jumps at the points.

If you're getting sudden jumps at the nodes then it sounds like a bug in your implementation, possibly with how you deal with crossing sectors.  The thing is that using the implementation in the tutorial you should get continuous motion even with no sub-sampling since the sampling rate just determines how accurately you're able to control the object velocity.  If this is a bug when crossing sectors like I suspect, check out the other discussion thread for this tutorial, there's discussion in there with someone who had the same problem.

Now that you point it out...it was due to a floating point error>.< I had a for loop that ended if it was more than or equal to 1 and incremented t by .1...well, by the time it got to .9, it was like .900001 and it would just jump to 0, which I had assumed would be equal to the last value. So, it would skip from .9->the start of the new seg>.<
I had read the last comments in an attempt to make it right the first time. I was sure I took everything into account, and I did, but I forgot the darn nature of floating point. That makes things much better now.

[Jason Doucette]

Jason Doucette

Jason Doucette

Visit Jason Doucette's website.

Show Jason Doucette's last posts.

Show general stats for Jason Doucette.

• 
• The Architect
• Newbie
• Score: 0
• Posts: 4
• The Architect

Thanks for this tutorial.  It's the best one for Catmull-Rom Splines on the 'net that I've found.  Many game makers are trying to use splines for their enemy motions, and have no idea on how to get the speed to be constant.  In fact, it's hard to find any information on this at all on the 'net.  It's too bad this tutorial wasn't ranked higher in Google.  I had to specifically search for 'shmup' to find it.  And the document I found was this:
http://www.shmup-dev.com/forum/index.php?topic=1638.0;wap2
which is an unformatted page, so it is likely skipped.  In any case, thanks for the tutorial, it's helped greatly.  It basically convinced me this was the only sane way to get constant speeds out of these splines.  And I like to us Catmull Rom rather than others for the same reasons you do: because they go through the waypoints.

Take care,

[OMNICYPHER]

OMNICYPHER

OMNICYPHER

Show OMNICYPHER's last posts.

Show general stats for OMNICYPHER.

• 
• Newbie
• Score: 0
• Posts: 8

thanks for the spline formulas, and great explination too! it seems very usefull, but at the same time, couldn't there be an easier way around the problem? if you want an object to keep its velocity while moving through specific coordinates, couldnt you just rotate its vector with logic? then when the seeking missle reaches its target, it aims towards the next target on the list. depending on how you adjusted the the vector direction, couldnt you produce the same curve with less computation per frame? or would that be more computation? im not really sure... anyway, awsome tutorial!

[relsoft]

relsoft

relsoft

Visit relsoft's website.

Show relsoft's last posts.

Show general stats for relsoft.

• 
• jelly
• Editor
• Sr. Member
• Score: 6
• Posts: 434

Sorry for necroing this thread.

But I implemented this tutorial using bezier-splines. Worked like a charm but I need some help.

Anyone know how to calculate the differential of a bezier spline? The "dx and dy" Motorherp was referring to.

Thanks!

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Sorry for necroing this thread.

But I implemented this tutorial using bezier-splines. Worked like a charm but I need some help.

Anyone know how to calculate the differential of a bezier spline? The "dx and dy" Motorherp was referring to.

Thanks!

Which kind of bezier spline have you used?  There's a fair number of types such as linear, quadratic, cubic etc.  Might be easiest if you post up the equations you've used and I'll try and calculate the differential for you if you want.  Its been a while since I've flexed my calculus muscles but I'll give it a crack

[mpersano]

mpersano

mpersano

Visit mpersano's website.

Show mpersano's last posts.

Show general stats for mpersano.

• 
• Full Member
• Score: 2
• Posts: 101

Anyone know how to calculate the differential of a bezier spline? The "dx and dy" Motorherp was referring to.

The easiest way to find the derivative of the curve at t is to evaluate it at P(t) and P(t + e), where e is a very small number. Then subtract P(t + e) from P(t) and normalize. This works for any curve, not just bezier splines.

I suppose you could also find a closed-form solution, but you'd need a bit of calculus.

[relsoft]

relsoft

relsoft

Visit relsoft's website.

Show relsoft's last posts.

Show general stats for relsoft.

• 
• jelly
• Editor
• Sr. Member
• Score: 6
• Posts: 434

Sorry for necroing this thread.

But I implemented this tutorial using bezier-splines. Worked like a charm but I need some help.

Anyone know how to calculate the differential of a bezier spline? The "dx and dy" Motorherp was referring to.

Thanks!

Which kind of bezier spline have you used?  There's a fair number of types such as linear, quadratic, cubic etc.  Might be easiest if you post up the equations you've used and I'll try and calculate the differential for you if you want.  Its been a while since I've flexed my calculus muscles but I'll give it a crack

Thanks for the offer. Here's the bezier-spline equation:
Sorry, I prototyped it in basic.

Code:

function Bezier(byval p0 as Single, byval p1 as Single, byval p2 as Single, byval p3 as Single, byval t as single) as Single
   
    dim as single bez
   
    'A = p1
    'B = p0
    'C = p3
    'D = p2
               
    dim as single b = 1 - t
    dim as single b2 = b * b
    dim as single b3 = b * b * b
   
    dim as single t2 = t * t
    dim as single t3 = t * t * t
   
           
    bez = p1 * b3 + 3* p0 *(b2) * t + 3 * p3 *(b) * (t2) + p2 * (t3)
   
    return bez

 
   
end function

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Rightio, if I've calculated this correctly the derivative of your bezier should look like:

a = p₀(1 - 4t + 3t²)
b = p₁(2t - 1 - t²)
c = p₂t²
d = p₃(2t - 3t²)

bez_derivative = 3(a + b + c + d)

That should give you the rate of change of position along the curve if you run that for the x and y components.  Normlise the x,y you get into a unit length vector to get the direction.  Let me know if that works

[relsoft]

relsoft

relsoft

Visit relsoft's website.

Show relsoft's last posts.

Show general stats for relsoft.

• 
• jelly
• Editor
• Sr. Member
• Score: 6
• Posts: 434

Fantastic!!! Works great!! Thanks!!!

Even on 20.12 fixed point math, it worked flawlessly!

mpersano: I used to do it that way but my rotations are jumpy.

[IIporpammep]

IIporpammep

IIporpammep

Show IIporpammep's last posts.

Show general stats for IIporpammep.

• 
• Newbie
• Score: 0
• Posts: 4

Hello, motorherp, thanks for this tutorial, it's very usefull!
I have a problem with implementation,t always smaller 1.
Here is how I create a table.

Code:

         
                StreamWriter stream = File.CreateText(saveFileDialog1.FileName);
                // Write control points to file
                stream.WriteLine(Points.Count); 
                for (int i = 0; i < Points.Count; i++)
                {
                    stream.WriteLine(Points[i].X + " " + Points[i].Y);
                }
               
               
                int j = 0;
                int Rate = 11; // Number of Slices +1 per segment
                stream.WriteLine((Points.Count - 3) * Rate); //  per all segments
                float Length= 0;
                Point P1 = Points[1];
                Point P2;
               
                while (j < Points.Count - 3)
                {
                    float f = 0;
                    int q = 0;
                    while (q < Rate)
                    {

                        if (q == 0)
                        {
                            if (j == 0)
                            {
                                stream.WriteLine(P1.X + " " + P1.Y + " " + f.ToString() + " 0");
                              }
                            else
                            {
                                stream.WriteLine(P1.X + " " + P1.Y + " " + f.ToString() + " " + Length.ToString());
                     
                            }
                            f += 1f / (Rate - 1);
                       
                        }
                        else
                        {
                            P1 = CatmullRom(Points[j], Points[j + 1], Points[j + 2], Points[j + 3], f);
                            P2 = CatmullRom(Points[j], Points[j + 1], Points[j + 2], Points[j + 3], f - 1f / (Rate - 1));
                            Length+= (float)Math.Sqrt((P1.X - P2.X) * (P1.X - P2.X) + (P1.Y - P2.Y) * (P1.Y - P2.Y));
                            stream.WriteLine(P1.X + " " + P1.Y + " " + f.ToString() + " " + Length.ToString());
                            f += 1f / (Rate-1);

                        }
                           
                        q++;
                    }
                   
                    j += 1;
                }

            stream.Close();

The table looks like this:
5
162 516
210 178
636 182
615 526
957 524
22
210 178 0 0
239 163 0.1 32.20248
278 151 0.2 73.0069
324 143 0.3 119.6974
374 138 0.4 169.9467
427 137 0.5 222.9562
479 139 0.6 274.9946
529 145 0.7 325.3533
573 153 0.8000001 370.0747
609 166 0.9000001 408.35
636 182 1 439.7347
636 182 0 439.7347
650 204 0.1 465.8116
654 234 0.2 496.0771
651 271 0.3 533.1985
642 311 0.4 574.1985
630 354 0.5 618.8415
618 396 0.6 662.5222
608 437 0.7 704.7241
603 473 0.8000001 741.0696
604 504 0.9000001 772.0858
615 526 1 796.6825

In my game I load this table, than I move my object on curve, but when object reaches the end of first segment
, it jumps to the start of first segment, 'cause t always smaller 1, than it moves on first segment to the end.
Here is code of moving object:

Code:

  Vector2 Position; // Position of object
  float t=0;
  float Distance = 0;
  int SegmentNum = 0;
  int CurrentPoint;
  void  MoveOnSmoothCurve(SmoothCurve Curve,float Speed)
        {
         
            if (SegmentNum < Curve.ControlPoints.Count - 3)
            {
                  Distance += Speed;
                   while (Distance > Curve.Length[CurrentPoint + 1])
                {
                    CurrentPoint++;

                }
                  t = Curve.t[CurrentPoint] + ((Distance - Curve.Length[CurrentPoint]) / (Curve.Length[CurrentPoint + 1] - Curve.Length[CurrentPoint])) * (Curve.t[CurrentPoint + 1] - Curve.t[CurrentPoint]);
            if (t > 1f)
            {
                SegmentNum += (int)t;
                 t -= (int)t;
            }
                  Position = Vector2.CatmullRom(Curve.ControlPoints[SegmentNum], Curve.ControlPoints[SegmentNum + 1], Curve.ControlPoints[SegmentNum + 2], Curve.ControlPoints[SegmentNum + 3], t);
       }

I've tried consider length of segment, but when object pass first segment end, it jumps to the start of third segment move little bit , then jumps to the start of second segment and normaly moves to the third segment.

Code:

void  MoveOnSmoothCurve(SmoothCurve Curve,float Speed)
        {
         
            if (SegmentNum < Curve.ControlPoints.Count - 3)
            {
                  Distance += Speed;
              if (Distance > Curve.Length[10 * (SegmentNum + 1)]&& SegmentNum + 1 < Curve.ControlPoints.Count - 3)
                {
                     SegmentNum += 1;
                }
                   while (Distance > Curve.Length[CurrentPoint + 1])
                {
                    CurrentPoint++;

                }
                  t = Curve.t[CurrentPoint] + ((Distance - Curve.Length[CurrentPoint]) / (Curve.Length[CurrentPoint + 1] - Curve.Length[CurrentPoint])) * (Curve.t[CurrentPoint + 1] - Curve.t[CurrentPoint]);
                  Position = Vector2.CatmullRom(Curve.ControlPoints[SegmentNum], Curve.ControlPoints[SegmentNum + 1], Curve.ControlPoints[SegmentNum + 2], Curve.ControlPoints[SegmentNum + 3], t);
       }

Thanks!
P.S Sorry for my English it's not my native language.

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Hi.  It seems your understanding is correct.  Like you say, for any segment the t values should always be between 0 and 1.  The problem is in how you are updating your position in the table since you are relying on t being greater than 1 to update your segment number.  In your first example, seems to me that there is no need to be tracking segment number seperately.  You're already correctly incrementing your 'CurrentPoint' index which itself is keeping track of your position in the table and hence you should use the value of 'CurrentPoint' to retreive your control points to feed the spline equation.

[IIporpammep]

IIporpammep

IIporpammep

Show IIporpammep's last posts.

Show general stats for IIporpammep.

• 
• Newbie
• Score: 0
• Posts: 4

Sorry, I didn't understand you, should I replace SegmentNum to expression with CurrentPoint in this line

Code:

   Position = Vector2.CatmullRom(Curve.ControlPoints[SegmentNum], Curve.ControlPoints[SegmentNum + 1], Curve.ControlPoints[SegmentNum + 2], Curve.ControlPoints[SegmentNum + 3], t);
         

Thanks!

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

No it shouldn't be a direct substitution, but since you are already tracking your current position in the table you can calculate easily which segment index that belongs to since you also know how many times you sampled each segment.

For example, if the number of table entries you made for each segment was 'n', then knowing your current position in the table you can relate this back to the correct segment index using:

int segmentIndex = currentPoint / n;

[IIporpammep]

IIporpammep

IIporpammep

Show IIporpammep's last posts.

Show general stats for IIporpammep.

• 
• Newbie
• Score: 0
• Posts: 4

Many thanks for your help, now everything works fine!!!
Thank you for taking the time to me!

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Not a problem  .  Good luck with your game

[IIporpammep]

IIporpammep

IIporpammep

Show IIporpammep's last posts.

Show general stats for IIporpammep.

• 
• Newbie
• Score: 0
• Posts: 4

Thanks again, good luck you too!!!

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

Thanks for the many great tutorials and info you've posted on here

I was wondering however if you could post a quick java implementation of this. I've not had much experience with curved line maths etc (but just enough to look things up and generally understand them) I'm really confused with these however.

Do you have a class for each spline (or a class with an array of splines) as well as the generated tables?

So each object can have any predetermined splines assigned to it, but theyre NOT made on the fly during the game (or during object instantiation?)

A quick java prototype would be so so helpful

edit://
I've found some info relating to my coding environment (namely Processing/Java) http://forum.processing.org/topic/can-toxi-spline2d-be-use-for-more-than-vector-positions#25080000000749048

With the Toxiclibs library it seems you can:

• Create a 2D spline (s = new Spline2D())
• Add points to this with (s.add(new Vec2D(0,0))
• Can computeVertices(resolution) to get the points along the spline

(Class reference here: http://toxiclibs.org/docs/core/toxi/geom/Spline2D.html )

Im having a read through your post again with the above in mind now, but if you can make any advice relate to this that would be great!

Question:
The very last bit of code i dont really understand
I have a List<Vec2D> with all the 100 points along the spline, and another List<Float> for the lengths at each point
How much does 't' increment by? And how do you do this last bit? Id love to get this movement system working

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Hi XYX.  With regards to your questions:

I was wondering however if you could post a quick java implementation of this. I've not had much experience with curved line maths etc (but just enough to look things up and generally understand them) I'm really confused with these however.

I'm not particularly experienced with java so I'm afraid I cant help you out here.  Also posting up finished implementations sort of defeats the point of what I was trying to achieve here.  These tutorials are really intended as learning resources so people who are interested can create their own implementations to their needs and in the language of their choice.

Do you have a class for each spline (or a class with an array of splines) as well as the generated tables?

This is really down to your own prefence and needs, you could do it either way.  Personally I prefer for each spline to be its own class but which can contain any number of spline nodes.

So each object can have any predetermined splines assigned to it, but theyre NOT made on the fly during the game (or during object instantiation?)

There's nothing to stop you from making splines and their tabulated data at run time if your game requires splines which cant be predetermined before run time.  For most scenarios however you will often know before hand the shape of the needed splines and thus in those cases it makes sense to build them as an offline process and load them into your game since tabulating them on the fly could be expensive.

edit://
I've found some info relating to my coding environment (namely Processing/Java) http://forum.processing.org/topic/can-toxi-spline2d-be-use-for-more-than-vector-positions#25080000000749048

With the Toxiclibs library it seems you can:

• Create a 2D spline (s = new Spline2D())
• Add points to this with (s.add(new Vec2D(0,0))
• Can computeVertices(resolution) to get the points along the spline

(Class reference here: http://toxiclibs.org/docs/core/toxi/geom/Spline2D.html )

Im having a read through your post again with the above in mind now, but if you can make any advice relate to this that would be great!

I dont have any experience of Toxiclibs sorry, cant really help you there.

Question:
The very last bit of code i dont really understand
I have a List<Vec2D> with all the 100 points along the spline, and another List<Float> for the lengths at each point
How much does 't' increment by? And how do you do this last bit? Id love to get this movement system working

I think you've misunderstood the idea behind what I've described.  The intention is that you program would track arc-length along the spline for each object following the spline.  Its this arc-length that you would increment according to the desired speed of your object.  You then look up the associated value of 't' for the current arc-length using the table of length data you tabulated as described about half way through the tutorial.  Once you've determined the 't' value for your desired arc-length, you can then plug that 't' into the spline equations to get your objects position co-ordinates.

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

Thanks very much for the response!

Its this part i dont understand fully:

I think you've misunderstood the idea behind what I've described.  The intention is that you program would track arc-length along the spline for each object following the spline.  Its this arc-length that you would increment according to the desired speed of your object.  You then look up the associated value of 't' for the current arc-length using the table of length data you tabulated as described about half way through the tutorial.  Once you've determined the 't' value for your desired arc-length, you can then plug that 't' into the spline equations to get your objects position co-ordinates.

So:

Code:

float L = 0; //length currently along spline
float S = 0.75; //speed, must be float < 1? or would that just cause it to always move with some calculated points not from the tables?

if(L > 1)
{
  L -= 1; //leaves .float
  currentTableValue++;
  calculate new pos with remainder;
}else{
  calculate with float < 1;
}

Im still confused, what would you do in C++ if you had 2 tables, one of points, one of lengths?

When i get this, ill have a tool to output drawn paths in xml or .dat files

Thanks for your respones

[LorenzoGatti]

LorenzoGatti

LorenzoGatti

Show LorenzoGatti's last posts.

Show general stats for LorenzoGatti.

• 
• Jr. Member
• Score: 5
• Posts: 97

The intention is that you program would track arc-length along the spline for each object following the spline.  Its this arc-length that you would increment according to the desired speed of your object.  You then look up the associated value of 't' for the current arc-length using the table of length data you tabulated as described about half way through the tutorial.  Once you've determined the 't' value for your desired arc-length, you can then plug that 't' into the spline equations to get your objects position co-ordinates.

Im still confused, what would you do in C++ if you had 2 tables, one of points, one of lengths?

You do have a table of points (containing the coordinates of successive spline control points) and a table of lengths (containing the spline parameter t corresponding to various arc lengths): it isn't an extension of the basic algorithm.

I cannot say much about your "code" sample because it is unclear, lacking context, and hard to relate to the full task of

• deciding on a certain arc length (presumably by incrementing a "previous" value to simulate something moving at constant speed along the curve)
• finding a t that approximates the desired arc length (for example by direct lookup or binary search in the lengths table and interpolation between adjacent entries)
• using the spline control points to construct the point of the curve at t

Do you have a working implementation of simple splines, without arc length tricks? Can you use them to animate by simply incrementing t? If you do, approximating arc length parametrization is simply a choice of t values that looks better.

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

Do you have a working implementation of simple splines, without arc length tricks? Can you use them to animate by simply incrementing t? If you do, approximating arc length parametrization is simply a choice of t values that looks better.

This is the very early prototype for a tool I'm coding now, this is what I was trying to get it all to work with:
http://openprocessing.org/visuals/?visualID=45922

We calculate this table for each spline segment by evaluating the position along that segment for lots of small increments of 't'.  If our 't' slices are small enough then we can approximate the little slices of curves between each evaluated point as straight lines.  What this means is that by adding up the lengths of the straight lines we can get an estimate for the arc length at each value of 't' we evaluated.  This pre-calculated table is then loaded into our game so that we can control our objects by incrementing their arc lengths directly giving us absolute control over object speed.

That is what my lengths table is, straight line lengths between the points. And the Vec2D list is the table of positions.

Very sorry about how rough the code is for the prototype, you can view the source if you click the relevant button, and the generated 'join' is not the correct formula yet to make a smooth curve

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

[adding up]

Ok, it looks like one thing you might be doing wrong which could be what you're struggling with is that the aim is not to store the straight line lengths between the points but to store the accumulated length along the spline:

We calculate this table for each spline segment by evaluating the position along that segment for lots of small increments of 't'.  If our 't' slices are small enough then we can approximate the little slices of curves between each evaluated point as straight lines.  What this means is that by adding up the lengths of the straight lines we can get an estimate for the arc length at each value of 't' we evaluated.  This pre-calculated table is then loaded into our game so that we can control our objects by incrementing their arc lengths directly giving us absolute control over object speed.

Therefore your first point will be length zero and your last point will be the total length of the spline.  Once you have this done you've successfully reparameterized the spline and you simply need to continue with the rest of the tutorial.  IE:

- For a given length along the spline you wish to know the position for, you look up that length in your table and get the corresponding 't' value (note this will likely involve some interpolation as described in the tutorial since its unlikely your table will contain an entry for that exact length).

- Now you plug that value of 't' into the spline equations given towards the top of the tutorial to calculate the position co-ordinates.

Job done.

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

Thanks again for your response and indeed job done this time!

Ok, it looks like one thing you might be doing wrong which could be what you're struggling with is that the aim is not to store the straight line lengths between the points but to store the accumulated length along the spline:

The lengths were being done correctly in this function:

Code:

void calcDists(List<Vec2D> v)
{
  arcLength = 0;
  lengths.clear();
  for (int i = 0; i < v.size() - 1; i++)
  {
    if (i > 0) {
      arcLength += dist(v.get(i-1).x, v.get(i-1).y, v.get(i).x, v.get(i).y);}
    lengths.add(arcLength);
  }
  println(lengths + " length");
}

The thing that confused me was t0 and t1 being used in such a way since for me they are Vec2Ds (ie (float,float)) and cannot be used in an expression that starts "t (single float) = Vec2D calcs"

I couldnt quite grasp what values they were, this confused me:

it’s unlikely that our table will contain this exact value of arc length to read off the exact 't' value.

so here 't' is the single float you're incrementing by objects set speed value

This can be done by following this formula where 'a0' and 'a1' are the two closest tabulated values of arc length

so they're single floats too, the number that increments according to speed, all good

and 't0' and 't1' are the corresponding values of 't' for 'a0' and 'a1' respectively

but hang on, here i thought a0 and a1 were values of 't', but in actuality theyre the Vec2Ds at those points along the length 't'

It seems to work fine now, i'll post an updated link to the sketch as an example

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

Errrr what?  No, just no  .  From the sounds of what you're saying you've got nothing right at all, you've really gotten yourself in a mess from the very start.  I dont really know what to suggest, you really just need to clear your mind of the mess you've created and start the tutorial again from the top.  Forget any pre-conceptions you have about how you 'think' this works and just take it slowly and dont skip anything.

Also you might want to try posting your source code here for everything regarding your splines and your attempted reparameterization using the [ code ] tags.  It's clear that you're not really understanding the tutorial but without seeing where you're first going wrong we cant really offer advice.

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

oooh dear

well ill tidy up the code, could you please explain whats wrong with my assumption about those last 3 quotes in the post? the reason i thought its working now is ive set up the objects speed to be 0-5 controlled by (5/width)*mouseX and it seems to maintain that speed even over parts of the spline where the points are visibly further away (where as before moving it +1 through the table values each frame caused the speed to change as you said in the start of the tutorial

all the spline calculations to get the points are already done via a library function for me, as stored as vector points

if t is the incremental value, and you look up the nearest values of the line length to that, then the values you find in the table with that are Vec2D(t0.x,t0.y) and Vec2D(t1.x,t1.y)

theres a couple of other bugs but im sure the speed seems to be working, it still slows down slightly along the join spline but i figured that was an error with that part, or the fact theres 300 points there along a much shorter curve

code will be tidied and ill post it, thanks though

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

could you please explain whats wrong with my assumption about those last 3 quotes in the post?

They're partailly things I've already tried to explain to you in previous replies, and honestly, I really couldn't explain everything you're doing wrong without practically repeating the tutorial in almost its entirety to you.  You're making up new definitions and even types for the parameters I described in the tutorial to make them fit your interpretation when their meaning is already clearly explained in the tutorial.  Really it would be better and easier if you forgot what it is you're doing now and re-read the tutorial again carefuly and objectively.

The reason your implementation probably appears to be working so far is because it sounds like you are creating so so many control points that really you're doing no spline interpolation at all but just hopping from one pre-calculated point to the next.  It's hugely wasteful.

If you post up your full source code I'll give it a scan over and try to work out what it is you're misunderstanding, but I cant really do much else until then sorry

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

[splineFollower -]

The reason your implementation probably appears to be working so far is because it sounds like you are creating so so many control points that really you're doing no spline interpolation at all but just hopping from one pre-calculated point to the next.  It's hugely wasteful.

If you post up your full source code I'll give it a scan over and try to work out what it is you're misunderstanding, but I cant really do much else until then sorry

I've uploaded a much neater version here http://openprocessing.org/visuals/?visualID=45922
Classes:

• splineFollower - this contains the 'interpolation' code (my confused take on it anyway) for the movement
• splinePath - gets a list of control points (4 in this case) and interpolates (actually does that, using a library function) to give "sqrt(path length)*segment modifier" number of positions along the spline, its here the list of lengths is done too
• splinePaths00 - main class, gets input etc, passes splinePath list of control points and segment number, stores the resulting spline paths in a list

A note on your first point there, I've added in that segment modifier this time, hold 'z' and move the mouse, mouseX in relation to width determines the decimal modifier for the number of segments

Using this you can see that the movement is still smooth not hoping between points after all, although the resulting speed is much quicker even if a small value is used

Once the last point of a spline is placed, the mouseX from that position controls the speed of the path follower (you might not see it if its going backwards first) but it moves freely backwards and forwards along it

Hope this is alot easier to read for you, that previous code was dire sorry, and thank you again

(on a side not have you coded many shmups that are about on the net?)[/size]

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

You are totally off, like motorherp expected.
But first lets see if I got your source right:

1. pathLengths is a float array you fill with hundreds of precomputed length values on the spline.
2. your t isn't kept between 0..1 but is rather a float casted to an int to be used as index into said pathLengths array (wait: you use it as index into the splineSegments array...).
3. at the same time that t is used for a0 and a1.
4. t0 and t1 are filled with the precomputed coordinates (not lengths).
5. you got the most inefficient a0/t0/a1/t1 lookup code I ever saw

Okay, let's see:

(1) seems to be okay.

(2) not keeping t inside 0..1 is okay, as long as the rest of your code takes this into account.
But now the bulls#%& starts Because later you don't look up the pathLengths but splineSegments (t0= / t1= )!

(3) a0=i respectively a1=i is just wrong: It should be

'a0' and 'a1' are the two closest tabulated values of arc length

but in your case a0 and a1 become t-values instead of pathLengths[t]-values... (since i is nothing more than a "rounded" t in your case).

(4) Similar t0 and t1 are wrong. Those you fill with the precomputed POSITIONS (?) close to t, while they should be the t that was used to create those table-values.

(5) Why don't you exploit the fact that your t is not kept in the range of 0..1? Because here it would ease things a lot: just cast t to an int and use that as index into your tables (with a range check for safety). No for-loop needed at all.

Let's compare your code

Code:

float tX = t0.x + ((a - a0) / (a1 - a0)) * (t1.x - t0.x);
float tY = t0.y + ((a - a0) / (a1 - a0)) * (t1.y - t0.y);

with the tutorial's formula

Code:

t = t0 + ((a - a0) / (a1 - a0)) * (t1 - t0)

Why do you come up with a 2D vector? The formula is about time and distance, not positions in 2D space.

So essentially it boils down to:

- t0 and t1 have to be float, not Vec2D
- tX and tY are wrong, you just need one single float result_t.
- a0 and a1 have to be values out of your pathLengths table.
- t0 and t1 have to be the t that was used to compute the pathLengths
- since your t is not kept in the range of 0..1 your result_t won't be neither. You have to take that into account when using that value later.

Phew.

EDIT: I first thought you didn't start your pathLength array at 0-distance when in fact you do. Nevertheless that doesn't change anything overall.

[XYX]

XYX

XYX

Show XYX's last posts.

Show general stats for XYX.

• 
• Newbie
• Score: 0
• Posts: 11
• human is the music, natural is the static...

Thanks hornet, that has cleared up a lot of this topic for me, and pointed out some pretty major oversights!

Code:

void draw()
  {
    float px = 0.0f;
    float py = 0.0f;
    speed = (1.0f/(width - path.splineSegments.get(path.splineSegments.size()-1).x ))*(mouseX - path.splineSegments.get(path.splineSegments.size()-1).x);
    //Speed = mouseX from last segment point (+ and -);
    t += (speed);
    if(t > 1){
    a += 1;
    t -= 1;
    }

  if(a < (path.splineSegments.size()-2)){
    float a0 = path.pathLengths.get((int)a);
    float a1 = path.pathLengths.get((int)a+1);
    float t0 = (int)a;
    float t1 = (int)a+1;
    float aL = a0 + ((a1 - a0) * t);
    //^ Actual desired length(?)
    t = t0 + ((aL - a0) / (a1 - a0)) * (t1 - t0);
    Vec2D p0 = path.splineSegments.get((int)t0 - 1);
    Vec2D p1 = path.splineSegments.get((int)t0);
    Vec2D p2 = path.splineSegments.get((int)t1);
    Vec2D p3 = path.splineSegments.get((int)t1+1);
    px = 0.5f * ((2.0f * p1.x) + (p2.x - p0.x)*t + (2.0f*p0.x - 5.0f*p1.x + 4.0f*p2.x - p3.x)*t*t + (3.0f*p1.x + p3.x - p0.x - 3.0f*p2.x)*t*t*t);
    py = 0.5f * ((2.0f * p1.y) + (p2.y - p0.y)*t + (2.0f*p0.y - 5.0f*p1.y + 4.0f*p2.y - p3.y)*t*t + (3.0f*p1.y + p3.y - p0.y - 3.0f*p2.y)*t*t*t);
 
  }

  ellipse(px, py, 20, 20);

  }

seems to be as close as i can get reading your previous post and the others over and over, it "seems" to be doing everything that's been said but the behaviour is well off now

aL is in there because a gets + 1 each time t > 1, but then later on a becomes the desired length (in the t = equation) so i made that aL and a the position/length/key index

anything appear wrong with that? :S

i realised the 'segment' needs 4 points, the middle 2 you move between but i think ive done all that correctly

note
t is always < 1 this time, and speed is always a float < 1 too, it seems to have to be like that else for instance:
if(speed > 1 ie 4.35)
while t > 1
a += 1;
t -= 1;

thatll move 2 key points, but even if the distance between point 2-3 is 700px for instance

[motorherp]

motorherp

motorherp

Visit motorherp's website.

Show motorherp's last posts.

Show general stats for motorherp.

• 
• Hero Member
• Score: 12
• Posts: 827
• shmupet

You're still getting confused between 't' and arc-length and which of these you should be tracking/incrementing and which you should be finding from your table lookup and interpolation.  Refer back to this reply:

The intention is that your program would track arc-length along the spline for each object following the spline.  Its this arc-length that you would increment according to the desired speed of your object.  You then look up the associated value of 't' for the current arc-length using the table of length data you tabulated as described about half way through the tutorial.  Once you've determined the 't' value for your desired arc-length, you can then plug that 't' into the spline equations to get your objects position co-ordinates.

[Hornet600S]

Hornet600S

Hornet600S

Visit Hornet600S's website.

Show Hornet600S's last posts.

Show general stats for Hornet600S.

• 
• Sr. Member
• Score: 14
• Posts: 324
• Motocycle crusher

Damn, I wrote BS myself above How could that happen? Maybe because I was overwhelmed by so much ugly Java...
Since I told you wrong I'll correct myself in addition to motorherps comment.

Your pathLength table should be build differently.
Instead of storing the arc-length in a simple table, you should build a list containing pairs of arc-length-value and t-that-created-that-value.

Then, when moving an object on that path (by adjusting an ARC-LENGTH-variable, get rid of the t, that's what the whole story is about), you scan that list for the two arc-length entries, where your current value is in between - and get the t's you stored with those. For simplicity do the scan via a simple for-loop for now until you got it working, later replace that by a binary search or so.

And then interpolate between the 2 pairs to get a t that better matches your current arc-length-variable.