Wednesday, 17 August 2011

Calculate Catmull-Rom splines using forward differencing

Update: Here's a little JavaScript canvas example to give you some sourcecode...

Splines are a nice for interpolation of all kinds of stuff. A very nice, thorough (Bezier) spline documentation with lots of examples can be found here.
Catmull-Rom splines are handy, because they always pass through their control points. No fiddling with tangents and stuff. You give up some control over the curve though. This is what they look like:


The formula for this type of spline is:

p(t) = 0.5 * (1, t, t2, t3)  *
[  0
2
0
0 ]
[Pa]
[ -1
0
1
0 ]
*
[Pb]
[  2
-5
4
-1 ]
[Pc]
[ -1
3
-3
1 ]

[Pd]

The interpolation parameter t runs from [0,1] and t=0 gives you Pb, t=1 gives you Pc. Pa and Pd influence the curve.
If you simplify the formula something along these lines:

p(t) = 0.5 * ( (Pd - 3*Pc + 3*Pb - Pa) * t3 + (-Pd + 4*Pc - 5*Pb + 2*Pa) * t2 + (Pc-Pa) * t + 2*Pb)

Now you can evaluate that formula for increasing values of t and once for P(a,b,c,d)x and P(a,b,c,d)y. This gives you new vectors you can use to draw lines or whatnot.

Now this formula is somewhat computationally intensive, but there's a better way to do it. You can use forward differencing to simplify the computations going on in the loop. This page describes the process quite well for Bezier curves.

No comments:

Post a Comment