Catmull rom spline - parametrization

[fabio.portieri]

Hello everybody
I'm quite a newbie at opengl and 3d math programming, i'm attempting to do a simple animation through a catmull rom spline, i did a quick attempt that works good on a simple ogl (jogl) test case i did, but not so good when i ported the algorithm to my worldwind based app.
Meanwhile i discovered that a correct representation of the spline is usually done via some parametrization functions, so i tried to study a bit of uniform parametrization (and i think i got it) and the arc length parametrization (i don't get it completely yet)

What am i currently missing is this: let's suppose i have a s(t) arc length parametrization already done, and a f(t) uniform parametrization.
Afaik, s(t) returns the arc length and by doing the inverse i can get the t factor. But, how do i get the point on the spline, when i know the arc length distance, i.e. how do i map s(t) and f(t) togheter?
just using the t retrieved by s^-1(arcLength) seems not correct by looking at this:
http://www.algorithmist.net/arclengthparam.html (page 5) since the two parametrization seems to define different points in the spline for the same t value

Surely i'm confused quite a lot, i can't neither find complete tuts or sample code so far i only got maths article but it's not so easy for me to port those informations into working code, so any help will be greatly appreciated.
Thanks in advance

[david_f_knight]

I'm not specifically familiar with the Catmull rom spline, but the technique I believe you are asking about can be used for any parametrized curve.

Here's the general idea:
You've got one parametric curve defined however you please. The arc length is not constant for a given change in the parameter, eg., the arc length of the curve evaluated from t to t+0.1 is not the same as the arc length of the curve evaluated from s to s+0.1 (unless t = s).

So, what to do if you want to go, say, one half of the arc length when you have the parameter go one half of the way, too?

You define a function that maps arc length to the parameter of the first curve.

First, build a table of different values for the parameter of the first curve and for the arc length of the first curve from its start to the point on the curve at each of those parametric values. You will have something like this:

   t   arc len
  ---  -------
  0.0    0.0
  0.1    1.1
  0.2    2.0
  0.3    2.9
  0.4    3.3
  0.5    3.5
  0.6    3.6
  0.7    3.7
  0.8    4.1
  0.9    5.5
  1.0    8.8

Next, you need to define some type of function to map arc length back to the parameter. There are infinitely many ways of defining such a function. The simplest is just to linearly interpolate. (It looks like the article you referenced defines a second Catmull rom spline to represent the arc length function for the first Catmull rom spline. You can do that if you'd like, but you're on your own. I'll explain it in terms of a linear interpolation function. The idea is still pretty much the same.) Linear interpolation is easy to program, fast, and works well provided your table that maps parameter to arc length is fine enough.

So, for example, if you wanted to go to the point that is at the midpoint of your arc, by arc length, you first recognize that the arc length is 8.8 (according to the table in the example above). Half that arc length (where you want to go in our example), is 4.4 . So, you look through the table and see that arc length 4.4 falls between arc lengths 4.1 (at t=0.8) and arc length 5.5 (at t=0.9). You need to interpolate between 4.1 and 5.5 to find your desired point, 4.4, and the parameter t that goes with it. For example:

 s = (4.4 - 4.1) / (5.5 - 4.1)
 s = 0.214285

s is proportionally how far along your desired arc length is between the two known arc lengths. Now, take that s and go that same proportional distance between the parametric t's associated with the arc lengths. You get:

 t = s * (0.9 - 0.8) + 0.8
 t = 0.8214285

There you go. Plug that t into your original curve's equation, and it will evaluate to the point on the arc whose arc length is about half way along the arc from the start of the arc. What you've done is defined a function g(t) that gives a parameter into another function (your Catmull spline) that gives you the point on your spline that is whatever arc length you want. In other words, you've indirectly parametrized the first curve by its arc length.

The value for t that you find is an approximation, because in general the function you use to map arc length to parametric value isn't the same function that defines the relation between them. If you knew what that function was, you could use it and be exact. But then you wouldn't need to go through any of this in the first place. We're assuming you don't know what the true mapping function is.

The next question you might ask is: how do I build that table that maps parameter to arc length? Once again, we assume you don't know the exact formula for arc length (if you knew that, you wouldn't need to do any of this stuff). The answer: estimate it. You can estimate the arc length by evaluating your curve at a number of parametric points along the way (i.e., the first column in the table), and just add together the length of each straight line segment between all the points on the curve at those parametric values. Once again, the smaller each step, and the more of them, the more accurate your estimated arc length will be.

You have to define this table only once, and you can see it will take a little time. But you can interpolate through the table quickly as many times as you need.

Higher order curves can be used rather than lines to allow using a smaller table, or a spline can be used to represent the information in the table, but the programming is more difficult in those cases. If you note, the table's arc length values are monotonically increasing (they have to be -- arc length can never be negative), so you could use a binary search to find where to interpolate very quickly.

[fabio.portieri]

That's great, a fantastic explanation that solved all my doubts
Many thanks, i really appreciate you for taking the time.