Trig Plus Algebra Plus Geometry Plus Vectors Equals Fun

Math teachers hear the most often-uttered student phrase in history a lot more than I do, but my ears have twitched to the infamous, “I’ll never use that” or its many variants over the years.  Funny how people know right now what will and will not be needed or used for the rest of their lives

Now, taken in strict isolation, a single trig or algebra formula might appear to have limited or no use in the myriad of life situations in someone’s future.  It is, however, quite interesting how often problems can be solved by strategic use of a single formula from multiple areas of study.  The problem discussed in this post is one such example.

In the prior post, I illustrated how some basic trig concepts could be used to solve a rotation and bounding-box problem without any presumptions or special considerations of the programming environment.  This example is similar in that it illustrates how to rotate a box around an arbitrary point in its interior.  The box is represented by a sequence of four coordinate pairs.  It is not a Flash symbol or anything other than a sequence of coordinates.  The drawing environment is simple; it can move the pen, draw lines, and draw filled circles.  The programming environment contains the typical set of math functions.

Our math background includes a semester of trig, analytic geometry, and algebra.  We know the very basics of vectors, but have not been introduced to matrices or matrix/coordinate transforms.  As it happens, all we need to know to solve the stated problem is

1 – Polar coordinates, i.e. x = r cos(a) , y = r sin(a)

2 – Parametric equation of a straight line, i.e. P = (1-t)P0 + tP1

3 – How to add and subtract vectors

4 – How to compute the distance between two points

Refer to the diagram below.

The four points of the box are A (x1,y1), B (x2,y2), C (x3,y3), and D (x4,y4).  The rotation point is R (rx,ry). The example code was written in Flex and the coordinate system in the Flash player is y-down.  We are not given the coordinates of R.  In fact, the box may be at an angle to the horizontal as shown in the lower, right part of the diagram.  The only thing we know about R is that the component parallel to each side of the box is a fraction of that side’s length.  This is where vector math can be useful.

The coordinates of R can be computed by adding the vectors V1 and V2.  The percentage inputs can be converted into numbers t1 and t2 in [0,1].  The exact coordinates of the terminal points of these vectors are obtained from the parametric equation of a line.  Let the non-bolded notation V1 and V2 refer to vectors from the origin representing these terminal points.  Then, V1 = (1-t1)A + t1B and V2 = (1-t2)A + t2D. Since the initial point of both V1 and V2 is A, the vector constituents (Δx and Δy) are immediately available.  Add the vectors and add the result to A to obtain the coordinates for R.  So, we can adjust sliders that change the percentage along each side and quickly compute R regardless of any prior rotation since we should always recompute the correct coordinates for A, B, C, and D.

When R is set, imagine lines drawn from R to each of the vectors A, B, C, and D.  Let the distances be r1, r2, r3, and r4, respectively.  Also compute the angle each line segment makes with the horizontal using the atan2() function.  Since this returns a value in [-Π, Π], a small adjustment is made to always record the angles in [0, 2Π].  This makes studying the angle computations a bit easier if you want to trace out the results as part of deconstructing the code.

Also record the initial rotation angle when R is assigned.  Subsequent changes to this value rotate the box around R by some delta.  If the initial angle of the box is θ, and the delta is δ, then the four points are rotated around R by an angle θ+δ. Compute the coordinates of each new vector, A, B, C, and D by using the formula for polar coordinates and add the center, R.

These concepts are illustrated in an online demo.

The percentage along each side used to compute R is adjusted by sliders as well as the rotation angle.  The red dot visually identifies the rotation point, R.  You may optionally display the circle traced by each of the four corner points as the box is rotated.  There is a _clear (Boolean) variable in the code that you may adjust to either clear the drawing each rotation update or choose to draw over each update of the box.  If the value is false, you can produce some spirograph-style drawings.

The UI was created in Flex, but the actual code is very straightforward and does not rely on anything unique to Actionscript.  It could be ported to many other environment quite easily.  There is also some internal documentation on how to use trig identities to reduce the number of trig computations at each rotation update.

