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 .
Catmull–Rom spline interpolation with four points
Definition
Barry and Goldman's pyramidal formulationKnot parameterization for the Catmull–Rom algorithm
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.
Gif animation for uniform, centripetal and chordal parameterization of Catmull–Rom spline depending on the α value
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 .
3D centripetal Catmull-Rom spline segment.
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][vague]
In this figure, there is a self-intersection/loop on the uniform Catmull-Rom spline (green), whereas for chordal Catmull-Rom spline (red), the curve does not follow tightly through the control points.
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.
importnumpyimportmatplotlib.pyplotaspltQUADRUPLE_SIZE:int=4defnum_segments(point_chain:tuple)->int:# There is 1 segment per 4 points, so we must subtract 3 from the number of points returnlen(point_chain)-(QUADRUPLE_SIZE-1)defflatten(list_of_lists)->list:# E.g. mapping [[1, 2], [3], [4, 5]] to [1, 2, 3, 4, 5] return[elemforlstinlist_of_listsforeleminlst]defcatmull_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.deftj(ti:float,pi:tuple,pj:tuple)->float:xi,yi=pixj,yj=pjdx,dy=xj-xi,yj-yil=(dx**2+dy**2)**0.5returnti+l**alphat0:float=0.0t1: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)*P1A2=(t2-t)/(t2-t1)*P1+(t-t1)/(t2-t1)*P2A3=(t3-t)/(t3-t2)*P2+(t-t2)/(t3-t2)*P3B1=(t2-t)/(t2-t0)*A1+(t-t0)/(t2-t0)*A2B2=(t3-t)/(t3-t1)*A2+(t-t1)/(t3-t1)*A3points=(t2-t)/(t2-t1)*B1+(t-t1)/(t2-t1)*B2returnpointsdefcatmull_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]fordinrange(QUADRUPLE_SIZE))foridx_segment_startinrange(num_segments(points)))all_splines=(catmull_rom_spline(*pq,num_points)forpqinpoint_quadruples)returnflatten(all_splines)if__name__=="__main__":POINTS:tuple=((0,1.5),(2,2),(3,1),(4,0.5),(5,1),(6,2),(7,3))# Red pointsNUM_POINTS:int=100# Density of blue chain points between two red pointschain_points:list=catmull_rom_chain(POINTS,NUM_POINTS)assertlen(chain_points)==num_segments(POINTS)*NUM_POINTS# 400 blue points for this exampleplt.plot(*zip(*chain_points),c="blue")plt.plot(*zip(*POINTS),c="red",linestyle="none",marker="o")plt.show()
Plot obtained by the Python example code given above
Code example in Unity C#
usingUnityEngine;// a single catmull-rom curvepublicstructCatmullRomCurve{publicVector2p0,p1,p2,p3;publicfloatalpha;publicCatmullRomCurve(Vector2p0,Vector2p1,Vector2p2,Vector2p3,floatalpha){(this.p0,this.p1,this.p2,this.p3)=(p0,p1,p2,p3);this.alpha=alpha;}// Evaluates a point at the given t-value from 0 to 1publicVector2GetPoint(floatt){// calculate knotsconstfloatk0=0;floatk1=GetKnotInterval(p0,p1);floatk2=GetKnotInterval(p1,p2)+k1;floatk3=GetKnotInterval(p2,p3)+k2;// evaluate the pointfloatu=Mathf.LerpUnclamped(k1,k2,t);Vector2A1=Remap(k0,k1,p0,p1,u);Vector2A2=Remap(k1,k2,p1,p2,u);Vector2A3=Remap(k2,k3,p2,p3,u);Vector2B1=Remap(k0,k2,A1,A2,u);Vector2B2=Remap(k1,k3,A2,A3,u);returnRemap(k1,k2,B1,B2,u);}staticVector2Remap(floata,floatb,Vector2c,Vector2d,floatu){returnVector2.LerpUnclamped(c,d,(u-a)/(b-a));}floatGetKnotInterval(Vector2a,Vector2b){returnMathf.Pow(Vector2.SqrMagnitude(a-b),0.5f*alpha);}}
usingUnityEngine;// Draws a catmull-rom spline in the scene view,// along the child objects of the transform of this componentpublicclassCatmullRomSpline:MonoBehaviour{[Range(0, 1)]publicfloatalpha=0.5f;intPointCount=>transform.childCount;intSegmentCount=>PointCount-3;Vector2GetPoint(inti)=>transform.GetChild(i).position;CatmullRomCurveGetCurve(inti){returnnewCatmullRomCurve(GetPoint(i),GetPoint(i+1),GetPoint(i+2),GetPoint(i+3),alpha);}voidOnDrawGizmos(){for(inti=0;i<SegmentCount;i++)DrawCurveSegment(GetCurve(i));}voidDrawCurveSegment(CatmullRomCurvecurve){constintdetail=32;Vector2prev=curve.p1;for(inti=1;i<detail;i++){floatt=i/(detail-1f);Vector2pt=curve.GetPoint(t);Gizmos.DrawLine(prev,pt);prev=pt;}}}
Code example in Unreal C++
floatGetT(floatt,floatalpha,constFVector&p0,constFVector&p1){autod=p1-p0;floata=d|d;// Dot productfloatb=FMath::Pow(a,alpha*.5f);return(b+t);}FVectorCatmullRom(constFVector&p0,constFVector&p1,constFVector&p2,constFVector&p3,floatt/* between 0 and 1 */,floatalpha=.5f/* between 0 and 1 */){floatt0=0.0f;floatt1=GetT(t0,alpha,p0,p1);floatt2=GetT(t1,alpha,p1,p2);floatt3=GetT(t2,alpha,p2,p3);t=FMath::Lerp(t1,t2,t);FVectorA1=(t1-t)/(t1-t0)*p0+(t-t0)/(t1-t0)*p1;FVectorA2=(t2-t)/(t2-t1)*p1+(t-t1)/(t2-t1)*p2;FVectorA3=(t3-t)/(t3-t2)*p2+(t-t2)/(t3-t2)*p3;FVectorB1=(t2-t)/(t2-t0)*A1+(t-t0)/(t2-t0)*A2;FVectorB2=(t3-t)/(t3-t1)*A2+(t-t1)/(t3-t1)*A3;FVectorC=(t2-t)/(t2-t1)*B1+(t-t1)/(t2-t1)*B2;returnC;}