I''m sure this one has been discussed before, but after reading everything I can get my hands on, I''ve still not reached a decent solution . I''m not geared up with calculus yet, so papers with pages of figures aren''t helping. I''ve written a *near* working solution, it just has annoying bugs. I''m trying to move an object (train) along a catmull-rom spline (track) at a constant speed. I decided to go for the mathsless approach of creating a lookup table. Currently, it goes a bit like this: I chop up the curve into chunks of equal length. I do this by first getting an approximate length of the curve, then I divide it into the size of my table. Next, I begin an evaluation of the curve in detail (in steps of like 0.0001 for t) and add up the distance travelled at each step. Once I get to a set distance (the chunk size I defined earlier) I shove the current t value into the table, then begin on the next chunk, until I reach the end of the curve. When it comes to moving stuff along the curve, I find out where my object is on the curve in relation to a table entry. (Eg: halfway along the curve means I go halfway into the table). I pull out the t value stored there, plus the next one along, and convert ''em to coords. I use the remainder from the distance-table division to interpolate between these two coordinates and give me a final position. Currently, this lets me draw beautifully curved accurate looking track, and my train moves with constant speed along it, to an extent. There''s two major problems though: Firstly, for very long curves, steps of 0.0001 are just not small enough when generating the table. I find that I end up stepping right past the distance I''m looking for, and therefore each chunk isn''t the same size. The result? The train stutters and jumps along the track at varying speeds as it switches between chunks. I can decrease the step size, but that leads me onto the next problem.. Generating the lookup table is just too damn slow. Since I have to get the distance travelled between each evaluation, I''m doing thousands of square roots. For 20 curves, it takes forever. If I use smaller steps to eliminate the stutter, I may as well go make a cup of coffee while my program initializes.. Is there a better way of tackling this problem or have I missed something? Should I start reading my industrial strength calculus books? David

First of all, a general point. Why recompute the lookup table every time you run the program? Processes that long should be pre-computed and the results saved to a file once you've got the tracks set.

What you really need the arclength parametrized version of your spline. This is a pretty common problem in computer graphics... you should be able to grab a reference on it from any reasonably detailed book that goes over splines.

I don't recall there being a generalized way to find this, so you'll have to use some approximation scheme to do it. One simple way is to get a bunch of sample points off the spline, and then run your favorite curve fit algorithm on them as data points. You can usually integrate the fitted curve you get back. That'll give you a pretty fast approximation of your arclen-spline to use at run time, and you can ditch the table.

[edited by - cheesegrater on June 14, 2002 3:51:59 PM]

I came across an article on catmull rom splines a while ago. I don''t really know a whole lot about them myself and I haven''t had the time to try them out for myself, but you might want to take a look at this guys tuturial here.

Moe''s site

Assume that your curve s is parametrised by u (u is not time) and has form s(u). You desire to move along s with constant speed, so that ^ds/dt = constant. We have that

ds   ds du-- = -- --dt   du dt   

The parametric speed, ^ds/_du, at a point on the curve is equivalent to the rate of change of a radius vector from your coordinate origin to that point on the curve. So, at any point you can determine

du   ds du-- = -- --dt   dt ds   

So, preprocess your curve to get a table of coordinates versus parameter u. Then, at each point - starting at your starting value of u - determine ^ds/_du and hence ^du/_dt. The next point on the track is given by s(current_u + ^du/_dt*Frame_Interval)

I hope this helps.

Timkin

[edited by - Timkin on June 14, 2002 10:35:57 PM]

quote:

---

Original post by CheeseGrater

---

Thanks for the quick reply!

quote:

---

First of all, a general point. Why recompute the lookup table every time you run the program? Processes that long should be pre-computed and the results saved to a file once you''ve got the tracks set.

---

My first attempt at building the tracks involved defining lots of straight sections of track joined so closely that it looked like a smooth curve. It worked fine, except the files needed to store the data were bigger than I wanted. Storing the lookup table really just takes me back to square one and eliminates the reason I wanted to use splines. Although the tables aren''t *that* big, its still more than I need considering how many seperate curves I could have.

quote:

---

You''ll have to use some approximation scheme to do it. One simple way is to get a bunch of sample points off the spline, and then run your favorite curve fit algorithm on them as data points. You can usually integrate the fitted curve you get back. That''ll give you a pretty fast approximation of your arclen-spline to use at run time, and you can ditch the table.

---

This would be the perfect situation if I could get it working. Could you point me to anywhere I could find more info on this? Any good books you could recommend?

Cheers,

David

quote:

---

(Moe) but you might want to take a look at this guys tuturial here.

---

Thanks for the link, the code is interesting. I wonder how the DX catmull rom function can make the demo move smoothly? I'll need to take that one apart for a look..

quote:

---

(Timkin) Assume that your curve s is parametrised by u (u is not time) and has form s(u)

---

This is where my knowledge of maths fails me. My curve is parameterised by time, s(t). How do I reparameterise for u?

David

[edited by - downward_spiral on June 16, 2002 12:24:50 PM]

Well, you said your level-files got too big. Have you tried to save them compressed and decompress them when loading. Although I don''t know where, there are surely free libs with implementation of Lempel-Ziv or something similar. also saving your data binary and not as text can save a huge amount of space if you haven''t already done so. Of course, this would waste a lot of work...


Yesterday we still stood at the verge of the abyss,
today we''re a step onward!

quote:

---

Original post by downward_spiral
This is where my knowledge of maths fails me. My curve is parameterised by time, s(t). How do I reparameterise for u?

---

Well, actually your curve is just parameterised by a free parameter, which you are calling t. How did you generate your parametric curves? If you''re just using a standard spline formula, then your parameter is the same as u and is not time. This may be the source of your problem... assuming that your parameter is time when it isn''t. If you were to traverse a nonlinear parametric curve at constant parameter intervals per second then motion along the curve would not be smooth. Indeed, in bends the motion will slow down and along straight sections it will speed up. This is probably the source of your ''jerky'' simulation. If it is, then you need to apply the maths from my last post. If you need help with that, just holler.

Cheers,

Timkin

quote:

---

Original post by Timkin
If you're just using a standard spline formula, then your parameter is the same as u and is not time.

---

I'm with you now. In that case, my code is already doing what you suggested.

quote:

---

Indeed, in bends the motion will slow down and along straight sections it will speed up. This is probably the source of your 'jerky' simulation. If it is, then you need to apply the maths from my last post. If you need help with that, just holler.

---

I understand that if the curve is evaluated with equal increments of t(or u), the actual distances will not be equal. This is why I'm precomputing a lookup table like you mentioned, with real distance related to t/u.

The jerk is caused when preprocessing the curve. I lose accuracy on very long curves because my steps in t/u during the preprocess are not small enough. The process steps right past the point on the curve that I wanted to gain the t/u value for.

This means the distances between consecutive table entries are not quite equal for big curves, causing a noticable shift in speed in certain places when using the table to get my real coords. I'm thinking about rewriting the table generator to use a binary search for the *exact* point I want.. it should be quicker too.

In any case, I'd rather bin the table, since I'm just far too 8bit to accept the speed or space loss when there is another way

Anyway, thanks for the reply!

David

[edited by - downward_spiral on June 17, 2002 11:52:27 AM]

Okay, so as I understand it then, your error is coming from this:

quote:

---

Excerpted from a post by downward_spiral
I chop up the curve into chunks of equal length. I do this by first getting an approximate length of the curve, then I divide it into the size of my table.

---

So, if you had a more accurate method of chopping up your curve, you would have less jerky motion. What method are you using to approximate your curves? I presume its one that is less accurate the longer the curve?

Cheers,

Timkin