Which Splines Do You Need? A Comprehensive Dive into Common Splines

数学 - 图形学
, , , , , , ,

This post introduces some widely used splines in computer games including Bézier curves, cubic Hermite splines, Catmull-Rom splines, B-splines, Kochanek–Bartels splines, etc. We show these splines can be bridged through re-formulation. Then, we focus on the extension and generalization of Bézier curves and introduce mathematical methods to create dynamic smooth splines. Last, we develop a simple Editor in Unreal Engine to enable easy creation of splines under different constraints and conditions.

Common Splines

Bézier Curve

The most typical and widely-used spline might be Bézier curves. Bézier curve leverages a set of control points to define a smooth and continuous curve generated by interpolation between these control points. Using the De Casteljau's algorithm,1 we can easily express a Bézier curve in terms of a sum of Bernstein polynomials:

When there are four control points, the generated curve is called cubic Bézier curve. A cubic Bézier curve can be expanded as:

The derivative of an -th order curve is:

Similarly, we can obtain the second-order derivative:

We will use these results later soon.

Degree elevation

Suppose is an -th order Bézier curve and we want to elevate its degree to . We can do this via the following process:

Note that when , , and when , . So and can be arbitrary. We simply set them to zero.

Composite Bézier curves

A composite Bézier curve is a series of Bézier curves joined end to end where the first point of one curve coincides with the last point of the previous curve. If a Bézier curve is composite, we say it's continuous.

However, sometimes we want higher degrees of continuity than at the joint of Bézier curves (note that individual curves are within their own inteval, and the discontinuity only happens at the meetings of consecutive curves).

Given two Bézier curves and , we can define different degrees of continuity at :

  • (positional continuity): consecutive Bézier curves meet at the same point. This holds by definition. In this case, it's .

  • (velocity continuity): the incoming and outgoing derivatives of are the same, vouching for a smooth transition from the first curve to the second. To show this, we let , and the solution is . This gives us . This equation tells us that and are not only colinear with respect to , but their vector lengths are also the same. Rewriting this equation to suggests is fully determined by and if we want continuity.

  • (tangent continuity): and are colinear but not requiring their vector lengths to be equal. Thus, we say is less strict than . If a composite curve is , then it must be . To guarantee , we just add an extra degree of freedom to the vector length: . means the two curves share a common tangent direction at the join point.

  • (acceleration continuity): following a similar process to continuity, the continuity can be defined by . That is to say, is fully determined by and . You should be very careful of using continuity: the continuity causes a loss of two control points and , leaving only one free control point . You perhaps cannot get the curve shape you expect. If you do not want to loss control over these points, you can use uniform B-splines, which will be introduced later.

  • (curvature continuity): this type of continuity requires except requiring , i.e., satisfying . To obtain this result, first expand and then plug in. Last, substitute for with and with , and you will get the right formula. Curvature continuity implies that the curves share a common center of curvature at the join point.

  • (jolt continuity): if a composite Bézier curve is , it satisfies . In this case, the fist curve full determines the second curve and thus the third, forth curve, etc. Now we say the generated composite Bézier curve is as there is indeed no joins.

If a curve is , then it must be . If a curve is , then it must be .

Rational Bézier curves

The Bezier curve will be fully determined if we specify a particlar type of continuity, say, . In such case, we cannot easily control the shape of the curve because all control points all equally weighted. We want to give it a little more flexibility: when we assign a larger weight to one point, the curve will bend more to that point. We call this type of Bezier curve as rational Bezier curve, which can be defined as:

where is the weight associated with each control point . It is clear from the definition that, when all weights are equal, it regresses to a standard -degree Bezier curve.

An interesting fact about an -degree rational Bezier curve is that it can be defined as the process of projection from an -degree standard Bezier curve to the -th dimensional plane. So how can this be done?

To show this, assume there are points in the -th dimensional space, i.e., and its corresponding weight . We append the weight to the coordinate and multiply it with each element in the vector to make up the homogeneous coordinate, denoted by . Using the points in the dimensional homogeneous space, we can obtain the Bezier curve:

Note that this Bezier curve is in the -th space, but what we really need is in the -th space, which is the original dimension of control points. So we can project this curve into the the one that is in the -th space, by dividing all elements by the value of the last element. Now the new curve becomes:

The first elements now comprise the dimensions of the new Bezier curve, and this is exactly we've defined above. From this derivation, we know that rational Bezier curve is kind of a projection from a higher space into a lower space, where the shape of curve is controlled by the weights.

We will show in later sections that rational Bezier curves are a special case of NURBS curves, and modifying a control point of a rational Bezier curve will lead to a global curve change.

Approximating circular arcs

Symmetrical 2D

A cubic Bézier curve can be used to approximate a circular arc. Let's first start with a simple case: the arc starts at point and ends at points , placed at equal distances above and below the -axis in the first quadrant, spanning an arc of angle . The radius is .

Assume the additional control points are and , and their indices are respectively and . Note that , or .

