Aldonline

Decomposing a Regular Transformation Matrix in AS3

If you ever find yourself building a GIS interface, mapping app or any kind of visual system that requires some sort of zooming in and out of complex nested hierarchies of visual objects, chances are you will need to use Matrix Transformations at some point.

Enter the Matrix


Matrix Transformations lie at the heart of display rendering because they provide a simple and efficient way to handle geometric calculations and other hierarchical transformations. In the case of Flash they are built into the native framework and surfaced through the Matrix class.

When you rotate, scale and translate an object, these operations affect its associated transformation matrix, which is then used for drawing and geometric operations. If this object is nested within another display object, then its associated matrix is combined ( through matrix concatenation ) with the matrices of all its ancestors. The resulting matrix is adequately dubbed the display object's concatenated matrix, and you can access it like so:

displayObjectA.transform.concatenatedMatrix;


Exit the Matrix

Manipulating Matrices and using them to perform complex calculations is quite useful, and we do it everyday. But, what if we need to go backwards?
What if, given a transformation Matrix we need to figure out exactly what amount of rotation, scaling and translation operations would produce it?

At first hand it seems like a trivial task. In fact, I have seen some people wondering why the Matrix class itself is "missing" the obvious properties: Matrix.rotation, Matrix.x, Matrix.y, etc...

Unfortunately, this is not trivial at all. Just a little experimentation will demonstrate the contrary.
The problem lies in the fact that operations are interdependent. Especially when introducing rotation steps.
If you translate and then rotate, and then translate again you end up with an unclear mapping between each individual step and the final result. In fact, you even need to take the order of the transformations into account. Different sequences can produce different results.

Go ahead and try to figure it out if you don't believe me. Fact is that there is no simple way to go from a Matrix to rotation, translation and scale.
But who needs simple anyway...

Eigenspace and Singular Value Decomposition


Luckily for us this problem is not new. We can resort to a set of concepts with fancy names: Singular Value Decomposition, Eigenvalue, eigenvector and eigenspace. In short, they provide us with a framework, theory and some alternative algorithms that allow us decompose a transformation Matrix into its constituent components and derive a minimum sequence of operations to reproduce it.
After a couple of hours trying different approaches to implement the math and and digging up old codebases ( of which Dojo was the most useful ) in search for ideas, I decided to save everyone else the pain of going down the same road and created a simple utility class that does all the work...

var c1:Panel = new Panel( );
var c2:Panel = new Panel( );

// nest the components
addChild( c1 ); // c1 is below root
c1.addChild( c2 ); // c2 is below c1

// apply some manual transformations to outer component
c1.x = 10;
c1.rotation = 5;
c1.scaleX = 2;

// apply some manual transformations to inner component
c2.x = 20;
c2.rotation = 10;
c2.scaleY = 0.3;

// access the resulting inner matrix
var m:Matrix = c2.transform.concatenatedMatrix;
// and decompose it ( THIS IS THE INTERESTING PART )
var svd:SingularValueDecomposition
    = SingularValueDecomposition.decompose( m ); 

// we can now access the individual transformation bits
trace( svd.dx ); // x translation with respect to root
trace( svd.dy ); // y translation with respect to root
// etc...
// or apply the transformation to a new display object

var c3:Panel = new Panel( );
addChild( c3 ); // c3 is below root

svd.apply( c3.transform.matrix );
// c3 now looks just like c2
//( scale, rotation and translation )
// but it is not nested


Notes

Now, there are a couple of important things to keep in mind.
The first one is that the apply() method follows some rules when applying the results. You can also apply each operation by hand. But remember to follow this sequence if you want to achieve the same results as the original matrix:

public function apply( matrix:Matrix ):void
{
    matrix.translate( dx, dy );
    matrix.rotate( angle2 );
    matrix.scale( sx, sy );
    matrix.rotate( angle1 );
}

Just think of this sequence as the quickest, generalized way to achieve all complex linear mappings (which include non-proportional scaling and rotation). And that is why you often end up two angles instead of just one.

Now, the second thing you should not forget is that this is an approximation.
Depending on the magnitude of scale, for example, you might see the fidelity of the results drop. This is due in part to the limited numeric representation internals: Numbers in flash can only hold so much info ( this is common to all platforms ). And since calculations operate on these numbers, and many calculations are required in each pass, some precision is lost along the way.

So, keeping the latter in mind, if you are planning on using this to achieve something like a really deep zoom-in effect (a la google earth, diving from outer space into your home... which is similar to what I was doing) I would recommend using an exponential approximation strategy, where you recalculate the trajectory whenever you travel 50% of what's left, for example, so you can gradually eat out the error.

Get the Code

The code for this class and its supporting classes are available from the trunk of the BigFlexLib project. There are no public releases yet for that project, but you are welcome to grab a copy and do as you wish.

See source here.

rus said...

10:39 AM  

Hey Aldo,

great work with this, however in some cases the recomposed matrix is significantly different from the original matrix after a decomposition/recomposition

original matrix:

a 0.7071075439453125
b 0.7071075439453125
c -0.7071075439453125
d 0.7071075439453125
tx 492 [0x1ec]
ty 328 [0x148]

original decomposed/recomposed:

a 0.7071075439453126
b -0.7071075439453125
c 0.7071075439453125
d 0.7071075439453126
tx 579.8281860351562
ty -115.96563720703122