Archive for March, 2011

Custom Spark Animation Class with Cubic Spline Interpolation

March 23, 2011 Comments off

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.

Categories: Flex, Math Tags: , , ,

Beta Version of Freehand Drawing Library

March 21, 2011 2 comments

Just a quick blurb about some interesting work I’ve been doing lately for which I retain complete code and IP interests.  I’ve received several inquiries over the last six months regarding freehand line drawing.  My general tendency is to refer people to the FlashAndMath example since that’s very similar to an algorithm I used back in the early ’90’s for variable-thickness drawings for a kiosk application.  For people wanting smooth, continuous point interpolation, I already have a variety of splines both in and outside Degrafa.

Requests for capability outside the F&M example have grown to the point that I decided to take this project on for a couple clients, especially since it piqued my research interests in terms of longer-term applications.  In my client’s minds, there is also a big difference between some script thrown together in a frame of a .FLA and a robust, commercial-quality AS 3 class library 🙂

The initial goal of this project is to provide a Freehand drawing class (Sprite subclass) that handles the single responsibility of drawing strokes in a defined boundary.  As always, I try to code to interfaces, not specific implementations, so Freehand implements IFreehandDrawable .  The algorithm is fundamentally similar to the one I used in the ’90’s and the F&M example, with support for speed-sensitive width, but fixed coloring.

Other features include the ability to reference and highlight individual strokes and input strokes manually as well as through mouse motion.  Mouse motions may be cached and then fed back into Freehand one at a time to create a stroke library or animate strokes.  Bitmap snapshot of the drawing area is provided.

Erasure by individual stroke or all strokes is possible and a dispose() method is provided to properly prepare Freehand instances for garbage collection.  Freehand instances may be used anywhere a Sprite is applicable (AS only, F3, or F4).  The current demo adds the Freehand instance as a child of a SpriteVisualElement.  Drawings occur inside bounds supplied during initialization and the Freehand container may be masked.

Internally, strokes are treated as Sprites, not bitmaps.  In the next release, a Stroke will be generalized to an implementation of a general IStroke interface, which opens the door for editable and transformable strokes.  A general-purpose gestures library will be used to map generic gestures to specific mouse/touch interactions to support device as well as online applications.

A screenshot of a Flex 4 (Spark) demo is shown below.

I can provide a demo link to interested clients.

Path Arc-Length Parameterization Preview I

March 10, 2011 Comments off

One of my favorite background projects at this time is arc-length parameterization of general paths.  Think of a path informally as an ordered collection of planar, parametric curves that may be both spatially discontinuous and discontinuous in first derivative at the end of one curve and the beginning of another curve.  Each curve in the path is called a segment and segments may degenerate into lines or points.

One may wonder if cartesian curves, i.e. y = f(x), x in [a,b], are allowable as path segments if all segments are parametric, i.e. x=x(t), y=y(t), t in [0,1].  We can reparameterize the cartesian curve as x(t) = (1-t)a + tb for t in [0,1] and y(t) = f( x(t) ).  So, it is acceptable in the future to have natural cubic splines comprise path segments.  Can any programmers spot an Adapter pattern here?

The problem in this development is an efficient strategy for the approximate arc-length parameterization of the entire path.  In other words, a query for the x-coordinate of the path at a parameter 0.5 should return the x-coordinate of the path segment that is ‘close’ to halfway along the entire path length.

The difficulty lies in the fact  that the individual segments (other than lines or points) are not naturally arc-length parameterized.  Aside from creating complex, higher-order curves that have the necessary parameterization embedded in the curve construction, the classic efficient solution is to interpolate natural parameter as a function of normalized arc length (i.e. fraction of total length in [0,1]).  This yields a model, t = M(s), where both t and s are in [0,1].

The re-parameterization problem consists of finding M for each segment in the total path.  Each segment comprises some interval of normalized arc length, i.e. [s0, s1].  Given an input value, s, in [0,1], the Path first determines which segment ‘owns’ that normalized arc length.  The segment evaluates its local model to return a natural parameter, t, corresponding to the approximate normalized arc length.  The segment is then evaluated in its natural form to return the requested coordinate values.

Because of the wide variety of potential segments, a key to efficient implementation is the concept of reducibility.  In other words, each segment must be efficiently approximated as a sequence of simpler segments.  Then, we can use one model for each of the ‘atomic’ elements of each segment.

