11,634,827 members (67,483 online)

# Overhauser (Catmull-Rom) Splines for Camera Animation

, 10 Nov 2008 CPOL 57.7K 2.2K 35
 Rate this:
An introduction to Overhauser splines from the perspective of a game writer, with C++ sample code

## Introduction

Many people are impressed by realistic camera animations in games or multimedia demos. The math behind what is commonly called camera interpolation is actually pretty simple. In this article, I will focus on a simple algorithm that uses a particular class of spline curves called Overhauser or Catmull-Rom splines, and I will show how and why they are superior to other existing more or less similar approaches.

## Math is Your Friend

You may hate me for this, but math can be really nice. We will brush up our knowledge of vector calculus in this section, which will allow us to understand the sample code better.

Let's start with the basics: A curve that passes through its control points is said to interpolate those points. Bezier curves interpolate only 2 out of each 4 control points, while B-splines interpolate none of the specified control points (the curve goes smoothly around those points). The Catmull-Rom splines, also called Overhauser splines, belong to a class of curves known as Hermite splines. They are uniform rational cubic polynomial curves that interpolate between N control points and pass through exactly N-2 control points (except the first and last one). They are uniform, because the control points (also known as knots) are spaced at equal intervals with respect to the curve's parameter (`t`). The interpolation is performed in a piecewise manner: a new cubic curve is defined between each pair of points.

The parametric equation of the Catmull-Rom spline is given by:

Figure 1: Parametric equation of Catmull-Rom spline.

Where the vectors V and T and matrix M are:

Figure 2: Members of Catmull-Rom spline equation.

We could simply use this equation as is, and code up our solution using vector and matrix multiplication. While doable, that would probably not be very efficient. Let us simplify the equation a bit. I encourage you to double-check my math -- it's fun. By multiplying the horizontal vector T with matrix M and factoring in the vertical vector, we get:

Figure 3A: Simplification of Eq1.

Where `b1`...`b4` are cubic polynomials in `t`:

Figure 3: Simplification of Eq1.

Figure 3A shows the final equation's members. `P1`...`P4` are the control points. In 3D, `Pn` are homogeneous or non-homogeneous vectors (3 or 4 coordinates). In 2D they are 2-coordinate vectors.

What does all of this gibberish mean? Well, it means that if you know N intermediate positions plus possibly axis/angle pairs for a camera at N moments in time, you can produce an accurate and smooth animation of the camera by interpolating between N-2 of those positions and axis/angle pairs using Eq 3A above. The camera will pass through all the middle N-2 points. [Note: If you double the start and end points, the camera will pass through all N positions.]

## Coding It Up

First, we need a class to provide an abstraction for our control points, `Pn`. We will write up a minimal 3D vector class with just a couple of operations. Feel free to extend this as necessary. Also please note that the enclosed sample application nullifies the Z coordinate of these vectors and essentially uses them for plotting 2D curves. However, the package is fully capable of computing 3D splines! Let us review the 3D vector class, `vec3`:

```/// Minimal 3-dimensional vector abstraction
class vec3
{
public:

// Constructors
vec3() : x(0), y(0), z(0)
{}

vec3(float vx, float vy, float vz)
{
x = vx;
y = vy;
z = vz;
}

vec3(const vec3& v)
{
x = v.x;
y = v.y;
z = v.z;
}

// Destructor
~vec3() {}

// A minimal set of vector operations
vec3 operator * (float mult) const // result = this * arg
{
return vec3(x * mult, y * mult, z * mult);
}

vec3 operator + (const vec3& v) const // result = this + arg
{
return vec3(x + v.x, y + v.y, z + v.z);
}

vec3 operator - (const vec3& v) const // result = this - arg
{
return vec3(x - v.x, y - v.y, z - v.z);
}

float x, y, z;
};```

Pretty simple. Now we will introduce a new class for abstracting our spline.

```#include <span class="code-string">"vec3.hpp"</span>
#include <vector />

class CRSpline
{
public:

// Constructors and destructor
CRSpline();
CRSpline(const CRSpline&);
~CRSpline();

// Operations
void AddSplinePoint(const vec3& v);
vec3 GetInterpolatedSplinePoint(float t);   // t = 0...1; 0=vp[0] ... 1=vp[max]
int GetNumPoints();
vec3& GetNthPoint(int n);

// Static method for computing the Catmull-Rom parametric equation
// given a time (t) and a vector quadruple (p1,p2,p3,p4).
static vec3 Eq(float t, const vec3& p1, const vec3& p2,
const vec3& p3, const vec3& p4);

private:
std::vector<vec3> vp;
float delta_t;
};```

This is, again, pretty intuitive: the `CRSpline` class is essentially a container for a bunch of control points (represented as a `std::vector`). It has a `static `member function for solving the spline equation for a given parameter `t` and four control points `P1`...`P4`. The function returns a 3-coordinate vector, which is the result of the interpolation between the given 4 control points, for the given value of `t`.

The methods `AddSplinePoint` and `GetInterpolatedSplinePoint` allow us to specify the 2D/3D curve's control points and get the smooth curve back. Let us take a quick look at the latter, which contains one last bit of tricky logic:

