Centripetal Catmull–Rom spline explained

In computer graphics, the centripetal Catmull–Rom spline is a variant form of the Catmull–Rom spline, originally formulated by Edwin Catmull and Raphael Rom,^[1] which can be evaluated using a recursive algorithm proposed by Barry and Goldman.^[2] It is a type of interpolating spline (a curve that goes through its control points) defined by four control points

, with the curve drawn only from to .

Definition

Let

denote a point. For a curve segment defined by points and knot sequence , the centripetal Catmull–Rom spline can be produced by:

where

and

in which

ranges from 0 to 1 for knot parameterization, and with . For centripetal Catmull–Rom spline, the value of is . When , the resulting curve is the standard uniform Catmull–Rom spline; when , the result is a chordal Catmull–Rom spline.Plugging into the spline equations and shows that the value of the spline curve at is . Similarly, substituting into the spline equations shows that at . This is true independent of the value of since the equation for is not needed to calculate the value of at points and .The extension to 3D points is simply achieved by considering a generic 3D point and

Advantages

Centripetal Catmull–Rom spline has several desirable mathematical properties compared to the original and the other types of Catmull-Rom formulation.^[3] First, it will not form loop or self-intersection within a curve segment. Second, cusp will never occur within a curve segment. Third, it follows the control points more tightly.^[4]

Other uses

In computer vision, centripetal Catmull-Rom spline has been used to formulate an active model for segmentation. The method is termed active spline model.^[5] The model is devised on the basis of active shape model, but uses centripetal Catmull-Rom spline to join two successive points (active shape model uses simple straight line), so that the total number of points necessary to depict a shape is less. The use of centripetal Catmull-Rom spline makes the training of a shape model much simpler, and it enables a better way to edit a contour after segmentation.

Code example in Python

The following is an implementation of the Catmull–Rom spline in Python that produces the plot shown beneath.

import numpyimport matplotlib.pyplot as plt

QUADRUPLE_SIZE: int = 4

def num_segments(point_chain: tuple) -> int: # There is 1 segment per 4 points, so we must subtract 3 from the number of points return len(point_chain) - (QUADRUPLE_SIZE - 1)

def flatten(list_of_lists) -> list: # E.g. mapping 1, 2, [3], [4, 5]] to [1, 2, 3, 4, 5] return [elem for lst in list_of_lists for elem in lst]

def catmull_rom_spline(P0: tuple, P1: tuple, P2: tuple, P3: tuple, num_points: int, alpha: float = 0.5,): """ Compute the points in the spline segment :param P0, P1, P2, and P3: The (x,y) point pairs that define the Catmull-Rom spline :param num_points: The number of points to include in the resulting curve segment :param alpha: 0.5 for the centripetal spline, 0.0 for the uniform spline, 1.0 for the chordal spline. :return: The points """

# Calculate t0 to t4. Then only calculate points between P1 and P2. # Reshape linspace so that we can multiply by the points P0 to P3 # and get a point for each value of t. def tj(ti: float, pi: tuple, pj: tuple) -> float: xi, yi = pi xj, yj = pj dx, dy = xj - xi, yj - yi l = (dx ** 2 + dy ** 2) ** 0.5 return ti + l ** alpha

t0: float = 0.0 t1: float = tj(t0, P0, P1) t2: float = tj(t1, P1, P2) t3: float = tj(t2, P2, P3) t = numpy.linspace(t1, t2, num_points).reshape(num_points, 1)

A1 = (t1 - t) / (t1 - t0) * P0 + (t - t0) / (t1 - t0) * P1 A2 = (t2 - t) / (t2 - t1) * P1 + (t - t1) / (t2 - t1) * P2 A3 = (t3 - t) / (t3 - t2) * P2 + (t - t2) / (t3 - t2) * P3 B1 = (t2 - t) / (t2 - t0) * A1 + (t - t0) / (t2 - t0) * A2 B2 = (t3 - t) / (t3 - t1) * A2 + (t - t1) / (t3 - t1) * A3 points = (t2 - t) / (t2 - t1) * B1 + (t - t1) / (t2 - t1) * B2 return points

def catmull_rom_chain(points: tuple, num_points: int) -> list: """ Calculate Catmull-Rom for a sequence of initial points and return the combined curve. :param points: Base points from which the quadruples for the algorithm are taken :param num_points: The number of points to include in each curve segment :return: The chain of all points (points of all segments) """ point_quadruples = (# Prepare function inputs (points[idx_segment_start + d] for d in range(QUADRUPLE_SIZE)) for idx_segment_start in range(num_segments(points))) all_splines = (catmull_rom_spline(*pq, num_points) for pq in point_quadruples) return flatten(all_splines)

if __name__

"__main__": POINTS: tuple = ((0, 1.5), (2, 2), (3, 1), (4, 0.5), (5, 1), (6, 2), (7, 3)) # Red points NUM_POINTS: int = 100 # Density of blue chain points between two red points

chain_points: list = catmull_rom_chain(POINTS, NUM_POINTS) assert len(chain_points)

num_segments(POINTS) * NUM_POINTS # 400 blue points for this example

plt.plot(*zip(*chain_points), c="blue") plt.plot(*zip(*POINTS), c="red", linestyle="none", marker="o") plt.show

Code example in Unity C#

using UnityEngine;

// a single catmull-rom curvepublic struct CatmullRomCurve

using UnityEngine;

// Draws a catmull-rom spline in the scene view,// along the child objects of the transform of this componentpublic class CatmullRomSpline : MonoBehaviour

Code example in Unreal C++

float GetT(float t, float alpha, const FVector& p0, const FVector& p1)

FVector CatmullRom(const FVector& p0, const FVector& p1, const FVector& p2, const FVector& p3, float t /* between 0 and 1 */, float alpha=.5f /* between 0 and 1 */)

See also

• Cubic Hermite splines

External links

• Catmull-Rom curve with no cusps and no self-intersections implementation in Java
• Catmull-Rom curve with no cusps and no self-intersections simplified implementation in C++
• Catmull-Rom splines interactive generation via Python, in a Jupyter notebook
• Smooth Paths Using Catmull-Rom Splines another versatile implementation in C++ including centripetal CR splines

Notes and References

1. Book: Computer Aided Geometric Design . Catmull . Edwin . Rom . Raphael . 1974 . 978-0-12-079050-0 . Barnhill . Robert E. . 317–326 . A class of local interpolating splines . 10.1016/B978-0-12-079050-0.50020-5 . Edwin Catmull . Raphael Rom . Riesenfeld . Richard F..
2. Barry . Phillip J. . Goldman . Ronald N. . August 1988. A recursive evaluation algorithm for a class of Catmull–Rom splines . Proceedings of the 15st Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988. 10.1145/378456.378511. Association for Computing Machinery. 22 . 4 . 199–204.
3. Yuksel . Cem . Schaefer . Scott . Keyser . John . July 2011 . Parameterization and applications of Catmull-Rom curves . Computer-Aided Design . 43 . 7 . 747–755 . 10.1016/j.cad.2010.08.008. 10.1.1.359.9148 .
4. Web site: Yuksel; Schaefer; Keyser. Cem; Scott; John. On the Parameterization of Catmull-Rom Curves.
5. Jen Hong . Tan . Acharya . U. Rajendra . 2014 . Active spline model: A shape based model-interactive segmentation . . 35 . 64–74 . 1402.6387 . 10.1016/j.dsp.2014.09.002. 6953844 .