A linear interpolation model sounds reasonable, at least in terms of efficient evaluation.  Certainly, any curve may be reduced to a number of small segments over which the normalized arc length as a function of natural parameter is near-linear.  The problem is the large number of required subdivisions.

The current work uses a quadratic Bezier as an atomic element.  I’ve already illustrated with Degrafa that a wide variety of both cartesian and parametric splines can be reasonably approximated as a sequence of quadratic Beziers.  Subdivision of cubic Beziers into sequences of quads is a well-known process.

By reducing all segments other than lines and points to sequences of quadratic Beziers, the re-parameterization problem reduces to that of modeling natural parameter as a function of normalized arc length for a quad. Bezier.  It is computationally simple to subdivide a quad. Bezier into a sequence of smaller quad. Beziers.  As the number of subdivisions increases, it is reasonable to expect the quad. sequence to ‘flatten’ and eventually approach straight lines.  While this approach is suitable for fitting a linear model, it has the disadvantage of producing a very large number of sub-segments.  Each subdivision sweep involves fitting and testing a model, so linearization is not an efficient approach.

The current work uses a quadratic model and a more intelligent procedure for subdividing the original quad. Bezier.  That process is based on curvature as curvature vs. arc-length is a natural means for describing the shape of a curve.  This procedure only fits a quadratic model if the subdivided segment first passes a simple curvature-based test.  Subdivision proceeds only if the model fails a relative error test.

In addition to producing much fewer atomic segments for the model, this approach has the advantage of allowing the geometry of the original quad. Bezier to dictate the number of interpolation points.  This avoids oversampling for small, flatter segments and undersampling for long segments with large curvature.

I’m currently working on the model for a single, quad. Bezier segment and the structure of the class library.  The screen shot below illustrates a sample unit test.

This is just a query of coordinates at normalized arc length 0, 0.5, and 1.  The boundary tests are important as the above quad. Bezier is itself subdivided into ten smaller quadratic Beziers.  This is far less than the nearly 30 samples I would use for linear interpolation and even with the number of samples for a crude approach to cubic spline interpolation.  The latter is very accurate, but very expensive.  So, I’m very pleased with this first result although a great deal of additional testing is required before moving onto more complex segments and paths.

The code itself is built entirely to interfaces, not specific implementations.  This allows new segments to be quickly inserted into paths and application-specific versions of paths to be created without modifying the code that uses a path.  In the current test code, the following interfaces and factories are imported,

import path.SegmentFactory;

import path.PathFactory;

import path.IPath;

import path.IPathSegment;

The two relevant class variables are

private var __path:IPath;

private var __segment:IPathSegment;

The general approach is to create an IPath instance using PathFactory, create segments using SegmentFactory, add those segments to the path, then manipulate the path.

__segment = SegmentFactory.createSegment(p0.x, p0.y, p1.x, p1.y, p2.x, p2.y);

__path = PathFactory.createPath();


Currently, there is a default Path class that implements IPath.  In the event a programmer needs to modify that functionality, the PathFactory may be modified to return a new IPath implementation.  The interface supports getParam() and setParam() methods to allow for access and mutation of arbitrary parameters.  The factory constructor supports variable arguments, so it is possible to create a wide variety of IPath implementations without modifying the core application code that uses the path.

The SegmentFactory functions in a similar manner.  The first variable arg is an optional String.  If that argument is a String, it is treated as the fully qualified class name of a Class that implements IPathSegment.  The instance is constructed using the remaining parameters.  This allows splines, for example, to be quickly constructed and added to paths without worrying about the specific implementation of each spline.

That’s it for the first preview.  Unfortunately, I have to put this project on the back burner once again since I’ve picked up a couple short-term projects.  I’ll post more code snippets and results as time allows in the future.

Categories: Flash, Flex, Math Tags: , , ,

Recent Work XML Function Graphing Engine

March 7, 2011 1 comment

I’m in the process of creating permalinks to some significant recent projects, so I would be remiss not to include what I consider to be the most extensive project I’ve worked on in the last couple years (not to mention the most fun).  The AS3 function graphing class library allowed layout and many graphing details to be described in XML.  Perhaps the most unique feature of the library was the high level of interactivity.  The library supports multiple zoom levels (bounds of each zoom level specified in XML) and unlimited panning via dragging the graph display.  The code automatically redraws axes, labels, function graphs, and overlays while dragging.

A simple. blank graph (with default control panel) is shown below.

created with the following XML

