tag:blogger.com,1999:blog-44918195681908505052023-02-01T07:25:57.908-08:00Algorithm StuffPhylliidahttp://www.blogger.com/profile/12153498938579020989noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-4491819568190850505.post-41945069368135932552018-08-27T13:42:00.000-07:002018-08-27T13:53:29.946-07:00Rotation mathsMy <a href="https://algorithmstuff.blogspot.com/2018/08/quaternions-are-just-weird-encoding-of.html">previous post</a> was designed to give you some intuition when working with quaternions. If you already have a library that does multiplications and inverses for you, you should be fine. If you'd like to learn more details or don't have a quaternion library, this blog post is for you.<br /><br /><br />How do we rotate something by some axis $V=(v_x, v_y, v_z)$ and some angle $\theta_V$?<br /><br />To answer that, lets start with something simpler first: we ball with a stick in it, the stick is pointing in direction $D=(d_x, d_y, d_z)$. We want to rotate the ball via $V$ to get a new stick direction $R=(r_x, r_y, r_z)$.<br /><br />We can do this by using <a href="https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula">Rodrigues' rotation formula</a>.<br /><br />$R = cos(\theta) D + sin(\theta) (V \times D) + (1-cos(\theta))(V \cdot D) V$<br /><br />where $\times$ is the cross product (returns a vector)<br /><br />$(V \times D)_x = (v_y d_z - v_z d_y)$<br /><div>$(V \times D)_y = (v_z d_x - v_x d_z)$</div><div>$(V \times D)_z = (v_x d_y - v_y d_x)$<br /><br />and $\cdot$ is the dot product (returns a single value)<br /><br />$(V \cdot D) = v_xd_x + v_yd_y + v_zd_z$</div><div><br /></div><div>This formula comes from splitting D into two pieces: $D_{\Vert}$, the part that is parallel to V, and $D_{\perp}$, the part that is perpendicular to V. Assuming $V$ and $D$ are normalized, $D_{\Vert}=(V \cdot D)V$ is the <a href="https://en.wikipedia.org/wiki/Vector_projection">vector projection</a> of $D$ onto $V$, and then $D_{\perp}=D-D_{\Vert}$ (also known as the <a href="https://en.wikipedia.org/wiki/Vector_projection#Vector_rejection">vector rejection</a> of $D$ onto $V$).</div><div><br /></div><div>Then we can find $R_{\Vert}$ and $R_{\perp}$ and get $R=R_{\Vert}+R_{\perp}$. (this isn't quite right, there are weighting terms on $R_{\Vert}$ and $R_{\perp}$ based on $\theta_V$, but this is a good intuition)</div><div><br /></div><div>$D_{\Vert}$ is unaffected by the rotation, so $R_{\Vert}=D_{\Vert}$. </div><div><br /></div><div>$D_{\perp}$ is rotated $\theta_V$ degrees around $V$. If $\theta_V=90$, $R_{perp}$ will be perpendicular to $D_{\perp}$ and $V$. The cross product of any two vectors is known to return a vector that is perpendicular to them both, so if $\theta_V=90$ degrees, $R_{\perp} = V \times D_{\perp}$. Likewise, if $\theta_V=-90$ degrees, $R_{\perp}= V \times D_{\perp}$, and if $\theta_V=180$ degrees then $R_{\perp}=-D_{\perp}$.<br /><br />The math for getting $R_{\perp}$ is then identical to what happens when you rotate the 2D vector $(1,0)$ by $\theta_V$ degrees around the origin, just replace $(1,0)$ with $D_{\perp}$ and $(0,1)$ with $V \times D_{\perp}$. See the <a href="https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula">Rodrigues' Rotation Formula wiki page</a> for the full details.</div><div><br /></div><br />TODO:<br /><br />If I have axis angle $V=(v_x, v_y, v_z), v_{\theta}$ and another axis angle $U=(u_x, u_y, u_z), u_{\theta}$, intuitively how we combine them is easy: we apply V to an object, then apply U to an object. But can we make a new axis angle $W=(w_x, w_y, w_z), w_{\theta}$ so that when we apply $W$, it is the same as applying $V$ and then applying $U$?Phylliidahttp://www.blogger.com/profile/12153498938579020989noreply@blogger.com5tag:blogger.com,1999:blog-4491819568190850505.post-15864804089727658162018-08-27T11:52:00.000-07:002018-08-27T13:52:55.346-07:00Quaternions are just a weird encoding of a rotation around a vectorWhenever the topic of Quaternions comes up, programmers I talk to are always annoyed by them. Quaternions seem useful, but tutorials that give nice intuitive pictures are very hard to find. Just look at the <a href="https://en.wikipedia.org/wiki/Quaternion">Wikipedia</a> page and you'll see what I mean.<br /><br />Let's fix that :)<br /><br />The takeaway here is this: <b>a single Quaternion is equivalent to an axis (3D unit vector) and a rotation θ degrees around that axis. Quaternions are just a weird encoding of these 4 values that make some computations nice.</b><br /><b><br /></b>How do we get the angle axis representation? Given a quaternion $Q=(q_x,q_y,q_z,q_w)$, our axis of rotation $V=(v_x, v_y, v_z)$ is:<br /><br />$v_x = q_x / \sqrt{1-q_w*q_w}$<br />$v_y = q_y / \sqrt{1-q_w*q_w}$<br />$v_z = q_z / \sqrt{1-q_w*q_w}$<br /><div><br /></div><div>and our rotation angle $\theta_V$</div><div><br /></div><div>$\theta_V = 2 * acos(q_w)$</div><div><br />You can just call this $\theta$, I just use this notation to make it clear that this is the axis $V$'s angle and not some other axis $W=(w_x, w_y, w_z)$'s angle (which would be $\theta_W$).<br /><br />Cool so that's nice. Intuitively, rotating objects with these is nice: we stick the axis $V$ pointing out from the center of that object, then rotate the object $\theta_V$ around it. But how do we represent this in code? If you have a library (such as Unity) that has quaternions, just use their code. If not, see my <a href="https://algorithmstuff.blogspot.com/2018/08/rotation-maths.html">follow up blog post</a>.<br /><br /><b>The important takeaway here is that every time you use a quaternion, just imagine it as an angle axis in your head.</b><br /><br />For example, given two quaternions Q_V and Q_U that by using the formula above map to angle axes $V=(v_x, v_y, v_z), \theta_V$ and $U=(u_x, u_y, u_z), \theta_U$, if you do $Q_V*Q_U$ that is equivalent to a new angle axis that rotates by V and U.<br /><br />What order do these happen in? Well, rotations are weird in that they are associative (you can swap parenthesis, so $(Q_V*Q_U)Q_W=Q_V*(Q_U*Q_W)$), but they aren't communicative so $Q_V*Q_W$ isn't always equal to $Q_W*Q_V$. So if want to rotate some $M$,<br /><br />$M*Q_V*Q_U$<br /><br />means: rotate M by V, and then by U<br /><br />while<br /><br />$Q_V*Q_U*M$<br /><br />means: rotate M by U, and then by V.<br /><br />The main reason we use quaternions (as far as I know) is that to rotate positions and vectors using angle-axis, you end up using some sins, cos, dot products, etc. With quaternions you can rotate positions and vectors via linear functions that you can just represent as a 4x4 matrix.<br /><br /></div>Phylliidahttp://www.blogger.com/profile/12153498938579020989noreply@blogger.com4