Quad Bezier Refinement in Degrafa

De Casteljau subdivision is a procedure by which a Bezier curve is defined.  It is also used to subdivide a quadratic Bezier curve into two distinct quadratic Beziers representing individual segments of the original curve.  The first Bezier segment is in the interval [0,t] and the second lies in [t,1] for t in (0,1).  Some 3D graphics packages use the term refinement to describe to the process of subdividing or splitting a curve into two equivalent segments at some interior point.  Refinement is also used to describe a process of extracting the coefficients of an equivalent-degree curve at two interior points.  In this context, refining a quadratic Bezier curve produces another quadratic Bezier that represents the original curve in the interval [t1,t2] where t1 < t2 and both t1, t21 are in [0,1].

This is an infrequent operation, although I recently used it in the organic scroller, the boundary of which is a quadratic Bezier spline.  The process may also be used to extrude any segment of a path comprised of quadratic Beziers (such as a circle approximation).

The quad refinement algorithm is now in Degrafa.  I’m still in the process of conducting some unit tests for possible numerical issues.  I wanted to get a release out now, while I’m in between gigs, since I have the time and am thinking about it.  Otherwise, you know what happens.  It’s onto the next gig and I forget 🙂

A screen shot of the demo program is shown below.

Quadratic Bezier Refinement in the Interval [0.2, 0.6]

Not much to the demo.  The blue curve is the quad. Bezier that interpolates the three points, P0, P1, and P2 with chord-length parameterization.  The red curve is drawn from coefficients returned from the quadRefine() method of the BezierUtils class.  Above, the red curve illustrates refining the original quad in the interval [0.2, 0.6].

Drag the points to see how the refinement is modified.  Adjust the stepper thingies to modify the interval.  [t1,t2] can  be extended to a maximum of [0.1,0.9] in increments of 0.1.  Note that t2 must be strictly greater than t1.  Code has been committed to the Origin branch.

View demo.

View source.

Automatic Bezier Arcs in Degrafa

An interesting problem is to draw an eye-pleasing arc between two points.  This can be used for anything from drawing origin-destination route arcs to approximating trajectories in animation.  Since we already know how to interpolate a quadratic Bezier between three points, one possible solution is to parameterize the generation of a middle interpolation point given two initial points.

I’ve used an algorithm along these lines since about 1982.  It takes two parameters, one of which determines the concavity of the arc.  The second parameter controls the distance between the midpoint of the line segment from first to last point and the middle interpolation point.  This provides a large amount of control over the generated arc.

A closely related problem is animating the arc.  This is trivial with a quadratic Bezier as the section of arc at any parameter value can be drawn with a single curveTo command using deCasteljau subdivision.

The auto-arc generation is now in the BezierUtils class and the subdivision method has been added to the AdvancedQuadraticBezier class.  A screen shot from the rather plain and simple demo is shown below.

Quadratic Bezier auto-fit between two points

The code has been checked into the Origin branch.

View demo.

View source.

Speaking at Dallas TechFest

If you’re in the D/FW area and are interested in attending Dallas TechFest, then I hope to see you at the session on computational geometry in Flex and Degrafa. Little knowledge of Flex is required; only a desire to add cool geometry buzzwords to your vocabulary. I’ll introduce Degrafa, highlight some differences between Degrafa and FXG, and then launch into the low-level computational geometry capability in Degrafa. In addition to declarative drawing, you can see how to perform more advanced tasks in Actionscript ranging from possible charting applications to animating route arcs.

More on the conference below – see you at the end of July!


Degrafa and FlashBuilder Part II

Continuing from Part I of this series, there is still a bit more work to do in terms of project setup using the styles.css file from the standard Degrafa Template.  In the project settings, edit the Flex Compiler settings to ensure the Halo theme is used,

-locale en_US -theme=${flexlib}/themes/Halo/halo.swc

Next, insert the mx namespace into the styles.css file and reference the Application container and Button with mx|Application and mx|Button.  The fill woes continue here as using the cool Degrafa skinning of the Application container creates a conflict with ComplexFill.  We can get the Degrafa logo skinned into the application background with a quick hack … and I do mean hack 🙂

First, here is the styles.css file with some additional font changes and the new mx|Application styling.

