## 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.

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.

## Computational Geometry in Degrafa

Thanks to everyone who attended my talks at Dallas TechFest and D-Flex. For anyone who is interested, here is a link (PDF) to the presentation on Computational Geometry in Degrafa. Lots of links to demos (with View Source). Enjoy 🙂

## 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.

The code has been checked into the Origin branch.

## 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 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:s="library://ns.adobe.com/flex/spark"

xmlns:degrafa="http://www.degrafa.com/2007"

xmlns:mx="library://ns.adobe.com/flex/mx" minWidth="600" minHeight="400">

<fx:Declarations>

<degrafa:RegularRectangle width="100" height="100" graphicsTarget="{ [myCanvas] }">

<degrafa:stroke>

<degrafa:SolidStroke color="0xff0000" />

</degrafa:stroke>

</degrafa:RegularRectangle>

</fx:Declarations>

<s:BorderContainer id="myCanvas" width="300" height="300" />

</s:Application>

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 🙂

## 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”

xmlns:comp=”components.*”

xmlns:degrafa=”com.degrafa.*”

xmlns:paint=”com.degrafa.paint.*”

xmlns:geom=”com.degrafa.geometry.*”

xmlns:splines=”com.degrafa.geometry.splines.*”

layout=”absolute”

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,

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” />

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

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

## Bezier Y at X Algorithm

A few requests for the algorithm behind the Bezier y-at-x and x-at-y methods have been received. The code is self-contained in the com.degrafa.geometry.AdvancedQuadraticBezier and AdvancedCubicBezier classes. Both classes accept control points in their constructors and use classes from com.degrafa.utilities.math . The latter classes are independent from any internal Degrafa architecture. So, people who maintain their own Bezier class libraries have a path to include the y-at-x and x-at-y capability.

Finding the y-coordinates at a given x or the x-coordinates at a given y is an exercise in root-finding. Suppose the Bezier curve is B(t) which is quadratic or cubic in t. For the cubic Bezier, the vector equation for the curve produces two scalar equations, one for the x-coordinates and one for the y-coordinates, i.e.

B_{x}(t) = c_{0x} + c_{1x}t + c_{2x}t^{2} + c_{3x}t^{3}

B_{y}(t) = c_{0y} + c_{1y}t + c_{2y}t^{2} + c_{3y}t^{3}

For the y-at-x case, the required y-coordinates are found at the t-parameters corresponding to the intersection of B(t) with the vertical line x = a, or

c_{0x} + c_{1x}t + c_{2x}t^{2} + c_{3x}t^{3} – a = 0

The problem reduces to one of finding roots of a cubic polynomial. This starts by finding one root. Synthetic division is used to factor out the single root leaving a quadratic polynomial. The two possible roots of that polynomial are found with the venerable quadratic formula. Only roots in [0,1] are valid solutions to the y-at-x problem. The roots (values of t) are used to compute the y-coordinates using the equation for B_{y}(t). With a quadratic Bezier, roots are found directly with the quadratic formula.

The x-at-y problem is similar in that the required x-coordinates are the intersection of B(t) with the horizontal line y = a. There is one degenerate case where the Bezier curve is a segment of a horizontal or vertical line and the single parameter describing the line is the input value. For example, a cubic Bezier curve is the line x = a and the y-coordinates for x = a are desired. Theoretically, there are an infinite number. The Degrafa code does not currently handle this case. Some argue that no values should be returned while otheres argue that perhaps t = 0, t = 1/2 and t = 1 should be returned.

Given the rarity of this case actually occurring, the argument is postponed in lieu of more important developments. Tomorrow, I’ll post some code from the demos.