Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have one triangle in 3d space that I am tracking in a simulation. Between time steps I have the the previous normal of the triangle and the current normal of the triangle along with both the current and previous 3d vertex positions of the triangles.

Using the normals of the triangular plane I would like to determine a rotation matrix that would align the normals of the triangles thereby setting the two triangles parallel to each other. I would then like to use a translation matrix to map the previous onto the current, however this is not my main concern right now.

I have found this website http://forums.cgsociety.org/archive/index.php/t-741227.html that says I must

  • determine the cross product of these two vectors (to determine a rotation axis)
  • determine the dot product ( to find rotation angle)
  • build quaternion (not sure what this means)
  • the transformation matrix is the quaternion as a 3 by 3 ( not sure)

Any help on how I can solve this problem would be appreciated.

share|improve this question
    
This may be helpful: gamedev.stackexchange.com/questions/20097/… –  process91 Aug 8 '12 at 21:21
4  
I know it's not your main concern right now, but I suspect it will become a concern later: There's no reason to expect that after applying an arbitrary rotation aligning the normals the triangles will be related by a translation -- you'd still have to rotate around the normal to align them. Stated differently, it's not clear that aligning the normals is a good first step, since you then have to perform two separate rotations. You can get the axis of the full rotation by taking the cross-product of the changes in the differences between two pairs of vertex positions. –  joriki Aug 9 '12 at 5:13
    
That is a very good point I had not even though of that –  user1084113 Aug 9 '12 at 14:23
2  
@user1084113: No, that would be the cross-product of the changes in two vertex positions; I was talking about the cross-product of the changes in the differences between two pairs of vertex positions, which would be $((A-B)-(A'-B'))\times((B-C)\times(B'-C'))$. This gives you the axis of rotation (except if it lies in the plane of the triangle) because the translation drops out due to the differences, so this is purely the change in two different vectors due to rotation. The translation wouldn't drop out in your version. –  joriki Aug 10 '12 at 13:51
2  
@user1084113: There's no canonical answer to that question. An orientation-preserving isometry of $\mathbb R^3$ can be written as a composition of a rotation and a translation (in either order), but this decomposition is not unique -- you can shift the rotation axis and compensate by performing a different translation. Thus you can only determine the direction of the axis from the data, not its position. You can choose the position arbitrarily, e.g. through the origin, and choose the translation accordingly. –  joriki Aug 10 '12 at 14:33

8 Answers 8

Suppose you want to find a rotation matrix $R$ that rotates unit vector $a$ onto unit vector $b$.

Proceed as follows:

Let $v = a \times b$

Let $s = \|v\|$ (sine of angle)

Let $c = a \cdot b$ (cosine of angle)

Then the rotation matrix R is given by: $$R = I + [v]_{\times} + [v]_{\times}^2{1-c \over s^2},$$

where $[v]_{\times}$ is the skew-symmetric cross-product matrix of $v$, $$[v]_{\times} \stackrel{\rm def}{=} \begin{bmatrix} \,\,0 & \!-v_3 & \,\,\,v_2\\ \,\,\,v_3 & 0 & \!-v_1\\ \!-v_2 & \,\,v_1 &\,\,0 \end{bmatrix}.$$

share|improve this answer
    
I confirm that this works and gives answers identical to those in my answer. –  Kuba Ober Aug 14 at 22:46