/* CSS file */

@namespace s "library://ns.adobe.com/flex/spark";
@namespace mx "library://ns.adobe.com/flex/mx";

/*------------------------------------------------------------------------------ Fonts */

  src: url('../fonts/Myriad.swf');
  fontFamily: 'Myriad Pro';
  fontWeight: Regular;

  src: url('../fonts/Myriad.swf');
  fontFamily: 'Myriad Pro Semibold';
  fontWeight: Semibold;

  src: url("/Library/Fonts/Arial.ttf");
  fontFamily: 'Arial';
  fontWeight: Regular;
  embedAsCFF: false

/*------------------------------------------------------------------------------ Global */

  font-family: 'Myriad Pro';
  color: #CCCCCC;
  embedAsCFF: false

/*------------------------------------------------------------------------------ Text */

  fontSize: 14;
  color: #000000;
  fontWeight:	Semibold;

  font-size: 24;
  text-align: right;
  color: #CCCCCC;

/*------------------------------------------------------------------------------ Application */

  background-color: #222222;
  borderSkin: ClassReference("DegrafaBackground")

/*------------------------------------------------------------------------------ Button */

  fill-colors:  #222222, #222222;
  border-color:	#666666;
  color: #CCCCCC;
  corner-radius: 0;
  text-roll-over-color:	#FFFFFF;
  highlight-alphas:	0,0;
  border-alpha:	1;

And, here is the DegrafaBackground.as file, aka quick hack for the border skin,

  import flash.display.Graphics;
  import mx.skins.ProgrammaticSkin;
  import mx.utils.ColorUtil;
  import flash.display.BitmapData;
  import flash.display.Bitmap;

  public class DegrafaBackground extends ProgrammaticSkin
    private var DegrafaImage:Class;  

    public function DegrafaBackground()

    override public function get measuredWidth():Number
      return 8;

    override public function get measuredHeight():Number
      return 8;

    override protected function updateDisplayList(w:Number, h:Number):void
	super.updateDisplayList(w, h);

        var g:Graphics       = graphics;
        var fillColors:Array = getStyle("backgroundGradientColors");
        var fillAlphas:Array = getStyle("backgroundGradientAlphas");

	if (!fillColors)
	  var bgColor:uint = getStyle("backgroundColor");

	  if (isNaN(bgColor))
		bgColor = 0xFFFFFF;

	    fillColors = [];
            fillColors[0] = ColorUtil.adjustBrightness(bgColor, 15);
            fillColors[1] = ColorUtil.adjustBrightness(bgColor, -25);

	if (!fillAlphas)
	  fillAlphas = [1, 1];

        drawRoundRect(0, 0, w, h, 0, fillColors, fillAlphas, verticalGradientMatrix(0, 0, w, h));

        var backgroundImage:Bitmap       = new DegrafaImage();
        var backgroundBitmap:BitmapData  = new BitmapData( backgroundImage.width, backgroundImage.height, true, getStyle("backgroundColor") );
        backgroundBitmap.draw( backgroundImage );

        g.beginBitmapFill( backgroundBitmap );
        g.drawRect( 0, 0, backgroundImage.width, backgroundImage.height );

And, with that, I was able to get the AdvCubicBezier example up and running with the Degrafa logo skinned into the application background. With F4, Degrafa fills are bad news. Fortunately, splines and such do not involve fills, at least not the declarative type, so it’s clear sailing ahead for low-level Degrafa development.

If there is any interest, I’ll clean up the project and post a .zip to an FXP file for download.

Degrafa and FlashBuilder Part I

I’ve moved onto new gigs and part of that move is migrating my home office to the MacBook Pro and FlashBuilder (I still want to call it Flex 4).  I’ve been working with Jason on getting Degrafa setup with FlashBuilder and finding out what issues are involved with migration.  This is the first in a series of posts on this issue.

When importing the Origin branch from SVN [branches/Origin/Degrafa], setup the project as a Flex Library Project.   Under Project Properties, Flex Library Build Path | Classes Tab – Select classes to include in the library.  Make sure com is checked.  FB wants to setup the main source folder as src.  Leave it blank.

