Generating splines from points (with normals)

[Lantz]

Hi there. Could use some hints on how to accomplish this:

(original http://www.gamedev.net/community/forums/topic.asp?topic_id=154493, this is for a computer game in a wipeout-ish style)

If I have a set of points where each point also have a normal, how would I interpolate between them to generate a spline (without any kind of control points) that go through each point? What I want is to to be able get the position of a point and its normal over the entire spline. Also, will I need to generate one huge spline (with possibly hundred of points) or will it still fit together if I divide it into shorter splines with say like, 2-5 points per spline?

Any suggestions, formulas, source code, links or thoughts on this would be great.

Regards,
Lantz

 

[arcnets]

Hi Lantz, what do you mean by 'normal'? Normal vector to the curve?

 

[Lantz]

Yea, I'm doing a racing game and I would like to represent the track as a set of points with normals, where the normal points up from the track. So the normal will be the orientation of the track at each point, and of course I will need some way to interpolate the normals between points too. Too bad I ain't got the slightest clue on how to do this .

 

[arcnets]

The simplest way to interpolate between n points is the polynomial spline:
y = a0 x^0 + a1 x^1 + a2 x^2 + ... + a(n-1) x^(n-1).
You plug each point (x|y) into this equation. That gives you n equations which determine the n variables a0 ... a(n-1).
Example: 3 points always define a parabola (n = 2).

However, the graph will zig-zag a lot if n is large, (say n>5 or so).
To avoid this, you use only 4 points at a time, which gives you cubic splines. They have the same curvature at intersections, which is probably good for a race-track.

Now for normals. If you know the normal, then you also know the tangent. The formula for the tangent is, of course
y' = a1 x^0 + 2 a2 x^1 + 3 a3 x^2 + ...

This gives you more equations. Which means, you have to use a polynomial of higher grade (probably 2n). I'm afraid this will zig-zag even more.

 

[Hurkyl]

Well, there are lots of ways to do interpolation.

http://mathworld.wolfram.com/CubicSpline.html

Cubic splines are something I hear a lot (I haven't used them personally), and they have the property that they pass through the points you specify.


For your problem, I think we can do something different.

If you have a set of points through which the curve passes, and a normal vector at each point, we can write equations for that.

Suppose we want the curve (x(t), y(t)) to start at the point (a, b) and end and the point (c, d), and that the normal vector at the first point is (j, k) and the normal vector at the second point is (m, n). Also, for simplicity, we want t to range from 0 to 1.

Then:

x(0) = a
y(0) = b
x(1) = c
y(1) = d
x'(0) * j + y'(0) * k = 0
x'(1) * m + y'(1) * n = 0

We have 6 equations, so we can solve an equation with 6 unknowns, which we can write as 3 unknowns for x and 3 for y. Let's make them polynomial equations because they're easy to compute.

x(t) = p + q * t + r * t * t
y(t) = u + v * t + w * t * t

Plugging into the above 6 equations will yield 6 equations in 6 unknowns, and you can solve for these 6 unknowns, which will yield a quadratic interpolation that passes through the adjacent points and is going in the correct direction as it passes through.

 

[Lantz]

Thanks to both of you for your replies. Though I am afraid I didn't understand much of what you wrote. I've studied one variable calculus and linear algebra, so I don't know much about this sort of thing. What you wrote Hurkyl looked quite interesting and I'm really interested in finding out more about those equations, especially about how they would look in three dimensions. Is there any chance that you or anyone else perhaps could explain some more and maybe come up with a few clever equations that would get me started on this or maybe point me to some good web page on this subject? I guess I could try myself and finish what you started on but I'm pretty sure I would get stuck pretty fast as I'm not very good at solving stuff with that many unknowns.

Thanks in advance,
Lantz

 

[Hurkyl]

I'm not very good at solving stuff with that many unknowns.

That's what TI-89's and Mathematica is for.


Anyways, for the 3-d case...

You say you have the normal to the curve you wish to draw. Does that mean that you have two vectors orthogonal to the curve (which describe the normal plane), you have just one vector orthogonal to the curve and you don't care about the other degree of freedom, or that you have just one vector and that the derivative of the tangent vector should point in the same direction as the normal (or possibly opposite)?

As to how nice my parabolic interpolation would look, I'm not sure, I haven't done much with actually plotting interpolations.

Hurkyl

 

[Lantz]

Originally posted by Hurkyl
That's what TI-89's and Mathematica is for.

Too bad I only got a TI-83 hehe.

You say you have the normal to the curve you wish to draw. Does that mean that you have two vectors orthogonal to the curve (which describe the normal plane), you have just one vector orthogonal to the curve and you don't care about the other degree of freedom, or that you have just one vector and that the derivative of the tangent vector should point in the same direction as the normal (or possibly opposite)?

Yea I basically only need the normal (I think) since I will generate the geometry using two points on the spline for every small strip of track.

However, I just found a great web page that shows how to do just what I wanted, so I think I should be able to get something working now.

Anyway, many thanks for your help.

Lantz