Archive

Archive for October, 2008

Using Xray with Papervision

October 29, 2008 Comments off

If you are a regular user of PV3D, you’ve probably already seen this, so this notice is for those who may have been away from Papervision for a while (like me).  John (aka Superman) Grden has modified Xray to work with Papervision so you can get detailed information on the objects in your scene.  While clearly useful for debugging, I can also see numerous opportunitites for using this tool in optimization as well.

Read more about it here and take time to pass only some props to John!

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.

Federer Wins in Basel

October 26, 2008 Comments off

After an exit in the semis in Madrid (although no one should feel bad losing to Murray on a very fast court), it was good to see Roger follow up with a win in front of his home crowd at the Swiss Indoors.  Although not exactly a major championship field, there were some strong tests for Federer and Nalbandian is no pushover.  After surviving a couple stiff early challenges, it was good to see Roger finish so strong, including a commanding performance in the final.  Here’s hoping that bodes well for the 2009 season.

Categories: Tennis Tags: , , ,

Gurobi Optimization

October 25, 2008 2 comments

Good friend and former colleague Ed Rothberg has started a new venture.  Gurobi Optimization is scheduled to release their suite of optimization products in March 2009.  With Ed and Bob Bixby behind the product suite, it’s sure to be groundbreaking.

Ed is one of those rare people who is both personable and can take anyone you think is bright and seriously blow them away.  You’ve probably seen some of those interviews where a Flash celebrity is asked who they look to for inspiration.  Whenever I think of that question, Ed’s name pops into my head.

I’m glad to have known and worked with Ed and wish him the best of luck at Gurobi.

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.

Gates’ New Venture?

October 23, 2008 Comments off

So, how many people thought Bill Gates would really ‘retire’? bgC3 is described as a ‘think tank’ and could simply be a way for Mr. Gates to stay involved in the development of technology.  Think tanks do have a way of spinning off new companies of which Gates could simply be an investor or the whole operation could be a disguise fora new venture.  If so, is there a first right of refusal for MSFT on any new technology in exchange for funding? That’s about all we have at this point; questions and speculation.  Here are a couple announcements if you’re interested,

Tech Flash

Crunch Gear

In the spirit of the season, perhaps we should have a poll 🙂

Categories: General Tags: , , , ,

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.