Archive

Posts Tagged ‘path deform’

Text Along Spline Code Part VI

November 4, 2008 2 comments

Continuing from this post, this is the last in the deconstruction of the basic algorithm for distributing text along an arc-length parameterized spline.  The final case to consider is when the amount of text to distribute excedes the physical boundary of the spline curve.  A simple way to handle this caase is to estimate the slope towards the end of the curve and continue the text in a straight line in the direction of that estimate.  This is the idea behind the else block,

else
{
  // text extends beyond end of spline - slope estimate towards
  // end of spline to continue along in a straight line
  if( cacheRotation )
  {
    dX            = endX - __spline.getX(0.92);
    dY            = endY - __spline.getY(0.92);
    d             = Math.sqrt(dX*dX + dY*dY);
    uX            = dX/d;
    uY            = dY/d;
    rotation      = Math.atan2(dY, dX)*Consts.RAD_TO_DEG;
    cacheRotation = false;
  }

  tf.rotation  = rotation;
  myWidth      = tf.textWidth;
  myHeight     = tf.textHeight;

  // distance along line from end of of spline to current
  // text starting position
  d    = (s-1)*arcLength;
  myX  = endX + d*uX;
  myY  = endY + d*uY;
  tf.x = myX + uY*myHeight;
  tf.y = myY - uX*myHeight;
}

which handles the case when the current s-parameter is greater than 1 (meaning the next letter is placed beyond the physical boundary of the spline).  The advantage of extrapolating along a straight line is that the rotation value can be computed once and re-used for each letter.  There is also a constant normal vector.  All these values can be computed once (the first time through the else block) and continually re-used.  This is the idea behind the cacheRotation value that is initialized to true.

The Δx and Δy values are estimated by,
dX = endX – __spline.getX(0.92);
dY = endY – __spline.getY(0.92);

The 0.92 value is arbitrary. A more sophisticated algorithm might use the mean of two or more estimates. The exact slope at s=1 sounds reasonable, but visually the text often flows better when using some sort of average estimate.

Notice that every time through the else block, the current TextField’s rotation property is set to the same value,

tf.rotation  = rotation;
myWidth      = tf.textWidth;
myHeight     = tf.textHeight;

The amount by which the current s-parameter exceeds 1.0 provides an indication of how far along the line to place the text,

d    = (s-1)*arcLength;
myX  = endX + d*uX;
myY  = endY + d*uY;
tf.x = myX + uY*myHeight;
tf.y = myY - uX*myHeight;

The computations are the same as before, except that the unit and normal vectors have constant orientation. They are ‘shifted’ along the straight line using the spline endpoint plus the distance along the straight line. After that, TextField positioning is the same as before.

I hope this series of posts provides a good high-level deconstruction of the simple algorithm. Understanding the algorithm at this level is necessary before adding numerous adjustments and refinements to take font metrics, punctuation, and other issues into account.

Text Along Spline Code Part V

November 1, 2008 1 comment

I was going to post this yesterday, but an emergency trip to the dentist (just call me Marathon Man) wiped out that plan.  Continuing from this post, let’s review the unit and normal vectors that arise during the computation. The Δx and Δy values used to approximate the unit vector in the direction of the spline tangent are used to orient the text along the spline.  The next question is where do we place the text?  Another question that usually follows is what is the difference between placing the text ‘below’ and ‘above’ the curve.

The registration point of the TextField is upper, left-hand corner, so an easy approach is to place the text field at the point on the spline correspoding to the computed arc length.  This approach orients the text ‘below’ the curve.  It’s what you may have seen in a few other examples similar to the one being deconstructed here.

Sometimes, you may have need to place the text ‘above’ the curve.  Additionally, you may need to have some control as to how far away from the curve the text is placed.  For example, the demo I would eventually like to put online has a spline curve represeningt slow-moving waves of water with text moving along the top of the wave.

This is where the normal vector is useful.  Using a rotation matrix, we can rotate the unit vector either counter-clockwise or clockwise. Recall that clockwise rotations are positive in Flash.  Study the Wikipedia article and compute the values of the 2D rotation matrix for a counter-clockwise rotation of ∏/2.  The normal vector components are simple multiples of the unit vector.

