Thursday, September 30, 2010

Bezier Curves as Ellipses

A couple weeks ago, I was exploring the source code for the Java runtime classes, trying to figure out exactly how Java draws a circle, and was surprised at what I found. A circle can be defined as an instance of the java.awt.geom.Ellipse2D class with equal width and height. Graphics2D attempts to draw the Ellipse2D shape by calling for its PathIterator. A PathIterator returns segments of the shape in the form of SEG_MOVETO, SEG_LINETO, SEG_QUADTO (quadratic Bezier curve), SEG_CUBICTO (cubic Bezier curve), or SEG_CLOSE. An Ellipse2D contains an initial MOVETO, four CUBICTO segments, and a final CLOSE.

I eventually got my head around what that meant and its implication: The standard 2D graphics library doesn't concern itself with center points and radii, or foci, or pi. In fact, it doesn't even render a real circle, but a very close approximation. It renders four cubic Bezier curves representing 90 degree arcs of the circle. I found this discovery strange at the time, but on reflection it made sense.

First, turning the radius and angle into Cartesian coordinates requires using sine and cosine functions. Java doesn't contain its own sine calculator or lookup table, it delegates to a native library. Second, once all the Bezier control points are established, no expensive division or square roots need to be done in order to calculate the curve. Only addition, subtraction, and multiplication. Third, while conic sections can all be represented by Bezier curves, the reverse is not true, so if you had to pick one, Bezier would be it. Lastly, applying affine transforms to curves is as easy as applying the transforms to the control points and redrawing. So basically these curves look the same to the naked eye as a circle, and are easier on the processor to render. Whether or not that's why the Java developers went that direction, I have no idea.

So, what's a Bezier curve, anyway?

A Quadratic Bezier curve is a distortion to a straight line with a single "control point" that has influence over it, acting like a sort of gravity well. The closer a point on the line would be to the control point, the more the curve is distorted from the line.

Plotting the curve is surprisingly simple. Start with a line between the start and control points, and another between the control and end points.

Next, pick a percentage, that we'll call "t". Plot a point t% between start and control, and another t% between control and end. Draw a line between these points. On this ancillary line, the point at t% gets added to the curve.

That's it. Repeat this for all possible "t"s, and you have your curve. Below is a simplified example, showing t at 25%, 50%, and 75%:

This shows the same curve at 5% iterations instead of in quarters, showing more detail of the curved shape:

A Cubic Bezier curve functions on the same basic principle, except there is an additional control point distorting the curve. Plotting them out is similar, but you have two ancillary lines instead of one, which you draw an... ancillarier? tertiary? line between, as illustrated here:

You can make fancier shapes with a cubic curve, such as moving one control point on the opposite side of the start/end line to make an s-shape:

Neat, but doesn't help us draw a circle. What does, however, is the equation for kappa, , which G. Adam Stanislav derives for us here. If the start and end points are on opposite corners of a square, and control points are on perpendicular lines, each kappa * side away from a termination point, a circular arc is drawn:

...which is the way Java does it. The equation for kappa evaluates to roughly .5522847498307933, which Java has as a static variable in the java.awt.geom.EllipseIterator class, to avoid needing to calculate a square root every time a circle is drawn.

public static final double CtrlVal = 0.5522847498307933;

1 comment: