Jump to content

  • Log In with Google      Sign In   
  • Create Account


Cubic splines


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 h4tt3n   Members   -  Reputation: 997

Like
0Likes
Like

Posted 06 June 2011 - 01:14 PM

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 wikipedia article. 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 (Pk, tk) for k = 1, ..n can be used to find a tangent, mk for each control point. The trouble is, that both tk and mk are described as tangents, and the article isn't clear about the difference between them, except thart you need to know the value of tk to calculate mk. Could someone please explain what tk represents in the data set (Pk, tk)? The only thing I can think of, is that tk 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

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12485

Like
0Likes
Like

Posted 06 June 2011 - 01:53 PM

The Wikipedia page says "A data set (tk, pk) for k = 1, ..., n [...]". The tk are values of the parameter ("time"), the pk are the points, and the mk are the tangents. I don't see a problem, other than perhaps that you read it wrong.

#3 h4tt3n   Members   -  Reputation: 997

Like
0Likes
Like

Posted 06 June 2011 - 02:42 PM

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 (tk, pk), 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

#4 Álvaro   Crossbones+   -  Reputation: 12485

Like
1Likes
Like

Posted 06 June 2011 - 02:52 PM

The curve is a mapping from time to points. At time tn the point is pn and at time tn+1 the point is pn+1. In order to make the formulas easier, when you actually want to compute the point corresponding to a t between tn and tn+1, you actually reparametrize that piece of the curve to use times between 0 and 1 (by computing (t-tn)/(tn+1-tn)).

Does that help?

#5 A Brain in a Vat   Members   -  Reputation: 313

Like
1Likes
Like

Posted 06 June 2011 - 02:57 PM

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 tn 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.

Edited by A Brain in a Vat, 06 June 2011 - 03:32 PM.


#6 Álvaro   Crossbones+   -  Reputation: 12485

Like
0Likes
Like

Posted 06 June 2011 - 03:02 PM

tk is a point there. It isn't an interpolation parameter.

You are not helping. tk is a number. If not, I don't know what it would mean to divide by (tk+1 - tk-1) (see the Catmull-Rom spline section).

#7 h4tt3n   Members   -  Reputation: 997

Like
0Likes
Like

Posted 06 June 2011 - 05:23 PM

Ah, this is weeding out some of the misunderstandings. All the articles I've read so far assumes t 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 tn for a corresponding point Pn, if t isn't normalized. The wikipedia article defines t like this:

For interpolation on a grid with points xk for k = 1,...,n, interpolation is performed on one subinterval (xk,xk + 1) at a time (given that tangent values are predetermined). The subinterval (xk,xk + 1) is normalized to (0,1) via t = (xxk) / (xk + 1xk).


This is causing me some trouble. If x, xk 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 t for each point x.

Cheers,
Mike

#8 A Brain in a Vat   Members   -  Reputation: 313

Like
0Likes
Like

Posted 06 June 2011 - 05:39 PM

Ah, this is weeding out some of the misunderstandings. All the articles I've read so far assumes t 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 tn for a corresponding point Pn, if t isn't normalized.


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.

#9 Álvaro   Crossbones+   -  Reputation: 12485

Like
0Likes
Like

Posted 07 June 2011 - 08:58 AM

For interpolation on a grid with points xk for k = 1,...,n, interpolation is performed on one subinterval (xk,xk + 1) at a time (given that tangent values are predetermined). The subinterval (xk,xk + 1) is normalized to (0,1) via t = (xxk) / (xk + 1xk).


This is causing me some trouble. If x, xk 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 t for each point x.


The Wikipedia article is not very consistent with its notation: Those xk seem to be the same as the tk in other parts of the article.

#10 h4tt3n   Members   -  Reputation: 997

Like
0Likes
Like

Posted 07 June 2011 - 09:35 AM

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 t 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 tn and tn+1 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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS