Friday, September 14, 2012

Path Interpolation Using Cubic Bezier and Control Point Estimation in Javascript

Let's say I have a series of individual points and I want to find a smooth path through them from start to end:

[caption id="attachment_243" align="aligncenter" width="500"> Set of points P0-P8[/caption]

Without any other information, I'd like to create a new semi-continuous path of points that smoothly runs through each of these key points in the defined path:

[caption id="attachment_242" align="aligncenter" width="500"> Key points anchor the line which smoothly winds through each one[/caption]

Immediately, a Bezier function of some sort seems appropriate to find this path.  An initial glance at the math to find this path through 9 points seems daunting.  Every site I looked at had long sets of calculations, proofs, and other notations which were not answering my question.  Fortunately, after some digging, I came to the conclusion that I did not need to find a curve through all the points at once.  It is possible to construct smaller curves point-to-point which will result in one larger smooth Bezier curve (Wikipedia).  In that case, we need at least three points to find a curve.  However, a quadratic Bezier (three points) does not have an inflection point so our curved segments would not flow nicely together.  Instead, we need to go one order higher to a cubic Bezier (four points) so we can build an "S" shaped segment.  With that concept in mind, we should be able to iteratively build cubic Bezier curves using several points at a time and then link these individual curves together end-to-end to form one continuous path from P0 to P8.

The first challenge to solve is how to find control points the Bezier function needs to calculate the curvature.  The points we're feeding into the algorithm are only anchor points.  However, each segment needs two anchor points and two control points.  After some research, I found a nice reference that showed how to construct triangles and midpoints from the anchor points to infer the control points.  As I was working on a demo, I got a little confused because in my mind I was trying to find four points to use in the cubic Bezier function and was calculating triangles from three anchor points which created two control points around the second point in the triangle ... etc.  Needless to say, there are a lot of points.  So with my trusty pen and paper, I set out to label all the points and attempt to make sense of them all.  When all was said and done I ended up with the following basic approach:

  1. Working with four sequential points at a time (P0, P1, P2, P3) from our total list of points do the following

    1. Find two control points (C1 and C2) based on the first three points (P0, P1, P2).

    2. Find two more control points (C3 and C4) based on the last three points (P1, P2, P3).

    3. Find the cubic Bezier curve for P1 and P2 using C2, C3 as the control points.

    4. Return the interpolated set of points between P1 and P2.

  2. Append the returned curve segment to the end of the prior segment and shift forward one point and repeat.

Once this process is complete, you will have assembled a curve that runs through all the points.  Each curve segment requires four points to construct.  These four points are not the inputs to the cubic Bezier function.  Instead, they create two triangles that are used to find the two points control points that will be used in the Bezier function.  Each triangle yields two control points, but only one of those points per triangle is used per segment (they actually all get used, the other control points that are calculated are for the segment before and after the segment being built.  It was just easier to throw it away and recalculate it later than trying to store it and recall it in subsequent iterations of the algorithm).  For any segment, you need to know the point before and the point after so you can find the correct curvature that will allow each curve segment to flow together seamlessly.

There are several observations you might make when looking at this algorithm:

  1. There is no point before the first point nor is there a point after the last point so how does the first and last segment get calculated.  The solution I came up with was to duplicate the first and last points and add it to the front and end of the list of points, respectively.  This creates a zero length leg on the triangle which creates a zero length control point which finally creates a zero length first/last segment.  However, the rest of the segments can be calculated properly because we have these fake anchor points.

  2. Every segment does a lot of math.  A creative solution is needed to find an algorithm to calculate the cubic Bezier with the least amount of math in the iteration steps.  I found one that only does addition in the looping section by calculating various derivatives prior to the loop.  This site has a nice explanation of the math if your curious.  The control point calculation algorithm also avoids using trigonometric functions to find the tangents to the the curve by using basic midpoints, proportions, and point translations.

Hooking all these pieces together I built a demo which allows you to plot some points on an HTML5 Canvas.  As you do this, the Bezier curve is calculated and each segment is drawn.  The curve is always one point behind since you need an extra point to calculate the prior curve segment (unless you click the "New" button which will complete the current curve by pushing a copy of the last point onto the end of points and run the calculation on the final segment).  The example also draws the various in-between points calculated to find the required control points.  I drew an example using the demo and labeled the various points to explain the process:

[caption id="attachment_249" align="alignnone" width="340"> The first point.  P0' is the copy of P0 which will allow the first segment to be calculated.[/caption]

[caption id="attachment_250" align="alignnone" width="340"> Add P1 - only three points so far - not enough to find a segment yet.[/caption]

[caption id="attachment_251" align="alignnone" width="340"> Add P2 - now there are four points so we can find the first segment.[/caption]

Above, you can see that after the first four points are plotted, we can find the first curve segment.  For the first iteration, you can only see one triangle (yellow lines).  This is the second triangle formed by P0,P1, and P2 (the first triangle is P0', P0, P1 but since the length of (P0',P0) is zero, that leg is not visible.  Notice that both triangles share the line (P0,P1).  The midpoints (M0,M1) are found on each line and the point Q1 is found on (M0,M1) by using the proportion of  the length of line (P0,P1) compared to the length of line (P1, P2).    The green line that connects M0 and M1 represents the tangent of the curve at P1.  If we translate M0 and M1 relative to the distance between Q1 and P1, we get the control points C1 and C2 which forms the red tangent line that runs through P1 (C2 is not shown here because its thrown out on this pass).  Notice how the length of (C1, P1) is the same as (M0, Q1).  We now have three of the points we need to find the curve - P0, P1, and C1.  But what about the other control point?  C0 is also calculated but since this is the first segment and P0' is the same as P0, it will be equal to M0.  So the first Bezier curve segment is found by (P0,C0,C1,P1).

[caption id="attachment_252" align="alignnone" width="340"> Add P3[/caption]

Now you can better see how the different control points are found.  For the curve between P1 and P2, we need C2 and C3.  Notice how C2 completes the other side of the tangent line through P1 and is just a translation of M1 relative to the vector between Q1 and P1.  So in this iteration, the control points C1, C2, C3, and C4 were all found, however, C1 and C4 are thrown out because they are not needed to find the curve between P1 and P2.  However, C2 and C3 can only be found by finding M0, M1, and M2.  We need those points to find Q1 and Q2 so the correct translation can be found to "copy" M1 to C2 and M1 to C3.

[caption id="attachment_253" align="alignnone" width="340"> Add P4[/caption]

Now I want to finish my curve.  However, I need a point after P4 to find the curve between P3 and P4.  The solution is to add P4 again:

[caption id="attachment_254" align="alignnone" width="340"> Close Line - add P4' to allow final segment to be calculated.[/caption]

You might notice that the plot points in the curves have a tendency to spread out and clump together.  The number of points to find is based on the distance between the anchor points.  This means that if the distance between point A to B is small and the distance from B to C is large, you will get points closer together between A and B and further apart between B and C because the number of points calculated is the same but spread out over two different distances.

Hopefully, this demonstration was clear enough to illustrate the process of building an interpolated curve using the cubic Bezier function.  I know it took me some time to rationalize all the calculations and points being created before understanding the what each piece represented and meant.  The efficiency of the algorithm compared to using trigonometric functions and many multiplications in the iterator makes it an excellent tool for quickly finding paths to use in various time critical tasks like animations.  This algorithm can even be used to draw sinusoidal shapes without using sine or cosine.  A few improvements I might investigate is controlling the step counter to make more even sets of points and allow control over scaling the control points so you can make smoother/sharper curves.  However, this is a pretty good starting point for the applications I have in mind for the function.