Rotation with three shears | Hacker News Reader

Rotation with three shears

cohost.org

325 pointsschemescape63 comments

Hah! Author of that 20-year-old web page here.

At the time I was attempting to use standard open source image processing software like ImageMagick to manipulate scientific data. I was disappointed to find that it was not suitable, both due to approximations like this one, and because all the libraries I looked at only allowed 8-bit grayscale. I really wanted floating point data.

Here is what I was working on back in those days: https://www.ocf.berkeley.edu/~fricke/projects/israel/project...

I was a summer student at the Weizmann Institute of Science in Rehovot, Israel, processing electron micrographs of a particular protein structure made by a particular bacterium. It's very interesting: this bacterium attacks plants and injects some genetic material into the plant, causing the plant to start manufacturing food for the bacterium. By replacing the "payload" of this protein structure, the mechanism can be used to insert other genetic structures into the plant, instead of the sequence that causes it to produce food for the bacterium. Or something like that.

Here's a random chunk of my research journal from those days: https://www.ocf.berkeley.edu/~fricke/projects/israel/journal...

The work contributed to this paper: https://www.jbc.org/article/S0021-9258(20)66439-0/fulltext

Here's the Wikipedia article about the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth

And his original web page that I linked to, now via archive.org: https://web.archive.org/web/20050228223159/http://people.ouc...

If you liked this trick, check out Alan Paeth's "Graphics Gems" series of books.

Kudos and thanks to the OCF at UC Berkeley which has hosted my web page there for more than a quarter century with just about zero maintenance on my part.

And thanks for the trip down memory lane!

> the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth

It seems that this algorithm was independently discovered by several authors, some of them earlier than Paeth's:

* H.Kiesewetter, A.Graf, Rotation in Digital Grids and Corresponding Models, Tech. Rep. Zentralinstitut für Kybernetik und Informationsprozesse, Akademie de Wissenschaften der DDR, 1985

* A.W.Paeth, A fast algorithm for general raster rotation, Proceedings GIVIP 1986

* P.E.Danielsson, M.Hammerin, High-accuracy rotation of images, CVGIP: Graphical Models and Image Processing, 1992.

And this algorithm was implemented on the image package of the ICL Distributed Array Processor [0] as soon as 1984.

The most cited reference for this method seems to be the famous "Yaroslavski" rotation:

* M.Unser, P.Thevenaz, L.Yaroslavski, Convolution-Based Interpolation for Fast, High-Quality Rotation of Images, IEEE Trans. Image Processing 1995

This is the same method but the shears are computed as filters in the frequency domain, thus they are exactly invertible (which is not the case if you use splines to perform the shears). Here the method really shines: you can rotate 36 times by 10 degrees and get back to the initial image, which is really spectacular.

I wouldn't be surprised if the decomposition itself was a well-known older result in linear algebra, for it seems to be closely related to the QR factorisation.

[0] https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processo...

A 2d shear looks like [[1,a],[0,1]] and a rotation of q is [[cos q, -sin q],[sin q, cos q]]

So you have a system like this to solve:

    [[1,a],[0,1]]*[[1,0],[b,1]]*[[1,c],[0,1]] 
    == [[cos q, -sin q],[sin q, cos q]]

It's not hard to solve (despite being overdetermined) and you can even throw that line above into a CAS directly. The solution is a bit long to paste here though.

> At the time I was attempting to use standard open source image processing software like ImageMagick to manipulate scientific data. I was disappointed to find that it was not suitable, both due to approximations like this one, and because all the libraries I looked at only allowed 8-bit grayscale. I really wanted floating point data.

Did you try ImageJ (https://imagej.net/)? I think it had support for floating point data 20 years ago. It also can be extended through plug-ins, so if it lacked a feature, it could be added fairly cleanly.

Kudos!

Back in those days, game programmers were like wizards. They did some pretty awesome stuff, with terrible toolsets.

They also tended to be paid fairly poorly, and worked to death, if I remember. I was once recruited by Sierra Online, and decided that discretion was the better part of valor, and all that.

You were doing fixed floating headers 20 years ago? Now I know who to blame ;-)

I'm not sure what you're talking about.

Your site has a fixed floating header. See that bar at the top that follows you as you scroll down? Sorry if I didn't use the technical term or establish enough context that you could infer what I was referring to. (Not sorry if it's just an issue of you playing dumb or not making an effort on your end.)

Oh I see what you mean. My page is the one linked from that page. It's written in very plain HTML: https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/r...

I had Dr. Alan Paeth as a university professor for 4 years, one or two classes every semester. I tried to fit my schedule around the classes he was teaching.

When you went to his classes you really had no idea what it was going to be about. I got the sense that sometimes he would just teach whatever was on his mind that day, nevermind the syllabus. It was sometimes bizarre, often challenging, and always interesting. I learned a lot from him.

I'm sad that he has passed and sorry to see his website is no longer online, but also pleased that his legacy is living on and people other than me still think of him -- thank you!

Somewhat related: performing two reflections can perform arbitrary rotations and translations:

