# Generating splines from points (with normals)

• Lantz
In summary, generating splines from points with normals involves using mathematical curves to connect a series of data points in a smooth and continuous manner. This process is commonly used in computer graphics and animation to create smooth and realistic movement. The normals, or direction vectors, of the points are also taken into account to ensure that the spline follows the desired curvature. This technique is useful for creating complex and organic shapes, such as curved roads or flowing hair, with a high level of precision and control.
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

Last edited by a moderator:
Hi Lantz, what do you mean by 'normal'? Normal vector to the curve?

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 .

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.

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.

Last edited:
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.

Lantz

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

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

## 1. What is the purpose of generating splines from points with normals?

The purpose of generating splines from points with normals is to create a smooth and continuous curve that can accurately represent a set of points. This technique is commonly used in computer graphics, engineering, and scientific visualization to create 3D models or to interpolate data.

## 2. How do you generate splines from points with normals?

To generate splines from points with normals, you first need to calculate the tangent vectors at each point based on the normal vectors. Then, you can use an interpolation algorithm such as Catmull-Rom or B-spline to calculate the curve between each point. Finally, the resulting curve can be adjusted and smoothed to achieve the desired shape.

## 3. What is the difference between interpolating splines and approximating splines?

Interpolating splines pass directly through each given point, while approximating splines only pass near the points. This means that interpolating splines can accurately represent the given data, but approximating splines may provide a smoother and more aesthetically pleasing curve.

## 4. Can you generate splines from a set of points without normals?

Yes, it is possible to generate splines from a set of points without normals. In this case, the tangent vectors can be calculated using other methods such as the average of the surrounding points or using a curvature estimation algorithm. However, using normals can provide more accurate and visually appealing results.

## 5. What are some applications of generating splines from points with normals?

Generating splines from points with normals has various applications in different fields. In computer graphics, it is used to create smooth and realistic 3D models. In engineering, it can be used to design and optimize curves for objects such as airplane wings or car bodies. In scientific visualization, it is used to interpolate and visualize data from experiments or simulations.

• General Math
Replies
4
Views
4K
• Calculus and Beyond Homework Help
Replies
4
Views
2K
• General Math
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Special and General Relativity
Replies
5
Views
1K
• Mechanics
Replies
9
Views
1K
• Sci-Fi Writing and World Building
Replies
7
Views
1K
• General Engineering
Replies
5
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
30
Views
2K
• General Math
Replies
1
Views
1K