Math behind rotation in MS Paint (2011) | Hacker News Reader

Math behind rotation in MS Paint (2011)

math.stackexchange.com

165 pointsnamelost28 comments

The 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/...

I 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.

That'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.

> 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.

I see! But scaling surely requires 2D interpolation, then, right?

Scaling requires interpolation, but nearest neighbor sampling was good and fast enough for old school rotozoom effect.

Yeah. Ideally you'd use a mix of both: GPU texture lookup for live preview and slower, more accurate method for the final result.

There are still plenty of situations where low level software solutions are needed for graphics rendering on embedded hardware.

Another 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.

I 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!

> 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.

Thanks! Didn't know that.

How is a rotation matrix "a trick"? It is just ordinary highschool maths.

The “trick” is decomposing it in terms of only skewing and stretching because those are the operations available in Paint.

Probably in high schools where they teach matrixes at all.

Which are on the "REQUIRED" part of the curriculum in German high schools.

They certainly weren't in rural Texas, where I went to school.

I think common core is supposed to include them now, so that school should teach them nowadays.

Curriculum changes aren't retroactive.

I 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.

My school (mid 2000s) skipped over them.

They are not in Germany, see https://www.kmk.org/fileadmin/Dateien/veroeffentlichungen_be... which lists it as one optional alternative.

The KmK requires as minimum either Vectorial Analytical Geometry, or Linear Transformations (and both of these topics would teach people about this topic).

States can add upon these requirements, and several require both.

As the document clearly states matrix transformations are not part of the core curriculum in both topics[0]. You also know that not every German student goes through this curriculum at all.

[0]: Yes, it's just a multiplication which is taught but be honest: How many students will come up with that on their own without being told?

This is about achieving rotation through a combination of skewing and scaling about X and Y, not just about a direct application of a rotation matrix.

It's a trick because to many it's not immediately obvious (even if you know about transformation matrices).

This is exactly the kind of thing I visit HN for -- the demonstration and explanation of an interesting hack. You may not have found it interesting, which is perfectly fine, but please don't assume that others didn't.

Reply on news.ycombinator.com