- If the two lines we're reflecting across meet at a point, we'll get a rotation around that point (with twice the angle between the lines)

- If the two lines are parallel, we'll get a translation (perpendicular to the lines, of twice the distance between the lines)

In projective geometry (where parallel lines "meet at infinity"), rotation and translation are the same thing.

There's also a link to geometric algebra, which composes reflections into arbitrary "rotors"/"motors" (which are the same thing, projectively). To transform an object with a rotor, we apply it twice; due to this underlying 'two reflections' behaviour.

(Demo: https://enkimute.github.io/ganja.js/examples/coffeeshop.html... )

Interestingly, almost all higher dimensional rotations also can be decomposed into three shears. See https://www.sciencedirect.com/science/article/pii/S107731699... (click “view PDF” in top left to read)

I think using that in a voxel editor would be very useful.

even if "view PDF" is available, I always click my "Sci-Hub X Now!" button, as a matter of principle

Oh yeah, stuff like that is very common in graphics!

I remember a college exercise where I had to prove this by calculating the resulting transformation matrix which would apply these three shears in order and comparing it to the rotation matrix as provided.

Similarly, translation in 2D is the same as shearing in 3D - and translating in 3D is the same as shearing in 4D. That's why a lot of game engines use a 4D matrix for, well, everything: it's a very convenient way to scale, orient, and position an object.

Takes a while to get used to - especially if you have never used matrices before - but they are actually really easy in practice.

Of course the most important trick matrices have is that you can't just do all of those transformations with them. The matrix product is associative, and the matrix product is the composition of the linear maps, so you can do all those transformations at the same time, or multiple times, in any order.

There used to be a website that showed off cool mspaint tricks like putting an image on top of another with 50% opacity, and rotating images using shear. Pretty funny.

Do you remember which? Maybe it's still up, or at least archived. I'm curious for this 50% opacity trick now

50% opacity probably works my manually interlacing two images, then reducing the size to 50%. You can also do fun stuff like gradients in MS Paint: start out with a square canvas, divide it diagonally and fill each resulting triangle with a different color. Then use the "Stretch/Skew" dialog to horizontally (or vertically) stretch it all to the minimum (5%, if memory serves me right).

Edit: Actually, I suppose the minimum stretch was 1%. So the square should be 100x100 in size :)

iirc it was called nerdhaven or something. I can't seem to find it. But the other commenter got it right :)

1. Enlarge image by 200% -- mspaint uses nearest neighbor interpolation so this turns every pixel into 4 with no smoothing.

2. Replace every second row with a gnarly pink color, or anything else that's not in your original picture. Kinda tedious but with copy paste you can do it pretty fast.

3. Set that pink as your background color, then use the "transparent select" or whatever, it will select all pixels in your rectangle that's not your current background color.

4. Enlarge the target image by 200% in another mspaint, copy the first image over, then shrink by 50%.

I loved doing that haha, showed it to all my nerd friends.

IIRC - the game Wing Commander used the three shear method to rotate the ship images. Can anyone corroborate?

That is common knowledge for people of the old BBS intro timeline. I used this in good old Turbo Pascal to have my very first effects togehter with mode 13h. And im only like 4 decades old...

https://stackoverflow.com/questions/65909025/rotating-a-bitm...

Has links to two detailed blog posts about the method.

Was there any hardware/software which actually did this?

I can't think of any games console hardware which allowed a combination of more than two shears by modification of sprite/bg offset registers, it was either X, Y, or X+Y, but not X+Y+X.