At the top of my head (do the checking yourself) Let the given vectors in $R^3$ be $A$ and $B$, for simplicity assume they have norm 1, and assume they are not identical. Define $C$ as the cross product of $A$ and $B$. We want an orthogonal matrix $U$ such that $UA=B$ and $UC=C$. First change bases, to the new base $(U_1,u_2,u_3)=(A,B,C)$. In this new basis the matrix doing the job is simply $G=\left(\begin{smallmatrix} 0&1&0\\1&0&0\\0&0&1\end{smallmatrix}\right)$. Then we need the basis shift matrix, to the new basis. Write the coordinates of the vectors in the old base as simply $A=(a_1,a_2,a_3), B=(b_1,b_2,b_3), C=(c_1,c_2,c_3)$. Then the basis shift matrix can be seen to be $\left( \begin{smallmatrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3 \end{smallmatrix}\right)^{-1}$. The result is now simply $U=F^{-1} G F$, which is an orthogonal matrix rotating $A$ into $B$.

share|improve this answer
    
Actually, I think there may be further trouble - your matrix $U$ is only guaranteed to be orthogonal if $F$ is, which is only the case if $A$ and $B$ are orthogonal. In other instances, the angles of various other vectors to which $U$ is applied may be stretched or compressed. –  process91 Aug 9 '12 at 19:21
    
Your thought process is a good one, though - don't give up on it yet! I think there is a solution this way if you consider different original basis vectors which still have an easily represented form of $A$ and $B$. You could, for instance, choose the projection of $A$ on $B$, the rejection of $A$ on $B$, and $A \times B$. –  process91 Aug 9 '12 at 19:50
    
Just so that people aren't derailed: this answer doesn't work as-is, one has to take process91's comments into account. +1 since it provided valuable inspiration. –  Kuba Ober Aug 14 at 22:26

The quaternion is a 4-dimensional complex number: http://en.wikipedia.org/wiki/Quaternion used to describe rotations in space. A quaternion (like a complex number) has a polar representation involving the exponential of the arguments (rotations), and a magnetude multiplier. Building the quaternion comes from the cross product (the product of the complex components), which will give you the argument in those 3 dimensions, you'll then get a number from that in the form A+Bi+Cj+Dk, and write it out in the matrix form described in the article there.

An easier way would be to simply fingure out what your original vectors are in the 4-space, and take the appropriate inverse operations to get your resultant quaternion (without going through the dot/cross product steps) but that requires a good foundation in hypercomplex algebra.

share|improve this answer
    
Just to be clear: from the article, the dot product will be your scalar part, and the cross product the vector part, so with dot product: x and scalar product iy + jz + ka the quaternion q would be q = x +iy +jz +ka. –  Vilid Aug 8 '12 at 21:51
    
Not exactly. If the dot product is a, and the cross product is (x, y, z), it would be cos(a/2) + (x * sin(a/2))i + (y * sin(a/2))j + ( z * sin(a/2))k. Rotation quaternions are unitary. –  Jeff Jul 19 '13 at 2:33

Using Kjetil's answer answer, with process91's comment, we arrive at the following procedure.

Derivation

We are given two unit column vectors, $A$ and $B$ ($\|A\|=1$ and $\|B\|=1$). The $\|\circ\|$ denotes the L-2 norm of $\circ$.

First, note that the rotation from $A$ to $B$ is just a 2D rotation on a plane with the normal $A \times B$. A 2D rotation by an angle $\theta$ is given by the following augmented matrix: $$G=\begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix}.$$

Of course we don't want to actually compute any trig functions. Given our unit vectors, we note that $\cos\theta=A\cdot B$, and $\sin\theta=||A\times B||$. Thus $$G=\begin{pmatrix} A\cdot B & -\|A\times B\| & 0 \\ \|A\times B\| & A\cdot B & 0 \\ 0 & 0 & 1\end{pmatrix}.$$

This matrix represents the rotation from $A$ to $B$ in the base consisting of the following column vectors:

  1. normalized vector projection of $B$ onto $A$: $$u={(A\cdot B)A \over \|(A\cdot B)A\|}=A$$

  2. normalized vector rejection of $B$ onto $A$: $$v={B-(A\cdot B)A \over \|B- (A\cdot B)A\|}$$

  3. the cross product of $B$ and $A$: $$w=B \times A$$

Those vectors are all orthogonal and normal, and form an orthonormal basis. This is the detail that Kjetil had missed in his answer.

The basis change matrix for this basis is: $$F=\begin{pmatrix}u & v & w \end{pmatrix}^{-1}=\begin{pmatrix} A & {B-(A\cdot B)A \over \|B- (A\cdot B)A\|} & B \times A\end{pmatrix}^{-1}$$

Thus, in the original base, the rotation from $A$ to $B$ can be expressed as right-multiplication of a vector by the following matrix: $$U=F^{-1}G F.$$

One can easily show that $U A = B$, and that $\|U\|_2=1$. Also, $U$ is the same as the $R$ matrix from Rik's answer.

2D Case

For the 2D case, given $A=\left(x_1,y_1,0\right)$ and $B=\left(x_2,y_2,0\right)$, the matrix $G$ is the forward transformation matrix itself, and we can simplify it further. We note $$\begin{aligned} \cos\theta &= A\cdot B = x_1x_2+y_1y_2 \\ \sin\theta &= \| A\times B\| = x_1y_2-x_2y_1 \end{aligned}$$

Finally, $$U\equiv G=\begin{pmatrix} x_1x_2+y_1y_2 & -(x_1y_2-x_2y_1) \\ x_1y_2-x_2y_1 & x_1x_2+y_1y_2 \end{pmatrix}$$ and $$U^{-1}\equiv G^{-1}=\begin{pmatrix} x_1x_2+y_1y_2 & x_1y_2-x_2y_1 \\ -(x_1y_2-x_2y_1) & x_1x_2+y_1y_2 \end{pmatrix}$$

Octave/Matlab Implementation

The basic implementation is very simple. You could improve it by factoring out the common expressions of dot(A,B) and cross(B,A). Also note that $||A\times B||=||B\times A||$.

GG = @(A,B) [ dot(A,B) -norm(cross(A,B)) 0;\
              norm(cross(A,B)) dot(A,B)  0;\
              0              0           1];

FFi = @(A,B) [ A (B-dot(A,B)*A)/norm(B-dot(A,B)*A) cross(B,A) ];

UU = @(Fi,G) Fi*G*inv(Fi);

Testing:

> a=[1 0 0]'; b=[0 1 0]';
> U = UU(FFi(a,b), GG(a,b));
> norm(U) % is it length-preserving?
ans = 1
> norm(b-U*a) % does it rotate a onto b?
ans = 0
> U
U =

   0  -1   0
   1   0   0
   0   0   1

