Sign in to follow this  
h4tt3n

Cubic splines

Recommended Posts

Hello,

Lately, I've been studying cubic splines in order to be able to make my 2d polygon graphics look more rounded and "organic". I've implemented both Catmull-Rom and Hermite cubic splines successfully, but I'm having trouble understanding something from the [url="http://en.wikipedia.org/wiki/Cubic_Hermite_spline"]wikipedia article[/url]. In the article topic "Interpolating a data set", several methods for choosing a tangent vector is described: finite difference, cardinal spline and catmull-rom spline. A data set (P[sub]k[/sub], t[sub]k[/sub]) for k = 1, ..n can be used to find a tangent, m[sub]k[/sub] for each control point. The trouble is, that both t[sub]k[/sub] and m[sub]k[/sub] are described as tangents, and the article isn't clear about the difference between them, except thart you need to know the value of t[sub]k[/sub] to calculate m[sub]k[/sub]. Could someone please explain what t[sub]k[/sub] represents in the data set (P[sub]k[/sub], t[sub]k[/sub])? The only thing I can think of, is that t[sub]k[/sub] might be an arbitrarily chosen tangent vector set by the user. I've implemented the tangent equations as I assumed they were supposed to, but they return garbage.

Cheers,
Mike

Share this post


Link to post
Share on other sites
The Wikipedia page says "A data set (t[sub]k[/sub], [b]p[sub]k[/sub][/b]) for k = 1, ..., n [...]". The t[sub]k[/sub] are values of the parameter ("time"), the [b]p[sub]k[/sub][/b] are the points, and the [b]m[sub]k[/sub][/b] are the tangents. I don't see a problem, other than perhaps that you read it wrong.

Share this post


Link to post
Share on other sites
Okay, maybe I did, but I still don't get it. the t parameter is plugged into the spline equation to find a point on the curve between the control points Pn and Pn+1, where t = 0 equals Pn, t = 1 equals Pn+1, and any value between 0 and 1 gives you the corresponding point on the spline. So, for each spline section Pn, Pn+1 you iterate through the equation with slightly higher values of t for each iteration in order to get a decent representation of the curve between those two points. So, I don't see the meaning of a data set (t[sub]k,[/sub] p[sub]k[/sub]), since no single value of t is assigned to or connected to each control point. What the heck am I missing here? I've implemented all these equations from other articles, but the part on interpolating from the wikipedia article still doesn't make any sense :-)

cheers,
Mike

Share this post


Link to post
Share on other sites
The curve is a mapping from time to points. At time t[sub]n[/sub] the point is p[sub]n[/sub] and at time t[sub]n+1[/sub] the point is p[sub]n+1[/sub]. In order to make the formulas easier, when you actually want to compute the point corresponding to a t between t[sub]n[/sub] and t[sub]n+1[/sub], you actually reparametrize that piece of the curve to use times between 0 and 1 (by computing (t-t[sub]n[/sub])/(t[sub]n+1[/sub]-t[sub]n[/sub])).

Does that help?

Share this post


Link to post
Share on other sites
You're right, alvaro. Post deleted for being incorrect and adding confusion! Sorry about that.

