a maths day

Since is always posting about his antics bending Maya to his will, I felt like sharing my working day. Without going into detail about what I’m working on (which is still hush-hush until it’s announced), I can say that today I did more maths than I’ve done in a long time. I wrote some code to do adaptive subdivision of a Catmull-Rom spline.

First a bit of background. Wikipedia defines a Catmull-Rom spline as “a cardinal spline with a tension of 0.5”. In slightly easier terms, a Catmull-Rom spline is basically a parametric curve given by a cubic polynomial and as many waypoints as you like. It has the nice property that the curve passes through each waypoint. Four waypoints are required to specify the curve: between any two waypoints P1 and P2 you also need P0 and P3 (the waypoints immediately before and after the segment you are considering) to calculate the curve. This also means that if you want a curve n waypoints long, you need n+2 waypoints (one extra at each end). There is also a DirectX function to calculate a point on the curve given the four waypoints and the parameter t, where t=0 at P1 and t=1 at P2.

First, I had to figure out the functionality I was after. Regular subdivision is where you step between waypoints with a regular step size. I.e. if you wanted 4 subdivision segments, your values of t would be 0.25, 0.5, and 0.75 (dividing the curve into quarters). Adaptive subdivision works differently: it takes advantage of the fact that the curve might be a straight line between t=0 and t=0.5, say, so there wouldn’t be much point adding subdivision points there – they are better used where the curvature of the spline is higher. If you want 3 subdivision points, they might end up at t=0.7, t=0.8, and t=0.9.

That’s the functionality in English. In more mathematical terms, the curvature of the line is another way of saying “how large is the second derivative?” Calculus! I had to calculate d²y/dx². But for a parametric curve, it’s a little more tricky than usual. Most equations you meet every day on the street are of the form:

y = (something to do with x)

But a parametric equation is of the form:

y = (something to do with t)
x = (something else to do with t)

(In the case of the Catmull-Rom spline, the “something” and “something else” are in fact basically the same thing, but that doesn’t immediately make it any easier.)

Since the equations are in the form of t, we can’t immediately compute dy/dx (the first derivative – a step along the way). Instead, we can compute dy/dt and dx/dt. Then use the chain rule:

dy/dx = (dy/dt) / (dx/dt)

Fair enough – a plain cubic polynomial is easy enough to differentiate and I obtained dy/dt and dx/dt in short order. But it doesn’t stop there. What I’m really after is the second derivative, d²y/dx², which is another way of saying I want to differentiate dy/dx. But I have dy/dx in the form of a fraction with a nasty polynomial on the bottom. I turned to the quotient rule:

let f = dy/dx = u/v
then df/dt = (v.du/dt – u.dv/dt) / v²

Again, the quadratic (at this stage) polynomials u and v are easy to differentiate. So far so good.
Finally another application of the chain rule:

df/dx = (df/dt) / (dx/dt)

And I have finally obtained df/dx, i.e. (d/dx)(dy/dx), i.e. d²y/dx², the second derivative of the curve! All that remained was to write a loop to insert subdivision points as necessary based on a threshold value of the second derivative, do a bit of debugging, and Bob’s your uncle. I now have a nicely adaptively-subdivided Catmull-Rom spline.

But what, you ask, was the ultimate point? Well, with any subdivision, the curve is approximated with a series of straight lines. Because an adaptively-subdivided curve is more intelligent about where it places subdivision points, it can typically achieve accurate approximation of the curve with fewer points than required by a regular subdivision method. The practical upshot of which in my case is fewer polygons, fewer calculations, and therefore faster code. Every microsecond counts!