Booniverse
16Dec/118

Waypoints & Catmull-Rom Splines

Thought I'd share some more code. Yay, right?! This time, I've been working on turning a series of Vector3 coordinates (waypoints) into a Catmull-Rom spline. The code works by providing an array of Vector3, an output array (also of Vector3) and specifying the number of curve samples, per span, to return in the output array.

Catmull-Rom splines employ an algorithm which takes four points (p0, p1, p2, p3) and a normalised distance parameter (0 to 1). The first and last points (p0 and p3) are used to define curvature, while the normalized distance parameter is used to calculate a position on the resulting curve between p1 and p2.

What this means in practice is that the code below will appear to ignore the first and last waypoints in the array. To include them in the final curve, duplicate them at the start and end of the array. For example, given the points A, B, C, D and E, your array should look like: A, A, B, C, D, E, E. This will give you a resulting curve which starts at point A, ends at point E and passes through points B, C and D on the way.

Here's a picture demoing the linear input path (cyan) and the resulting Catmull-Rom spline output path (red).

Technically, no curve is actually generated. The main method returns a second linear path, albeit with more (smoothed) waypoints. With enough samples-per-span (the image above has 10 samples) the Vector3 output array will describe a visually smooth curve. The code is included below:

/// <summary>
/// Takes an array of input coordinates used to define a Catmull-Rom spline, and then
/// samples the resulting spline according to the specified sample count (per span),
/// populating the output array with the newly sampled coordinates. The returned boolean
/// indicates whether the operation was successful (true) or not (false).
/// NOTE: The first and last points specified are used to describe curvature and will be dropped
/// from the resulting spline. Duplicate them if you wish to include them in the curve.
/// </summary>
public static bool CatmullRom(Vector3[] inCoordinates, out Vector3[] outCoordinates, int samples)
{
	if (inCoordinates.Length &lt; 4)
	{
		outCoordinates = null;
		return false;
	}
 
	List results = new List();
 
	for (int n = 1; n &lt; inCoordinates.Length - 2; n++)
		for (int i = 0; i &lt; samples; i++)
			results.Add(PointOnCurve(inCoordinates[n - 1], inCoordinates[n], inCoordinates[n + 1], inCoordinates[n + 2], (1f / samples) * i ));
 
	results.Add(inCoordinates[inCoordinates.Length - 2]);
 
	outCoordinates = results.ToArray();
	return true;
}
 
/// <summary>
/// Return a point on the curve between P1 and P2 with P0 and P4 describing curvature, at
/// the normalized distance t.
/// </summary>
 
public static Vector3 PointOnCurve(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t)
{
	Vector3 result = new Vector3();
 
	float t0 = ((-t + 2f) * t - 1f) * t * 0.5f;
	float t1 = (((3f * t - 5f) * t) * t + 2f) * 0.5f;
	float t2 = ((-3f * t + 4f) * t + 1f) * t * 0.5f;
	float t3 = ((t - 1f) * t * t) * 0.5f;
 
	result.x = p0.x * t0 + p1.x * t1 + p2.x * t2 + p3.x * t3;
	result.y = p0.y * t0 + p1.y * t1 + p2.y * t2 + p3.y * t3;
	result.z = p0.z * t0 + p1.z * t1 + p2.z * t2 + p3.z * t3;
 
	return result;
}

There are probably quite a few ways this code could be optimised (feel free to point them out if you've stopped by!) but I'm only using this code during the level's initialization stage, so optimisation is not really all that important for me. The next stage will be to investigate means of normalizing the curve sampling to provide equidistant samples rather than distances being based on curvature and waypoint separation. It's not all that critical as I can reliably construct the paths to ensure a more-or-less equidistant array of waypoints and prevent visible variations in sample density, but it's still something I'd like to solve. At any rate, I hope this is useful to someone.

Comments (8) Trackbacks (1)
  1. Just a small update via comment: I got an object to follow the resulting curved path at a constant speed with minimum fuss. If there’s any call for the code, I’ll post it.

  2. I would indeed like to see the code for the constant speed result.

  3. yup, been struggling to fix the constant speed issue for dayz ;)

  4. I did not check your solution but this is a right solution for this problem.

    This link explain mathematical background, its called arc-length parameterization.

    http://www.algorithmist.net/arclengthparam.html

    And here is a code (download Singularity package).

    http://www.algorithmist.net/cranimation.html

    I would like to see your code if you port it.

  5. Hi Boon, you mentioned above that you felt you could optimise your catmull-rom code – any chance you could PM me to discuss? More than happy to pay for your time!

    • Hey sorry, I appreciate the offer but I’m just way too busy right now to pick up anything else, but if that changes I’ll let you know. You’re of course free to do what you will with any code on my blog!


Leave a comment