<learningObject id="graph" x="0" y="0" width="100" height="100" display="{ALL}" graphType="" pannable="true" lockZoom="true" sampling="auto" hideControlsOnShapshot="true" >
<controls id="myControls" x="0" y="0" />
<learningObject id="background" />
<learningObject id="grid" />
<arrows color="0x000000" length="10" width="8" alpha="1" curvature="5" />
<learningObject id="title" />

A robust library of predefined functions (AS3 classes written to a specific interface) exist to rapidly plot common functions over arbitrary open/closed intervals as shown in the following screenshot.

which is created from the following XML

<function id="complexStepfunc">
<lineMetrics thickness="2" color="0xff0000" />
<data d1="closed" d2="open" radius="4" openFill="0xffffff">
<interval left="-inf" right="-1" functionClass="graphing.functions.library.Polynomial" functionParams="-3,1,2" />
<interval left="0" right="10" functionClass="graphing.functions.library.SineWave" functionParams="a:2,b:1,c:1" />

More complex displays are created by deriving a function from another function. One simple example is the derivative of a function. All functions in the base library evaluate their first and second derivatives (or indicate that no such definition is available in which case derivatives are numerically approximated). The following example shows the plot of a cosine wave and its first derivative.

created with the following XML

<function id="cosine" >
<lineMetrics thickness="2" color="0x0000ff"/>
<function id="deriv"
<lineMetrics thickness="2" color="0xff0000"/>

The concept of derived functions allows a wide variety of plots from a single base function. The following example shows the plot of a tangent line that can be derived from any base function.

and its associated XML

<function id="tangentLine"
derivedFrom="cubic" params="length:auto" derivedParams="x-coord:1" plotType="LINEAR">
<lineMetrics thickness="2" color="0xff0000" />

I must admit that my favorite function display is freeform. Many functions are not re-used enough to support creating a function display class to fit into the graphing engine. Instead, these functions can be described in a calculator-like syntax with arbitrary parameters such as a, b, c, etc. Specific parameter values describe a unique plot of a family of functions as shown below.

and the XML

<function id="freeForm1" params="1,-1,2,1">
<data vars="a,b,c,d,x" function="a*x + b*x^2 - 3*sin(c*x) + d*x^3" />
<lineMetrics thickness="2" color="0xff0000" />

A variety of ‘overlays’ are supported in the engine. The simplest is an interactive Marker or draggable visual symbol that follows the trace of a function. An example is shown below.

created from the following XML

<function id="cubic"
params="3,1,-1,0.5" plotType="LINEAR">
<lineMetrics thickness="2" color="0x0000ff" />
<function id="myMarker"
derivedFrom="cubic" params="marker:test.symbols.TangentMarkerSymbol,rolloverColor:0x9ACD32,digits:2" derivedParams="x-coord:1" >

On rollover, a tooltip-style displays shows the numerical value of the function and its first derivative.  Custom Markers are created by extending the Marker class.  The base library includes TangentMarker and SecantMarker classes that display a Marker along with tangent and secant lines.

Probes represent interactive overlays that are bound to the graph dimensions, not any specific function. On drag, they continuously dispatch a (bubbling) custom event, allowing information to be computed and displayed that depends on the current horizontal or vertical probe location. A horizontal Probe is shown below.

<learningObject id="horProbe" y="-1" snap="0" color="0x000000" thickness="2" updateOnSnap="true"
symbol="test.symbols.Probe1Handle" showAllHandles="true" tipID="probe1" >

The MarkerProbe is an interesting overlay that has attributes of both a Marker and Probe. Its display is derived from a specific function, as shown in the following diagram and XML.

<learningObject id="markerprobe"
x="0.5" snap="0" color="0x000000" thickness="2" updateOnSnap="true"
symbol="test.symbols.Probe1Handle" showAllHandles="true" derivedFrom="cubic" tipID="probe1" >
<params horVisible="true" vertVisible="true" />
<marker symbol="test.symbols.TangentMarkerSymbol" rolloverColor="0x9ACD32" digits="2"/>
<text offset="2" >left</text>
<lineMetrics thickness="2" color="0x9933CC" alpha="1" lineStyle="line_solid" />
<text offset="2">below</text>
<lineMetrics thickness="2" color="0x9933CC" alpha="1" lineStyle="line_dashed" dashWidth="6" dashSpacing="4" />

ShadedRegions are rectangular regions (some of which may extend infinitely) designed to draw attention to specific regions of the graph. Infinite regions are drawn as such when the graph pans as shown below.

