Archive
Actionscript Optimization
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.
Cubic Spline and Curvature
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.
Parametric Spline vs. Cubic Bezier Spline
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.
Comparing Parametric and cubic Bezier splines
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.
Parametric Spline
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.
A Parametric Cubic Spline
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.
Degrafa Natural Cubic Spline
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.
MXML Components to AS
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.
http://experts.na3.acrobat.com/p71443527/
enjoy!
Degrafa Quadratic Spline Released
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.
Quadratic Spline, tension 0.4
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.
Quadratic spline with a cusp
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.
Degrafa Quadratic Spline Preview 2
I made some small changes in the tension algorithm, so the spline is not quite as ‘tight’ as in earlier previews. The following screenshot illustrates a tension setting of 0.3 (which seems to be a good starting point).
Quadratic Spline (tension = 0.3)
An autoClose parameter was also added. If true, then an additional knot is added to the spline to create a closed shape. There is no attempt to match tangents at the join between the first and last knots. This allows for the creation of shapes that are different from a closed cubic Bezier spline. The following screenshot shows my pathetic attempt at something resembling a teardrop shape (I’m sure a real designer could do much better).
Auto-closed quadratic spline.
One or two more tests and the demo (and code) should be released in a day or two, although I’ll probably make one more change to the tension algorithm.
Degrafa Quadratic Spline Update
As promised, I did work on the Degrafa quadratic spline this weekend. I decided to pass on having an interpolative quad. spline (i.e. one that exactly passes through all data points). If there is one quadratic curve per segement (between each set of two data points) with tangent-matching at the joins, then one of the problems with a quadratic curve is handling inflections in between knots. I had temporarily alleviated this issue by inserting artificial data points, but did not like the general look of the curve.
At the end of the day, this is what the cubic Bezier spline is designed to accomplish. The purpose of the quadratic spline is fast drawing of ‘approximate’ shapes. The extra computation and complexity was simply going against the original purpose of this spline and was pushing the quad. spline towards functionality that already existed in Degrafa.
While I may revisit this issue at some future point, I hope to release the quad. spline this week or next after a few more rounds of testing. The spline will interpolate first and last data points. Interior points influence the shape of the spline, but the spline does not interpolate those points. It should draw pretty fast and will be further performance-optimized in the future.
Degrafa Quadratic Spline Preview 1
As development progresses on the Degrafa quadratic spline, I’ll post a few previews of how it works. Once the code is released, I will post the test driver. The non-interpolative path is finished; that is, the case where the spline passes through the first and last knots and its shape is influenced by interior knots. The spline does not pass through the interior points unless the tension is set to 1. Tension varies from 0 (loosest) to 1 (tightest). At a tension of 1, the spline degrades into a sequence of straight lines connecting the knots.
In MXML, it’s easy to define the spline and its parameters,
<QuadraticSpline id="quadSpline" graphicsTarget="{[splineLayer]}"
interpolates="false" tension="0" >
<stroke>
<SolidStroke weight="2" color="#0000FF"/>
</stroke>
</QuadraticSpline>
A screen shot is shown below.
Degrafa Quadratic Spline (non-interpolative)
I’ll probably start working on the interpolating code (where the spline passes through each knot regardless of tension) this weekend. As I mentioned previously, the implementation is targeted towards applications where splines need to be drawn (or redrawn) very fast. This spline creates a small number of lineTo and curveTo commands in the command stack and should draw very fast.
