Math behind rotation in MS Paint

For those who don't know, MS Paint only has the options to rotate an image by right angles. To carry out an arbitrary rotation ($\theta^\circ$), the following hack is suggested:

1. Horizontal skew by $\theta$

2. Vertical Stretch by $\displaystyle \frac{1}{\cos^2\theta}$

3. Vertical Skew by $-\theta$

4. Horizontal and Vertical Stretch by $\cos \theta$

I would like to know how this works.

(I guess one way would be to show that multiplying the above operations represented as matrices should return the $2$D rotation matrix, but I do not know what are the matrix representations for the intermediate steps.)

Solution 1:

I think the following matrix product gives an explanation.

The first step is given by the matrix $$ S_1=\left(\begin{array}{cc}1&\tan\theta\\0&1\end{array}\right). $$

The second step corresponds to $$ D_1=\left(\begin{array}{cc}1&0\\0&\frac{1}{\cos^2\theta}\end{array}\right). $$

The second shearing operation corresponds to $$ S_2=\left(\begin{array}{cc}1&0\\-\tan\theta&1\end{array}\right). $$

At this point we have done $S_2D_1S_1$ that after a little bit of matrix manipulation and using the identity $\sin^2\theta +\cos^2\theta=1$ becomes $$ S_2D_1S_1=\left(\begin{array}{cc}1&\tan\theta\\-\tan\theta&1\end{array}\right). $$

The last step amounts to a scalar multiplication by $\cos\theta$ and gives us the familiar rotation matrix $$ \cos\theta S_2D_1S_1=\left(\begin{array}{rc}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{array}\right). $$

Edit: I got to use this as an exercise in a freshman course that just ended. I was actually a bit unhappy with that youtube video, because it doesn't show the transitions from one step to the other. To fix this problem I made an animation, where the four steps are done gradually: in steps one and three I continuously move the shear (skew) parameter from zero to the desired value. Similarly in steps two and four the scaling parameter changes continuously from one to the proper value. All the steps are done sequentially.

Solution 2:

Let's call the transformations $T_1,T_2,T_3,T_4$. The horizontal skew $T_1$ through angle $\theta$ should send $e_1=\begin{pmatrix}1\\0\end{pmatrix}$ to $e_1$ and send $e_2=\begin{pmatrix}0\\1\end{pmatrix}$ to $\begin{pmatrix}\tan\theta\\1\end{pmatrix}$. So the matrix implementing this transformation (which I'll also call $T_1$) has these vectors as its columns: $T_1=\begin{pmatrix}1&\tan\theta\\0&1\end{pmatrix}$.

Similar considerations give $T_2=\begin{pmatrix}1&0\\0&1/(\cos^2\theta)\end{pmatrix}$, $T_3=\begin{pmatrix}1&0\\-\tan\theta&1\end{pmatrix}$ and $T_4=(\cos \theta) I$. Multiplying these matrices together: $ T_4T_3T_2T_1=\begin{pmatrix}\cos\theta&\sin\theta\\ -\sin\theta&\cos\theta\end{pmatrix}$ which is the matrix of rotation by the angle $\theta$ in a clockwise direction (as you can verify by figuring out what the columns of this rotation transformation should be).

Solution 3:

In fact, you can apply any invertible linear transformation $\binom xy\mapsto \begin{pmatrix}a&b\\c&d\end{pmatrix}\binom xy$ to your image by only using a sequence of skew, stretch and flip transformations. This is due to the fact that the invertible matrices are generated by the so-called elementary matrices:

• The elementary skew matrices are the matrices of the form $\begin{pmatrix}1&a\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\a&1\end{pmatrix}$ for $a\in\mathbb R$. With these you can apply any linear transformation which doesn't change the area of the image and which doesn't change the orientation of the image. In fancier language: the skew matrices generate the special linear group.

• The elementary stretch matrices are of the form $\begin{pmatrix}a&0\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\0&a\end{pmatrix}$ for $a> 0$. Combining these with the matrices above, we can generate any invertible matrix which doesn't change the orientation of the image.

• Finally, we need the flip matrices $\begin{pmatrix}-1&0\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\0&-1\end{pmatrix}$ to change the orientation of the image ("flip it inside out", like turning a paper around and looking at it from behind).

As an example, we can interchange the x and y axes, that is, map $\binom xy$ to $\binom yx$, by the following operations:

1. Shear horizontally by 45 degrees.
2. Shear vertically by -45 degrees.
3. Shear horizontally by 45 degrees.
4. Flip vertically.

Solution 4:

Use a planar affine transformation.

As you pointed out, your operations are translation, rotation, shearing (skew) and scaling (stretch). We will represent each point on your image in homogeneous coordinates which allows us to use the composite matrix operations. Homogeneous coordinates just means that we tack on a $1$. So if a point has the coordinates $(x,y)$ the vector in homogeneous coordinates is $$u = \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} $$

The transformation matrix to translate the image by $t_x$ and $t_y$ is: $$ T = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} $$

The rotation matrix to rotate it by $\theta$ degrees is: $$ T = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

The scaling matrix to scale each dimension is: $$ T = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

The shearing matrix: $$ T = \begin{bmatrix} 1 & a_x & 0 \\ a_x & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

And all you have to do is multiply these matrices to composite these transformations. E.g. suppose you wanted to rotate and shear:

$$ \begin{bmatrix}x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & a_x & 0 \\ a_y & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix}x \\ y \\ 1 \end{bmatrix} $$

And to obtain the point in screen coordinates just normalize by $w$, i.e. $$(x', y') = (x'/w',y'/w')$$