Cubic Interpolation

Unity Engine
1

Hi Everyone, I am currently working on a game in unity which requires a waypoint system and have run into a situation I am not sure how to resolve. First some background information, A scene can contain a collection of waypoints which can each be configured to use linear or cubic interpolation to calculate the path to the next waypoint. This allows me to have perfectly straight paths and just about any shaped curve that I need. The game requires it for aircraft flying in the traffice pattern above an airfield.

Everything works as expected when the curves have a constant angle, resulting in a constant velocity when interpolating them but if the curves are not of a constant angle then the velocity of the aircraft travelling between the waypoints will change. I would like to know if it is possible to adapt the cubic interpolation method to provide constant velocity no matter how the curve is shaped.

The only way I can think of doing it is if I step through the curve and create x amount of control points which I could then use to interpolate linearly while taking into account the distance between each control point to ensure constant velocity. My worry is that if I have too many control points on a small curve then the animation may become stuttery if the interpolation value keeps being clamped at 1.0 on each control point. The other problem is that if I have too little control points then it may no longer look like a smooth curve.

I may be going about this completely the wrong was so I would be interested in any ideas of how I can solve this problem whether it be adapting cubic interpolation to work the way I would like or by using a completely different method to achieve the desired result.

2

It sounds like what you’re looking for is ‘arc length reparameterization’. It’s not exactly trivial, but here is a paper (PDF) that might be of some use.

3

Just as a sphere is a collection of triangles, so is a curve a collection of straight lines. You only need four control points per curve, meaning that consecutive curves can use the last previous two points to calculate a new curve.

4 control points=1 curve
6 control points=2 curves
8 control points=3 curves

The control points will consist of two anchor points, which will lie directly on the curve, and two handle points which will control the shape of the curve between the handle points. Does that make sense, or should I elaborate?

4

Maybe I’m missing the obvious here, but what exactly does that have to do with the OP’s question?

5

You could check the distance between each point, as you are calculating the curve, in order to ensure the distance is within some range. If you have a small curve and you choose to create 20 points per curve, you may end up with having way too many points over a small distance. If you have a large curve, you may end up with too few points over a distance. The only way I can see of fixing this problem is to start with some amount of points, say 10 points, and then add 10 more points if you are below some minimum distance, or likewise subtract 10 points if you are above some maximum distance (between points which lie on the path). There is probably a better mathematical way of doing this, and I might have missed it altogether. If so, just ignore me. :smile:

Thought I would add this as well, as this is how I learned bezier curves.

http://www.gamedev.net/reference/articles/article1808.asp

If you need any of it converted to C# just let me know.

6

I think maybe you did - in fact, it’s mentioned in this very thread, right above your first post :slight_smile:

That said, arc length reparameterization isn’t the only solution, and may introduce more complexity than is necessary in some cases. But, if I’m understanding the original question correctly at least, it does seem to be what the OP is looking for (at least in principle).

7

Ah, alright my bad!

8

Thanks for the reply guys. Jesse that looks to be just what I am looking for. You are certainly right that it’s not trivial but I will try my best to implement it and will post my results.

9

There is a cheap solution for this:

  • calculate the slope (derivative) of each curve (x,y,z) at t
  • this becomes a velocity vector (x’, y’, z’)
  • the length of this vector is the speed
  • now you can modulate your step by: desired speed / actual speed
    t = t + step * desired / actual
    example in action: http://www.youtube.com/watch?v=vIHrjlnlykk
    to get things really smooth I use bspline interpolation (c2 continuous = smooth) and I interpolate the t parameter also …
1 Like