10 ms·
Math behind rotation in MS Paint (2011)
- raphlinus 9y agoThe book "Digital Image Warping" by George Wolberg[0] goes into these tricks in great detail, as well as choices for the resampling filter. The world is very different today, bilinear texture sampling is built into GPU hardware and is lightning fast. The idea that a sequence of skews might be more efficient is a curious relic of when CPU was considered a reasonable place to do image transformation. [0]: https://www.amazon.com/Digital-Image-Warping-George-Wolberg/dp/0818689447 https://www.amazon.com/Digital-Image-Warping-George-Wolberg/...
- exDM69 9y agoI think that using a series of skew operations for rotation could still be useful. Bilinear/trilinear texture lookup will always look a bit blurry. Most graphics processing apps are still done using the CPU for most basic operations. And when the GPU is used, it's mostly compute shaders to get bit-accurate results (they could still be using the texture unit, though). Real time graphics is of course a different matter.
- gugagore 9y agoThat's interesting. The sheer operations still require interpolation (just that, you don't need to do 2D interpolation, 1D works out), so you still need to interpolate. And the scaling also requires interpolation. So I'm not sure if it's better or worse in terms of bluriness.
- exDM69 9y ago> The sheer operations still require interpolation (just that, you don't need to do 2D interpolation, 1D works out), Back in the day, the "rotozoom" coefficients were chosen at a nearest integer to avoid interpolation. This of course means that you can't continuously choose the value of the angle. Interpolation doesn't play nice with a palette-based image with a fixed number of colors anyway. When palette and integers are not a restriction, higher quality interpolation (bicubic, etc) is also an option. Comes with tradeoffs, of course. Using integer coefficients will also enable all kinds of opportunities for assembly-level optimization.
- chongli 9y agoYeah. Ideally you'd use a mix of both: GPU texture lookup for live preview and slower, more accurate method for the final result.
- kevin_thibedeau 9y agoThere are still plenty of situations where low level software solutions are needed for graphics rendering on embedded hardware.
- nurettin 9y agoHow is a rotation matrix "a trick"? It is just ordinary highschool maths.
- evincarofautumn 9y agoThe “trick” is decomposing it in terms of only skewing and stretching because those are the operations available in Paint.
- kowdermeister 9y agoProbably in high schools where they teach matrixes at all.
- kuschku 9y agoWhich are on the "REQUIRED" part of the curriculum in German high schools.
- pavel_lishin 9y agoThey certainly weren't in rural Texas, where I went to school.
- kuschku 9y agoI think common core is supposed to include them now, so that school should teach them nowadays.
- tedunangst 9y agoCurriculum changes aren't retroactive.
- dymk 9y agoI dunno about you but my middle school makes me come back every 5 years to go over newly added content. Flying all that way really is a pain.
- chestervonwinch 9y agoAnother way to approach this is to compute the LDU decomposition of the rotation matrix. L and U are shears while D is the scaling in the horizontal and vertical directions.
- baristaGeek 9y agoI remember taking Linear Algebra and learning how to rotate shapes in order to be able to find their area. You learn that rotations are essentially a linear transformation (btw, just like function derivatives, which I find to be super cool), which is what the guy on StackOverflow is doing. Pretty clever!
- catnaroek 9y ago> You learn that rotations are essentially[sic] a[sic] linear transformation Rotations about the origin are linear transformations. Rotations about an arbitrary point are affine transformations.
- baristaGeek 9y agoThanks! Didn't know that.