[HN Gopher] Rotation with three shears
___________________________________________________________________
Rotation with three shears
Author : schemescape
Score : 293 points
Date : 2023-01-23 05:39 UTC (17 hours ago)
(HTM) web link (cohost.org)
(TXT) w3m dump (cohost.org)
| djmips wrote:
| IIRC - the game Wing Commander used the three shear method to
| rotate the ship images. Can anyone corroborate?
| matja wrote:
| 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?).
| cma wrote:
| 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
| TheRealPomax wrote:
| first place I found this was
| https://datagenetics.com/blog/august32013/index.html which is
| still a good read.
| tobinfricke wrote:
| 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!
| ChrisMarshallNY wrote:
| 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.
| enriquto wrote:
| > 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 fur
| 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...
| Y_Y wrote:
| 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.
| hoytech wrote:
| 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!
| [deleted]
| Someone wrote:
| > 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.
| [deleted]
| SilasX wrote:
| You were doing fixed floating headers 20 years ago? Now I know
| who to blame ;-)
| tobinfricke wrote:
| I'm not sure what you're talking about.
| MadameBanaan wrote:
| I remember doing this on Paint to rotate a image.
| qa-tari wrote:
| 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.
| Gravityloss wrote:
| Used to do this in Quake map editors too.
| danwills wrote:
| 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.
| colanderman wrote:
| Using simple interpolation to perform fractional pixel shears
| should do the trick.
| [deleted]
| crote wrote:
| 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.
| contravariant wrote:
| 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.
| schindlabua wrote:
| 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.
| Aardwolf wrote:
| Do you remember which? Maybe it's still up, or at least
| archived. I'm curious for this 50% opacity trick now
| Ennea wrote:
| 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 :)
| chriswarbo wrote:
| 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... )
| ilyt wrote:
| 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.
| eternityforest wrote:
| 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.
| stevekemp wrote:
| 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?
| ilyt wrote:
| That reminds me of AGDQ runs where someone used one
| controller to control few games at once, it was helluva
| impressive.
| HK47Revive wrote:
| 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...
| meindnoch wrote:
| Follows from the LU factorisation of the rotation matrix.
| enriquto wrote:
| Does it? I don't see how, can you explain?
| amelius wrote:
| 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.
| tiborsaas wrote:
| With a matrix multiplication:
| https://www.shadertoy.com/view/tsV3R3
|
| https://en.wikipedia.org/wiki/Rotation_matrix
| moffkalast wrote:
| 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.
| amelius wrote:
| 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.
| WithinReason wrote:
| Image lookups with bad locality is exactly what a GPU's
| texture pipeline is for
| moffkalast wrote:
| 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.
| flohofwoe wrote:
| 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).
| amelius wrote:
| Ok, I'm guessing from this that it only works for
| relatively small images (?)
| sheerun wrote:
| Same in special relativity
| hgsgm wrote:
| https://stackoverflow.com/questions/65909025/rotating-a-bitm...
|
| Has links to two detailed blog posts about the method.
| Someone wrote:
| 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.
| 4gotunameagain wrote:
| even if "view PDF" is available, I always click my "Sci-Hub X
| Now!" button, as a matter of principle
| hoseja wrote:
| Shouldn't that be obvious from the transformation matrices? (I'm
| just vaguely sure this is true.)
| softcactus wrote:
| 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!
| layer8 wrote:
| 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.
| eternityforest wrote:
| I thought it was super mind blowing to learn that percentages
| were reversible, apparently that's obvious to people who know
| math well.
| dTal wrote:
| Ah, the mathematician's "obvious", where it clearly isn't :)
| [deleted]
| skywal_l wrote:
| I am no mathematician but as far as I remember a shear matrix
| is just half of a rotation matrix (in 2D).
| [deleted]
| hgsgm wrote:
| as the article states, R = STS, where S is the same shear
| in both factors.
| ilyt wrote:
| This is domain where one letter variables is not only the
| norm but expectation.
| jjgreen wrote:
| 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!"
| ben_w wrote:
| 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.
| hgsgm wrote:
| Writing for for 5 minutes is much easier than thinking
| for 5 minutes.
|
| "Obvious" means you know it without thinking.
| defrost wrote:
| 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..
| kzrdude wrote:
| That get us to the obvious theorems that are actually
| false
| https://math.stackexchange.com/questions/820686/obvious-
| theo...
| hgsgm wrote:
| 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?
___________________________________________________________________
(page generated 2023-01-23 23:02 UTC)