Programming

# Smoothing 3d geometry, like a tunnel, with Catmull-Rom splines

An endless tunnel is the centerpiece of my game Radial Blitz. Flying smoothly through this tunnel was important to me. That required both a smooth tunnel and a smooth camera. In this article we look at how I constructed the tunnel and smoothed it using Catmull-Rom splines.

### Tunnel segments

The tunnel is comprised of many, relatively short, segments. While playing there are only about 10 segments at any given time. As they disappear behind the camera they are removed and a new one is added to the front end of the tunnel. This both limits the amount of geometry drawn per frame, but also prevents the tunnel from ever intersecting itself (which it might otherwise do).

Each segment has has only two key geometry properties:

• to: The location at at the end of this segment. This is float3 point defining the middle of the tunnel fragment.
• orient: The direction the tunnel is facing at the end of the segment. This is a float4 quaternion, which also encodes the “up” direction.

These are stored as a doubly-linked list, the calculations need the previous and next segments. The chain of to positions defines the core structure of the tunnel.

Instead of orient I previously using two float3 values, one for the facing direction and one for the up direction. If you were standing on a tile in the tunnel, with your feet pointing to the front of the tile, the facing is a vector defining which way, in world space, you would be looking. The up vector is the world direction from your feet to your head.

Storing two values is kind of wasteful, and somewhat unstable. A single float4 quaternion is able to encode both of those values, and can be directly interpolated. The facing and up vectors are derived as needed.

#### Creating segments

Deciding the values for the segments wasn’t hard, but involved a lot of fine tuning. To create the next segment I need to extend from the previous one, getting the position and facing at the end of the next segment.

To create a straight segment I’d take the facing vector at the end of the previous one and multiply it by the segment length. To provide some variation I add some random rotation to the vector. In order not to create too chaotic of a tunnel, this rotation is held for several segments. This results in long smooth tunnel corners.

The variance parameters are all controlled by the levels, thus allowing some levels to be more chaotic and bendy than others. There’s also an upgrade in the game that reduces the variatian: aiming in a straight tunnel is easier than a bendy one.

### Interpolating

If the segments were simply straight sections between the to positions, the tunnel would feel rather jagged. This is a video showing what that might look like. Notice the sharp delineation between segments and how the camera changes are also abrupt: adjusting for sudden changes in facing.

In graphics and animation the answer to any question of smoothing is usually splines. Likely a cubic spline as well, since everybody loves t^3 values. This answer is of course quite general as there are many ways to satisfy the values in a spline.

The Catmull-Rom values are suitable for path smoothing in games. There’s even built-in functions in DirectX for this type of spline.

A spline just lets us interpolate between two points, creating a smooth transition from one to the other. To interpolate we actually an additional two points, the one before the first and after the second. These four points are the control points, and define the overall curve. With these values we can calculate an interpolated position at t, the unit interval in the range 0...1: when t=0 we should be at point $P_n$ and when t=1 at point $P_{n+1}$.

$p(t) = \frac{1}{2} \cdot \begin{bmatrix}1 & t & t^2 & t^3\end{bmatrix} \cdot \begin{bmatrix} 0 & 2 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 2 & -5 & 4 & -1 \\ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix}P_{n-1} \\ P_n \\ P_{n+1} \\ P_{n+2} \end{bmatrix}$

### Code details

The control points are only scalars, thus the equation needs to be done for each dimension in the position, and also for each component of the quaternions. This calculation defines the structure of the tunnel itself, not just the mesh defining the visuals. It needs to be done a lot, per-frame, when calculating where all the game objects are located. For each segment however, most of the calculation can be pre-calculated.

 1 2 3 4 5 6 intOrient = float4x4( SplineParams( av.X, bv.X, cv.X, dv.X ), SplineParams( av.Y, bv.Y, cv.Y, dv.Y ), SplineParams( av.Z, bv.Z, cv.Z, dv.Z ), SplineParams( av.W, bv.W, cv.W, dv.W ) ); 

This creates a 4×4 matrix that can be multipled by the t vector to get the orientation at a point along this segment. The SplineParams just calculates the spline (it either calls CatmullRomParams or LinearParams, I just have it for testing).

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 float4 SplineParams( double p0, double p1, double p2, double p3 ) { return CatmullRomParams( p0, p1, p2, p3 ); //return LinearParams( p0, p1, p2, p3 ); } float4 CatmullRomParams( double p0, double p1, double p2, double p3 ) { return 0.5f * float4( (float)(2*p1), (float)(-p0 + p2), (float)(2*p0 - 5*p1 + 4*p2 - p3), (float)(-p0 + 3*p1 - 3*p2 + p3) ); } float4 LinearParams( double p0, double p1, double p2, double p3 ) { return float4( (float)p1, (float)(p2 - p1), 0, 0 ); } 

CatmullRomParams is the programmed version of the previous equation less the t vector. LinearParams does the straight line segments; it’s equation is good for understanding how the calculations are working.

Those matrices let me create LocAt and OrientAt functions to calculate the location and orientation at a given point in the tunnel.

 1 2 3 4 5 6 public float4 OrientAt( Segment seg, double step ) { NormalizeStep( ref seg, ref step ); var tVec = float4( 1, (float)step, (float)(step * step), (float)(step * step * step) ); var r = Vector.Transform( tVec, seg.intOrient ); return r; } 

step is just our t variable in the original equation. tVec was the unit interval component $\begin{bmatrix}1 & t & t^2 & t^3\end{bmatrix}$. The NormalizeStep deals with the linear list of segments: it finds the segment where step is in the range 0..1 as the input parameter can be outside that range.

### A smooth seque

The smooth experience isn’t just a result of the tunnel shape. How the camera moves plays an important role as well, but I’ll get into that in a future article. The lighting on the tiles can also change the apparent shape. By adjusting the normals some levels have a segmented wall, and others have a smooth looking tube.

Since doing this code I’ve revisited splines for my work on Fuse. I use them for custom animation timelines via Keyframe. I didn’t want to limit designers to just the “Catmull-Rom” parameters, so I went the more generic way with Kochanek-Bartel splines. These are very versatile, yet offer some basic configuration variables, the “tension”, “bias” and “continuity”. When all set to 0, the default, it results in the Catmull-Rom spline.