Shapes: Bezier Control Points & Data Models

This article explores a GUI that manipulates a shape with bezier shape segments.

The end result is the following applet. To use this applet:

1. Click the "Create New Path" button.
   
2. Click and drag in the large empty JComponent below the controls.
   
3. Repeat the previous step until you like your shape.
   
4. Double-click, or click "Create New Path" to leave path-creation mode.
   
5. Interact with the square and circular handles in the workspace.
   
6. Try fiddling with the scale and constraints.

You can download this jar (source included) here.

Data Models

The GeneralPath (or Path2D in Java 1.6) is the simplest way to represent an arbitrary shape in Java.

However for the applet above we need something a lot more specific. We need:

• A mechanism to change curve data after it has been added.
  
• A model that emphasizes a shape as a list of nodes, with optional control points before and after each node.

Also the book About Face mentions:

The closer the represented model comes to the user's mental model, the easier he will find the program to use and to understand.

In my case "the user" is actually the developer who wants to use the classes I write. I want to obscure from the developer that a PathIterator is really going to define a cubic segment #N with 3 points:

1. The second control point for the (n-1)th point.
   
2. The first control point for the nth point.
   
3. The nth point.

To mimick the GUI presented in the applet I defined the CubicPath. With this class you can iterate through the data in a shape in a couple of ways:

for(int nodeIndex = 0; nodeIndex < myPath.getNodeCount(); nodeIndex++) {
 myPath.getNode(nodeIndex, dest);
 //do something
}

... or:

for(int pathIndex = 0; pathIndex < myPath.getPathCount(); pathIndex++) {
 for(int nodeIndex = 0; nodeIndex < myPath.getNodeCount(); nodeIndex++) {
  myPath.getNode(pathIndex, nodeIndex, dest);
  //do something
 }
}

Similarly there are methods for getNextControlForNode(nodeIndex) and getPrevControlForNode().

(In this case "next" means "defined after" and "prev" means "defined before".)

It is possible for control points to be null. In the absence of control points on either side of a segment: that segment will look like a line.

(Also, deep down the SimplifiedPathIterator is used so if possible a cubic segment will be converted to a line in the PathIterator. But this is exactly the kind of implementation detail I'm trying to bury, so pretend I didn't say anything.)

Scaling Factor

I applied the first draft of the CubicPath to a project at work, and I was surprised that one my boss's first critiques was: the handles are too sensitive. That is: in order to get certain interesting curves you have the drag the handles outside of the JComponent.

At work we've modeled cubic-based shapes before, and a long time ago (in a very different, complicated architecture) we did in fact scale the vector the control points form with the actual end point. I don't think we scaled it by very much, and I was impressed my boss immediately noticed this contrast in the two models.

So to address this problem I added the scalingFactor field in the CubicPath. (See setScaleFactor and getScaleFactor). I'd have to fumble around for the right words to mathematically/programmatically express exactly what it does: but if you play around with this feature in the applet above it should be pretty self explanatory.

It in no way affects the underlying shape; but it does affect the points returned by getNextControlForNode() and getPrevControlForNode(). This lets you adjust the "sensitivity" of the handles.

Continuous Curves

In order to maintain continuous curves: the two control points surrounding a node must be collinear. Their magnitudes can vary, but their angle needs to be the same.

To help in this area I added a couple extra methods (see the "Constraint" feature in the applet to try these out):

setNextControlForNodeFromPrev(int nodeIndex,boolean includeDistance);
setPrevControlForNodeFromNext(int nodeIndex,boolean includeDistance);

So if you just defined the previous control point for a node, you can call setNextControlForNodeFromPrev to make sure the next control point matches the previous (and vice versa).

These methods will always force the angles of the control points to match. The boolean includeDistance controls whether the magnitude is supposed to match, too.

Conclusion

Like all my blog articles: this may be revised in coming days/weeks after I first publish it. But it is my hope that this is a solid interface for designing java.awt.Shapes that will really simplify my life. My goal is to never have to delve into this business again. Hopefully if this meets your needs you can use it and save some time, too.

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.

AlphaComposites: Which Does What?

It seems like every 4 months or so I come across a particular problem that I want to solve using AlphaComposites. The problem is I'm a very visual person; the equations listed in the javadocs don't help me visualize what each composite actually looks like.

Here is an applet that demonstrates most of the possible variables at play:

This applet (source included) is available here.

Also there are several AlphaComposite types where it makes a huge difference whether you're rendering images vs shapes. In this applet if "Use Images" is selected then the shapes you see are first rendered in a BufferedImage, and then those images are rendered together.

That's all. This is a clean, short article -- as much for my benefit as anyone else's.