https://cohost.org/tomforsyth/post/891823-rotation-with-three [noscript] log insign up tomforsyth Tom Forsyth @tomforsyth GPU designer and gfx coder * he/him * eelpi.gotdns.org/ Gfx coder and chip designer. Worked at Oculus, Valve, RAD, Muckyfoot, 3Dlabs, now back at Intel. Blade2, Larrabee, TF2, VR and many other atrocities. log in tomforsyth Tom Forsyth@tomforsyth1/23/2023, 2:17 AM --------------------------------------------------------------------- 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" --------------------------------------------------------------------- 15 comments You must log in to comment. in reply to @tomforsyth's post: porglezomp porglezomp cassie@porglezomp1/23/2023, 2:35 AM 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 mintexists mintexists mint@mintexists1/23/2023, 3:34 AM This is super cool!! login to reply SaberaMesia SaberaMesia Sabera Mesia@SaberaMesia1/23/2023, 3:57 AM this is awesome! knowledge for knowledge, although mine is substantially less useful: the r-type fighter's name is the r-9a arrowhead! in some of the later r-type games there are a wide variety of other models of fighter but that one is the original :3 login to reply tomforsyth tomforsyth Tom Forsyth@tomforsyth1/23/2023, 4:54 AM I'm sorry ARROWhead? It's got a head on it alright, but ARROW - no. login to reply SaberaMesia SaberaMesia Sabera Mesia@SaberaMesia1/23/2023, 5:30 AM yeah, i know, but that's what they called it! although r-type lore does exist, an explanation for the name is never given in any of it, so all we know is that somebody decided 'arrowhead' sounded cool at some point login to reply 0x10f 0x10f 0x10f@0x10f1/23/2023, 7:18 AM Lookin' good! login to reply zaratustra zaratustra @zaratustra1/23/2023, 9:21 AM This might be usable in javascript since CORS policies disallow pixel sampling login to reply sol-hsa sol-hsa Sol_HSA@sol-hsa1/23/2023, 10:21 AM I was aware this is possible for 90' rotations but didn't think it would work on any angle. File under "would have been useful 30 years ago". login to reply jix jix jix@jix1/23/2023, 12:21 PM 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 sol-hsa sol-hsa Sol_HSA@sol-hsa1/23/2023, 2:23 PM I at least won't mind, as I didn't notice it on mastodon =) Pretty neat! login to reply velociraptor velociraptor april@velociraptor1/23/2023, 1:41 PM I found out about this from a tutorial on how to rotate things in MS Paint login to reply gull gull gull@gull1/23/2023, 9:38 PM was JUST thinking "so this is how you rotate text in MS Paint...." lmao login to reply kaylon kaylon Kaylon@kaylon1/23/2023, 5:08 PM Love this. login to reply artie-codecrafter artie-codecrafter Arina Artemis, Codecrafter@artie-codecrafter1/23/2023, 5:46 PM I don't want to do the calculations myself, but I do wonder if the "three shearings" end up more or less equivalent to the rotation. Because if you look at the affine transformation matrix and divide the rotation matrix by cos(th) it looks a bit like half of the shearing matrix. login to reply twi twi the cat ever@twi1/23/2023, 10:25 PM 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 * (c) 2022 anti software software club llc * thanks for using cohost Legal * Terms of Use * Privacy Notice * Community Guidelines About * @staff * Support * cohost status * cohost on twitter * ASSC on twitter * Careers