Once we know the normal vector (counter-clockwise means it’s pointing in the direction ‘upward’ from the curve), we can compute a point any distance along that vector.  As a first approximation, we can query the text height from the TextField and use that to position the text above the curve, ad distance of text height units along the normal.  The current algorithm is an approximation for purposes of introduction and simplicity.

Now, you have an idea of how to both orient the text along the curve and position it either above or below the curve.  The final step in the deconstruction of the basic algorithm is discussing how to handle the condition where the text extends beyond the length of the spline.  That will be discussed next week.

Text Along Spline Code Part IV

October 28, 2008 5 comments

Continuing the code deconstruction from this post, the second pass of the algorithm is split into two parts.  The first distributes text up to the final knot in the spline.  The second part handles the case where the text extends beyond the natural spline boundaries.  This is done by using the curve’s orientation toward the end of the spline to extend the text in a straight line in that direction, as shown in this post.

The code segment for the first part of phase 2 is,

// second pass - place text along spline
var s:Number              = 0;
var endX:Number           = __spline.getX(1);
var endY:Number           = __spline.getY(1);
var cacheRotation:Boolean = true;
var rotation:Number       = 0;

for( i=0; i<__myText.length; ++i )
{
  tf = __letters[i];

  if( s <= 1 )
  {
    var myX:Number = __spline.getX(s);
    var myY:Number = __spline.getY(s);
    if( s < 0.95 )
    {
      var dX:Number  = __spline.getX(s+0.05) - myX;
      var dY:Number  = __spline.getY(s+0.05) - myY;
    }
    else
    {
      dX = endX - __spline.getX(0.94);
      dY = endY - __spline.getY(0.94);
    }

    // normalize
    var d:Number  = Math.sqrt(dX*dX + dY*dY);
    var uX:Number = dX/d;
    var uY:Number = dY/d;

    tf.rotation         = Math.atan2(dY, dX)*Consts.RAD_TO_DEG;
    var myWidth:Number  = tf.textWidth;
    var myHeight:Number = tf.textHeight;

    tf.x = myX + myHeight*uY;
    tf.y = myY - myHeight*uX;
  }

The variable, s, denotes arc length along the spline.  The variables, endX and endY record the coordinates of the spline at s=1 (or the endpoints).  The Boolean variable, cacheRotation istrue if we are using a constant (precomputed) rotation value, which is the case when the text extends beyond the end of the spline.  The rotation variable denotes the rotation of the TextField for each letter distributed along  the spline.

This block of code,

if( s <= 1 )
  {
    var myX:Number = __spline.getX(s);
    var myY:Number = __spline.getY(s);
    if( s < 0.95 )
    {
      var dX:Number  = __spline.getX(s+0.05) - myX;
      var dY:Number  = __spline.getY(s+0.05) - myY;
    }

estimates the tangent to the curve at the current s parameter.  The cumulative text width is multiplied by the inverse of arc-length to estimate the s-parameter corresponding to the beginning of each letter, as previously described.  We could use the Singularity method that returns the derivative of the spline at the parameter value (which is the slope of the tangent), however, I wanted this code block to be usable with other packages that draw Bezier curves.  Most of those packages do not return derivative information, so it is estimated by dy/dx ~ Δy/Δx for small Δx.

The tangent of the spline at s is used to orient the TextField to align with the tangent at that point.  This is just a starting-point for aligning the text and works reasonably well except in places where the spline has extremely high curvature.  Understanding this first approximation is helpful before delving into more complex algorithms.

A unit vector in the direction of the tangent approximation is computed next and the TextField’s rotation property is set,

var d:Number  = Math.sqrt(dX*dX + dY*dY);
var uX:Number = dX/d;
var uY:Number = dY/d;

tf.rotation   = Math.atan2(dY, dX)*Consts.RAD_TO_DEG;

Note the use of the atan2() function.  The x- and y-components of the unit vector are used to compute the normal vector, which is needed to position the TextField.  This will be discussed in the next part of the deconstruction.

Text Along Spline Code Part III

October 24, 2008 1 comment

The high-level deconstruction of the basic algorithm is given in this post, with the corresponding code segment posted here. In this post, we look at the following code,

__spline.draw(1.0);
__myText = __input__.text;

// first pass - get total width of displayed text (using
// uniform spacing - punctuation taken into account later)
var totalWidth:Number = 0;
for( var i:uint=0; i<__myText.length; ++i )
{
  var tf:TextField = __createLetter(__myText.charAt(i));
  totalWidth      += tf.textWidth + __tracking;
  __letters[i]     = tf;
}

var arcLength:Number = __spline.arcLength();
var aInverse:Number  = 1/arcLength;
var maxS:Number      = totalWidth*aInverse;

Recall that the spline is parameterized on arc length that has been normalized to [0,1].  The first line of code draws the entire spline.  The for loop creates a TextField for each character and computes the total width taken up by the text string, along with one space padding on the end.  This allows a sprite, for example to be placed at the end of the text string, one space from the last character.  This part of the computation is optional.

The lines,

var arcLength:Number = __spline.arcLength();
var aInverse:Number  = 1/arcLength;
var maxS:Number      = totalWidth*aInverse;

compute the total arc length along the Bezier spline.  The inverse of the arc length is used to multiply cumulative text length to convert to an equivalent arc-length parameter along the spline.  The maxS variable is optional.  It stores the arc-length or s-parameter along the spline corresponding to the end of the text string.  It could be greater than 1 if the amount of text exceeds the arc length along the spline.  It may be the case that you want to use a different algorithm in such cases than the one provided in this deconstruction.  The variable also provides a way to quickly place something at the end of the string at a later point, perhaps in response to an event handler.

At this point, references to TextFields containing the individual letters are stored in an array.  The remaining code places text along the spline and will be deconstructed in two subsequent posts; one dealing with text that can be entirely distributed along the spline and the other dealing with the case where text extends beyond the final knot.

Text Along Spline Code Part II

October 22, 2008 2 comments

Regarding the code listed in my previous post, let’s take one step back and look at the problem from a very high level. Often, it’s easier to understand an approach to solving a problem if you can relate it to something similar, yet simpler.  So, suppose your task were to render text one letter at a time with constant spacing (tracking) along a horizontal line.  How would you write the program?

Starting at the beginning of the line (minimum x-coordinate if rendering LTR), you would probably place a letter then use its width (and the number of px spacing) to compute the x-coordinate of the next letter.  The letter’s height would be used to compute the y-coordinate of the TextField relative to the y-coordinate of the horizontal line.  So, if the horiztontal line starts at coordinates (100,100) and the first letter happens to be 22px tall and 20px wide and there is a constant 15px spacing between letters, a simple algorithm for placing that letter would be to position the TextField at (100, 100-22).  The second letter would be positioned at (100+20+15, 100-22).  In this simple approach, puncutation and text metrics are not taken into account.  No consideration of lowercase descending characters, etc.

Next, suppose that the line is not horizontal.  How does the algorithm change?  Instead of positioning letters at strictly horizontal increments, we now have to move in increments along the line.  So, if a letter is 20px wide with a 15px spacing, we need to increment a distance of 35px along the line in order to place the next letter.  The easiest way to accomplish this task is to use a unit vector in the direction of the line.

We also have to orient (rotate) the TextField to match the slope of the line.  The angle the unit vector makes with the horizontal provides this information. The TextField is offset from the line along the normal (perpendicular to the line) the same distance as the text height.  Since we know the unit vector, we also know the normal vector as the rotation matrix for a CCW rotation of PI/2 is trivial.

In a simplistic sense, we are using Frenet-Serret coordinates (or frame – without the binormal) to position the text and the unit vector information to orient the text.

The final step in the overview is to translate the concept of a line with general orientation to a spline curve. The concept of distance along the line is now translated to distance along the spline.  This is why it is important that the spline be parameterized on arc length.  Arc-length parameterization allows us to request specific distances along the curve to compute the tangent and normal direction vectors.  Once we have these vectors, the approach is exactly the same as the straight line.

In subsequent posts, I will deconstruct how the posted code accomplishes the simple algorithm for text distribution along a cubic Bezier spline.

Text Along Spline Code Part I

October 20, 2008 4 comments

Although this work is not finished, I don’t have time to write a full TechNote on the subject, so I’m going to post the ‘basic’ code for this algorithm and deconstruct it over several posts.  This will provide an introduction to the method before it gets too complicated with production details.  The Flex driver is not yet ready for general posting and download, so here is the code from the handler that renders the text along the spline.  It is currently a two-pass algorithm,

__spline.draw(1.0);

__myText = __input__.text;

// first pass - get total width of displayed text (using
// uniform spacing - punctuation taken into account later)
var totalWidth:Number = 0;
for( var i:uint=0; i<__myText.length; ++i )
{
  var tf:TextField = __createLetter(__myText.charAt(i));
  totalWidth      += tf.textWidth + __tracking;
  __letters[i]     = tf;
}

var arcLength:Number = __spline.arcLength();
var aInverse:Number  = 1/arcLength;
var maxS:Number      = totalWidth*aInverse;

// second pass - place text along spline
var s:Number              = 0;
var m:Number              = -1;
var endX:Number           = __spline.getX(1);
var endY:Number           = __spline.getY(1);
var cacheRotation:Boolean = true;
var rotation:Number       = 0;

for( i=0; i<__myText.length; ++i )
{
  tf = __letters[i];

  if( s <= 1 )
  {
    var myX:Number = __spline.getX(s);
    var myY:Number = __spline.getY(s);
    if( s < 0.95 )
    {
      var dX:Number  = __spline.getX(s+0.05) - myX;
      var dY:Number  = __spline.getY(s+0.05) - myY;
    }
    else
    {
      dX = endX - __spline.getX(0.94);
      dY = endY - __spline.getY(0.94);
    }

    // normalize
    var d:Number  = Math.sqrt(dX*dX + dY*dY);
    var uX:Number = dX/d;
    var uY:Number = dY/d;

    tf.rotation         = Math.atan2(dY, dX)*Consts.RAD_TO_DEG;
    var myWidth:Number  = tf.textWidth;
    var myHeight:Number = tf.textHeight;

    tf.x = myX + myHeight*uY;
    tf.y = myY - myHeight*uX;
  }
  else
  {
    // text extends beyond end of spline - slope estimate towards
    // end of spline to continue along in a straight line
    if( cacheRotation )
    {
      dX            = endX - __spline.getX(0.92);
      dY            = endY - __spline.getY(0.92);
      d             = Math.sqrt(dX*dX + dY*dY);
      uX            = dX/d;
      uY            = dY/d;
      rotation      = Math.atan2(dY, dX)*Consts.RAD_TO_DEG;
      cacheRotation = false;
    }

    tf.rotation  = rotation;
    myWidth      = tf.textWidth;
    myHeight     = tf.textHeight;

    // distance along line from end of of spline to current
    // text starting position
    d    = (s-1)*arcLength;
    myX  = endX + d*uX;
    myY  = endY + d*uY;
    tf.x = myX + uY*myHeight;
    tf.y = myY - uX*myHeight;
  }

  _textContainer.addChild(tf);
  s += (myWidth + __tracking)*aInverse;
}

Text Along a Spline IV

October 15, 2008 Comments off

In many practical circumstances, the amount of text to be distributed along a curved path exceeds the length of the path. It is possible to extrapolate parametric curves beyond the normal [0,1] domain, however, arc-length parameterization applies only to the restricted domain. Arc-length parameterization is necessary to uniformly distribute text along the curve.

One reasonable compromise is to use the tangent approximation at the end of the curve to extrapolate along a straight line. This approach is also computationally efficient as a single unit vector and normal can be reused for each letter distributed along the line.

This approach is illustrated below.

I still have one small glitch to work out with this approach and then I will put the text-along-spline code on the back burner.  The next big priority is to help the Degrafa team start to move Singularity code into the Degrafa code base.  The first step in this process will be to rewrite the cubic Bezier spline to be independent of the current Composite class.  Although I can’t predict every possible porting issue, at a high level it should be largely a matter of replacing the FastBezier class with the Degrafa cubic Bezier class.

At least that’s the way it looks on paper 🙂  More to come later!