Bezier Curves

What Curves?

Bezier curves. We'll take the formal mathematical approach to this problem.

1. Take n+1 control points.
2. The curve will start at the first control point and end at the last control point.
3. Iterate between t = 0 and t = 1 for small steps of t for curve points and connect the points:

   Curve point(t) = Sum each point multiplied by the Bernstein polynomial for "n choose i" evaluated at t.

Note: For example, the Bernstein polynomial for the second (i = 1) of four points (n = 3) would be the Bernstein polynomial for 3 choose 1, which is 3(1-t)t^2.

Implementation

For my implementation, I created a BernsteinPolynomial class, which objects are instantiated for a given (i,n) pair. A call can be made to evaluate the polynomial at a given t value. Be careful, with this approach you need to regenerate all the polynomials every time you change the number of control points.

public class BernsteinPolynomial {
    private int mBinomialCoefficient;
    private int mI, mN;

    public BernsteinPolynomial(int i, int n) {
        // Sanity checks
        assert (n >= 0);
        assert (i >= 0);

        if (n < 0 || i < 0) {
            throw new Error("Cannot create Bernstein polynomial for " + i + ','
                    + " and " + n + '.');
        }

        // Setup object
        mI = i;
        mN = n;
        mBinomialCoefficient = Combinatorics.binomialCoefficient(mN, mI);
    }

    public String toString() {
        return "(" + mBinomialCoefficient + ") " + ((mI == 0) ? "" : "t^" + mI)
                + "(1-t)^(" + (mN-mI)+")";
    }

    /**
     * Evaluate this at the given t value.
     */
    public double evaluate(double t) {
        double oneMinusT = 1.0 - t;

        // Bn(t) = (n choose i)*(t to the i)*(1 - t to the n-i)
        return mBinomialCoefficient * Math.pow(t, mI)
                * Math.pow(oneMinusT, mN - mI);
    }
}


Writing the "n choose i" shows a useful case of recursion.


public class Combinatorics {

    public static int factorial(int i) {
        assert(i >= 0);
        if (i == 0 || i == 1)
            return 1;
        else
            return i * factorial(i - 1);
    }

    public static int binomialCoefficient(int n, int k) {
        return factorial(n) / factorial(k) / factorial(n - k);
    }
}


Encapsulation

A BezierCurve encapulasates this so we can change to a recursive implementation of the drawing without messing with our clients. It also handles caching between drawings so we don't need to recalculate every time we draw.

Write once, debug everywhere.

Java was initially heralded as the "Write once, run anywhere" language, and with its Swing GUI library this would end all programmers frustrations of porting code. Right? Of course this myth didn't last two long as there are a lot of undocumented hacks necessary to get our programs to play nicely on different systems. I remember one hack specifically from Game Programming in Java regarding an additional method call to the event queue to properly process events on Linux.

And of course I've run into this again on Windows with QtRuby. Something in several of my examples which use Qt::Timer (QTimer) for stepping simulations and repaints work fine on Linux, but not at all on Windows. Since I use Linux exclusively this isn't a critical issue right now, but I'm going to have to look into it if I plan to distribute any of my programs on Windows.