eden

eden

@eden

gamer girl incarnate

๐„† composer & percussionist ๐„ excitable lesbian ๐„ i play a lot of hardcore Destiny ๐„ a sweet face, and funny little horns! ๐„‡

โ™ฎ

twitter ๐„ช letterboxd ๐„ช backloggd

โ™ญโ™ฎโ™ฏ

log inask
eden
@eden
JillKatze
@JillKatze
tomforsyth
@tomforsyth

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.

The three successive shears to make up a full rotation

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.

Marge says "I just think they're neat"

You must log in to comment.

in reply to @tomforsyth's post:

porglezomp
@porglezomp

But why go to all this trouble though? Why not get your GPU to do it?

I've seen people use this trick in MS Paint which has (had?) shears but no rotations. Probably an unconventional place to be using it, but a very fun one.

login to reply
jix
@jix

Even less widely known: it generalizes to higher dimensions and to any volume preserving linear transformation A, not just rotations. So you could use this to linearly transform voxel data or go even higher dimensional. To do that you decompose A (permuting/flipping axes as required) into 3 unitriangular matrices and those are each just a bunch of axis aligned shears (exactly one shear each in the 2d case).

This is the algorithm I came up with a while ago: https://gist.github.com/jix/3df036fba9d1f1a4ae78a40bf6c67aac

(hope you don't mind me duplicating this comment here and on your mastodon post)

login to reply
twi
@twi

i put this in my rebug in tags-as-marginalia fashion but in absence of a feature showing tags in rebug notifications: this rules, i figured out i could sort of rotate stuff in mspaint this way but i only did the first two and not another x so it didn't work well except at relatively gentle angles. i had no idea a sequence of shears could actually map to a true rotation

login to reply
AlexStemcell
@AlexStemcell

Fun fact: The Sega Genesis/Mega Drive can shear background layers horizontally on a scanline-by-scanline basis, are vertically in 2-tile-wide blocks, and several games used this to simulate limited rotation (because at shallow angles, the visual elongation caused by not doing the third shear isn't as noticeable), notably Streets of Rage 2 and Castlevania: Bloodline.

The SNES had similar capabilities (vertical shearing was on a tile-by-tile basis but could only be done in three of the system's eight graphics modes) but they weren't generally used to simulate background rotation, owing the existence of mode 7.

login to reply
sanfierro
@sanfierro
#!/usr/bin/env python3
import cv2
import numpy as np
import math

def sheer(img, ratio, y=False, origin=None):
    result = img.copy()
    if y:
        result = np.transpose(result, (1, 0, 2))
    if origin is None:
        origin = result.shape[0] / 2
    for i in range(result.shape[0]):
        shift = round((i - origin) * ratio)
        if shift > 0:
            result[i,shift:] = result[i,:-shift]
        elif shift < 0:
            result[i,:shift] = result[i,-shift:]
    if y:
        result = np.transpose(result, (1, 0, 2))
    return result

def rotate(img, angle):
    img = sheer(img, -math.tan(angle / 2))
    img = sheer(img, math.sin(angle), y=True)
    img = sheer(img, -math.tan(angle / 2))
    return img

if __name__ == '__main__':
    a = cv2.imread('fox.png')
    # Photo by Jeremy Hynes https://unsplash.com/photos/UeCG6uMSKdE
    b = a.copy()
    for i in range(120):
        b = rotate(b, math.pi / 6)
    cv2.imshow('result', b)
    cv2.waitKey()

Look at what I got with this code https://i.imgur.com/BhrRrJG.png The code was slightly modified (+0.5 to origin, otherwise it looked bad) This extremely naive implementation of mine survives 12000 rotations by 30 degrees!

login to reply
Pinned Tags