Shapes: Parametric Equations (and Spirals!)

This article is split up in 2 parts:

1. Converting a parametric graph into a PathIterator
2. An applet demoing a Spiral2D class

Introduction

A coworker recently wanted to paint a spiral. He found a programming book that included some sample code to generate spirals, but there were two catches:

For a small company like ours: use of that code required a $500 license fee.

Even then: the spiral he rendered was basically a polyline. (That is: it was rendered as a series of lines, and had no curvature.)

Both of these restrictions made that implementation a bad idea, so I decided to flesh out a better model. What I ended up with is a model that helps convert parametric equations to java.awt.Shapes, and a subclass that caters specifically to spirals.

Parametric Equations and PathIterators

Suppose you have a parametric graph expressed as x(t) and y(t): how do you draw that in Java?

At its most basic level: drawing a shape in Java requires a java.awt.geom.PathIterator.

Preferably we'll then package this iterator in a java.awt.Shape, but with just an iterator you can use the following code to create a fillable/drawable shape:

GeneralPath path = new GeneralPath();
path.append(myPathIterator, false);

A PathIterator breaks a path up into a series of bezier segments: so our first task is to bridge the gap between a parametric expression and bezier curve.

Mathematically this is trivial to compute, but it may require a couple of pages of scrap paper to derive/understand everything.

Converting Parametric Equations into Bezier Curves

The most flexible bezier segment type that Java supports is the cubic segment, so that's the segment type we want to focus on. A cubic bezier segment has 4 control points: two for each end of the segment, and two to define the tangent slopes at each endpoint. Our goal is break our parametric function into a series of cubic bezier segments. That is: we're starting out with the parametric functions x(t) and y(t), and we have to extract from that a series of segments, where each segment is defined by 4 points.

Before we dig in to the math here, we need to make an important distinction: we're starting with a parametric equation that uses a variable t. We're going to convert that into a series of adjacent bezier curves, but a bezier curve is also a parametric equation. So I'm going to refer to those segments as using t_bezier for their t-values. So we have "t" (for the master equation) and "t_bezier" (for the individual segments used to replicate the master equation).

If we want our bezier curve to fit a range of t-values from [ta, tb], then we know that:

x_bezier(0) = x(ta);
dx_bezier(0)/dt = dx(ta)/dt;
x_bezier(1) = x(tb);
dx_bezier(1)/dt = dx(tb)/dt;

This only matches our bezier curve to the endpoints. The closer those endpoints are: the better a match this piecewise solution is going to give us. (If they are infinitesimally close: they will be a perfect match.) This is discussed more below. For now: assume that "ta" and "tb" are reasonably spaced.

Since a cubic bezier curve can be expressed in terms of a cubic polynomial, we also know that:

x_bezier(t_bezier) = ax*(t_bezier^3) + bx*(t_bezier^2) + cx*(t_bezier) + dx;
x_bezier(0) = ax*(0^3) + bx*(0^2) + cx*(0) + dx = dx;
dx_bezier(0) = 3*ax*(0^2) + 2*bx*(0) + cx = cx;
x_bezier(1) = ax*(1^3) + bx*(1^2) + cx*(1) + dx = ax + bx + cx + dx;
dx_bezier(1) = 3*ax*(1^2) + 2*bx*(1) + cx = 3*ax + 2*bx + cx;

So it follows that:

x(ta) = dx;
dx(ta)/dt = cx;
x(tb) = ax + bx + cx + dx;
dx(tb)/dt = 3*ax + 2*bx + cx;

So now we've mapped our source equation to the polynomial coefficients we need. But a cubic bezier curve is traditionally expressed as a series of 4 control points -- not as 4 coefficients. The article "Shapes: an Introduction" explains most of the math needed to make this conversion. Eventually if we solve for the control points in terms of the original parametric equation, then we'll end up with:

end1 = x(ta);
end2 = x(tb);
ctrl1 = (dx(ta)/dt+3*x(ta))/3;
ctrl2 = (3*x(tb)-dx(tb)/dt)/3;

That is all the information we need to define a cubic bezier segment that replicates our original graph from [ta, tb]. (We also have to apply exactly the same logic to the y-equations/coefficients, but the end result is the same system using "x" instead of "y".)

