Path Conversion for Animation
A recent post on the SVG Developer’s list reminded me of an algorithm that I thought could be used to prepare paths for animation, from one to another. The SVG specification requires that the values used to animate a d attribute must match command for command. For example, if your initial shape has the following command sequence, M C S h v z, then the “to” or “values” attribute describing the animation must have exactly and only those commands. This seems like a reasonable requirement since it allows the SMIL engine to worry only about changing values and not about changing path command types. At first, I found this to be an annoyance, but now I believe the working group made this decision out of necessity. We need only look at the path’s pathSegList.
Keeping a one-to-one correspondence of path data commands between animated path data values means that the path segment list of the path being animated remains constant. Without this requirement the SMIL engine would run into confusing situations. For instance, the initial path data might have a C command in the third position and the animation data might have a T command in the same place. The first command is a cubic Bezier, whereas the second command is a smooth quadratic Bezier. So, the first problem is how do we interpolate between the polynomials describing the cubic Bezier and the ones describing the quadratic Bezier? Another problem is how do we phase in the effect of the previous Bezier’s last handle? Note that the T command uses a proceeding Q, q, T, or t command’s handle to determine its own handle. If these situations are solvable, at the very least the solution would probably be complicated. Also, you may have noticed that we haven’t even begun to consider all of the combinations of path commands that could be encountered.
Okay, great. So, our path animation data must always have the same commands. Unfortunately, in the real world, the chances of two paths matching command sequences is low unless the shapes are very simple. Again, the only way we can animate between two paths is to make their path data match command for command. We need a way to convert our paths into paths with equivalent command sequences while at the same time preserving their original shapes. Here’s where that algorithm I mentioned earlier steps in.
It turns out that all path commands can be approximated using the cubic Bezier command. The same is probably true for the quadratic Beziers, but I am more familiar with the conversions using cubic Beziers. By converting all path commands to cubic Beziers, we now have a homogenious list of command types. The only thing we need to do now is somehow make the two lists equal in length.
In my Drawing Beziers tutorial, I show a method, not surprisingly, for drawing cubic Beziers known as the de Casteljau algorithm which uses only simple math. The approach uses geometry to calculate each point along the Bezier curve. As it turns out, there is neat little side-effect of this algorithm which allows you to split a Bezier at any point along its curve. Viola! Using that method, we now have a way to add new cubic Beziers to our path without changing the path’s appearance. To see the results of this approach, please have a look at the examples on my Path Parser page.
We need to considered where points should be added to each curve. I decided to base my insertions on relative arc length. The SVG specification includes a method in the path element interface that allows you to query a path’s length. We can make our way through our list of cubic Beziers, requesting the arc length of each. From there we can determine each segment’s relative arc length by finding its length relative to the entire curve’s length (a percentage). I make lists of these relative lengths for each path and begin traversing the lists of values in parallel. If a value exists in only one curve, then I add a new point at that relative arc length in the other curve. Once the two lists have been completely traversed, we end up with two paths with the exact same number of cubic Bezier commands.
As a final note, when adding a point to a Bezier curve, we need to know the value of a parameter t, which is between 0 and 1, inclusive. It seems reasonable to assume that a value of 0.5 would be at a position 50% along the curve; however, in reality this is not the case. The approach I used to add points to a curve is based on arc length, so I needed a way to associate arc length with that length’s corresponding t value. The SVG specification does not define a method in the path element’s interface to query for this value, so I had to write my own implemention which in turn required me to write my own arc length method.