```vec3 CRSpline::GetInterpolatedSplinePoint(float t)
{
// Find out in which interval we are on the spline
int p = (int)(t / delta_t);
// Compute local control point indices
#define BOUNDS(pp) { if (pp < 0) pp = 0;
else if (pp >= (int)vp.size()-1) pp = vp.size() - 1; }
int p0 = p - 1;     BOUNDS(p0);
int p1 = p;         BOUNDS(p1);
int p2 = p + 1;     BOUNDS(p2);
int p3 = p + 2;     BOUNDS(p3);
// Relative (local) time
float lt = (t - delta_t*(float)p) / delta_t;
// Interpolate
return CRSpline::Eq(lt, vp[p0], vp[p1], vp[p2], vp[p3]);
}```

As the code above shows, function `GetInterpolatedSplinePoint` divides the spline into 4-point segments, transforms the parameter `t` with respect to the local segment, and then uses the static equation solver to get the final result. The function assumes that `t` varies from `0 `to `1`, where `0 `represents the "start" of the spline (first control point) and `1 `represents the "end" of the spline (last control point). You can make up your own time scheme here, if this is not appropriate; remember however to adjust the computation of `p` and `lt` above.

Any sequence of 2D or 3D vectors can be interpolated in a similar fashion. For example, camera axis/angles, the positions and orientation of various moving objects in a scene, etc. The beauty of this approach compared to using b-splines or Bezier curves is that the resulting curves touch all of their control points (again, make sure to double the first and last control points to make that possible).

## Using the Code

Here, I included a very primitive application of the package, implemented in Borland Dev Studio 4. It basically instantiates the `CRSpline` class and populates it with pseudo-random control points, then uses BDS's `TCanvas` interface to plot the spline on a regular dialog box's canvas.

I hope you did not find my little math session too boring. Enjoy the code.

## References

• Computer Graphics: Principles and Practice; Foley, van Dam, Feiner, Hughes; Addison-Wesley, 1997
• Catmull, E. and R. Rom, "A Class of Local Interpolating Splines"; Computer-Aided Geometric Design; Academic Press, San Francisco, 1974

## History

• 7th November, 2008: Initial post

## About the Author

 Software Developer (Senior) Microsoft United States
Software engineering manager at Microsoft (Seattle area).

## Comments and Discussions

 First Prev Next
 My vote of 5 Kenneth Haugland8-May-15 11:39 Kenneth Haugland 8-May-15 11:39
 My vote of 5 futurejo18-Nov-11 2:00 futurejo 18-Nov-11 2:00
 Velocity and acceleration problems with Catmull Rom approach [modified] AmazingFactory5-Aug-10 23:49 AmazingFactory 5-Aug-10 23:49
 Re: Velocity and acceleration problems with Catmull Rom approach [modified] kmarnes1-Sep-10 10:23 kmarnes 1-Sep-10 10:23
 I dealt with this very problem several years ago for camera use within a game. What I did was roughly this: When initializing the spline, I wrote code to approximate each spline segment's length. This was achieved by breaking the spline into smaller pieces and calculating the linear distance between each sub-segment (10 segments between each node worked well). So you store the initial points and sub-segment distances and change the camera code to no longer use Catmull-rom calcs. Just simply lerp between each sub-point for exact constant speed. The main disadvantage to this method is an edge case when the camera encounters tight corners. it'll appear jerky, but that shouldn't be a problem if the designer doesn't try to break it. Also likewise for extraordinarily large segments. Just try to keep the segments relatively uniform and you'll be fine, or you can change the code to store a different number of sub-segments depending on it's overall size... but that might be over-engineering it. For what it's worth, I really like the Catmull-ROM spline system. It's very intuitive for use within editors and designers/programming types tend to really like it. It's also much easier to implement from a tools/engine standpoint. The only resistance I discovered was from a few artists, and it's because they experienced and comfortable with editing beziers, and felt the CR splines were more limited in control. While true, CR splines tend to work quite well for "game curves" such as camera movements or flight paths. The fact that the spline is guaranteed to pass through every node is nice. So best to check with the end-user and make sure they are okay with it before moving ahead. modified on Wednesday, September 1, 2010 4:30 PM
 Adding Point Luca D.22-May-09 5:19 Luca D. 22-May-09 5:19
 Bug Petr Janecek1-May-09 7:28 Petr Janecek 1-May-09 7:28
 Re: Bug Luca D.22-May-09 6:49 Luca D. 22-May-09 6:49
 Re: Bug LordFlashHeart8-Feb-15 17:10 LordFlashHeart 8-Feb-15 17:10
 Re: Bug Vertexwahn22-Sep-13 10:57 Vertexwahn 22-Sep-13 10:57
 Recommendations please Hugo Sanchez25-Mar-09 16:10 Hugo Sanchez 25-Mar-09 16:10
 Gracias! Hugo Sanchez24-Mar-09 15:59 Hugo Sanchez 24-Mar-09 15:59
 Re: Gracias! Radu Gruian24-Mar-09 16:47 Radu Gruian 24-Mar-09 16:47
 comment Member 49131924-Nov-08 13:15 Member 491319 24-Nov-08 13:15
 Re: comment Radu Gruian2-Dec-08 11:16 Radu Gruian 2-Dec-08 11:16
 Why... [modified] Stefan6319-Nov-08 22:39 Stefan63 19-Nov-08 22:39
 Re: Why... Radu Gruian24-Nov-08 6:25 Radu Gruian 24-Nov-08 6:25
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Jul-15 14:33 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.