replicator.org ... continuous garbage collection

Though I have ordered a new license on Friday, today my Resharper license run out, so I have time to do write a blog post :)

Cubic Béziers are built up from 4 points. A beginning point, an ending point and two spanning points that define the shape of the curve. If the two intermediate points are lying directly on the line connecting the beginning with the ending point, the cubic Bézier is a line.

What can be seen in most editing software is the manipulation of the cubic Bézier by dragging their spanning points. This is simple to implement, but does not reflect the user’s intentions. Users don’t care about points that don’t lie on the curve. So for my small graph/concept editor, I wanted to implement a more natural way to modify curves (if you have not seen it, take a look at the blog post about LightConcept).

I’ll try to explain the math by going through the steps that are required to implement the complete bending workflow:

Where is the curve?

Initially there is only a line to hit, but if the user has transformed a line to a curve, we need to find out where it is.

Though most graphical frameworks would give us hit testing for free, there is again, a usability problem: The user’s intention is not to hit the curve exactly with the mouse.

To ease the selection, hit testing should actually be valid for some pixels near the curve.

The GraphicGems series contains a algorithm collection for Bézier curves we can use here to shortcut the math:

First we need to find out the nearest point the lies directly on the curve. This is done with the function “NearestPointOnCurve”. The resulting point’s distance to the current mouse coordinates can be used to decide if the user has hit the curve.

The magical t

Popping out from “NearestPointOnCurve” also comes the interpolation t value that ranges from zero to one (just remove the last line and return t). Zero represents the beginning point and one the ending point of the curve. The t can be thought of as describing how far a point on the curve is from beginning to end.

Finding t after the hit test is important so that we are able to distribute movements on the curve’s spanning points.

Distribution of Movements

Now the user has hit a curve, and we know where and the value of t. As soon the user moves the mouse, we need to modify the curve’s points to ensure that it goes through the new position.

Though we have four points defining the curve, we can only modify the two spanning points. What we need to find out is how much each of the points contribute to a point at a given t.

Interestingly, this contribution value is constant for each t and is defined by the basis functions of a cubic Bézier:

Picture copyright 1986 - 1993, 1998, 2004 Thomas Williams, Colin Kelley (gnuplot.info)

where x is our t and bez0 is our beginning point bez3 our ending point and bez1/bez2 the two spanning points. The formulas for the four points are:

• (1 - t)^3
• 3 * (1 - t)^2 * t
• 3 * (1 - t) * t^2
• t^3

We now take the delta of the mouse moves and derive the two vectors required to change the curve for the two spanning points. Additionally, we have to take into account that

1. we can not change the start and ending point of the curve. So the contribution of the  start and ending point needs to be compensated by an additional modification of the spanning points.
2. we need to find some natural weight that should be applied to the contribution to the two spanning points. This weight is important so that the user can modify the curve more locally. The effect of the user’s moves should not be even for the complete curve. For example, if the user grabs the curve more near the ending point, changes near the starting point should be minimized.
   It turns out that a good weight choice is to use the value t and scale it three times so that 1/3 t only modifies the first spanning point and 2/3 only modifies the second spanning point. If (t-1/3)*3 is less than zero or greater then one we just clamp the value.

The final algorithm to compute the new spanning points looks like:

CubicBezier bend(CubicBezier bezier, double t, Point target)
{
  // compute the influence of each of the points.
  var basis = CubicBezierBasisFunctions.compute(t);
  // decide for a distribution to the spanning points.
  var pointOnBezier = bezier.pointOfT(t);
  var delta = target.sub(pointOnBezier);
  // influence factors for now (influence1 + influence2 < 1.0)
  var influence1 = basis[1];
  var influence2 = basis[2];
  // the factor of influences we want distribute on the source points.
  // so, when t == 1/3 the first span point must do everything, when t == 2/3
  // the second one, this way users have a more fine grained control over 
  // the angles at the ends.
  var distributionFactor = (t - (1d/3d)) *3d;
  if (distributionFactor < 0d)
    distributionFactor = 0d;
  if (distributionFactor > 1d)
    distributionFactor = 1d;
  var influenceFactor1 = 1d - distributionFactor;
  var influenceFactor2 = distributionFactor;
  // now compute the scale of the influence to match 1
  double influenceScale1 = influenceFactor1/influence1;
  double influenceScale2 = influenceFactor2/influence2;
  // this is the delta of the two points.
  var delta1 = delta.scaled(influenceScale1);
  var delta2 = delta.scaled(influenceScale2);
  return new CubicBezier(bezier.Start, bezier.Span1.add(delta1), bezier.Span2.add(delta2), bezier.End);
}

The new Curve

Now, the result are the two new spanning points, which, together with fixed start and ending point, build a curve that goes through the point of the current mouse coordinates. The point’s t stays constant, so the user also has the option to skew the curve.

If the user grabs and changes the curve in the middle between the start and end point, the curve changes as a whole. If it’s been selected more towards the end or the starting point, the effects are more local which enables the user to adjust the curve endings in more detail.

Try it

You can directly try out my implementation of this algorithm with LightConcept (Silverlight required):

1. click on the background to create a new node
2. press the (+) and drag it to create a second, connected node.
3. press the curve and drag to bend it.

Enjoy it!