# Optimizing hierarchical transform

I'm transforming objects in 3D space by transforming each vector with the object's 4x4 transform matrix. In order to achieve hierarchical transform, I transform the child by its own matrix, and then the child by the parent matrix. This becomes costly because objects deeper in the display tree have to be transformed by all the parent objects.

Is there a faster way to transform vertices to achieve hierarchical transform?

• Are you sure you have to transform all vertices? For raycasts for example it will be cheaper to transform the ray from world space to object space before testing it. Is it just a mesh for rendering? – Maik Semder Jul 10 '12 at 20:57

Quite a common thing to do with some matrices is to cache the value and only update it when it's changed. There's two ways to manage this scheme, push or pull.

Pushing matrices would involve, at the point of a matrix changing, letting child nodes know that the matrix has changed. These nodes will then have to let their children know, and so on. The upside is that it only requires storing the extra matrix, but you re-compute it every time it changes - if you change matrices within the hierarchy a lot then the matrices at the bottom will change an awful lot during the frame.

The reverse it to pull matrix changes - when a value is changed, it sets a boolean value which says that the matrix has changed since it was last read. This is commonly referred to as a dirty matrix (programmers are weird.)

Upon requiring a matrix, you check if it is dirty (or its parents). If it is, you recalculate the matrix. The downside of this is that you need to check if things are dirty all the time.

When I said there was only two methods, I lied: you can go for a hybrid approach somewhere in the middle. Push the dirty flag down the tree, and let children know that at least one of the parents' matrices are dirty. At the same time, calculate the matrix only when needed. If your only ever process the tree in a downward fashion (from the root to the leaves) then you can get away with only one matrix multiplication per node as a maximum.

• Hi Matt and thanks for your answers, however I need to know if the matrix concat method will work at all? – Robinicks Jul 11 '12 at 9:03
• Yes, it will. Matrix multiplication is associative - (A*B)*C = A*(B*C) = A*B*C. As long as you don't swap the order of A, B and C you will get the same result. Your transform matrix mill more than likely be Parent_of_Parent_of_Parent * Parent_of_Parent * Parent * Me. An important note is that vectors are just matrices with one dimension being length one - row vectors and column vectors are 1xN and Nx1 matrices respectively - so this associativity works for the first situation you describe too. – Matt Kemp Jul 11 '12 at 9:21
• Just to clarify: your initial situation you lay out is Vert * ChildMatrix * ParentMatrix * RootMatrix. This is exactly the same as Vert * (ChildMatrix * (ParentMatrix * RootMatrix) ) where the brackets are denoting what you work out first, or in other words the concatenation of the matrices and caching them. – Matt Kemp Jul 11 '12 at 9:23
• So when I concat (multiply) 2 4x4 transform matrices (A and B), and then project a vector using that concatenated matrix it will work as if I had first transformed by A then by B? – Robinicks Jul 11 '12 at 11:36
• Precisely. v * B * A = v * ( B * A ). The only thing you need to get right is to get the order correct, as multiplication is not commutative - in other words, A * B != B * A. – Matt Kemp Jul 11 '12 at 12:35