Basis splines

How are smooth and complex curves and curved surfaces constructed in computers for computer-aided design (CAD)? With splines!

Compared to simpler definitions such as arcs, polynomials, lines, planes, spheres and cylinders, splines allow creating smooth, complex surfaces from a set of control points. Because of this, splines are unmissable in creating organic shapes in products and architecture.

Different techniques exist for contructing splines; catmull-rom splines, bezier splines, basis splines, non-uniform rational basis splines (NURBS), T-splines and more. In this post I will focus on NURBS and T-splines, as this is most commonly used in CAD software.

Note that NURBS are only a small addition to basis splines, so if you understand basis splines, you understand NURBS. It also helps to first focus on curves, and later surfaces, because surfaces are constructed from curves.

Basis splines #

A basis spline \(C(t)\) is constructed from \(n\) control points. For each control point \(P_i\), a basis function \(B_i(t)\) is defined. These basis functions return a value between \(0.0\) and \(1.0\) for a given value of \(t\). In order to get the coordinate of basis spline C for a value of \(t\), we multiply each basis function with their corresponding control point, and sum the result:

In code this would be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

vec3 basis_spline(const std::vector<BasisFunction>& basis_functions, 
                  const std::vector<vec3>& control_points, 
                  const float t) {
  assert(basis_functions.size() == control_points.size());
  const int n = basis_functions.size();

  vec3 result = vec3(0, 0, 0);
  for (int i = 0; i < n; ++i) {
    result += basis_functions[i](t) * control_points[i];
  }
  return result;
}

Where BasisFunction is of type:

1
2

// returns the weight for a given value of t
using BasisFunction = std::function<float(float t)>;

In other words, each basis function gives the weight with which its control point contributes to the final coordinate.

Parameter space and coordinate space #

The basis functions \(\{B_0, B_1, \dots, B_n\}\) are in parameter space \((t)\).

Control points \(\{P_0, P_1, \dots, P_n\}\) are in coordinate space \((x, y, z)\).

Only at the final step, we move from parameter space into coordinate space by multiplying the basis functions with their corresponding control points, but before that everything happens in parameter space.

We therefore disregard coordinate space for now, and purely focus on parameter space.

Basis function #

A basis function can be understood as recursive linear interpolation. As a result, at each level of recursion, the degree of our function increases by 1.

This makes our function go from constant (\(d=0\)), to linear (\(d=1\)), to quadratic (\(d=2\)), to cubic (\(d=3\)), quartic (\(d=4\)), quintic (\(d=5\)), etc.

As our base case, we start with constant functions (\(d=0\)), defined within a specific domain in \(t\):

We recurse downwards from our desired degree to degree 0, at which point we reach the base case:

Where \(d\) is degree, \(k\) is the knot vector and \(i\) is the index of the basis function.

Basis spline surfaces #

A basis spline surface is a tensor product of two basis splines.

In code this would be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// control points are stored in row-major format
vec3 basis_surface(const std::vector<float>& knots_u,
                   const std::vector<float>& knots_v,
                   const std::vector<vec3>& control_points,
                   const int rows,
                   const int columns,
                   const int degree,
                   const float u, 
                   const float v) {
  vec3 result = vec3(0, 0, 0);

  for (int row = 0; row < rows; ++row) {
    for (int column = 0; column < columns; ++column) {
      const float basis_u = basis_spline(knots_u, degree, column, u);
      const float basis_v = basis_spline(knots_v, degree, row, v);
      const vec3 control_point = control_points[row * columns + column];

      result += basis_u * basis_v * control_point;
    }
  }

  return result;
}

Non-uniform rational basis splines (NURBS) #

Non-uniform #

The non-uniform part in the term means that the knot vector does not have equally spaced knots. This gives the user more control over the resulting curve.

As an effect, multiple knots can be placed at exactly the same value for \(t\).

Rational #

The rational part in the term means that we add a fourth component to our parameter space: \(w\). The result from our spline function \(C(t)\) then returns a 4D coordinate: \(P(xw, yw, zw, w)\). In order to get our point in 3D \((x, y, z)\), we divide each component by \(w\):

These 4D coordinates are also known as homogeneous coordinates. Dividing by w can be thought of as projecting the point from 4D onto the 3D hyperplane at \(w = 1\).