This logic has been built in to the abstract ParametricPathIterator, so there is a PathIterator that breaks a parametric equation up into thousands of smaller bezier segments as needed. The most crucial piece of information we're lacking now is: what are the values for "ta" and "tb"? If they are too widely spaced apart: then the piecewise segments will not match the graph well. If they are too close together: then the shape becomes unnecessarily complex. This spacing is the responsibility of the subclass, because the varying complexity of the parametric graph we're plotting will affect the interval between t values.

Spirals

Now that we have a model to convert parametric graphs to PathIterators: creating a Spiral2D should be easy. First we have to identify the parametric equations involved. Traditionally a spiral is expressed as:

x(t) = centerX+coilGap*t*cos(2*pi*t)
y(t) = centerY+coilGap*t*sin(2*pi*t)

After working with this format, though, I quickly realized I wanted at least two other variables:

angularOffset: to affect the initial angle.

coilOffset: to affect the coil offset.

My revised definition of a spiral looks like this:

x(t) = centerX+coilGap*(t + coilOffset)*cos(2*pi*t + angularOffset)
y(t) = centerY+coilGap*(t + coilOffset)*sin(2*pi*t + angularOffset)

We'll also need to know the derivative. (Of course we could also just numerically approximate the derivative, but let's calculate it correctly since this article is supposed to be instructive...) After refreshing my memory regarding the product rule, I ended up with these equations:

dx/dt = coilGap*cos(2*pi*t+angularOffset)-2*pi*coilGap*(t + coilOffset)*sin(2*pi*t+angularOffset)
dy/dt = coilGap*sin(2*pi*t+angularOffset)+2*pi*coilGap*(t + coilOffset)*cos(2*pi*t+angularOffset)

The Spiral2DPathIterator is the finished product. It extends the ParametricPathIterator and implements the spiral equations above. Each coil (from 0 to 360 degrees) is broken up into 8 bezier segments; this is not a magic number -- it is simply what empirically looked "good". Also (in keeping with Java conventions) there is a separate Spiral2D object that implements the java.awt.Shape interface for your convenience.

Here is an applet demonstrating the final implementation:

This applet (source included) is available here.

p.s. Try clicking in the applet to define the endpoint for the spiral. (Also try using the shift key.)

Shapes: An Introduction

I try to sprinkle in some fun open-source code snippets in most of my articles -- but this article is different. This article is simply an overview of the java.awt.Shape object. Several other articles build on (or assume knowledge of) what I cover here.

What is a java.awt.Shape?

When I refer to a "shape" in Java, I'm probably referring to the java.awt.Shape interface. The most interesting method in this class is getPathIterator(AffineTransform) -- the results of all the other methods can be derived from this method.

OK, so what is a java.awt.geom.PathIterator?

This is the heart of shape information in Java. This iterator is similar to the human gesture of dragging a pen from one point in space to another. A path is a series of segments, and there are 5 basic types of segments:

1. SEG_MOVETO: this is the initial position of a path. Each path must begin with this segment. If a MOVETO segment is not followed by any other segments, though: that path is considered empty. You might get a dot if you called Graphics2D.draw(shape), but you won't get anything if you call Graphics2D.fill(shape).
   
2. SEG_LINETO: this segment requires an x-coordinate and a y-coordinate. This connects a line from the last path location to the point indicated.
   
3. SEG_QUADTO: this segment requires two points: the end point and a control point (more on control points later.)
   
4. SEG_CUBICTO: this segment requires three points: two control points and an end point.
   
5. SEG_CLOSE: this is an optional segment that connects the previous segment to the SEG_MOVETO that began this shape. Even if you draw 4 sides of a square, you need to add a SEG_CLOSE for some java.awt.Strokes to correctly render the tips of all corners.

A single PathIterator can contain any number of MOVETO's. Each MOVETO is equivalent to lifting your pen off a piece of paper and repositioning it to start a new segment.

Bezier Control Points

Quadratic and cubic segments use control points. These are ingenious points that are used to tug an existing path in certain directions. There's a great wikipedia page that describes this concept in detail (with diagrams and everything). What I want to do is focus on the math. I'll break this up into the quadratic and the cubic cases:

