Editing A Cubic Bezier Spline

A couple months ago, this was something I believed I would never say about the Freehand Drawing Library.  Now, the library is and always will be a drawing library. Editing is not part of the core library architecture, however, it is something that requires a level of support inside the library.  In the past, this was accomplished by caching the sequence of mouse motions used to define a stroke.  The points could be edited and manually assigned to a stroke, either all at once or in an ENTER_FRAME event to animate the stroke.

This works cleanly with a simple interface for typical strokes, i.e. touch-move-release motions.  Now that the FDL supports splines and possibly other constructs that stretch the definition of a stroke, what about editing more complex drawings?  I want to maintain a light interface and not make editing operations an integral part of the library.  That inevitably leads to interface and code bloat in an attempt to satisfy every possible combination of customer-created editor.

I think it was the movie ‘War Games’ that popularized the phrase, ‘always leave yourself a back door.’  The back door to stroke manipulation outside normal FDL methods is to use arbitrary name-value parameters.  Every stroke has the ability to access or mutate arbitrary data objects.  It’s only two methods in the API, but they provide a wide variety of capability to custom strokes.

I added a simple spline editor to the PolyLine demo as an illustration.  After creating a spline (by clicking the end button), the knot/tangent display is overlaid on top of the stroke as shown below.

The spline knots are already available since they were manually assigned to the stroke.  The tangent information is entirely encapsulated inside the drawing engine, inside the stroke.  That information is obtained by the demo via a parameter request,

__stroke.getParam( “tangent” + i.toString() );

It is the responsibility of each stroke class to document all custom parameter queries and settings.  The above query returns in- and out-tangent values in an Object and that information is passed to the editor.  Knots may be dragged, which cause a parallel shift in the tangent.  The new knot and tangent information is conveyed back to the stroke with a sequence of parameter settings,

__stroke.params = { “changeKnot”:{vertex:index, x:editor.knotX, y:editor.knotY} };


__stroke.params = { “changeInTangent”:{vertex:index, x:editor.inTangentX, y:editor.inTangentY} };

__stroke.params = { “changeOutTangent”:{vertex:index, x:editor.outTangentX, y:editor.outTangentY} };

If a spline drawing engine is assigned to the PolyLine, it passes this information onto the internal FDLIntepolatingSpline instance.  A non-spline engine (line segments) ignores the parameters.

The screenshot below shows the result of a knot drag.

After dragging the middle vertex, the following screenshot shows the result of editing the first-vertex out-tangent.

This is all supported by the existing architecture, but there is one wrinkle.  If the edited spline is to be saved and then redrawn at a future time, we must have the facility to record the tangent edits *and* bypass the tangent Command when the spline is reconstructed.

I added an auxData parameter to the StrokeDataVO, which allows arbitrary auxiliary data to be recorded for a stroke.  It’s easy to deep-copy an Object with a ByteArray, so preserving immutability was no problem.  Now, by adding support for a ‘redraw’ parameter in the PolyLine stroke, the spline can be redrawn with arbitrary tangents supplied by external data instead of the tangents computed by the injected tangent Command.

Dynamic Bezier Spline Scroller With Source

Paul Taylor and I collaborated on a TinyTLF demo for 360|Flex last fall that used a quadratic Beizer spline to form left and right vertical constraints for dynamic text layout.  After the demo, a few people said it would be really cool to see the text scroll.  The idea scroller, however, should be organic to match the text boundaries, just as a vertical scroller matches a straight-line text boundary.  Since the spline boundary is dynamic, this means the scroller track and thumb should be dynamically drawn.

Since I had some time, I took on the task to create another demo for Adobe MAX 2010 and it was completed during the conference.  I envisioned a possible TechNote on the scroller’s construction, but time constraints have since rendered that idea impractical.  Since a TechNote implies open-sourcing the code, the next best solution is to just open-source the code.  If there is sufficient interest, I might do a deconstruction over the course of several blog posts.

Now, the track is the easy part since we already have the constraint and the quad. Bezier spline is one that I released in Degrafa.  It’s a simple construction with G-1 continuity and a tension parameter.  Additional artificial tangent control is provided by augmenting the spline with degenerate quad. segments at the beginning and end.  The spline is non-interpolative.

