Rotation with three shears

There’s a graphics trick that used to be widely known that has now probably almost vanished from the graphics consciousness – you can do rotations by applying three shears in a row. This should surprise you! It surprised me. And it re-surprises me every time I remember it.

Shears are very simple graphics operations to do – you just render the sprite, but shifting the lines or columns a bit each time. But rotations are gnarly things that involve lots of maths and interpolation and so on. So how could you possibly construct one from the other?

The derivation is relatively simple, but I won’t do it here because there’s a perfectly good explanation over here:
https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/rotation_by_shearing.html

But the TL;DR is you do three shears:

1. shear in X by -tan(angle/2)
2. shear in Y by sin(angle)
3. shear in X by -tan(angle/2)

(that’s not a typo – the third shear is exactly the same as the first!)

This works for all angles -90 degrees to +90 degrees, which is fantastic! Beyond that you just need to apply an X and Y flip first (i.e. a rotation by 180), which can usually be done as part of the first shear.

Here’s a GIF of the R-Type fighter being smoothly rotated. Each image is a sheared version of the one to its left, with the final rotated image on the right. Sorry I didn’t get the looping perfect.

But why go to all this trouble though? Why not get your GPU to do it? Well, what if you don’t have one? Back in the days of 16-bit and 32-bit machines, we didn’t have fancy GPUs that could do arbitrary rotations. But we did have “blitters” that could copy rectangles of pixels from one place to another. And if you were clever you could persuade them to do a shear at the same time, because it’s just offsetting the rows or columns as you go. So using this trick you could get arbitrary rotations done. Now, you are doing three of them for a single rotated sprite, so it’s not exactly free, but the fact that you could do them at all was pretty magical.

Doing rotations this way also has some very interesting characteristics that doing them with a more general GPU operation does not:

1. There is no “maths” needed on the pixel data. We’re just copying bits – there’s no interpretation of what the bits actually mean. This means you can do this with any pixel format – it can be bitplaned 4-bit-per-pixel, 8-bit palettised, 565 format, or true-colour – the algorithm doesn’t know or care.

2. Every pixel in the source image is there exactly once in the final rotated image. Shears are exact – they copy each pixel exactly once. So therefore the rotated version has every pixel in the source exactly once. There’s no duplicates, and none are removed.

3. Therefore the area of the final image is perfectly identical. It has to be – same number of pixels!

4. Therefore there are no problems with “aliasing” from over-sampling or under-sampling data. This is a problem with most image manipulation – if you have a single very bright pixel, as you manipulate the image, sometimes you miss it entirely, sometimes you duplicate it multiple times, and if this happens differently each frame, you get annoying flickers. Doesn’t happen here – each source pixel is always present exactly once. (of course you get spatial aliasing because of “the jaggies”)

5. It’s perfectly reversible. I’m actually not sure how helpful this is in practice, but it’s a cool fact!

I find it very odd watching the final result, especially as it rotates veeeeery slowly. As it rotates, every pixel is always present – they don’t appear and vanish, they just migrate. I find it very difficult to wrap my brain around how they move around the screen in circles, without causing any gaps, and without overwiritng each other. Mesmerising.

Anyway, this knowledge is probably of limited use these days – I just thought it was neat, and as I happened to be working on a project that has a blitter but no GPU, I remembered this and decided to implement it – that’s where the GIF above comes from.