4 ms·

Beautiful maths simplification: quaternion from two vectors (2013)

118 points by sytelus 8y ago

adamnemecek 8y ago
Quaternions are lo-to-the-co. Dual quaternions are lo-to-the-co^2 http://www.chinedufn.com/dual-quaternion-shader-explained/ http://www.chinedufn.com/dual-quaternion-shader-explained/
slavik81 8y ago
Interesting. I was implementing this function in my project a couple months ago. The half-angle identities seemed promising and I wondered if an optimization like this were possible. Alas, I also needed the angle to compute the torque applied by an angular spring, so I slapped an arccos in there and called it a day.
romwell 8y ago
Hey, I did a write-up (and implementation, in ProcessingJS) of quaternion multiplication for Arcball interface (aka spinning 3D objects around with mouse). You can play with the implementation at [1] and see the source (and maths explained!) at [2]. Quick summary: 1. Quaternion (cos(a), sin(a) u)--> rotation about the axis u by angle 2a (u is a unit vector in R^3) 2. (x,u) * (y,v) = (xy - u . v, xv + yu + u X v), where . stands for the dot product, and X stands for the vector cross product. If you look at the source, you can see that I was lazy and used trig / inverse trig. However, once you grasp how it works, it is not hard to improve this code according to the article. The article is good once you know how quaternions work; my write-up aims to explain that. If the article scared you away, check [1] out - hope it helps! The code is Java-like, so should be readable, and has plenty of comments. [1]http://www.math.tamu.edu/~romwell/arcball_js/index.html http://www.math.tamu.edu/~romwell/arcball_js/index.html [2]http://www.math.tamu.edu/~romwell/arcball_js/arcball.pde http://www.math.tamu.edu/~romwell/arcball_js/arcball.pde
panic 8y ago
Is there a connection to geometric algebra here? The similarity of the final result to the geometric product (a dot b + a cross b) seems like it can't just be a coincidence.
- mattnewport 8y ago
  Yes, a quaternion is basically equivalent to a rotor in geometric algebra which is the geometric product of two vectors from what I remember.
  - mattnewport 8y ago
    More specifically, the rotor that rotates (unit) vector a to vector b is the geometric product of a and the half angle vector between a and b. Barring a sign change that works out equivalent to the quaternion given in the article.
- grondilu 8y ago
  Check out my implementation of a trackball with GA : http://grondilu.github.io/cube.html http://grondilu.github.io/cube.html
Ono-Sendai 8y ago
Related: Fast rotation of a vector by a quaternion - http://forwardscattering.org/post/54 http://forwardscattering.org/post/54
bnolsen 8y ago
use geometric algebra. quaternions use a left handed convention.
- eggy 8y ago
  I thought quaternions are handless. I use geometric algebra (or Grassman Algebra instead), since it seems more elegant to me.
user2994cb 8y ago
There is a neat derivation of this from the fact that reflection in a plane with unit normal Q can be represented as P -> QPQ with P and Q considered as pure quaternions (ie. no scalar part).
chombier 8y ago
A more direct derivation: if you normalize the quaternion product y * x, you get twice the rotation taking x to y. So you need the square root of that, which you can obtain by adding 1 to the real part, then normalize again. This directly gives the final form of the article, up to a small optimization.
- jkabrg 8y ago
  That's a nice way of looking at it. The trick of adding 1 to the real part doesn't work in the degenerate case where y=-x. In that case, as I said in my earlier comment, an alternative formula is PERP(y)(yx+|yx|). Both formulas need to be used in practice, depending on which one is closer to giving a degenerate answer.
jkabrg 8y ago
It's a one-liner in quaternion algebra: vu-|vu| followed by normalization. Proof can be carried out completely in quaternion algebra. An interesting degenerate case is when u=-v. In that case, another expression can be used: PERP(v)(vu+|vu|) {where PERP(v) means an arbitrary vector perpendicular to v} followed by normalization. Both formulas need to be used in practice, depending on which one is closer to outputting a degenerate result.
deleted 8y ago
[deleted]
Doxin 8y ago
So as someone with just about a negative amount of math experience, Are quaternions mostly just a 3-vector with a scale component (W) added to the end, or am I misunderstanding?
jkabrg 8y ago
Apparently, Hamilton defined quaternions as the solution to almost this exact problem. Quaternions are effectively elliptical vectors. That's a lot nicer than defining them in terms of generators and relations. [1] - https://en.wikipedia.org/wiki/Versor https://en.wikipedia.org/wiki/Versor

