Archive

Archive for October, 2009

Degrafa Cardinal Spline

October 20, 2009 Comments off

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;
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,

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

October 16, 2009 Comments off

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″?>
<mx:Application
xmlns:mx=”http://www.adobe.com/2006/mxml&#8221;
xmlns:geom=”components.*”
xmlns=”http://www.degrafa.com/2007&#8243;
layout=”absolute”
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]}”>
<stroke>
<SolidStroke weight=”2″ color=”#0000FF”/>
</stroke>
</AdvancedCubicBezier>

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

<mx:Script>
<![CDATA[
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
assignBezierInterpolationPoints();

__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;
boundsLayer.graphics.clear();

addEventListener(Event.ENTER_FRAME, onPointMove);
break;

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

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

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

// 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.clear();
g.lineStyle(1,0xff0000);
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.beginFill(0xff0000);
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.beginFill(0xff0000);
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.beginFill(0xff0000);
g.drawCircle(myX, bezierLayer.y + myY, 4);
}
}
}

]]>
</mx:Script>

</mx:Application>

Bezier Y at X Algorithm

October 15, 2009 3 comments

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.

Bx(t) = c0x + c1xt + c2xt2 + c3xt3

By(t) = c0y + c1yt + c2yt2 + c3yt3

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

c0x + c1xt + c2xt2 + c3xt3 – 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 By(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.

Categories: Degrafa Tags: , , ,

New Degrafa Bezier Methods

October 14, 2009 Comments off

I have received a couple requests for x-at-y methods in the advanced quadratic and cubic Bezier classes to complement the existing y-at-x methods.  Fortunately, the algorithm is the same, just a different set of coefficients, so it was an easy addition.

The x-at-y problem is typically used to distribute sprites left-to-right and top-to-bottom along the contour of a Bezier curve.  The y-coordinate of the first sprite is fixed.  The horizontal location is determined by the x-coordinate of the Bezier curve corresponding to the specified y-coordinate (plus some offset).  Sprites are ‘stacked’ along the contour of the curve by incrementing the y-coordinate based on the height of the previous sprite plus some offset, then repeating the algorithm.

The following diagrams illustrate the quadratic and cubic cases.

Quadratic Bezier x-at-y

Quadratic Bezier x-at-y

Cubic Bezier x-at-y

Cubic Bezier x-at-y

These methods are in the AdvancedQuadraticBezier and AdvancedCubicBezier classes.  Update SVN and enjoy.

Categories: Degrafa Tags: , , ,

Cardinal Splines Part 5

October 8, 2009 1 comment

Continuing from part 4 of this series, we are looking at tension values outside the range of zero to one. When T is negative, then s = (1-T)/2 increases from 1/2 and grows without limit as T becomes larger negative. So, what happens for large values of s?

Using the same four knots and the same equation from part 4 of this series, P(0.5) serves as an approximate representation of the midpoint of the curve from P2 to P3. The curve is not naturally arc-length parameterized, so P(0.5) is a convenient point on the curve ‘away’ from both endpoints.

The expectation is that as s increases, the curve tends to follow the tangents more closely. Now,

P(0.5) = s/8[(P3 – P1) + (P2 – P4)] + 0.5(P2 + P3)

The second term is the midpoint between P2 and P3. If Pt(t) denotes the tangent, the above equation becomes

P(0.5) = s/8[Pt(0) – Pt(1)] + 0.5(P2 + P3)

The first term is the difference between the two tangents, multiplied by a constant term that grows without bound. The endpoint of this vector is added to the midpoint between P2 and P3. That means that P(0.5) is pushed arbitrarily far away from the fixed point 0.5(P2 + P3) as s increases without bound.

The following diagram shows what happens when s = 1 (corresponding to T = -1). The red curve is the Degrafa Catmull-Rom spline (s = 1/2) and the blue curve is the Cardinal spline with s = 1. Note the tendency for the curve to stay closer to the tangents at each join. Point reflection is used to compute the auxiliary points at the beginning and end (i.e. before P1 and after P4).

Cardinal Spline s = 1

Cardinal Spline s = 1

A cubic curve only has so much flexibility in terms of inflection. Driving T too far negative (and thus s too far away from 1/2) can cause strange behavior as shown in the case where s = 2, below.

Cardinal Spline s = 2

Cardinal Spline s = 2

Exact behavior varies depending on how the auxiliary points are chosen.

The case where T > 1 drives s negative. This reverses the role of in- and out-tangents. This causes the spline to loop around itself at each join. Look at the comments from part 4 for a link to a good demo of this case.

These extreme cases serve as poor interpolants, but can be used to draw cool-looking curves. So, there is some justification for allowing tension values outside the typical [0,1] range.

Categories: Degrafa, Math

Cardinal Splines Part 4

October 6, 2009 6 comments

Continuing from part 3 of this series, a formal tension parameter, T = 1-2s, was introduced. All we noted about tension was that T=0 corresponds to s = 1/2. At s=1/2, the Cardinal spline takes on the form of the more familiar Catmull-Rom spline. The Catmull-Rom spline may, however, be derived independently from the notion of Cardinal splines as the blending of two parabolas [1]. The zero-tension Cardinal Spline happens to conforms to a well-known C-1 continuous spline.

What happens as the tension parameter is moved away from zero? Can it reasonably be both positive and negative? To better understand the effect of the tension parameter on the spline, the Cardinal-spline basis matrix is

[ -s  2-s  s-2   s ]
[ 2s  s-3  3-2s -s ]
[ -s   0    s    0 ]
[  0   1    0    0 ]

Given four arbitrary knots,

[P1, P2, P3, P4]

the following vector equation applies for an aribrary point P(t) on the curve from P2 to P3

P(t) = s(-t3 + 2t2 – t)P1 + s(-t3 + t2)P2 + (2t3 – 3t2 + 1)P2 + s(t3 – 2t2 + t)P3 + (-2t3 + 3t2)P3 + s(t3 – t2)P4

We have already looked at T = 0, so consider T = 1, corresponding to s = 0. The equation for P(t) reduces to

(2t3 – 3t2 + 1)P2 + (-2t3 + 3t2)P3, which can be simplified to

(3t2 – 2t3)(P3 – P2) + P2. If u = 3t2 – 2t3, then

P(t) = (1-u)P2 + uP3, which is the parametric equation of a line from P2 to P3.

While u does vary from 0 to 1, the primary curve parameter is t. At t varies from 0 to 1, u is approximately sigmoid but very close to linear throughout its range. So, we can say that as T approaches 1, the spline approaches a straight-line interpolation between knots.

The following screenshot shows a four-knot example with a black line connecting the knots and the spline drawn in blue with T=1. The Degrafa Catmull-Rom spline is drawn in red, which corresponds to the Cardinal spline with zero tension. This allows a comparison of the range of fits available in the tension range from zero to one.

Tension Ranges in a Cardinal Spline

Tension Ranges in a Cardinal Spline

The natural tension range is from zero to one. Values outside this range are possible, although rarely practical. These factors are discussed in the next section of this series.

References:

[1] Salomon, D. “Computer Graphics and Geometric Modeling”, Springer Verlag, NY, 1999.

Categories: Degrafa, Math Tags: , ,

Cardinal Splines Part 3

October 1, 2009 1 comment

Continuing from part 2 of this series, the tension in a Cardinal spline is controlled by the s-parameter. Given a four-tuple of control points or knots,

[Pa, Pb, Pc, Pd]

cubic Hermite interpolation is applied with start-tangent s(Pc – Pa) and end-tangent s(Pd – Pb) .

Theoretically, s could vary from zero to positive infinity. A very long tangent vector, indicated by a large s-value causes the curve to follow the tangent very closely in and out of the join point. A very small tangent vector, indicated by a small s-value, causes the curve to approach and leave the join point more like a straight line.

Intuitively, this is the opposite of how we expect tension to behave. Larger tension should ‘pull’ the curve closer to a straight-line interpolation of the knots, with exactly straight lines as a limiting case. This gives rise to the convention of a formal tension parameter, T, that is inversely related to s.

The typical convention is to define s = (1-T)/2 or T = 1 – 2s. Note that the zero-tension case corresponds to s = 1/2 or a relatively ‘loose’ movement into and out of each join. This special case corresponds to the Catmull-Rom spline. For this reason, the C-R spline is sometimes called the zero-tension or neutral Cardinal spline.

The tension parameter will be discussed in more detail in subsequent posts in this series. Tangent vectors are arbitrary at the initial and terminal knots, just as with the Catmull-Rom spline. Fortunately, there are several methods for automatically assigning these tangents. The C-R spline in Degrafa implements two methods; point duplication and point reflection.  Line segment reflection can be added as a third option. It is also possible to allow designers to set these tangents interactively.

Local control via knot placement, tension control, and adjustment of initial/terminal tangent vectors provides artists with a variety of methods to design specific curves using Cardinal splines.