Turn a N-Ary B-Spline into a sequence of Quadratic or Cubic B-Splines

Question

I am doing some TTF work for MOSA (the correlating body between all the C# operating systems). Me and Colin Burn are currently working on getting some TTF code working (less me these days :) - he made a lot of progress).

In any case, the TTF spec allows for an arbitrary amount of control points between the 'handles' and gasp NO handles at all (the TTF has an example of a circle demonstrating it - well done idiots - you saved 10 bytes).

Can anyone give me a pointer on how this could be done? I looked at the Bezier article on Wikipedia but it wasn't really that much help - they show it happening, but don't give any math. Something 'program' ready would help (my Calculus isn't what it should be) - some pseudocode or something.

Thanks guys.

Answer 1

I did some digging and found some algorithms for the TTF spec over at this site over here.

Answer 2

From the Bezier article in wikipedia, with some practical calculus knowledge, you can translate the formulas to a computer program like the following pseudo C# code listing. I'm doing it with quadratic spline, but it is easy to translate to another.

// Quadratic spline, with three given points
// B(t) = (1-t)^2P(0) + 2*tP(1) + t^2P(2)
// where T is a real number in the interval [0, 1]

public void DrawQuadSpline(Point p0, Point p1, Point p2, int steps) 
{
    Point next = p0;
    Point previous = p0;
    double tStep = 1 / ((float) steps);
    double t = 0;
    for (int i = 0; i < steps; i++) 
    {
        float x = CalculateQuadSpline(P0.x, P1.x, P2.x, t);
        float y = CalculateQuadSpline(P0.y, P1.y, P2.y, t);
        Point next = new Point(x, y);
        drawLine(previous, next);
        previous = next;
        t = t + tStep;
    }
} 

private void CalculateQuadSpline(float z0, float z1, float z2, float t) 
{
    return (1.0-t)*(1.0-t)*z0 + 2.0*t*z1 + t*t*z2;
}

It might need some tweaking as I've only did this in Java before, but that's basically it.

Answer 3

Okay, it looks like TTF outlines are defined as quadratic b-splines.

There are two algorithms that you'll want to be familiar with.

The first is Bezier extraction via knot insertion. This will get you quadratic Bezier segments. Then you'll want to degree-elevate each Bezier segment to get cubics.

The main reference I use is my CAGD class textbook, which is online. Bezier extraction is covered in section 6.3. Degree elevation of Bezier curves is covered in section 2.4. Let me know if you have any problems..