Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generating splines from points (with normals)

  1. May 2, 2003 #1
    Hi there. Could use some hints on how to accomplish this:

    (original thread at gamedev.net, 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: May 2, 2003
  2. jcsd
  3. May 2, 2003 #2
    Hi Lantz, what do you mean by 'normal'? Normal vector to the curve?
     
  4. May 2, 2003 #3
    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 :frown:.
     
  5. May 2, 2003 #4
    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.
     
  6. May 2, 2003 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: May 2, 2003
  7. May 3, 2003 #6
    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
     
  8. May 3, 2003 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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


    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
     
  9. May 4, 2003 #8
    Too bad I only got a TI-83 hehe.

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Generating splines from points (with normals)
  1. Function from points (Replies: 3)

Loading...