Saturday, 12 January 2013

Calculate Catmull-Rom splines using forward differencing - UPDATE

I finally had the time to finish this post by whipping up a small JavaScript canvas example to show forward differencing in action - Here it is. If it doesn't seem to work try to view the page on its own, there's some issue with the onload() event...

Regular Forward differencing

Not much to see there, actually, other than that the regularly drawn spline and the one drawn with forward differencing look the same. Here's the part of the code that does the forward differencing calculation for one section of the spline:

ctx.moveTo(points[1][0], points[1][1]);
//calculate values at point a and b
var ax = points[3][0] - 3.0 * points[2][0] + 3.0 * points[1][0] - points[0][0];
var ay = points[3][1] - 3.0 * points[2][1] + 3.0 * points[1][1] - points[0][1];
var bx = 2.0 * points[0][0] - 5.0 * points[1][0] + 4.0 * points[2][0] - points[3][0];
var by = 2.0 * points[0][1] - 5.0 * points[1][1] + 4.0 * points[2][1] - points[3][1];
//calculate 1st, 2nd, 3rd derivative between a and b
var stepsize = 1.0 / subdivision;
var stepsize2 = stepsize * stepsize;
var stepsize3 = stepsize * stepsize2;
var dx =  0.5 * stepsize3 * ax + 0.5 * stepsize2 * bx + 0.5 * stepsize * (points[2][0] - points[0][0]);
var dy =  0.5 * stepsize3 * ay + 0.5 * stepsize2 * by + 0.5 * stepsize * (points[2][1] - points[0][1]);
var d2x = 3.0 * stepsize3 * ax +       stepsize2 * bx;
var d2y = 3.0 * stepsize3 * ay +       stepsize2 * by;
var d3x = 3.0 * stepsize3 * ax;
var d3y = 3.0 * stepsize3 * ay;
//calculate points while updating derivatives
var px = points[1][0];
var py = points[1][1];
for (var j = 0; j < subdivision; j++) {
    px += dx; dx += d2x; d2x += d3x;
    py += dy; dy += d2y; d2y += d3y;
    ctx.lineTo(px, py);
}


A nice addition would be to do adaptive subdivision of the spline, depending on curvature, but I haven't gotten that right yet...

3 comments:

agamedesigner said...

Hi,

Thanks for sharing this! I've been looking for a solution such as this as I'd like to use it in a small game i'm working on. But, I suck at math. I was wondering if you could tell me what the variable 'points' is referring to. I'm assuming it's a 4x4 matrix. But can you please state how you have it defined in your code?

Thanks in advance for any insight you can provide.

Kim said...

Your browser can show the source. That might help you. Points is just an 2D array of float numbers ala ((x0,y0), (x1,x2))...

agamedesigner said...

Thank you!

Post a Comment