Maybe I can still help though. The confusion is that each point p is assigned a parameter scalar t. This t is semantically equivalent to a time value, as alvaro says. That means that if, for example, you multiply all [color=#1C2837][size=2]t[sub]n [/sub][/size][/color]by 2 for each n, then you have doubled the velocity (and the length of each tangent) at each point along the curve. The curve would look the same, but something traveling along it would move twice as fast.
[color=#1C2837][size=2][/size][/color] Edited by A Brain in a Vat

Share this post


Link to post
Share on other sites
[quote name='A Brain in a Vat' timestamp='1307393845' post='4820257']
t[sub]k[/sub] is a point there. It isn't an interpolation parameter.[/quote]
You are not helping. t[sub]k[/sub] is a number. If not, I don't know what it would mean to divide by (t[sub]k+1[/sub] - t[sub]k-1[/sub]) (see the Catmull-Rom spline section).

Share this post


Link to post
Share on other sites
Ah, this is weeding out some of the misunderstandings. All the articles I've read so far assumes [i]t [/i]to be in the range [0, 1], which caused some of the confusion. But I still don't understand how to calculate the value of t[sub]n[/sub] for a corresponding point[b] P[/b][sub]n[/sub], if [i]t[/i] isn't normalized. The wikipedia article defines [i]t[/i] like this:

[quote Wikipedia]For interpolation on a grid with points [i]x[/i][sub][i]k[/i][/sub] for [i]k[/i] = 1,...,[i]n[/i], interpolation is performed on one subinterval ([i]x[/i][sub][i]k[/i][/sub],[i]x[/i][sub][i]k[/i] + 1[/sub]) at a time (given that tangent values are predetermined). The subinterval ([i]x[/i][sub][i]k[/i][/sub],[i]x[/i][sub][i]k[/i] + 1[/sub]) is normalized to (0,1) via [i]t[/i] = ([i]x[/i] ? [i]x[/i][sub][i]k[/i][/sub]) / ([i]x[/i][sub][i]k[/i] + 1[/sub] ? [i]x[/i][sub][i]k[/i][/sub]).[/quote]

This is causing me some trouble. If x, x[sub]k[/sub] and so forth are points on a plane - or 2d vectors, if we're talking computer graphics - then what does the division mean? As you mentioned above, Alvaro, you can't divide vectors. If you divided the x and y components separately, you'd get two different values of [i]t[/i] for each point x.

Cheers,
Mike

Share this post


Link to post
Share on other sites
[quote name='h4tt3n' timestamp='1307402633' post='4820296']
Ah, this is weeding out some of the misunderstandings. All the articles I've read so far assumes [i]t [/i]to be in the range [0, 1], which caused some of the confusion. But I still don't understand how to calculate the value of t[sub]n[/sub] for a corresponding point[b] P[/b][sub]n[/sub], if [i]t[/i] isn't normalized.
[/quote]

So you're saying, what if you are given the points in order but not the corresponding t's?

Sometimes it makes sense to normalize for constant velocity, meaning you calculate values of t such that the tangent at every point along the curve will be of the same length.

Sometimes you don't renormalize at all, and assume that the interval between each point is the same. In this case you might not end up with constant velocity, but often you don't need it.

Share this post


Link to post
Share on other sites
[quote name='h4tt3n' timestamp='1307402633' post='4820296']
[quote Wikipedia]For interpolation on a grid with points [i]x[/i][sub][i]k[/i][/sub] for [i]k[/i] = 1,...,[i]n[/i], interpolation is performed on one subinterval ([i]x[/i][sub][i]k[/i][/sub],[i]x[/i][sub][i]k[/i] + 1[/sub]) at a time (given that tangent values are predetermined). The subinterval ([i]x[/i][sub][i]k[/i][/sub],[i]x[/i][sub][i]k[/i] + 1[/sub]) is normalized to (0,1) via [i]t[/i] = ([i]x[/i] ? [i]x[/i][sub][i]k[/i][/sub]) / ([i]x[/i][sub][i]k[/i] + 1[/sub] ? [i]x[/i][sub][i]k[/i][/sub]).[/quote]

This is causing me some trouble. If x, x[sub]k[/sub] and so forth are points on a plane - or 2d vectors, if we're talking computer graphics - then what does the division mean? As you mentioned above, Alvaro, you can't divide vectors. If you divided the x and y components separately, you'd get two different values of [i]t[/i] for each point x.
[/quote]

The Wikipedia article is not very consistent with its notation: Those x[sub]k[/sub] seem to be the same as the t[sub]k[/sub] in other parts of the article.

Share this post


Link to post
Share on other sites
Okay, now I think I understand it. I had a growing suspicion something wasn't quite right with the wikipedia article, and that this was the cause of the confusion. As I understand it, the [i]t[/i] parameter can have any arbitrary value, but for simplicity it can be normalized to (0, 1). If you want consistent velocity along the spline, the difference between [i]t[/i][sub]n[/sub] and[i] t[/i][sub]n+1[/sub] can be set to the length of the spline section between the corresponding control points by reparametrizing the spline. Or you can use any other odd method for setting the values that you might find useful.

Now it's time to code :-)

Thank you very much for helping me out, both of you.


Cheers,
Mike

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this