<learningObject id="region1"
fill="0xffcccc" alpha="0.5" points="0,1 0,3 4,3 4,0 3,0 3,1" >
<lineMetrics thickness="1" color="0x0000ff" alpha="1" />
<learningObject id="region2"
fill="none" points="0,0 0,-3 +inf,-3 +inf,0">
<lineMetrics thickness="3" color="0xff0000" alpha="1" />

Highlights can be considered a non-rectangular type of ShadedRegion that are bound above or below by a function. These are used to emphasize the geometry of the area above or below a function.  Since these overlays are bound by a function, they must be derived from a function in XML.

<function id="quad"
params="-3,1,2" plotType="LINEAR">
<lineMetrics thickness="2" color="0x0000ff" alpha="1" />
<function id="quadHighlight" derivedFrom="quad" params="direction:above,color:0xff0000,alpha:0.2" />

Recent Work XML Map System

March 3, 2011 Comments off

This is a brief overview of a project I’ve been working on for an Agency client.  This client does a lot of work with interactive applications involving navigation between ‘views’ and ‘frames’ of individual views.  Sometimes, the views correspond to geographic maps, although the images are highly artist-stylized (otherwise we could just use Google/ESRI).  In some applications, the views might correspond to a floor plan or concert hall.  Each new view represents a different snapshot (revealing more detail) of some larger perspective.  We loosely use the term ‘map’ to refer to each view, although programmatically, a view is nothing more than an image.  Frames of a view correspond to rectangular regions having the same aspect ratio as the main ‘map’ window.  Views may have interactive ‘hotspots’, clickable ‘icons’, and animated overlays associated with them in addition to arbitrary framings.  If map projection information is available for a view, icons may be geo-coded.

Instead of developing each such application from scratch, the client wanted a class library, Flash ‘template’ and XML data structure to help organize each application into a common structure.  This provides numerous benefits in addition to code re-use.  Decoupling visual assets from the primary application facilitates easy distribution of design/development workflow among multiple people.  Structuring view/frame layout in XML allows non-coders to make simple changes to the application without touching code.  The system employs a template .FLA (this agency works only with Flash) and base Document class that encourages commonality among all applications using this ‘map system.’  This makes it very easy for one person to learn the application structure and quickly help on another application without having to deconstruct another person’s code and decipher library assets.  The map system employs an internal transition engine that is programmed to an interface, not any specific implementation.  This allows transitions to be coded once and then re-used by simply including the transition in the XML and linking it to a view transition by id.  Artists may experiment with different view transitions and parameters simply by editing XML.  Framing and frame transitions are an interesting exercise in analytic geometry.  These are handled internal to the system by a general-purpose zooming engine.

The template .FLA allows a designer to position the ‘map’ application by placing a blank MovieClip on Stage.  Since all such applications begin with a common, base template, the clip already resides on Stage for the artist.  The widow size is set in XML.  The system itself handles internal preloading of the application and all map assets.  The lead developer extends the base Document class to override event handlers and add any application-specific logic outside the map.  Some of the wiring with regard to hotspots and other interactive elements is handled in XML.  Printing is automatically integrated into the system.  Either the map or the entire Stage may be printed and print parameters are assigned in XML.  Modality is also automatically handled internal to the system and exposed to the application developer via the system API.

Unfortunately, I can’t show the XML or even discuss the code in detail as it’s proprietary, but here are some screen shots shown views/framing, hotspots, and animated overlays.

Interactive Hotpots

This application involved a very complex transition between views.  Once coded, however, the parameters can be modified in XML and re-used in other map applications simply by including the transition class in the XML and assigning it to a view transition via id.  Hotspot interactivity is wired into the main application in XML as each hotspot graphic is associated with a class extending MovieClip inside the system.

Baseline framing of a view

This application used only one view with many framings/overlays.  Frame transitions are handled internally by the zoom engine.  After specifying the framing (rectangle coordinates), the designer sets the transition time in seconds in XML.  The application developer initiates the transition from the Document class.  A default handler is always overridden to implement app-specific functionality after each transition completes.

Framing of a View

Although the term ‘map’ is used to describe the system, the manipulation of views/frames is generic and does not necessarily pertain to geo-coded data.  In addition to the numerous coding challenges (including being forced to debug/develop using the Flash IDE), I enjoyed the practical application of analytic geometry in this project.  I can only hope that the client is open to extending this system to work with AS only projects in FlashBuilder in the future 🙂