Even more importantly, there is nothing in the code or the algorithm that relies on a box being rotated other than computing R.  The actual rotation is applied to a sequence of points using the simplest of concepts from a few math disciplines.  I hope this provides some sense of appreciation of problems that can be solved using only the most fundamental techniques from a few branches of applied math.

View demo

View source

Trig 101

In the previous post, I promised to discuss the math behind rotating a rectangular sprite about its upper, left-hand registration point; that is, the origin of the sprite in its local coordinate space is the upper, left-hand corner.  This is actually a segue into a more general discussion of rotation about an arbitrary point.

While some programming environments offer more direct capability than others, low-level math serves as a common denominator between them.  If you understand the math, then it’s easy and efficient to port capability from one environment to another.  There are also times where inlining direct computations offers opportunities for performance optimization in mobile apps or games.  So, let’s start with that age-old question of what will I ever use trig for?

The programming example in the prior post dealt with computing the axis-aligned bounding box of a rectangular sprite after rotation about its origin.  Refer to the diagram below.

The original sprite in light blue is rotated through an angle, a, to the orientation shown in light red.  The origin (upper, left-hand corner) remains the same while the points A, B, and C are rotated to new positions A’, B’, and C’.  Once the coordinates of these new points are known, it is trivial to compute the AABB (axis-aligned bounding box) shown in red.

From the outset drawing to the lower, right, let the width and height of the sprite be represented by w and h, respectively.  The distance, r, is simply sqrt(w² + h²) and the angle, b, may be precomputed using the atan2 function available in most any programming language.  Using the base definitions of sine and cosine, the coordinates of point A’ are ( w*cos(a), w*sin(a) ).  The coordinates of B’ are ( r*cos(a+b), r*sin(a+b) ).  If a+b = c, then the coordinates of C’ are computed as ( h*cos(c+Π/2), h*sin(c+Π/2) ) .

There is no need for an additional trig computation for C’ since we can use the well-known identity, sin(x+y) = sin(x)*cos(y) + sin(y)*cos(x).  cos(x+y) = cos(x)*cos(y) – sin(x)*sin(y).   cos(Π/2) = 1 and sin(Π/2) = 0.  Plug these into the identities and you should see that we can re-use the computation of cos(c) and sin(c).  Refer to the code (the rotation() mutator function) in the prior post to check your computations.  It should be easy to follow whether Actionscript, Javascript, C++, or Obj C is your language of choice.

Once we have the coordinates, the AABB is trivially computed and the computations can be easily ported to any programming environment or further optimized inside the application.  All with some very basic trig and your friendly, neighborhood pythagorean theorem  The operations could be optimized beyond what is illustrated in the code and that is left as an exercise.

Notice that we computed the rotated points in the sprite’s local coordinate space.  The AABB is often computed in parent space, so it’s necessary to translate to the origin of that space.  This is illustrated in the boundingBox() accessor function.

There is, of course, nothing special about rotation about the upper, left-hand corner.  The next example will cover rotation about the centroid of the sprite, which is a special case of rotation about an arbitrary point in the sprite’s coordinate space.  No matter what application you are working on or language you are working with, understanding what is happening ‘under the hood’ can go a long way.  I hope you found something useful in this post.

Typescript and Jangaroo

I think I’m about to set a new personal record for lowest number of posts in a given year. Is it really October already?

Well, at least I’m working and on a pretty interesting project from both a mathematical and programming perspective, so I should be thankful for that.

I am, however, still interested in doing something new and interesting this year and I think it will be along the lines of a computational geometry library and/or version of the Freehand Drawing Library in Javascript.  The CG library is likely to be released through a series of posts in an open-source context similar to the TechNotes series I did in Actionscript for Flash/Flex programmers.  The JS FDL is intended for clients doing mobile development in an HTML/JS environment.  Okay, it’s mostly for me to have fun – I confess! However, an extra license or two never hurt anyone

To this end, I’m currently looking into both Typescript and Jangaroo.  Coffeescript is on the list as well, but I’m really looking to get back into Visual Studio and C++/C# development, so Typescript has some natural appeal.  Perhaps sufficient time will arise to deep-dive into all three?

I guess we’ll have to wait and see.  Sorry again for the waiting part.  This has been a strange (but fortunately very profitable) year.

