How do I code a spline path?

[Blessman11]

Hi

I'm trying to create a spline path as seen in the link below but trying to find the fomular to use has been the most difficult aspect since I don't know how to interpolate the points. The spline will be used to create a path for a game I'm making were I need objects to follow such a path (is sonething a bit similar to zuma deluxe: http://www.terragame.com/screens/zuma_deluxe.jpg ).

http://www.cs.berkeley.edu/~sequin/CS184/IMGS/SplineTypes.JPG

Plus what code could I use to generate such a path.

[ne555]

Interpolation
c_j = (1-\alpha) a_j + \alpha b_j

Look at the blossoming algorithm. (and De Casteljau)

[Blessman11]

@ne555 thanks, but after scouring through Google for the algorithms I was met with maths I haven't learnt yet (currently doing A-level maths whilst on degree). Its just taking ages plus it usually filled with jargon that leads to jargon on most sites.


But now I've realised that I'm looking for the Hermite Spline algorithm instead, is yours it? I dont quite understand it yet since I don't understand what

alpha

and

a_j

and

b_j

are. Is

alpha

part of the distance between the 2 points and

a_j & b_j

?

[ne555]

a, b and c are points. \alpha is a number
a_j, or a[j] represents one cartesian coordinate of the point
a[0] = x
a[1] = y
a[2] = z
...

That formula is showing how to calculate the coordinates of the interpolation point.
Taking different values for alpha (factor of interpolation) we get different interpolated points.
It could be writted as
c[j] = w1 a[j] + w2 b[j] where w1 + w2 = 1
As you can see, when we interpolate, we assign a weigth to every point. Larger the weigth, the result will be near to that point.
(like an atraction force, if it is negative it will repel it)

So if we take \alpha = 0, we get c = a
\alpha = 1, then c = b
\alpha = 0.5, c is the midpoint.

If you take 0 <= \alpha <= 1 the result will land between the control points (a, b).
else it will land outside.
But always on the straight line that connects 'a' with 'b'


Now, Bézier. Let's just take order 3, that uses 4 control points.
First and last points are the endpoints of the curve.
The other mark the derivatives of the curve at those endpoints. (the arrows)

So p0, endpoint
vector (p1-p0), start direction. Larger its modulo faster will go.

Now you 'interpolate' the 4 points, with De Casteljau algorithm.
And here is something interesting. \alpha is now time.
At time=0 you are at the start (p0), at time=1 you are at the goal (p3)
Intermediate times will give you intermediate positions that are not equally spaced, but that take into account your 'particle' velocity.


You want Hermite. That one ask for continuity of endpoints and its velocities.
So you need to make sure that p3 = q0
and vector(p2-p3) = - vector(q1-q0)

[mik2718]

For a single span cubic hermite I make it

p(t) = (t^3-t^2-t+1)p0 + (t^3-2t^2+t)p1 + (t^3-t^2)p2 + (-3t^3+4t^2)p3

This for a spline starting at p1 and ending at p3. The control point for p0 is p1 and the control point for p3 is p2

You just substitute values for t from 0...1 into the formula, multiplying the vectors p0...p3 by those coefficients

This will work in any dimension.

(Agree about the internet - couldn't understand any of that stuff so worked it out by hand)

[ne555]

Or you apply De Casteljau

q01 = interpola(p0, p1, t);
q12 = interpola(p1, p2, t);
q23 = interpola(p2, p3, t);

ra = interpola(q01, q12, t);
rb = interpola(q12, q23, t);

the_point = interpola(ra, rb, t);

point interpola( point a, point b, double alpha ){
  return (1-alpha)*a + alpha*b; //std::valarray is useful
}

Other good thing is that the line ra;rb is tangent to the curve in 'the_point'

[Blessman11]

@mik2718

p(t) = (t^3-t^2-t+1)p0 + (t^3-2t^2+t)p1 + (t^3-t^2)p2 + (-3t^3+4t^2)p3
How does the formular work for "n" components?

[Blessman11]

Is it just all about repeating these coefficients in a pattern:

(t^3-t^2-t+1)p0 + (t^3-2t^2+t)p1 + (t^3-t^2)p2 + (-3t^3+4t^2)

[Blessman11]

@mik2718

(t^3-t^2-t+1)p0 + (t^3-2t^2+t)p1 + (t^3-t^2)p2 + (-3t^3+4t^2)

Why do these coefficients generate negative results?

[mik2718]

Sorry, I made a mistake, this is the correct formula

p(t) = (t^3-t^2-t+1)p0 + (t^3-2t^2+t)p1 + (t^3-t^2)p2 + (-3t^3+4t^2)p3

Hmmm - thats the same as before - so I had it right after all.

Check
p(0) = p0 - ok
p(1) = p3 - ok

p'(t) = (3t^2-2t-1)p0 + (3t^2-4t+1)p1 + (3t^2-2t)p2 + (-9t^2+8t)p3

p'(0) = p1-p0 - ok (derivative at first end is pointing towards first control point)
p'(1) = p2-p3 - ok (derivate at other end is pointing towards second control point)

so the formula look right to me after all

are you sure you have programmed it right?

p0, p1, p2, and p3 are vectors. to multiple a vector by a scalar you just multiply each element by the scaler

p0 is the start point of the spline and p3 the end point