Of the dozens of request-for-help emails I get every week, one of the most common topics is general suggestions for actionscript optimization. There are numerous online resources for this topic, one of which is the ActionscriptWiki page. John Grden also has a nice post on this topic.
I’m a big fan of Polygonal Labs, and Michael has numerous posts such as this one that deal with fast approximation algorithms. This is another good one from his Actionscript category (well worth your time).
I believe I’ve mentioned Joa Ebert’s paper before in this blog, but it’s worth repeating. Post your favorite techniques and resource sites.
In comparing the parametric cubic spline to the cubic Bezier spline, you may notice that the parametric spline has a tendency to produce a ‘tighter’ or ‘less curved’ fit through the knot set. There is a technical reason for this observation that is based on the derivation of the parametric spline from the natural cubic spline, discussed in this TechNote.
Suppose the cubic spline, S, is to fit a set of knots in the interval [a,b]. Suppose the knots have some functional representation, f (which is unknown), and that the second derivative of f is continuous in [a,b]. By interpolating f with S at the knots, we exactly represent f at each knot and approximate f in between knots. It can be shown that
∫[S”(x)]2d(x) ≤ ∫[f”(x)]2d(x)
where the intgeral is over [a,b]. Since the curvature of a function is given by
|f”(x)|[1 + f'(x)2]-3/2
|f”(x)| is an approximation to the curvature, which is minimized by the natural cubic spline. As a result, this spline has a tendency to take a ‘less curved’ path through the knots.
Not as entertaining as Celebrity Deathmatch, but it is interesting to compare the two splines fitting the same set of knots. The demo used in the previous post introducing the parametric (cubic) spline has been modified to fit the Degrafa cubic Bezier spline to the same set of knots, as shown below.
The parametric spline is drawn in blue, as before. The cubic Bezier spline is drawn in red. There is a technical reason why the parametric spline tends to take the ‘less roundabout’ path through knots, which I may discuss in future posts. Neither drawing is more or less ‘correct’ than the other. They are just different tools that can be used by artists. In order for the parametric spline to be efficiently integrated into the Degrafa command stack, I will eventually work on a methodology to approximate general splines with quad. Bezier segments. Yet another item on that Degrafa ‘to do’ list 🙂
You may view the new demo and source code from the same links as in the parametric spline post.
In discussing the natural cubic spline, I mentioned that it was a piecewise cubic interpolant intended for tables of data with non-overlapping intervals. While there are some very useful theoretical advantages to this spline as an interpolant, it is difficult to use the spline as a drawing tool. A parametric spline is built on top of the natural cubic spline and it suitable for static drawings.
The spline is parameterized on chord-length. Each knot is mapped into [0,1] based on the fraction of the cumultative Euclidean distance between knots to the total distance. The domain in this parameterization is monotonically increasing. Two natural cubic splines are fit to the parameterized data; x vs. t and y vs. t.
The screen shot below shows an example plot.
The drawing is old-school; simple line segments. As such, it is not yet a candidate for direct inclusion in Degrafa. Because of the plotting method and the internal computational complexity, I would only use such a spline for static drawings. It is, however, built on top of the Degrafa natural cubic spline and serves as an example of how that spline can be used in practice.
If time allows this weekend, I will modify the demo to compare the parametric cubic spline to the Degrafa cubic Bezier spline. The current demo provides the parametric cubic spline as a standalone .as file. Degrafa is required to build the demo.
I ported the Singularity natural cubic spline to Degrafa over the weekend. Although it is intuitive to think of splines as drawing aides, the natural cubic spline is used primarily as an interpolant. If you believe there is a smooth (polynomial) relationship between data points representing an unknown function to be interpolated, the natural cubic spline is often a good choice. There is some theory that shows the natural cubic spline produces the smoothest curve that fits a data set (with non-overlapping intervals).
The smooth fit can often be obtained with fewer control points, compensating for the extra computation. The spline is piecewise cubic and C-2 continuous at the joins. The second derivatives are zero at the first and last knots (hence the term ‘natural’ cubic spline). The details are discussed in this TechNote.
Since the cubic spline is intended as an interpolation utility, it is located in the com.degrafa.utilities.math package. As an aside, the parameteric spline discussed in the TechNote can produce very eye-pleasing fits of arbitrary data points. Over the long term, I hope to add the ability to approximate non-Bezier splines with quadratic Beziers, allowing the parametric and Catmull-Rom splines to be included in Degrafa as drawing tools.
In the mean time, an extremely simple (non-interactive) demo is available.
Here is a link to a nice presentation on converting MXML components to straight AS. Had to do this a few times myself and it’s always helpful to have an understanding of what’s going on under the hood.
Well, once again I made changes to the tension algorithm. Interior knots in the quadratic spline serve as control points for individual quadratic Bezier segments. Anchor points are positioned along the line segments between knots. It is not possible to move the spline away from one knot without moving it closer to the next knot in sequence. This effect is somewhat balanced out by using a tension parameter in the middle of the range, say 0.3 to 0.6. A tension of 0.4 is shown in the screenshot below.
As the tension goes to zero, the spline moves away from the first interior knot at the expense of exactly interpolating the second. It moves away from the third interior knot at the expense of exactly interpolating the fourth, and so on as shown below. This actually allows cusps to be created with the spline, something not possible with the cubic Beziers spline.
As the tension moves from the midrange to 1, the spline progressively approaches straight-line segments from knot to knot. This allows the quad. spline to be used for a variety of drawings that are not possible with the cubic Bezier spline.
A simple online demo is available (first update your SVN – Origin branch). Position the cross-hair in the drawing area and click to define knots. After three knots are defined, the spline is automatically drawn. You can adjust the tension in MXML and recompile to test tension changes.