Select the Flex Library Compiler settings.  For now, we need to use the Flex 3.5 SDK.  Set the namespace url to http://www.degrafa.com/2007 .  On the next setting below Namespace URL, browse to the project manifest file and select it.

Click here to see a screenshot of my settings.

When you build the project, there should be a .swc in the bin folder.

When creating a new project, go to the Flex Build Path settings in Project Properties, Library Path.  Click Add Project and select your Degrafa source project.

Now, a few things have changed.  In the new FB 4 universe, Canvas is out and the spark BorderContainer is the new kid on the block.  Degrafa plays nicely with the new kid, but the Degrafa declarations should go inside the fx:Declarations tag.  Here is a minimal example,

<?xml version="1.0" encoding="utf-8"?>
<s:Application xmlns:fx="http://ns.adobe.com/mxml/2009"
xmlns:mx="library://ns.adobe.com/flex/mx" minWidth="600" minHeight="400">
    <degrafa:RegularRectangle width="100" height="100" graphicsTarget="{ [myCanvas] }">
      <degrafa:SolidStroke color="0xff0000" />
<s:BorderContainer id="myCanvas" width="300" height="300" />

There are some issues, currently with fills. Jason is looking into current issues and a full-on Flex 4-compatible release (ah, I like Flex 4 much better). I will expand on fills and style-related issues in future posts. Once I get some reasonable examples up and running, it will be time to return to spline goodies. Flex setup … boring … math stuff … fun 🙂

Quad Bezier Arc Length Revisited

This question comes up quite regularly.  While in general, the elliptic integral for arc length of a parametric curve has no closed-form solution, the problem is tractable for a quadratic Bezier.  The integral is quite involved.  It is discussed in this post, including a reference to the solution.

Now, just because you have a formula for something does not necessarily mean you should always use it.  There are several divisions in the equation and some quads. can result in near-zero divisors.  There are other numerical issues, some of which can be exposed by exploring the Degrafa demo provided in the above post.

Computationally, the closed-form solution is close to a wash with numerical integration.  While the latter does have some subtle issues, I tend to use the numerical approach as it works for all parameteric curves and all values of the natural parameter.  The closed-form solution for the quad. only works for quadratic Beziers at t=1.   The numerical method can be used for arc-length parameterization as well as the segment problem; that is, computing the arc length of a segment of a curve from t=t1 to t=t2.

If you are a calculus student, you should study the derivation of the closed-form formula as it’s a great example of integration 🙂

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 Bezier X at Y Test Program

There is not much difference from the demo of the Bezier x-at-y method from the previously posted y-at-x demos.  Here is the MXML for the test case.  Most of the heavy lifting is in the displayXatY() method.  Study that and you should have a pretty good understanding of how the Bezier x-at-y method is applied.

If time allows, I’ll try to cook up a demo illustrating how to align sprites along the contour of a Bezier curve, but that will most likely wait until after I return from my upcoming business trip.

<?xml version=”1.0″ encoding=”utf-8″?>
width=”600″ height=”500″
pageTitle=”Degrafa Advanced Cubic Bezier X at Y”
applicationComplete=”test()” xmlns:degrafa=”http://www.degrafa.com/2007&#8243; viewSourceURL=”srcview/index.html”>

<mx:Style source=”assets/style/style.css”/>
<mx:Canvas id=”background” x=”50″ y=”90″ width=”500″ height=”320″ backgroundColor=”#FFFFFF” />
<mx:Label text=”Adv. Cubic Bezier X-at-Y” x=”250″ y=”30″ width=”300″ styleName=”title”/>

<mx:Canvas id=”bezierLayer” />
<mx:Canvas id=”boundsLayer” />

<geom:InteractivePoint id=”pointA” x=”90″ y=”250″ pointLabel=”A” radius=”5″ color=”0x00ff00″ width=”100″ height=”20″ />
<geom:InteractivePoint id=”pointB” x=”150″ y=”150″ pointLabel=”B” radius=”5″ color=”0x00ff00″ width=”100″ height=”20″ />
<geom:InteractivePoint id=”pointC” x=”290″ y=”200″ pointLabel=”C” radius=”5″ color=”0x00ff00″ width=”100″ height=”20″ />
<geom:InteractivePoint id=”pointD” x=”360″ y=”300″ pointLabel=”D” radius=”5″ color=”0x00ff00″ width=”100″ height=”20″ />

