Correctly transforming a node relative to a specified space?

Question

I'm currently working with nodes in a hierarchical scene graph and I'm having difficulty correctly translating/rotating a node relative to a specific transformation space (e.g. a parent node).

How do I properly translate/rotate a node relative to its parent node in a scene graph?

The Problem

Consider the following water molecule diagram (without the connecting lines) for the parent/child structure of the scene nodes, with the Oxygen atom being the parent node and the 2 Hydrogen atoms being the child nodes.

Translation Issue

If you grab the parent Oxygen atom and translate the structure, you expect the Hydrogen children to follow and stay at the same relative position from their parent. If you grab a child H atom instead and translate that, then only the child would be affected. This is generally how it currently works. When O atoms are translated, H atoms automatically move with it, as expected from a hierarchical graph.

However, the when translating the parent, children also end up accumulating an additional translation, which essentially causes the children to 'translate twice' in the same direction and move away from their parent instead of staying at the same relative distance.

Rotation Issue

If you grab the parent O node and rotate it, you expect the children H nodes to also rotate, but in an orbit, because the rotation is being performed by the parent. This works as intended.

However, if you grab a child H node and tell it to rotate relative to its parent, I expected only the child would end up orbiting around its parent in the same way, but this doesn't happen. Instead, the child rotates on its own axis at a faster rate (e.g. twice as fast as rotating relative to its own local space) in its current position.

I really hope this description is fair enough, but let me know if it isn't and I'll clarify as needed.

The Math

I'm using 4x4 column-major matrices (i.e. Matrix4) and column vectors (i.e. Vector3, Vector4).

The incorrect logic below is the closest I've come to the correct behavior. Note that I've chosen to use a Java-like syntax, with operator overloading to make the math easier to read here. I've tried different things when I thought I had figured it out, but I really hadn't.

Current Translation Logic

translate(Vector3 tv /* translation vector */, TransformSpace relativeTo):
    switch (relativeTo):
        case LOCAL:
            localTranslation = localTranslation * TranslationMatrix4(tv);
            break;
        case PARENT:
            if parentNode != null:
                localTranslation = parentNode.worldTranslation * localTranslation * TranslationMatrix4(tv);
            else:
                localTranslation = localTranslation * TranslationMatrix4(tv);
            break;
        case WORLD:
            localTranslation = localTranslation * TranslationMatrix4(tv);
            break;

Current Rotation Logic

rotate(Angle angle, Vector3 axis, TransformSpace relativeTo):
    switch (relativeTo):
        case LOCAL:
            localRotation = localRotation * RotationMatrix4(angle, axis);
            break;
        case PARENT:
            if parentNode != null:
                localRotation = parentNode.worldRotation * localRotation * RotationMatrix4(angle, axis);
            else:
                localRotation = localRotation * RotationMatrix4(angle, axis);
            break;
        case WORLD:
            localRotation = localRotation * RotationMatrix4(angle, axis);
            break;

Calculating World-Space Transforms

For the sake of completeness, the world transforms for this node are calculated as follows:

if parentNode != null:
    worldTranslation = parent.worldTranslation * localTranslation;
    worldRotation    = parent.worldRotation    * localRotation;
    worldScale       = parent.worldScale       * localScale;
else:
    worldTranslation = localTranslation;
    worldRotation    = localRotation;
    worldScale       = localScale;

Also, a Node's full/accumulated transformation for this is:

Matrix4 fullTransform():
    Matrix4 localXform = worldTranslation * worldRotation * worldScale;

    if parentNode != null:
        return parent.fullTransform * localXform;

    return localXform;

When a node's transformation is requested to be sent to the OpenGL shader uniform, the fullTransform matrix is used.

Answer 1

worldTranslation = parentNode.worldTranslation * localTranslation;
worldRotation    = parentNode.worldRotation    * localRotation;
worldScale       = parentNode.worldScale       * localScale;

This is not how accumulation of successive transformations works. And its obvious why not if you think about it.

Let's say you have two nodes: a parent and a child. The parent has a 90-degree, counter-clockwise local rotation about the Z axis. The child has a +5 offset in the X axis. Well, a counter-clockwise rotation should cause it to have a +5 in the Y axis, yes (assuming a right-handed coordinate system)?

But it doesn't. Your localTranslation is never affected by any form of rotation.

This is true of all of your transformations. Translations are affected only by translations, not by scales or rotations. Rotations are not affected by translations. Etc.

That's what your code says to do, and it's not how you're supposed to do it.

Keeping the components of your matrices decomposed is a good idea. That is, having separate translation, rotation, and scale (TRS) components is a good idea. It makes it easier to apply successive local transformations in the proper order.

Now, keeping the components as matrices is wrong, because it really makes no sense and wastes time&space for no real reason. A translation is just a vec3, and there's nothing to be gained by storing 13 other components with it. When you accumulate translations locally, you just add them.

However, the moment you need to accumulate the final matrix for a node, you need to convert each TRS decomposition into its own local matrix, then transform it into the parent's overall transformation, not the parent's individual TRS components. That is, you need to compose the separate transformations locally, then multiply them with the parent transformation matrix. In pseudo-code:

function AccumRotation(parentTM)
  local localMatrix = TranslationMat(localTranslation) * RotationMat(localRotation) * ScaleMat(localScale)
  local fullMatrix = parentTM * localMatrix

  for each child
    child.AccumRotation(fullMatrix)
  end
end

Each parent passes its own accumulated rotation to the child. The root node is given an identity matrix.

Now, TRS decomposition is perfectly fine, but it only works when dealing with local transformations. That is, transformations relative to the parent. If you want to rotate an object in its local space, you apply a quaternion to its orientation.

But performing a transformation in a non-local space is a different story entirely. If you want to, for example, apply a translation in world-space to an object that has some arbitrary series of transformations applied to it... that is a non-trivial task. Well actually, that's an easy task: you compute the object's world-space matrix, then apply a translation matrix to the left of that, then use the inverse of the parent's world-space matrix to compute the relative transformation to the parent.

function TranslateWorld(transVec)
  local parentMat = this->parent ? this->parent.ComputeTransform() : IdentityMatrix
  local localMat = this->ComputeLocalTransform()
  local offsetMat = TranslationMat(localTranslation)
  local myMat = parentMat.Inverse() * offsetMat * parentMat * localMat
end

The meaning of the P^-1OP thing is actually a common construct. It means to transform the general transformation O into the space of P. Thus, it transforms a world offset into the space of the parent's matrix. We then apply that to our local transformation.

myMat now contains a transformation matrix which, when multiplied by the parent's transforms, will apply transVec as if it were in world space. That's what you wanted.

The problem is that myMat is a matrix, not a TRS decomposition. How do you get back to a TRS decomposition? Well... that requires really non-trivial matrix math. It requires doing something called Singular Value Decomposition. And even after implementing the ugly math, SVD can fail. It's possible to have a non-decomposable matrix.

In a scene graph system I wrote, I created a special class that was effectively a union between a TRS decomposition and the matrix that it represents. You could query whether it was decomposed, and if it was you could modify the TRS components. But once you tried to assign a 4x4 matrix value directly to it, it became a composed matrix and you could not longer apply local decomposed transforms. I never even tried to implement SVD.

Oh, you could accumulate matrices into it. But successive accumulation of arbitrary transforms won't yield the same result as decomposed component modifications. If you want to affect the rotation without affecting prior translations, you can only do that if the class is in a decomposed state.

In any case, your code has some correct ideas, but some very incorrect ones too. You need to decide how important having a TRS decomposition is vs. how important it is to be able to apply a non-local transformation.

Answer 2

I found Nicol Bolas' response to be somewhat helpful, even though there were still a few details I wasn't so clear on. But that response helped me see the non-trivial nature of the problem I was working on, so I decided to simplify things.

A Simpler Solution - Always in Parent Space

I've removed the Node.TransformSpace in order to simplify the problem. All transformations are now applied relative to a parent Node's space, and things are working as expected. Data structure changes that I intended to perform after getting things to work (e.g. replacing the local translation/scaling matrices for simple vectors) are also now in place.

A summary of the updated math follows.

Updated Translation

A Node's position is now represented by a Vector3 object, with the Matrix4 being built on-demand (see later).

void translate(Vector3 tv /*, TransformSpace relativeTo */):
    localPosition += tv;

Updated Rotation

Rotations are now contained in a Matrix3, i.e. a 3x3 matrix.

void rotate(Angle angle, Vector3 axis /*, TransformSpace relativeTo */):
    localRotation *= RotationMatrix3(angle, axis);

I still plan to look at quaternions later, after I can verify that my quaternion <=> matrix conversions are correct.

Updated Scaling

Like a Node's position, scaling is now also a Vector3 object:

void scale(Vector3 sv):
    localScale *= sv;

Updated Local/World Transform Computations

The following updates a Node's world transforms relative to its parent Node, if any. An issue here was fixed by removing an unnecessary concatenation to the parent's full transform (see original post).

void updateTransforms():
    if parentNode != null:
         worldRotation = parent.worldRotation * localRotation;
         worldScale    = parent.worldScale    * localScale;
         worldPosition = parent.worldPosition + parent.worldRotation * (parent.worldScale * localPosition);
    else:
        derivedPosition = relativePosition;
        derivedRotation = relativeRotation;
        derivedScale    = relativeScale;

    Matrix4 t, r, s;

    // cache local/world transforms
    t = TranslationMatrix4(localPosition);
    r = RotationMatrix4(localRotation);
    s = ScalingMatrix4(localScale);
    localTransform = t * r * s;

    t = TranslationMatrix4(worldPosition);
    r = RotationMatrix4(worldRotation);
    s = ScalingMatrix4(worldScale);
    worldTransform = t * r * s;