Quadratic Parametric Equations

The javadocs are the place to start when you want to study the math here. They describe a quadratic segment as:

P(t) = B(2,0)*CP + B(2,1)*P1 + B(2,2)*P2
       0 <= t <= 1

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = C(n,m) * t^(m) * (1 - t)^(n-m)
C(n,m) = Combinations of n things, taken m at a time
       = n! / (m! * (n-m)!)

This sounds a lot more complex than it actually is if you're willing to break it down. We can get rid of C(n,m):

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = [ ( n! / (m! * (n-m)!) ) * t^(m) * (1 - t)^(n-m) ]

And then expand the first equation:

P(t) = [ ( 2! / (0! * (2-0)!) ) * t^(0) * (1 - t)^(2-0) ]* CP +
       [ ( 2! / (1! * (2-1)!) ) * t^(1) * (1 - t)^(2-1) ] * P1 +
       [ ( 2! / (2! * (2-2)!) ) * t^(2) * (1 - t)^(2-2) ] * P2

Simplify everything:

P(t) = (1 - 2*t + t^2) * CP +
       [ (2*t - 2*t^2) ] * P1 +
       [ t^(2) ] * P2

This is still not really useful to me, though. What I want is an expression in terms of t:

P(t) = (CP-2*P1+P2)*(t^2) +
       (-2*CP+2*P1)*t +
       CP

In my code this usually manifests itself something like this:

double ax = lastX-2*x1+x2;
double bx = -2*lastX+2*x1;
double cx = lastX;

Likewise you can replace "x" with "y" to get the y coefficients. From here you can treat your bezier segment as a good ole parametric equation. You can always spot-check your math (in both the quadratic and cubic case below) by checking the values at t=0 and t=1. At t=0 you get lastX -- which is the right starting point -- and at t=1 you simply add all those terms together -- and the terms cancel to x2.

I hardly ever use quadratic segments, though. If the user needs more than lines, the cubic segment gives you a lot more flexibility...

Cubic Parametric Equations

Again, we'll start by looking at the javadocs for a cubic curve:

P(t) = B(3,0)*CP + B(3,1)*P1 + B(3,2)*P2 + B(3,3)*P3
0 <= t <= 1

B(n,m) = mth coefficient of nth degree Bernstein polynomial
       = C(n,m) * t^(m) * (1 - t)^(n-m)
C(n,m) = Combinations of n things, taken m at a time
       = n! / (m! * (n-m)!)

Expand that:

P(t) = [ 3! / (0! * (3-0)!) * t^(0) * (1 - t)^(3-0) ] * CP +
       [ 3! / (1! * (3-1)!) * t^(1) * (1 - t)^(3-1) ] * P1 +
       [ 3! / (2! * (3-2)!) * t^(2) * (1 - t)^(3-2) ] * P2 +
       [ 3! / (3! * (3-3)!) * t^(3) * (1 - t)^(3-3) ] * P3 

Now simplify:

P(t) = [ (1 - t)^3 ] * CP +
       [ 3 * t^(1) * (1 - t)^2 ] * P1 +
       [ 3 * t^(2) * (1 - t)^1 ] * P2 +
       [ t^(3) ] * P3 

Expand the exponents:

P(t) = [ (1 - 3*t + 3*t^2 - t^3) ] * CP +
       [ (3*t - 6*t^2 + 3*t^3) ] * P1 +
       [ (3*t^2 - 3*t^3)^1 ] * P2 +
       [ t^(3) ] * P3 

But what we really want is the equation in terms of t:
Lastly:

P(t) = [-CP+3*P1-3*P2+P3]*(t^3) + 
       [3*CP-6*P1+3*P2]*(t^2) +
       [-3*CP+3P1]*t +
       CP

So now we have the cubic equation expressing this curve in terms of T. Here is how I'd usually integrate this into my code:

double ax = -lastX+3*x1-3*x2+x3;
double bx = 3*lastX-6*x1+3*x2;
double cx = -3*lastX+3*x1;
double dx = lastX;

... and you can likewise define ay, by, cy and dy.

This concludes the introduction; look up other articles that are prefaced with "Shape" to see possible uses for this.