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.

Drawing a Rosette

Building the Rosette

Above is a picture of a rosette with 40 points. To make a rosette, create a set of equidistant points around a circle and then connect every point to every other point.

Candidate Points

First, we need to compute the rosette points by making points equally spaced around a circle.

struct GLFloatPoint{GLfloat x, y;};

// Compute the candidate points, by equally
// spacing them around a circle.
GLFloatPoint* points = new GLFloatPoint[numPoints];
float angleStep = (3.14159f * 2.0f / numPoints);
float currentAngle = 0.0f;
for(unsigned int i=0; i<numPoints; i++)
{
  points[i].x = radius*cos(currentAngle);
  points[i].y = radius*sin(currentAngle);

  currentAngle += angleStep;
}

Connecting Points

If you connect every point to every other one, you end up with duplicate edges between vertices.

How do you get not create duplicate edges in the simplest possible way? Once you connect a certain point to all others, keep it out of the list of points to connect to. This can be done using two loops. The outer loop tracks the vertex we are connecting from, and in the inner loop tracks the vertex to which we are connecting.

unsigned int index = 0;
// The vertex we are connecting from.
for(unsigned int j=0; j<numPoints; j++)
{
  // Connect to all other points.
  // Lines have an origin and end point.
  for(unsigned int k=j+1; k<numPoints; k++)
  {
    rosettePoints[index].x = points[j].x;
    rosettePoints[index].y = points[j].y;
    index++;
    rosettePoints[index].x = points[k].x;
    rosettePoints[index].y = points[k].y;
    index++;
  }
}

Drawing

Vertex Arrays

Using vertex arrays, we can build the entire rosette at startup, and then can send all the vertices to be drawn at once. Using an array of GLFloatPoint, causes the x's and y's in the structs to align in memory just as if they had been put into an array of GLfloat.

Conceptually,

/* Structs  */
  GLFloatPoint A, B, C;
  GLFloatPoint pointArray[] = {A, B, C}
/* Manually */
  GLfloat      floatArray[] = {A.x,A.y,
                      B.x,B.y, C.x,C.y}

// You need to cast the pointers for this to work,
// but this is why I miss pointers in Java/Ruby.
GLFloatPoint* pointPtr = (GLFloatPoint*)floatArray;
  pointPtr[0].x = // A.x
  pointPtr[0].y = // A.y
  pointPtr[1].x = // B.x

GLfloat*      floatPtr = (GLfloat*)pointArray;
  floatPtr[0] = // A.x
  floatPtr[1] = // A.y
  floatPtr[2] = // B.x
  floatPtr[3] = // B.y

Struct Pointer Magic

In short, we can merrily use the array of GLFloatPoint in place of a big array of floats. This makes it easier to figure out where you are in the array quickly, since incrementing a GLFloatPoint* in a loop will move you forward one point. Also, you can use array notation, point[10], for the 11'th point, for instance.

  // Allow us to use vertex arrays
  glEnableClientState(GL_VERTEX_ARRAY);

  // Set the array of points to use
  glVertexPointer(2, GL_FLOAT, 0, rosettePoints);

  // Render lines from the array vertices.
  // rosetteSize = (numPoints-1)*numPoints/2*2.
  //    This comes from connecting every point to
  //    every other point without duplicates.
  //    The "*2" comes from two vertices per line.
  glDrawArrays(GL_LINES, 0, rosetteSize);

Ruby Vector2D

A 2D Vector for Ruby. This is for the Koch snowflake and future 2D examples. Feel free to let me know how I can improve it, or where I can find a good third-party implementation.

Writing geometry classes has been one of my biggest frustrations because of the different implementations, or lack thereof, in the various graphics packages. As a result of this, my first instinct when picking up a new framework is figuring out what geometry is supported and the operations that are available.

A good geometry class for points, vectors, lines, shapes, etc., can save you a lot of headache trying to remember how to do a certain geometrical operation, and focus instead on putting these operations together.

# Use this so glVertex works.
require 'opengl'

class Vector
 attr_accessor :x, :y;

 def initialize(x,y)
  self.x = x
  self.y = y
 end

 def gl_vertex
  GL::Vertex2f(x,y)
 end

 def normal
  Vector.new(-@y,@x)
 end

 def normalize
  before_length = length
  return if before_length == 0
  @x /= before_length
  @y /= before_length
 end

 def length
  return Math.sqrt(@x*@x + @y*@y)
 end

 def reverse
  @x = -@x
  @y = -@y
 end

 def add_vector(v)
  @x += v.x
  @y += v.y
 end

 def sub_vector(v)
  @x -= v.x
  @y -= v.y
 end

 def multiply(scalar)
  @x *= scalar
  @y *= scalar
 end

 def divide(scalar)
  @x = @x / (1.0 * scalar)
  @y = @y / (1.0 * scalar)
 end

 def Vector.copy(p)
  return Vector.new(p.x,p.y)
 end

 def Vector.between(p1,p2)
  between = Vector.new(p2.x,p2.y)
   between.sub_vector(p1)
  return between
 end

 def to_s
  "#{x}, #{y}"
 end

 def Vector.midpoint(p1, p2)
  midpoint = Vector.new(p1.x,p1.y)
  midpoint.add_vector(p2)
  midpoint.divide(2.0)
  return midpoint
 end
end