118 points by sytelus 8y ago

Quaternions are lo-to-the-co. Dual quaternions are lo-to-the-co^2 http://www.chinedufn.com/dual-quaternion-shader-explained/ http://www.chinedufn.com/dual-quaternion-shader-explained/

slavik81 8y ago

Interesting. I was implementing this function in my project a couple months ago. The half-angle identities seemed promising and I wondered if an optimization like this were possible. Alas, I also needed the angle to compute the torque applied by an angular spring, so I slapped an arccos in there and called it a day.

romwell 8y ago

Hey, I did a write-up (and implementation, in ProcessingJS) of quaternion multiplication for Arcball interface (aka spinning 3D objects around with mouse). You can play with the implementation at [1] and see the source (and maths explained!) at [2]. Quick summary: 1. Quaternion (cos(a), sin(a) u)--> rotation about the axis u by angle 2a (u is a unit vector in R^3) 2. (x,u) * (y,v) = (xy - u . v, xv + yu + u X v), where . stands for the dot product, and X stands for the vector cross product. If you look at the source, you can see that I was lazy and used trig / inverse trig. However, once you grasp how it works, it is not hard to improve this code according to the article. The article is good once you know how quaternions work; my write-up aims to explain that. If the article scared you away, check [1] out - hope it helps! The code is Java-like, so should be readable, and has plenty of comments. [1]http://www.math.tamu.edu/~romwell/arcball_js/index.html http://www.math.tamu.edu/~romwell/arcball_js/index.html [2]http://www.math.tamu.edu/~romwell/arcball_js/arcball.pde http://www.math.tamu.edu/~romwell/arcball_js/arcball.pde

panic 8y ago

Is there a connection to geometric algebra here? The similarity of the final result to the geometric product (a dot b + a cross b) seems like it can't just be a coincidence.

mattnewport 8y ago
Yes, a quaternion is basically equivalent to a rotor in geometric algebra which is the geometric product of two vectors from what I remember.
- mattnewport 8y ago
  More specifically, the rotor that rotates (unit) vector a to vector b is the geometric product of a and the half angle vector between a and b. Barring a sign change that works out equivalent to the quaternion given in the article.
grondilu 8y ago
Check out my implementation of a trackball with GA : http://grondilu.github.io/cube.html http://grondilu.github.io/cube.html

Ono-Sendai 8y ago

Related: Fast rotation of a vector by a quaternion - http://forwardscattering.org/post/54 http://forwardscattering.org/post/54

bnolsen 8y ago

use geometric algebra. quaternions use a left handed convention.

eggy 8y ago
I thought quaternions are handless. I use geometric algebra (or Grassman Algebra instead), since it seems more elegant to me.

user2994cb 8y ago

There is a neat derivation of this from the fact that reflection in a plane with unit normal Q can be represented as P -> QPQ with P and Q considered as pure quaternions (ie. no scalar part).

chombier 8y ago

A more direct derivation: if you normalize the quaternion product y * x, you get twice the rotation taking x to y. So you need the square root of that, which you can obtain by adding 1 to the real part, then normalize again. This directly gives the final form of the article, up to a small optimization.

jkabrg 8y ago
That's a nice way of looking at it. The trick of adding 1 to the real part doesn't work in the degenerate case where y=-x. In that case, as I said in my earlier comment, an alternative formula is PERP(y)(yx+|yx|). Both formulas need to be used in practice, depending on which one is closer to giving a degenerate answer.

jkabrg 8y ago

It's a one-liner in quaternion algebra: vu-|vu| followed by normalization. Proof can be carried out completely in quaternion algebra. An interesting degenerate case is when u=-v. In that case, another expression can be used: PERP(v)(vu+|vu|) {where PERP(v) means an arbitrary vector perpendicular to v} followed by normalization. Both formulas need to be used in practice, depending on which one is closer to outputting a degenerate result.

deleted 8y ago

[deleted]

Doxin 8y ago

So as someone with just about a negative amount of math experience, Are quaternions mostly just a 3-vector with a scale component (W) added to the end, or am I misunderstanding?

jkabrg 8y ago

Apparently, Hamilton defined quaternions as the solution to almost this exact problem. Quaternions are effectively elliptical vectors. That's a lot nicer than defining them in terms of generators and relations. [1] - https://en.wikipedia.org/wiki/Versor https://en.wikipedia.org/wiki/Versor