It seems to me that using dx+dy 8.8 or 16.16 fixed-point coefficients for an inverted rotation matrix would by faster in terms of only one read+write required per pixel, rather than multiple (at least that's how I always saw rotations in the VGA mode 13h days, maybe things like the Amiga blitter could do it better?).

Didn't lots of consoles have a small scratch memory you could blit into and out of, making it possible to do in multiple steps?

https://www.sega-16.com/forum/archive/index.php/t-21390.html

Related: you can rotate a square by translating each quadrant to the position of its neighbor, and repeating recursively within each quadrant, until you stop at the single-pixel level.

If you think about these mrhtods using physics, it's extremely frustrating because nothing actually rotates. At the first detail, each pixel is facing the same direction. This is fine for discrete pixels, but feels wrong. Is it valid in real physics? Do the smallest particles have orientation?

Yeah! I loved learning this (some time ago) too! Wonder whether there's any cool filtering tricks that can give you something similar but also filtered result. Ie an 'anti-aliased' version - although interestingly the method in the article mentions the reversibility of the whole-pixel-shears approach, which is a fun exception to what 'aliasing' usually means: worse recovery of original signal.

Using simple interpolation to perform fractional pixel shears should do the trick.

Yeah, you resample fractional pixel values in the shears, ideally with a sinc() kernel. This has the virtue that the resampling weights are identical across lines in the shear, which allows a very efficient SIMD implementation. This is how we do CPU-based image rotations!

Follows from the LU factorisation of the rotation matrix.

Does it? I don't see how, can you explain?

How would you implement image rotation on a GPU? You wouldn't get good data locality for either the source or the target image, I suppose.

Probably easiest to just calculate the inverse? You're rendering the pixel that the original one would be transformed to, so you just have to find the original one in the sampled texture. Maybe just doing the same sin/cos vector but with negative angle.

Yes, you can scan e.g. horizontally (x axis first) through the target image, but for the source image you will have to do a memory lookup with bad locality.

Well you don't need to scan, each SIMD processes a pixel in paralel and they spit out the whole thing simultaneously in the end, at least according to my understanding. You'd also presumably need to cache the entire texture that's being rendered anyway, so cache misses due to locality problems likely aren't huge.

Textures usually reside entirely in fast GPU accessible memory, but cache misses during sampling can still be a problem (so entirely random access across the whole texture is still worse then accessing nearby pixels). The texture data is 'scrambled' in memory for better 2D spatial locality though, so once in cache, access of pixel groups which are close together both horizontally or vertically is fast.

(disclaimer: I'm not a hardware guy, and I also don't know if this applies to all pixel formats and different GPU architectures - texture cache details are also notoriously bad documented by GPU vendors).

Ok, I'm guessing from this that it only works for relatively small images (?)

Image lookups with bad locality is exactly what a GPU's texture pipeline is for

How does this pipeline deal with the locality issue, assuming the texture doesn't fit in the cache?

The texture cache tries to guarantee that every pixel is only read from DRAM once, and the texture sampler does bilinear sampling "for free". So a sequential copy and a "rotation copy" should take about the same time.

With a matrix multiplication: https://www.shadertoy.com/view/tsV3R3

https://en.wikipedia.org/wiki/Rotation_matrix

Used to do this in Quake map editors too.

I find it funny that modern pixel art games run on GPUs where single core (of which they have thousands) is hundreds time faster than the consoles of ye olde with that kind of pixel art.

Just for pure insanity value, I wonder how many copies of an old 8 bit game you could run at once.

Maybe you could run them like an ensemble model. All randomness in every game unique and user input delayed by 0-25ms on all of them. Instead of losing a life you lose a parallel copy, specifically one of the ones you died in.

The display shows them overlaid all at once.

I once tried to combine Pong with Tetris.

The paddle would be a tetris field, so you'd be playing that as usual, but also moving it up and down to bounce the ball.

The idea of putting games inside each other like that appealed for a while. I could imagine running snake inside the "dots" of pacman, and other simple things for example.

Controlling them would be a nightmare, but it's a fun experiment to imagine the games that would go well inside each other. Defender in the logs floating in frogger, for example?

That reminds me of AGDQ runs where someone used one controller to control few games at once, it was helluva impressive.

first place I found this was https://datagenetics.com/blog/august32013/index.html which is still a good read.

I remember doing this on Paint to rotate a image.

The biggest downside is that Paint squeezes the result of shearing into the original selection, losing pixels in the process. Neither resizing or shearing is antialiased either, only resizing the whole image applies a bilinear filter.

Same in special relativity

Shouldn't that be obvious from the transformation matrices? (I'm just vaguely sure this is true.)

Ah, the mathematician's "obvious", where it clearly isn't :)

I am no mathematician but as far as I remember a shear matrix is just half of a rotation matrix (in 2D).

as the article states, R = STS, where S is the same shear in both factors.

Question at a mathematical seminar: "Isn't it obvious that [...]?", the speaker turns to blackboard, writes furiously for 5 minutes muttering to himself, then replies "Yes it is!"

Sounds about right; any code I could write in 5 minutes is necessarily trivial, so I assume similar for other professions that don't have hard time limits.

Writing for for 5 minutes is much easier than thinking for 5 minutes.

"Obvious" means you know it without thinking.

In a math lecture context obvious is intuitively true, five minutes on the blackboard is "trust (your gut) but verify".

Not everything pans out the way even the best think - and the very best are notorious for "knowing" results in a flash .. but having to diddle about to produce a logical chain that "proves" that flash for minute, hours, days and sometimes years or a century after their death..

That get us to the obvious theorems that are actually false https://math.stackexchange.com/questions/820686/obvious-theo...

To be fair many of those "obvious truths" are rapidly discounted by the kinds of teenagers that go on to become university core math students.

Fractal surface areas, the re-order of terms in an infinte series, infinite hotel questions, etc. were all high school puzzles in the 80s in my part of remote Australia so I can't imagine them stumping or confusing a university math lecturer.

This is domain where one letter variables is not only the norm but expectation.

I thought it was super mind blowing to learn that percentages were reversible, apparently that's obvious to people who know math well.

When reading the title I thought that too (maybe not “obvious”, but “unsurprising”), but what’s neat is that each pixel can be preserved 1:1, which I hadn’t expected.

I am not sure why you are being downvoted. I have been doing a project with Homogeneous Transform Matrices recently and also assumed that this was "obvious" since the shear diagonal lives in the rotation part of the matrix. Still, it's a very neat trick and I appreciate the OP for posting it!

Reply on news.ycombinator.com