<AdvancedCubicBezier id=”bezier” graphicsTarget=”{[bezierLayer]}”>
<SolidStroke weight=”2″ color=”#0000FF”/>

<mx:Label x=”50″ y=”440″ text=”” width=”500″ fontSize=”12″ color=”#FFFFFF” id=”__x1__”/>
<mx:Label x=”50″ y=”460″ text=”” width=”500″ fontSize=”12″ color=”#FFFFFF” id=”__x2__”/>
<mx:Label x=”50″ y=”480″ text=”” width=”500″ fontSize=”12″ color=”#FFFFFF” id=”__x3__”/>

<mx:VSlider x=”500″ y=”95″ height=”310″ id=”__mySlider__” allowTrackClick=”false” minimum=”0″ maximum=”1″ enabled=”false” change=”displayXatY(event)” liveDragging=”true”/>

import mx.events.PropertyChangeEvent;
import mx.events.SliderEvent;

import com.degrafa.GraphicPointEX;
import com.degrafa.core.collections.GraphicPointCollection;

private var __yMin:Number;
private var __yMax:Number;

private function test():void
// restrict dragging for each point
var bounds:Rectangle = new Rectangle(background.x, background.y, background.width, background.height);
pointA.restrict      = bounds;
pointB.restrict      = bounds;
pointC.restrict      = bounds;
pointD.restrict      = bounds;

// actions when a property is changed on any InteractivePoint
pointA.addEventListener(PropertyChangeEvent.PROPERTY_CHANGE, onPropertyChanged);
pointB.addEventListener(PropertyChangeEvent.PROPERTY_CHANGE, onPropertyChanged);
pointC.addEventListener(PropertyChangeEvent.PROPERTY_CHANGE, onPropertyChanged);
pointD.addEventListener(PropertyChangeEvent.PROPERTY_CHANGE, onPropertyChanged);

// assign the quad. bezier data from script

__mySlider__.alpha = 0.2;
__yMin             = __mySlider__.y;
__yMax             = __mySlider__.y + __mySlider__.height;

private function assignBezierInterpolationPoints():void
// property changes trigger redraw
var params:Array = bezier.interpolate( [new Point(pointA.x, pointA.y), new Point(pointB.x, pointB.y),
new Point(pointC.x, pointC.y), new Point(pointD.x, pointD.y)] );

private function onPropertyChanged(_e:PropertyChangeEvent):void
switch( _e.property )
case InteractivePoint.MOUSE_DOWN:
__mySlider__.enabled = false;
__mySlider__.alpha   = 0.2;

addEventListener(Event.ENTER_FRAME, onPointMove);

case InteractivePoint.MOUSE_UP:
removeEventListener(Event.ENTER_FRAME, onPointMove);

// enable slider
__mySlider__.enabled = true;
__mySlider__.alpha   = 1.0;
__mySlider__.value   = 0;

// redraw control points and bezier curve when an InteractivePoint is moved
private function onPointMove(_e:Event):void

// display X at Y
private function displayXatY(_e:SliderEvent):void
// line does not track the middle of the thumb, but the slider value
var myY:Number   = (1-_e.value)*__yMax + _e.value*__yMin – bezierLayer.y;
var values:Array = bezier.xAtY(myY);

__x1__.text = “”;
__x2__.text = “”;
__x3__.text = “”;

var g:Graphics = boundsLayer.graphics;
g.moveTo( __mySlider__.x+10, myY + bezierLayer.y);
g.lineTo( background.x     , myY + bezierLayer.y);

if( values.length != 0 )
var o:Object   = values[0];
var myX:Number = o.x;
__x1__.text    = “t: ” + o.t + “, x: ” + myX;

g.drawCircle(myX, bezierLayer.y + myY, 4);

if( values.length > 1 )
o           = values[1];
myX         = o.x;
__x2__.text = “t: ” + o.t + “, x: ” + myX;

g.drawCircle(myX, bezierLayer.y + myY, 4);

if( values.length == 3 )
o           = values[2];
myX         = o.x;
__x3__.text = “t: ” + o.t + “, x: ” + myX;

g.drawCircle(myX, bezierLayer.y + myY, 4);