According to the expanded Bézier curve expression:

we have , which gives:

On the other hand, according to the derivative of a cubic Bézier curve , we know the derivative at is . It is equal to the tangent at multiplied by some coefficient :

However, we highlight that the resulting curve is not exactly a perfect circular arc, which means that there are small deviations from a perfect circular arc. Assuming the radius is and as the approximate planar parametric curve, we can use the quantity as a measure of the error of approximation. The non-absolute version is defined as . Both refer to the error.

Asymmetrical 2D

Now we've obtained the control points and .

What about and are not symmetrical? Assume the angle of is and the angle spanned by the arc is , where the end point is . We can first rotate both and by . This now becomes the case discussed above. We can calculate the index of after being rotated:

The rotated will be .

Now we can follow the aforementioned process to calculate the control points:

Last, we rotate and back to the original positions:

Besides using transformation and rotation, we can also utilize another approach to calculate the control points, with which we can eliminate the need of transforming points and directly getting to the absolute coordinates.2

Let us assume the starting point , end point , and two unknown control points , , where is the Euclidean length of two vectors and . Plugging these four points into the Bezier curve, we have:

giving . We can then directly compute the non-absolute version error as:

where and . We choose so that . Of course you can use other metrics to minimize this error, but is a simple and intuitive choice. We can solve as follows:

When we choose , the resulting Bezier curve will never enter inside the circle. Then the error is given by:

By differentiating and solving , we find obtains its maximum at and the maximum is . This implies that when is small, we have and , showing that the error decreases at the speed of the sixth order of circular angle . But when approches a full circle, i.e., , the error grows without bounds.

Returning to the more general case where the angle of is and the angle spanned by and is , or in other words and , we can similarly compute the control points and :

Recall that the choice of restrains the generated curve outside the circle. This can result in an error larger than expected. In fact, we can reduce the error by slightly "pushing" the curve in towards. We achieve this by multiple all the control points with a coefficient : . This gives us the new error .

Note that attains its extreme values at the same points as , i.e., , and we can compute them as:

We expect the overall error to be reduced by setting the minimum, i.e. at the right opposite side of the maximum value, i.e. . We then have:

When we have set up, we can readily compute the maximum value . When is small, , which significantly reduces the maximum error.

3D Space

The three-dimension case is more complicated because four control points will form a Bezier curve in 3D space. We should put one constraint on the points: the curve made up of these control points lie in the 2D space.

Cubic Hermite splines

Cubic Hermite splines construct a curve based on two points along with their respecive tangents.

Suppose the given starting point is at and ending point at , as well as the starting tangent and . The fitted cubic polynomial can be defined by:

Proof is quite simple. Assume our function is , and given that , we have:

Solving it gives us:

Rearranging gives the equation proposed at the beginning.

We can also reformulate in terms of Bézier curves with respect to the four control points . To show this, recall that a cubic Bézier curve can be expresses as:

We can rewrite as follows:

This shows that a cubic Bézier curve that patches the control points in the middle determines the tangents of the interpolation curve at the respective outer points.3

B-splines

Definition and Properties

B-spline stands for basic splines. Let be a series of nondecreasing knots, where are the two ends in the spline. The -th B-spline of degree , written as , is defined recursively as follows:

From the following diagram, we know that the polynomial covers the span of range . Thus, is non-zero on . And reversely, on any knot span , at most degree basic functions are non-zero, i.e., .

B-spline has the following important properties:

  • is a degree polynomial in .
  • is non-negative on .
  • On any knot span , at most degree basic functions are non-zero, i.e., .
  • The sum of all non-zero degree basic functions on span is 1. That is, .
  • If the number of knots is and given degree , all basic functions with degree are .
  • At a knot of multiplicity , basic function is continous.
  • At each internal knot of multiplicity , the number of non-zero basic functions is at most , where is the degree of basic functions.

B-spline Curves

Given control points and a series of knots , the B-spline curve of degree can be defined as:

Note that when , will be last basic function with degree , that is to satisfy , or . In other words, a B-spline curve of degree with points must be associated with knots ; or if knots and control points are given, the degree will be .

Typically, B-spline curves can be categorized into three types: open curve, clamped curve and closed curve.

  • Open B-spline curves: the generated curve does not connect to the first and last control point.
  • Clamped B-spline curves: the curve is connected to the first and last control point and is also tangent to them. To be a clamped curve, the first and last knot must be of multiplicity (recall that there are in all knots).
  • Closed B-spline curves: the generated curve forms a closed loop.

Open B-spline Curves

Clamped B-spline Curves

Closed B-spline Curves

Non-uniform rational B-spline (NURBS)

Beta-splines

Catmull-Rom splines

Connections between Splines

  1. https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm↩︎

  2. https://www.sciencedirect.com/science/article/abs/pii/016783969090019N↩︎

  3. https://en.wikipedia.org/wiki/Cubic_Hermite_spline↩︎