tag:blogger.com,1999:blog-44918195681908505052023-10-13T14:58:55.581-07: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>&nbsp;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&nbsp;<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&nbsp;D)_y = (v_z d_x - v_x d_z)$</div> <div> $(V \times&nbsp;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,&nbsp; $D_{\Vert}=(V \cdot D)V$ is the&nbsp;<a href="https://en.wikipedia.org/wiki/Vector_projection">vector projection</a>&nbsp;of $D$ onto $V$, and then $D_{\perp}=D-D_{\Vert}$ (also known as the&nbsp;<a href="https://en.wikipedia.org/wiki/Vector_projection#Vector_rejection">vector rejection</a>&nbsp;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}$.&nbsp;</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>&nbsp;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.com1tag: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&nbsp;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&nbsp;θ degrees&nbsp;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.com3