Actionscript Optimization

Of the dozens of request-for-help emails I get every week, one of the most common topics is general suggestions for actionscript optimization.  There are numerous online resources for this topic, one of which is the ActionscriptWiki page.  John Grden also has a nice post on this topic.

I’m a big fan of Polygonal Labs, and Michael has numerous posts such as this one that deal with fast approximation algorithms.  This is another good one from his Actionscript category (well worth your time).

I believe I’ve mentioned Joa Ebert’s paper before in this blog, but it’s worth repeating.  Post your favorite techniques and resource sites.

Using Xray with Papervision

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

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.

Good Programmers Into Great Programmers

Interesting article here by Jeff Cogswell, author of ‘Designing Highly Usable Software.’  I particularly liked the point about programmers understanding where things can go wrong.  In my current gig, I receive specs all the time that indicate how something should work and be displayed under average use conditions.  It’s the extreme cases where the UI breaks down or the specification does not work that can kill the product.  Understanding and identifying these cases up front leads to spec modification that saves a lot of downstream headaches and refactoring.

Although the article does not deal with Flash, the principles are still valid.  From your own experience managing or working with great programmers, what do you think makes a really great Flash/Flex programmer?

Joining Degrafa

I started the parameteric curve library back in 2004, with the first TechNote appearing in 2005.  My original goal for this library was to have a code repository to illustrate mathematical concepts discussed in TechNotes.  My strong belief is that fundamental principles of computational geometry should be freely available (with mathematical and code details) to everyone in the Flash/Flex community.  You should never have to buy a book, CD or any other resource to learn how to create and use Bezier curves, splines, etc.  In fact, I maintain that the level of detail in the Singularity parametric curve library and the online TechNotes surpasses that of any Flash book purporting to discuss similar topics, and it’s absolutely free

In 2007, Singularity was expanded to include another of my favorite topics – kinematics.  A preliminary version of 2D rigging classes was added to the library.  Along the way, Singularity took on a new role as people began using the library in production applications.  Although I don’t mind such use, I never originally intended the library for that purpose and do not want to be in the business of maintaining and supporting a production application library.

There are over a dozen commercial users of Singularity to date and I’ve recently been thinking about the future of the parametric curve library.  Many have suggested the creation of yet another open-source project.  Not a bad idea at all, but there is something lacking.

If I do anything different with this library, it would be expanding its usefulness to people that do not have the mathematical and programming skills to use a low-level computational geometry library. I can create all the Flex demos in the word, but that does not help someone who understands Flex but lacks the mathematical and programming background to use Singularity.

Ah!  Understands Flex … hold that thought for a second.  What if the algorithm technology in the Singularity parametric curve library could be used in a declarative markup environment?  Wouldn’t that be cool?  Hmmm … what existing open-source projects offer such a facility?

Well, I’m happy to announce that I’ll be joining the Degrafa team as a contributor/consultant/general math guy with the goal of helping transition the algorithm technology in Singularity to Degrafa.  This satisfies both my goals of making fundamental algorithm technology freely available to the community and increasing its applicability beyond a relatively small group of programmers.

What this means is that I will no longer be developing application code for the Singularity parametric curve library.  I will be using my spare time to help the Degrafa core team migrate existing code and tecnology to their code base.  I will also devote research time to issues of primary intererest to the Degrafa team and community.  In fact, my current background project that spawned the Spline Tangent series is based on a stated desire from the Degrafa team.

I will continue creating and posting online demos, however, over time you will see most of the computational geometry demos migrate to Degrafa examples.  I will continue to work on the rigging classes and expand the scope of kinematics coverage in Singularity over time.

I think this is an exciting develoment and I look forward to working with the awesome developers on the Degrafa team as well as helping support the incredible community of Degrafa users.

More PureMVC Links

As a follow-on to my previous post listing some PureMVC links, here are some more I’ve come across that may be of interest to PureMVC users. Enjoy.

Interview with Cliff Hall, creator of PureMVC.

The Manifold Project.

Discussion of Cairngorm and PureMVC as patterns of GUI architecture.

PureMVC Startup Manager.

PureMVC Asset Loader example.