Most of the details are in the thumb construction and update.  This demo uses a relatively simple arc-length parameterization based on adaptive interpolation, and the interpolator may be injected.  Two interpolators are provided with the demo, but I’ve only tested one.

The scroller uses a linear model to map thumb position to [0,1] for the thumb value.  I don’t like the linear model since it has some issues, so I sketched out a quadratic model, but did not have bandwidth to test the implementation.  I also did not have time to test every conceivable path through the code, so there may be a bug or two yet to be uncovered.  So, check it out and see if you can come up with some interesting ideas for using this in an application.

Yes, that’s a pretty ugly-looking demo 🙂  Your job is to turn it into something visually impressive.  Good luck!

View (Flex 3) Demo

View Source

The companion demo illustrates how to use two of the Bezier splines to bound the width of an element.

View (Flex 3) Demo

View Source

Custom Spark Animation Class with Cubic Spline Interpolation

This example derived from a recent conversation involving the Spark animation classes and interpolation.  The question involved whether or not it was possible to use the Spark animation classes to perform a path interpolation based on a cartesian spline.  Interpolators aside, Spark animations are based on properties that vary over time.  A cartesian spline (such as the natural cubic spline) interpolates a path with y described strictly as a function of x.  A natural extension of the original question is whether or not the implementation could be performed with a minimal change to existing MXML.  So, consider something along the lines of

<s:Animate id="pathAnimation" target="{marker}" duration="2000">
<!-- Note - time values should be consistent on both x and y keyframes; since this is a cartesian interpolation, x-values must be strictly increasing with time -->

<s:MotionPath id="xKeyframes" property="x">
<s:Keyframe time="0" value="0"/>
<s:Keyframe time="250" value="100"/>
<s:Keyframe time="500" value="250"/>
<s:Keyframe time="750" value="300"/>
<s:Keyframe time="1000" value="400"/>
<s:Keyframe time="1250" value="450"/>
<s:Keyframe time="1500" value="500" />
<s:Keyframe time="1750" value="550" />
<s:Keyframe time="2000" value="600" />

<s:MotionPath id="yKeyframes" property="y">
<s:Keyframe time="0" value="0"/>
<s:Keyframe time="250" value="50"/>
<s:Keyframe time="500" value="150"/>
<s:Keyframe time="750" value="100"/>
<s:Keyframe time="1000" value="200"/>
<s:Keyframe time="1250" value="350"/>
<s:Keyframe time="1500" value="300" />
<s:Keyframe time="1750" value="450" />
<s:Keyframe time="2000" value="600" />

The keyframes describe a path over time.  We could execute the animation with linear interpolation between keyframes, but that moves a sprite along the straight line between spatial points.   So, can we use the existing Spark animation structure to replace this with an animation along a path between keyframes based on a cubic spline interpolation (an example of a cartesian spline)?

My first thought was trying to ‘back-door’ an interpolator for the y-coordinate keyframes with the understanding that the animation proceeds strictly from beginning to end (i.e. forward in time).  We can temporarily treat x as a function of time with linear interpolation.  The trick is relating the fraction passed into the subclass of  spark.effects.Interpolator to some global value in [0,1].  For each keyframe interval in the y-coordinate set, Flex passes a local fraction in [0,1] along with the y ranges.  Given min/max ranges for the independent variable in the cubic spline, this information can be converted to a global t-value in [0,1], which can be used to approximate the global x-coordinate used to interpolate y.

The problem I encountered is inconsistent fraction values between the x- and y-interpolators (which I found by replacing the default interpolator for the x keyframes with my own linear interpolator and tracing the fraction values).  This caused the x-values positioned by Flex to be out of snych with the y-coordinates computed by the spline.  Ugh.

This, however, lead to what I consider to be a more elegant (but less than optimal) solution, namely push Flex as far out of the picture as possible by writing my own custom Animate class.  This process is described in the help files as well as this tutorial.  It’s so easy, even a mathematician can do it 🙂

I wrote a factory, SplinePathAnimation, and a custom instance, SplinePathAnimationInstance which contains a natural cubic spline via composition.  The keyframe data is accessed in the  overridden play() method and used to initialize the natural cubic spline.  The overridden animationUpdate() method linearly interpolates x and uses the natural cubic spline to interpolate y.

