Finding out a rotation matrix between two vectors

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Jun 16, 2007 at 14:41

I need to find the rotation matrix between two directional vectors that have the same origin and are rotated against each other in the x- and y-axes. Z-rotation is not possible, as one of the vectors most conveniently forms the local coordinate frame’s z-axis and rotating it along the z-axis would not change it.

What I am currently doing is to find out the angles (more accurately: the cosines of the angles) by projecting one of the vectors onto the yz-plane (which becomes vector a) and the xz-plane (vector b), respectively, and then find out the angles via:

cos(x-rotation) = (a * z) / ( a * z )
cos(y-rotation) = (b * z) / ( b * z )

This works quite well and I can use the resulting cosines in my rotation matrix (and the sines aren’t difficult from here either), but I was wondering if there is a less computationally intensive procedure to manage this.

10 Replies

Please log in or register to post a reply.

B7568a7d781a2ebebe3fa176215ae667
0
Wernaeh 101 Jun 16, 2007 at 22:18

Hey there !

I guess you won’t get any faster here, without using some less intuitive (and probably numerically quirky) method.

The common practice without resorting to projections would probably be to calculate the angle from the first vector to the second as in (v dot w) / (||v|| * ||w||), then build an axis perpendicular to both vectors as in (v cross w), then build a rotation matrix from the given axis and the given angle, which in total should boil down to nearly the same amount of operations you already have.

Generally, you should first see if a) optimization is required here and b) if there is a better algorithmic (i.e. higher level) optimization you can perform, before moving on to some sort of hack here.

Cheers,
- Wernaeh

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Jun 17, 2007 at 11:32

Well, the whole projection thing is more of a thought experiment than an actual computation. I just flatten the 3d-vector onto a plane by neglecting one of its components, making, for instance, (y, z) out of (x, y, z). When visualizing this, it looks like projecting the vector onto the plane when looking at it perfectly perpendicular.

As I recently found out, this also gives me a few other neat advantages. Since the y-component of the z-axis vector will always be zero, I don’t even have to calculate a real dot product and can reduce the calculation even further.

I don’t really understand your way of doing it, though I’ve seen it in a few of the papers I’ve read. I’ll have a look into it once I am done with this thing.

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Oct 18, 2007 at 16:10

Sorry to dig out this terribly old thing, but this issue has come up for me again, and there is no trick around this time.

I’m not at all sure what this method that has been proposed to me a few posts up really does and why it works, though I’m confident it does. The paper I’m reading only says the following when going to find the rotation between two vectors: “Next, a transformation defining the relation of the new axis to the other segment’s axis must be found. This can be done using techniques described in standard graphics texts for rotating a given vector into another arbitrary vector. I.e., find a local coordinate system for which the vector is the z-axis by taking the cross-product of the vector with another non-parallel vector, and then taking the cross-product of the vector with this new vector. Normalize axes and use them as rows in a rotation matrix.”

To me this seams like another way of doing it (somehow involving two cross products and no dot product). Right now, I have no idea how either of the two ways works, so I’d be happy about any help.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Oct 18, 2007 at 16:14

How about just taking the cross product of the two vectors, calculating the sine and cosine of the angle between them, and using the axis-angle rotation matrix formula (near the bottom of this page?

3ab032b513836588b8ffee8a594a8c15
0
J22 101 Oct 18, 2007 at 20:22

You can do this simply by using quaternions: v=(s+d)/|s+d|, q=[cross(v, d), dot(v, d)], where s=source unit vector, d=destination unit vector and q=resulting rotation quaternion. Then just convert the quaternion to matrix. You can further optimize this by removing v’s normalization by using quat->matrix conversion which works for non-unit quaternions.

855230605f07055d00f3f9c25c60fc63
0
Sniffman 101 Oct 20, 2007 at 13:10

Sorry for the rather long post coming up. I’d be glad if you read it all, though. ;-)

All of these are good proposals, so don’t get me wrong now, since I’m still trying to understand this approach I posted. I found it via a Google search as well, so it must be working. I’m having a few difficulties understanding it, though.

First of all, here’s what I know of how they do it in the paper: You take a vector you want to have a rotation matrix to in your current coordinate frame and assume that it is to be the z-axis of its new own coordinate system. Then, they build a cross product of this vector and ANY non-parallel vector (which is exactly the big deal for me). Then they take a cross product between the original vector and the new vector, normalize all of them and have the three unit vectors for the new coordinate frame. Then they simply enter them row-by-row into a matrix and they’re done.

I have a fairly good geometrical understanding of this now. When doing the first cross product, what is simply done is that on any arbitrary plane on which the original vector is located, another vector is constructed. This is then orthogonal to the original vector. The arbitrary non-parallel vector is just to make this plane. Then, they can just calculate the third axis by making a cross product of the other two.

But here’s the big question, or rather, the problem: If you take a different arbitrary non-parallel vector, of course all the axes are different, and the entire matrix will be a completely different one. In the paper, this goes uncommented and seems to be alright. But what good is this, if you, using this method, could possibly construct any number of different transformations? I mean, you want to have it definite, don’t you?

I find this very illogical at this point, so I’d be happy to be told what kind of fallacy I’m making here.

F15213bd1bee350b83c3a2e5f9748b13
0
flux00 101 Oct 20, 2007 at 15:07

Why are you constructing an arbitrary coordinate system? Just cross the two vectors you have to get a direction to rotate around, and then get the cosine of the angle between them using the dot product. Derive the sin of the angle from the cosine and build the matrix using the formula reedbeta posted.

3ab032b513836588b8ffee8a594a8c15
0
J22 101 Oct 20, 2007 at 15:09

@Sniffman

But what good is this, if you, using this method, could possibly construct any number of different transformations? I mean, you want to have it definite, don’t you?

There’s infinite number of correct transformations because you can freely rotate the object about z-axis and still have your contraints fullfilled. You should rather have rotation constrained to the axis that’s orthogonal to both new and old z-axis (cross product of the vectors), which is exactly what the quaternion solution does. Quaternion solution also performs better because you don’t have to compute any squareroots.

647e430ca6b2c38d008dc55b1c3a7ecc
0
karligula 101 Oct 22, 2007 at 19:17

Using quaternions is probably the most mathematically elegant aproach, but you’d have to convert your vectors to quaternions in the first place, so I don’t see the advantage really. I prefer the simpler way of using the cross product of two vectors you have as one axis, either of the two vectors as another axis, and the cross product of those two axes as the third axis. Then get the dot product of the two original vectors to find the angle.

All these different ways usually boil down to the same number of operations in the end anyway.

3ab032b513836588b8ffee8a594a8c15
0
J22 101 Oct 22, 2007 at 20:58

Those two approaches boil down to quite different set of instructions. Quick count gives me:
quaternions: 25 muls, 20 adds, 1 div
cross-product: 18 muls, 8 adds, 1 div, 1 sqrt
Also, quaternions don’t have unstability problem when both axis are pointing to the same direction, though they have unstability like cross-product when the axes point to opposite directions. You might get away of that with quaternions though by doing d*=1.0001f; ;)