Jump to content
  • Advertisement
Sign in to follow this  

Finding a Rotation Matrix when Start and End Object Vertex Positions are Known

This topic is 3943 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, After reading Advanced Character Physics by Thomas Jakobsen I have been trying to implement the system myself. I was able to finish the constraint system fairly easily but when it comes to applying those constraints to a model and orienting my model based on the new positions of the "particles" I run in to trouble. For example: I have a box with 5 vertices ( or "particles" as Jakobsen calls them ). One on each corner of the box and also one at the center of mass ( the center of mass particle is probably useless ). At the beginning of my program I store an arbitrary vector between two of these particles (Note: at the beginning of the program the orientation matrix is equal to the identity matrix). After physics does it's thing, the vector between these two particles will change. I can now use this vector and the original vector to form a rotation matrix using the axis angle formula. This works fine for a simple "stick" but for a box you need more information to form your orientation matrix. So to my question. Knowing the start and end positions of all vertices, how would I go about forming an orientation or rotation matrix? Thanks, Peter ***EDIT*** I figured it out a solution soon as I posted this... always seems to happen when I start writing my problems down. Anyway, what I'm going to do is just do another axis-angle equation after my first one. The axis that will be used is the vector that I rotated in to after my first axis angle equation. If anyone has a better method though please feel free to tell me as two axis-angle equations seems like a bit much.

Share this post

Link to post
Share on other sites
One simple solution for generic affine transforms is this,

but if you want specifically a rotation matrix, then you might be able to rewrite it as
a 3x3 rotation with no scale or translation factors and do something similar from there to solve it with fewer data points. (You will need at least 2 or 3 probably, though, because of the number of degrees of freedom of a rotation.)

Anyway, on to the case of a general affine transform.
So, lets imagine we have a vector to vector transformation. This transformation is an affine transformation matrix, and since we are using 3d homogenous coordinates, this means that we have:

|x'| |a11 a12 a13 tx| |x|
|y'| |a21 a22 a23 tx| |y|
|z'| = |a31 a32 a33 tx| |z|
| 1| | 0 0 0 1| |1|

Following from this definition, we can concatenate 4 column vectors on input and output to create a matrix equation in terms of 3 4x4 matrices.

|x1' x2' x3' x4'| |a11 a12 a13 tx| |x1 x2 x3 x4|
|y1' y2' y3' y4'| |a21 a22 a23 tx| |y1 y2 y3 y4|
|z1' z2' z3' z4'| = |a31 a32 a33 tx| |z1 z2 z3 z4|
| 1 1 1 1| | 0 0 0 1| | 1 1 1 1|

apply a matrix multiply, you can see that this is true.

Now, lets define this as the matrix formula [Vo] = [A][Vi]. We know Vi, because we know 4+ input points. We also know Vo, because we know 4+ output points. Using standard matrix math, we can say that [A]=inv([Vi]) * [Vo]. This matrix is the affine transformation that converted the input points to the output points.

It might be a bit more computationally intense than whatever you came up with, but it is a good toolbox to have, and this is really easy to implement if you have a matrix class that can handle these things for you.

As I said before, you said that you already know that its not going to have any scale or translation or shear factors, so that might allow you to decompose it into a translation with only 2x2 elements, or 3x3, for ease of calculation..As a matter of fact, if you know that your system is just a rotation, you could decompose it to just the upper left 3x3 quadrants, with only 3 input points (and no homogeneous '1') If you know that one of your input or output vectors are orthogonal,then the inverse of the matrix is just the transpose, which should be VERY fast for a 3x3. You can even flip the unknown matrix from one side of the equation to the other very easily using that trick..

Anyway, hope that helped

Share this post

Link to post
Share on other sites
Thanks for the reply. I've now come to the conclusion that my double axis-angle method might not work due to the fact that the second rotation axis might not be orthogonal to the vector and it's intended position.

I'm trying to go about understanding your method but I'm unsure if I understand fully. I may be wrong here, but if I want an orientation matrix for the entire object using your method I believe my column vectors contained in Vo have to be basis vectors. My vectors in Vi will then be those transformed basis vectors.

If I do it that way I know it will work but, unfortunately, I don't store that information anywhere, only my constraint vectors.

As an example:

Free Image Hosting at www.ImageShack.us

Consider you've got a tetrahedron and you know the initial positions of all the vectors between your vertices and the ending positions of all the vectors. How would you go about generating your orientation matrix for the new object?

Again, maybe your method will work just fine but I was under the impression it would only work if I am using basis vectors.


Share this post

Link to post
Share on other sites
Steve132, you got me thinking. I believe you had a really good idea there, and unless I am mistaken, we can always use the transpose for the inversion (and with only 3 points in each set).

We know that there are no shears or scales. We need 4 vectors on every side of your equation. As long as they are the "same ones" in the start and end coordinate systems, and all are inlinearly independent, it does not really matter what they are, they could be anything.

With 3 points A, B, C, we have 2 vectors. One is the "bone" or "lookat" vector going from C to A, and one is the "right" vector going from C to B. Cross product will give us the "up" vector. We can normalize and do another "backwards" cross product to ensure that those 3 vectors are an orthonormal base. This is exactly what the well-known standard "lookat" calculation works like.
For the fourth vector, we choose the vector from the origin to our point C.

So we have all 4 vectors that we can fill into your equation. Unluckily, we need to invert our "start" matrix, which is computionally intensive for the general case. We already made sure that we have an orthonormal base in the upper left, but we still have a translational component in that matrix. If only we had no translation.

But wait... here comes! Who said we cannot choose an arbitrary orgin for our world? It won't make a difference for our ONBs, and as long as we see the start and end offset points in the same coordinate system, it doesn't matter for them either.
So, what we do is, we imagine that our origin is in point C. Now, the last column for the "end" matrix is Cend-Cstart, and the last column in the "start" matrix is ZERO.
This just happens to be the matrix that we must find the inverse for, and now we can use the transpose.

Does that sound about right, or am I talking complete nonsense?

Share this post

Link to post
Share on other sites
Sorry, I should have replied to this post with my solution ( which sounds like what you described samoth, I didn't read it that closely since I have a solution already :) ).

Anyway. As long as I have two constraints I can build an orthonormal basis using those constraints. I then have my starting "basis" when my orientation is supposedly equal to the identity. All I need to do is form another "basis" later in the program and then as you said:

A * O = B

where A is my starting basis, O is the orientation matrix, and B is my ending matrix.

I can then say

A * A^-1 * 0 = B * A-1

0 = B * A-1

And that's my new orientation.

To form my basis I use one of my constraints as my "x axis" and then cross that vector with my other constraint to get my "y axis". I then cross my x and y axis to get my z axis and there we go. After making sure all basis vectors are normalized I have my orthonormal basis and I can throw it in to a matrix.

Again, it looks like this is what you were describing samoth but I didn't look too closely.


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!