This details my approach to building a tool that allows you to load and edit basic COLLADA mesh files that are now used by many major modeling packages and real time graphics engines. A COLLADA file describes a scene graph (much like SVG) that is a hierarchical representation of all objects in the scene (meshes, cameras, lights, etc.), as well as their coordinate transformations. Here I built Bezier curves and surfaces using de Casteljau's algorithm, manipulated half-edge meshes, and implemented Loop subdivision.

Bezier Curves and Surfaces

Bezier Curves with 1D de Casteljau Subdivision

A Bezier curve is a parametric curve defined by a single parameter, t, which ranges between 0 and 1. A Bezier curve of degree n is defined by (n+1) control points. Using de Casteljau's algorithm, we can evaluate these parametric curves for any given set of parameters. As an example to illustrate de Casteljau's algorithm, say we have three line segments. Following the algorithm, we use linear interpolation along with the parameter, t, to find a point on each of the line segments, giving a 3-point polygon. We can then find a new point on each of the line segments using linear interpolation, and the same t value, giving a 2-point polygon, or a line. We find a point on this line using linear interpolation again. As we vary the parameter t between 0 and 1, this final point traces out our smooth curve. These are the kind of curves Pixar typically uses to control the motion of their animated characters.

The following animation provides a visualization for de Casteljau's algorithm applied to bezier curves: