20

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.

water molecule representing parent/children node relationship

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.

6
  • 1
    Not an answer, but have you considered using Quaternions to avoid incremental loss of precision?
    – o11c
    Jun 25, 2016 at 18:13
  • A long time ago I made a similar program (interactive manipulation of chemical diagrams). I used a simple ball & springs model (with dynamic "virtual" springs to maintain displayed angles) when moving atoms, as well as a rigid body model (each atom has a location within a 2D or 3D volume and the volumetric box is manipulated using standard rigid body formulas, the likes of which you can find all over the place) when moving whole molecules. In short: by handling your atoms individually you are making this harder than it needs to be. Never assume that rotation and translation are distinct tasks.
    – Dave
    Jun 25, 2016 at 18:50
  • @o11c: I wanted to use quaternions to allow smooth interpolation, especially when the node has a camera attached and you want to move the camera by means of the node. But I'm currently tracking down a problem that would seem to be in the quaterion -> matrix conversion, which seems to produce an odd clipping plane within the camera's view frustum. My guess is the conversion is wrong somewhere... even though I've tried quite a few things. I think I'll have to post a question on that one soon.
    – code_dredd
    Jun 25, 2016 at 22:38
  • @Dave: Could you be more concrete? The molecule here is simply a visual way to explain how my parent/child nodes in the scene graph are organized, and I'm not sure I follow the part of "Never assume that rotation and translation are distinct tasks". Can you be more specific? Did you spot the issue in the math or have a guess?
    – code_dredd
    Jun 25, 2016 at 22:40
  • Sorry I haven't looked over your code. Have you considered using a library to handle the complexities for you? Most 3D engines have routines for these transformation tasks which have already been worked out & tested extensively (as well as natively using quaternions and handling all of that logic for you too). If you really want to do it yourself, I'd suggest you sit back with pen & paper for a bit and start from scratch (when working on a complex problem it's easy to get stuck into a "special case" / "small tweak" mentality when you'd be better off coming at it from a different angle).
    – Dave
    Jun 25, 2016 at 22:47

3 Answers 3

11
+50
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.

2
  • I've edited the post to clarify something that may not have been clear. It seems like I was already doing something similar to your 1st recommendation as per AccumRotation in my implementation for fullTransform, where the concatenated local xform is concat'ed to the parent's fullTransform matrix, if present. That seems to address the translation issue in children. (I had mistakenly concat'ed the world, not local, TRS matrices.) I'm still taking a look at the rest of your post and the rotation issue.
    – code_dredd
    Jun 27, 2016 at 0:52
  • It seems I did not fully get the 2nd part of your explanation, as I seem unable to get it to work correctly. I've removed the Node.TransformSpace for the time being to avoid remaining stuck for longer than I've been already. I've updated the transforms in a different way and it appears to be working correctly.
    – code_dredd
    Jun 27, 2016 at 9:44
4

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;
3

Ths basic problem is how to solve the commuting matrix problem.

Suppose you have a matrix X and a matrix product ABC. And suppose you want to multiply find a Y such that

X*A*B*C = A*B*Y*C

or vice versa.

Assuming no matrices are singular, first eliminate common terms:

X*A*B = A*B*Y

Next, isolate. Keeping track of left vs right, multiply by inverses:

A^-1*X*A*B = A^-1 *A *B *Y
A^-1*X*A*B = B *Y
B^-1*A^-1*X*A*B = Y

or in the case where you have Y but want X:

X*A*B *B^-1 *A^-1 = A*B*Y*B^-1 *A^-1
X = A*B*Y*B^-1 *A^-1

The above is just a special case of the general rule:

X*A = A*Y

Means

X=A*Y*A^-1
A^-1*X*A=Y

With the note that (A*B)^-1 = B^-1 * A^-1.

This procedure lets you examine a chain of transformations and ask "I want to apply a transformation at a specific spot, but store it by applying it elsewhere.", which is the core of your problem.

The chain of matrices you work with should include all transformations -- translations, rotations, scales -- not just transformations of the same kind, as solving for X * B = B * Y does not produce a solution for X * A * B = A * B * Y.

8
  • There're things I'm still not clear on; please edit for clarification/readability. I stated I'm using column-major matrices/vectors, but your math seems to be a mix of column/row major interpretations, and lacks operators, which is inconsistent & diff to follow. Also, when you say my equation is missing an inverse: missing where, exactly? Also, I know matrix ops are not commutative, please explain why/how this "forces" that; I didn't follow that. Nodes also return their full translation by concatenating Tw * Rw * Sw (w=world). There're some reasons to keep the T*R*S matrices separate.
    – code_dredd
    Jun 26, 2016 at 6:18
  • I meant to say that Nodes also return their full transforms (not translation) by concatenating Tw * Rw * Sw matrices. Since they're 4x4 column matrices and are read right-to-left, the order in which they're applied is equivalent to Tw * (Rw * Sw).
    – code_dredd
    Jun 26, 2016 at 6:38
  • 1
    @ray imagine someone posted code where it was full of manual loops via jumps and does addition and comparison with bit-by-bit operations written manually at each spot. And it did not work. You can spot that at least one of the bit operations has an error, because they had no carry-in logic, but cannot follow what it should be. You pointed out that using flow control and standard operations thr code would work better. They respond that gotos and bit operations have certain advantages, and ask you to tell you where they should get the carry-in from, and they are using 3s complement addition. Jun 26, 2016 at 7:02
  • Even if I put everything into a single matrix, and it suddenly works, I'm not really correcting the mathematical misunderstanding I currently have. I think your comment misses this. There're also things that appear to become more difficult -e.g. can no longer set an absolute world position just by creating a new translation matrix from a vector b/c I'd lose rotation/scaling transforms. It's also difficult for me to follow your explanation due to the column/row-major mix you have in your math. Unfortunately, the answer is not too useful for me in its current condition.
    – code_dredd
    Jun 26, 2016 at 7:29
  • 1
    I guess I'll see your edit later today as I'm calling it a night, but note that the way in which multiplications between matrices and vectors are written/read depends on whether you're using column or row major ones. For example, if using column-major organization (which is what I'm using), matrix-vector multiplication must be written as v' = M*v, whereas writing v' = v*M implies a row-major organization. That's the standard in math texts. Hope that helps clear ambiguities, and since these ops are not commutative, it does matter to the math.
    – code_dredd
    Jun 26, 2016 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.