Making Splines Useful: Speed Control

Timothy Barnes  —  4 months ago [Edited 0 minutes later]
Introduction to Series
This is the fourth part in a series about programming with splines. Part 1: Introduction, Part 2: Closest Point, and Part 3: Arc Length can be found at those links.

Introduction to Post
The gist of what I will be explaining today is the problem of inconsistent speed when moving down a spline. This happens when the spline’s control points are at different arc lengths from each other. This can occur when the control points have been specified by a person using a game’s level editor, or the control points are from a path imported from a digital content creation tool. I will show an approach to this problem I learned from a paper titled “Arc-Length Parameterized Spline Curves for Real-Time Simulation”,[1] that involves generating a new spline path of control points at equal arc length along the spline. I will also briefly discuss some problems with this approach.

Introduction to the Problem
If we linearly increase the spline parameter from the spline interpolation equation we discussed in part 1 each frame, there is no guarantee that the interpolated point will be moving at a constant speed. It could speed up or slow down significantly depending on how close the control points are to each other.

For instance, if we used the elapsed time since the application started running as the spline parameter, then within one second the interpolated point would transition from control point 0 to control point 1. At the end of the second second, it would be on control point 2, and so on. In this case it takes one second to move to each new control point, regardless of the distance between the control points. If the next control point is very far away, then the interpolated point will appear to move quickly. If a control point is near to a previous one, the interpolated point will appear to move slowly.

What we would like to do is write our program so that an interpolated object does not hit these snags and speedy places, but instead will move at a constant speed.

There are times when you want to vary the speed, but you first need to be able to interpolate smoothly down the spline at a constant speed in order to have complete control of the speed. For example, if you were writing a single player racing game, you might program the other drivers to move down the track on a spline path. In that example it might be a good idea to vary the speed of the other drivers so that they slow down when going around a tight curve. If you did not start with a spline that moved at a constant speed, then you would be at the mercy of however close or far away the next control point would be.

Numerical Methods
The numerical methods approach to the problem of moving at a constant speed down the spline is to write a function that takes in a parameter for the distance along the arc length that you want the interpolated point to be, and that has an output of the correct spline parameter for that given arc length.

Once the spline parameter is found it can be passed to the spline interpolation function we previously discussed to find a point at a given arc length down the spline. Unless a lookup table is generated, this approach relies on real-time numerical methods, which bring along all the host of problems we have previously discussed (variable execution time, no promise of convergence).

Generating an Equally Segmented Spline
Despite that this problem is often solved using numerical methods, a different approach exists that is more stable due to not relying on real-time numerical methods. I learned this other approach in a paper by Wang, H., Kearney, J., and Atkinson, K. [1] I call it the “equally segmented spline” approach because it involves generating a new spline in which each segment has an equal arc length.

This approach works by generating a new spline with different control points. These control points are chosen so that they lie on the path of the old spline, but are at an equal arc length from each other. Using this approach, you would pass the desired arc length parameter into the interpolation function for the new spline. If you generated the spline so that the control points are each at one world unit from each other, then you now have the point at your given arc length along the spline. Otherwise the parameter to the interpolation function would need to be scaled based on the chosen set distance between the control points. This relied on no real-time numerical methods, and the computation cost is identical to interpolating on any other spline.

Problems with the Equally Segmented Spline Approach
This approach relies on preprocessing a spline curve before an object is able to move at a constant speed down the path. This needs to be taken into account as to the technical complexity it might bring to a project. If the control points in a spline are in constant motion, then the new spline would need to be regenerated each frame before being used for interpolation. This could be prohibitively expensive.

The other problem involves choosing the number of control points for the new spline. If too few control points are chosen for the new spline, then the new spline will not approximate the old spline well. The worse case is when the original spline pinches tightly or forms a loop like a roller coaster. If the loop is one meter along the arc length, and the distance you have chosen between all the new control points is also one meter, you could end up having two control points directly next to each other, one at the start and one at the end of the loop. Since the new spline has no middle control point between the two, there will be no loop there. The control points may end up not being at and equal arc length from each other after all!

Conclusion
The best method for moving smoothly at a constant speed down a spline depends on the problem you are trying to solve. If you have tried using numerical methods for this purpose and found it lacking, give the equally segmented spline approach a try. If you know of other approaches to this problem, please let me know and post in the comments below.

[1] Wang, H., Kearney, J., and Atkins...e for real-time simulation (2002)
Log in to comment