Now with random vectors:

> vu = @(v) v/norm(v);
> ru = @() vu(rand(3,1));
> a = ru()
a =

   0.043477
   0.036412
   0.998391
> b = ru()
b =

   0.60958
   0.73540
   0.29597
> U = UU(FFi(a,b), GG(a,b));
> norm(U)
ans =  1
> norm(b-U*a)
ans =    2.2888e-16
> U
U =

   0.73680  -0.32931   0.59049
  -0.30976   0.61190   0.72776
  -0.60098  -0.71912   0.34884

Implementation of Rik's Answer

It is computationally a bit more efficient to use Rik's answer.

ssc = @(v) [0 -v(3) v(2); v(3) 0 -v(1); -v(2) v(1) 0]
RU = @(A,B) eye(3) + ssc(cross(A,B)) + \
     ssc(cross(A,B))^2*(1-dot(A,B))/(norm(cross(A,B))^2)

The results produced are same as above, with slightly smaller numerical errors since there are less operations being done.

share|improve this answer

You can easily do all this operation using the following reusable library

Vector3 Lib

The following four steps worked for me.

         Vector3 axis = Vector3.CrossProduct(v1, v2);


        if (axis.Magnitude != 0)
        {
            axis.Normalize();
            Vector3D vAxis = new Vector3D(axis.X, axis.Y, axis.Z);
            Matrix3D m = Matrix3D.Identity;
            Quaternion q = new Quaternion(vAxis, AngleFromZaxis);

            m.RotateAt(q, centerPoint);
            MatrixTransform3D mT = new MatrixTransform3D(m);

            group.Children.Add(mT);

            myModel.Transform = group;
        }

Hope this helps !

With Regards, Shan

share|improve this answer

Use Rodrigues' rotation formula (See the section "Conversion to rotation matrix"). $\cos\theta$ is the dot product of the normalised initial vectors and $\sin\theta$ can be determined from $\sin^2\theta + \cos^2\theta =1$

share|improve this answer

Here's how to find the transformation from one triangle to another.

First triangle has vertices $a,b,c$ and normal $n$ and second triangle has vertices $a',b',c'$ and normal $n'$.

First we will find transformation $f(x)=Mx+t$ from reference triangle to the first triangle and another transformation $g(x)=M'x+t'$ from reference triangle to the second triangle. Then the transformation mapping first triangle to the second is $$T(x) = g(f^{-1}(x)) = M'(M^{-1}(x-t)) + t' = Rx + s$$ where $R = M'M^{-1}$ and $s = -M'M^{-1}t + t'$.

As the reference triangle we will use triangle with vertices $(0,0,0),(1,0,0),(0,1,0)$ and normal $(0,0,1)$

Then: $$M = [ b-a, c-a, n]$$ $$t = a $$ $$M' = [ b'-a', c'-a', n' ] $$ $$t' = a' $$

You have to be cautious and give vertices $a,b,c$ and $a',b',c'$ in right order. This has to satisfy $((b-a)\times (c-a))\cdot n > 0$ and the same for second triangle.


If those two triangles are not the same then matrix $R$ will not be orthogonal. But we can find isometry which maps one triangle to the another as close as possible in some sense. For this you can use Kabsch algorithm which is well explained here.

share|improve this answer

I have a simpler method comes from Erigen's "Mechanics of Continua". R is rotational matrix that rotate vector "a" align with vector "b" Matlab Code:

%%%%%% Rotate vector a align with vector b%%%%%%%%%% 

syms ax ay az bx by bz k real

a=[ax ay az]'
au=a./sqrt(ax^2+ay^2+az^2)

b=[bx by bz]'
bu=b./sqrt(bx^2+by^2+bz^2)

R=[bu(1)*au(1) bu(1)*au(2) bu(1)*au(3);

   bu(2)*au(1) bu(2)*au(2) bu(2)*au(3);

   bu(3)*au(1) bu(3)*au(2) bu(3)*au(3)]

To verify:

c=R*a
cu=c./sqrt(c(1)^2+c(2)^2+c(3)^2)
simple(bu-cu)

A zero result means that $c$ (rotated $a$) and $b$ are aligned with each other.

simple(sqrt(c(1)^2+c(2)^2+c(3)^2)-sqrt(c(1)^2+c(2)^2+c(3)^2))

A zero result means that $c$ (rotated $a$) and $a$ are of the same length.

share|improve this answer
    
Here's a MathJax tutorial :) –  barto Jul 25 at 17:50
    
Note that R = (au*bu')'. Or, simply, $R_{ij} = \hat{b}_i \hat{a}_j$ –  Kuba Ober Aug 14 at 18:49
    
Of course this doesn't really work. Say let a=[1 0 0], b=[0 1 0], we should get a simple $90^\circ$ rotation around the z axis, with R=[0 1 0; 1 0 0; 0 0 1]. –  Kuba Ober Aug 14 at 18:54
    
In all cases the $R$ squishes $a \times b$ to zero. –  Kuba Ober Aug 14 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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