The demo draws a cubic spline path, then animates a sprite over that path.  The sprite is just an FXG graphic that I ripped off from an Adobe example.  The demo still has some rough edges, but then it’s just a demo 🙂  The important consideration is that all I had to change in the MXML was replace s:Animate with util:SplinePathAnimation (with the namespace declaration xmlns:util=”utils.*”) and the closing tag.  This makes it pretty easy to switch out animations and keep the keyframe data intact in MXML.

I’d personally prefer controlling time myself and writing this as a custom animation outside the Spark framework, but the direct answer to the question is that I suppose it’s possible (at least in an approximate sense).  At least you have another example on how to create custom Spark animations, although this example illustrates the absolute minimal implementation to execute the demo.  It is not robust and the demo itself is still pretty rough.

View (crude) demo

View source

If you’re interested in how the natural cubic spline is constructed, read all about it here.

Organic Scroller Preview Part II

I have received several questions regarding the organic scroller preview.  The code will be released when Paul Taylor releases the final set of TinyTLF demos (layouts are currently being refactored).  Our collaborative work will illustrate html text laid out respecting a spline boundary with the right boundary serving as a dynamic scroller component.  I’ll provide a brief overview of how the scroller works in this post.  A detailed deconstruction is a topic for a later white paper or book chapter.

The boundary spline is a G-1 continuous quadratic Bezier spline.  The spline is generally non-interpolative and has a tension parameter.  I tend to like 0.3 a lot 🙂  The spline interpolates the first and last points.  Interior control points influence the shape of the spline, but the spline does not necessarily interpolate those points.  I’ve covered the spline in past posts and its fundamentally the same algorithm I implemented in the Degrafa quadratic spline.  As the spline is naturally composed of quadratic Bezier segments, it constructs and renders fast.

The boundary is duplicated and shifted a number of pixels to the right to create the scroller track.  The spline is naturally uniform parameterized.  If invalidated, the spline is reparameterized on arc length.  This is done with a simple heuristic that varies the interpolation granularity based on the length of each spline segment.  I will overhaul this heuristic in the future when I release arc-length parameterization for an arbitrary path.  For now, it’s a demo, so it’s kept simple.  Simple is good 🙂

The scroller thumb length is a fraction in [0,1] representing the fraction of the total boundary spline length to use when rendering the thumb.  The component maps the thumb value to arc length in [s1,s2] so that the thumb length is preserved and the midpoint of the thumb (in arc length) represents the thumb value.

Now, for the fun part.  The scroller class returns a vector of quadratic Bezier instances representing the path along the boundary from arc length s1 to arc length s2.  This is an exercise in deCasteljau subdivision.  Subdividing a quadratic Bezier at parameter t produces two independent quadratic Beziers that exactly represent segments of the original curve.  The first quadratic represents the original curve in [0,t].  The second represents the original curve in [t,1].  The subdivision code was modified to return coefficients of either segment.  That’s fine when s1 and s2 represent points in different quadratic segments.  The situation is more subtle when s1 and s2 are in the same quad.  This involves refining the original quadratic Bezier in the interval [s1,s2].  Once the vector of quadratic Bezier coefficients is returned, the thumb can be drawn quickly with the usual moveTo(), lineTo(), curveTo().

Interactivity is also an issue.  For a vertical scroller, vertical mouse movements do not map linearly into scroller arc length.  Attempting to do so may cause the scroller to jump erratically in some configurations.  Instead, a quadratic model for mapping vertical mouse movements into thumb value is employed.

I suspect there is still some tweaking to do (isn’t there aways), so I’ll continue to provide updates.  In the mean time, the next background project is arc-length parameterization of a general path, which may be both spatially discontinuous and likely discontinuous in first derivative.

Actionscript Organic Scroller Preview

Just a quick note to say hello from Adobe MAX in LA.  This is a short preview of a project I’ve been working on with Paul Taylor.  At 360|Flex, we showed a demo where TinyTLF was used to layout text respecting a spline boundary.  Paul showed scrolling with TinyTLF here at the 360|Flex Unconference.  The next natural progression is to have both the text boundary and the scroller be organic; that is, both are based on the same Bezier spline.  The scroller itself and the thumb are dynamically rendered in Actionscript.  The small image below shows a preview of one test case.

