7 ms·
Rotation with three shears
- danwills 4y agoYeah! 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.
- colanderman 4y agoUsing simple interpolation to perform fractional pixel shears should do the trick.
- deleted 4y ago[deleted]
- stephencanon 4y agoYeah, 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!
- schindlabua 4y agoThere 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.
- Aardwolf 4y agoDo you remember which? Maybe it's still up, or at least archived. I'm curious for this 50% opacity trick now
- Ennea 4y ago50% 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 :)
- schindlabua 4y agoiirc 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.
- Someone 4y agoInterestingly, almost all higher dimensional rotations also can be decomposed into three shears. See https://www.sciencedirect.com/science/article/pii/S1077316997904202 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.
- 4gotunameagain 4y agoeven if "view PDF" is available, I always click my "Sci-Hub X Now!" button, as a matter of principle
- tobinfricke 4y agoHah! 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/projects.html 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.html 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 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 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.bc.ca/awpaeth/awpaeth.html 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!
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- enriquto 4y ago> the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth 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_Processor https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processo...
- MadameBanaan 4y agoI remember doing this on Paint to rotate a image.
- qa-tari 4y agoThe 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.
- hoseja 4y agoShouldn't that be obvious from the transformation matrices? (I'm just vaguely sure this is true.)
- dTal 4y agoAh, the mathematician's "obvious", where it clearly isn't :)
- skywal_l 4y agoI am no mathematician but as far as I remember a shear matrix is just half of a rotation matrix (in 2D).
- deleted 4y ago[deleted]
- hgsgm 4y agoas the article states, R = STS, where S is the same shear in both factors.
- jjgreen 4y agoQuestion 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!"
- chriswarbo 4y agoSomewhat 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#pga2d_rotors_and_translators https://enkimute.github.io/ganja.js/examples/coffeeshop.html... )
- meindnoch 4y agoFollows from the LU factorisation of the rotation matrix.
- enriquto 4y agoDoes it? I don't see how, can you explain?
- Gravityloss 4y agoUsed to do this in Quake map editors too.
- HK47Revive 4y agoThat 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...
- amelius 4y agoHow 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.
- moffkalast 4y agoProbably 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.
- amelius 4y agoYes, 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.
- moffkalast 4y agoWell 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.
- flohofwoe 4y agoTextures 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).
- 4y ago
- sheerun 4y agoSame in special relativity
- djmips 4y agoIIRC - the game Wing Commander used the three shear method to rotate the ship images. Can anyone corroborate?
- ilyt 4y agoI 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.
- eternityforest 4y agoJust 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.
- stevekemp 4y agoI 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?
- ilyt 4y agoThat reminds me of AGDQ runs where someone used one controller to control few games at once, it was helluva impressive.
- hgsgm 4y agohttps://stackoverflow.com/questions/65909025/rotating-a-bitmap-with-3-shears https://stackoverflow.com/questions/65909025/rotating-a-bitm... Has links to two detailed blog posts about the method.
- hgsgm 4y agoRelated: 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?
- TheRealPomax 4y agofirst place I found this was https://datagenetics.com/blog/august32013/index.html https://datagenetics.com/blog/august32013/index.html which is still a good read.
- crote 4y agoOh 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.
- contravariant 4y agoOf 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.
- matja 4y agoWas 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?).
- cma 4y agoDidn'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 https://www.sega-16.com/forum/archive/index.php/t-21390.html