Hi all

I'm getting myself confused with rotations in 2D when rotating about a point about another point. I'm using a simple tree as my scene graph. Each node knows its position relative to its parent, and there is a root node that is the ancestor of all nodes. So when I move a node all of its children move with it.

Rotations of a node about its parent are simple. But how do I rotate a node about another node ?

What I could find on the internet talks about translating the origin to the node being rotated around, rotating it, then translating back. So based on that, I came up with:

• From the node to be rotated walk up the tree to the root node building a translation matrix (1)
  
• From the origin node walk up the tree to the root node building a translation matrix (2)
  
• inverse the origin node's translation (2) matrix
  
• Form the origin translation matrix by multiplying matrix (1) by matrix (2), forming matrix (3)
  
• Multiply the node to be rotated by matrix (3). It's now a vector relative to the rotation origin
  
• apply rotation matrix
  
• multiply the node by the inverse of matrix (3), its now a vector relative to its parent again.
  

But that seems somewhat over complicated, which makes me think I'm either doing it wrong, or have found a convoluted way of doing something simple.


Any help greatly appreciated.

First of all, using a scene graph is, well, deprecated, but using it and ignoring its natural parenting seems me strange. Why do you want to rotate around grand-parent nodes?

However, here is the solution:

1. Every node has a position relative to its parent node and expressed as translation matrix T[sub]i[/sub] for the i-th node. Every node has an orientation relative to its parent node and expressed as rotation matrix R[sub]i[/sub] for the i-th node. Then the local transformation matrix of the i-th node is given by (using row vectors here)
L[sub]i[/sub] := R[sub]i[/sub] * T[sub]i[/sub]

2. The belonging global matrix, i.e. the transformation matrix relative to the overall common reference space (a.k.a. "the world") is computed as
W[sub]i[/sub] := L[sub]i[/sub] * W[sub]i-1 [/sub]= L[sub]i[/sub] * L[sub]i-1[/sub] * L[sub]i-2[/sub] * ... * L[sub]1[/sub]
where W[sub]i-1[/sub] denotes the global transformation matrix of the parent node. Please notice the recursive definition.

3. The center of rotation should be given by a node above the current one, e.g. W[sub]j[/sub] with 0 < j < i. As your internet source correctly stated, you have to make this temporarily the origin. You do this by applying the inverse matrix, because you go from global to local space. Hence
W[sub]i [/sub]* W[sub]j[/sub][sup]-1 [/sup]= L[sub]i[/sub] * L[sub]i-1[/sub] * ... * L[sub]j+1[/sub]
would do the trick. Now apply the rotation
W[sub]i [/sub]* W[sub]j[/sub][sup]-1 [/sup]* R
and finally shift the temporary center back to its original position:
W[sub]i[/sub]' := W[sub]i [/sub]* W[sub]j[/sub][sup]-1 [/sup]* R * W[sub]j[/sub]

4. If you want to know the local transformation, then do
L[sub]i[/sub]' = W[sub]i[/sub]' * W[sub]i-1[/sub][sup]-1[/sup]

Comparing this with the prescription given in the OP, you'll see the going from the current node up to the grand-parent node in the index sequence i-1 ... j+1 in the formulas above. Of course, you don't really need to compute W[sub]j[/sub] and W[sub]j[/sub][sup]-1[/sup] to just yield in the desired result L[sub]i[/sub]', because of
W[sub]i[/sub]' * W[sub]i-1[/sub][sup]-1[/sup] = W[sub]i [/sub]* W[sub]j[/sub][sup]-1 [/sup]* R * W[sub]j[/sub] * W[sub]i-1[/sub][sup]-1 [/sup]= ( L[sub]i[/sub] * L[sub]i-1[/sub] * ... * L[sub]j+1[/sub] ) * R * ( L[sub]j+1[/sub][sup]-1[/sup] * ... * L[sub]i-1[/sub][sup]-1[/sup] )
where the parentheses are only used for clarity (i.e. there is no mathematical necessity). However, due to the parenting mechanism you'll have to implement the computation of W anyway.


EDIT: Please check the formulas twice before using it, because mistaking an index is done quickly ;(

Thanks for an awesomely detailed post haegarr. I was able to follow the maths (which is rare =P).

Quick question, why are scene graphs deprecated ?

Quick question, why are scene graphs deprecated ?

Scene graphs are an example of violating the principle of single responsibility. It is used for logical grouping, assembling models, defining parent-child transformation hierarchies, doing spatial partitioning, ... all at once.

However, a single structure cannot do all this without enforcing restrictions. E.g. a scene graph naturally introduces a hierarchical bounding volume scheme. But what if you want to use a binary space partitioning scheme instead? Just an example. You'll find dozen of threads about this theme in GDnet as well as some articles on the internet.

I don't say that scene graphs are senseless, but IMHO using a single structure for each kind of job is the way to go today.

Yes Scene Graphs are frustrating when you try to force everything inside the Scene Graph design.. it's just annoying and stupid to follow such goal.