Organic Scroller Based on Quadratic Bezier Spline

Needless to say, there is a *lot* of math involved ranging from arc-length parameterization to interpolation models to a nonlinear model for scroller thumb interaction.  The alpha component is being turned over to Paul for integration into a TinyTLF demo and further testing.  Once it’s solid, we will work on a vehicle for distributing the code, which will include at least a white paper on all the math used in the scroller construction.

More to come later!

Degrafa Cardinal Spline

The Degrafa Cardinal spline is now available from the Origin branch.  Usage is very similar to the Catmull-Rom spline with the exception of the tension parameter.  The Cardinal spline is based on the C-R code base, so it supports closure.  The algorithm is the same as the C-R spline, so it is best used for tensions in the [0,1] range.  For example,

<mx:Application xmlns:mx=”http://www.adobe.com/2006/mxml&#8221;
width=”600″ height=”500″
pageTitle=”Cardinal Spline”
applicationComplete=”test()” viewSourceURL=”srcview/index.html”>


<paint:SolidStroke id=”redstroke” weight=”2″ color=”#FF0000″/>

<splines:CardinalSpline id=”crspline” graphicsTarget=”{[splineLayer1]}” stroke=”{redstroke}” knots=”453,159 350,302 218,202 146,297 400,110″ tension=”0″ closed=”true” />

produces the same fit as the Catmull-Rom spline,

Closure with Zero Tension
Closure with Zero Tension

Changing the tension to 1 ‘pulls’ the spline to the point where the fit is line-to-line,

<splines:CardinalSpline id=”crspline” graphicsTarget=”{[splineLayer1]}” stroke=”{redstroke}” knots=”453,159 350,302 218,202 146,297 400,110″ tension=”1″ closed=”true” />

Closure with Tension = 1
Closure with Tension = 1

Tensions in the range -1 to 3 are supported.  Negative tension ‘loosens’ the fit.  Tensions greater than 1 cause the spline to loop in on itself going into and out of each knot.  The effect at initial and terminal knots depends on how the auxiliary control points are chosen (same options as the C-R spline).

Splines are open by default.  For example,

<splines:CardinalSpline id=”crspline” graphicsTarget=”{[splineLayer1]}” stroke=”{redstroke}” knots=”453,159 350,302 218,202 146,297 400,110″ tension=”-0.5″ />

produces the following

Loosening the tension in a Cardinal spline
Loosening the tension in a Cardinal spline

I’m preparing for a long business trip, so posts and Degrafa updates will be sparse over the next several weeks.

Degrafa Quadratic Hermite Spline

The quadratic Hermite spline is now available in the Origin branch.  It works pretty much like any of the other splines with the exception of the method to manually assign the start tangent.  The default is automatic selection of start tangent, which uses the reflection discussed in this post.  A screenshot is provided below.

Automatic Selection of Start Tangent
Automatic Selection of Start Tangent

The blue curve results from plotting the low-level utility upon which the Degrafa spline is based.  It is plotted old-school, point-to-point with manual start tangent.  The red curve is the Degrafa spline fitting the same set of points in MXML with automatic selection of start tangent, and approximated by quadratic Beziers in the Degrafa command stack.

The relevant MXML is

<?xml version="1.0" encoding="utf-8"?>
 <mx:Application xmlns:mx="http://www.adobe.com/2006/mxml"
 width="600" height="500" >

 <mx:Canvas id="quadSpline" />
 <paint:SolidStroke id="redstroke" weight="2" color="#FF0000"/>
 <splines:QuadraticHermiteSpline id="hermiteSpline" graphicsTarget="{[quadSpline]}"
 stroke="{redstroke}" knots="90,250 250,230 330,320 410,250" />

The next screenshot shows what happens if the start tangent is arbitrarily set to the point (100,100).

Assigning 100,100 as the start tangent
Assigning 100,100 as the start tangent

The only change to the MXML is the line

<splines:QuadraticHermiteSpline id=”hermiteSpline” graphicsTarget=”{[quadSpline]}” stroke=”{redstroke}” knots=”90,250 250,230 330,320 410,250″ startTangent=”100,100″ />

A very wide variety of interesting curves can be created by changing knot coordinates and the start tangent point.  Update your SVN and enjoy 🙂