Rotation

A programming koan

by Peter Hosey


Original version: 2006-03-27

One of the hardest problems in working with raster graphics is rotation. How do you rotate an array of pixels by an arbitrary angle in such a way that the picture still looks good?

Let's start with nine pixels.

The starting 3-by-3 square of colors. In English reading order: red, orange, yellow, purple, gray, green, violet, blue, light blue.

Now we rotate them 45°.

Same square, rotated 45 degrees counter-clockwise. The square pixels are now diamonds; red is the left corner, and yellow is the top corner.

Simple enough, right?

The problem is, monitors don't adapt so easily to diamond-shaped pixels. We need to convert these diamond-shaped pixels back to square pixels.

Previous diamond arrangement, with the individual pixels rotated back to squares.

This is equivalent to showing the original square arrangement with diamond pixels:

Original (pre-rotation) square arrangement, with diamond-shaped pixels.

But there's a problem: Those gaps between the pixels. They make for a low resolution and will ruin our pretty colors. (Think of viewing the image through one of those roll-up car window shades.)

So we need to take the gaps out. This leaves us with one of two hopscotch-like representations:

The diamond arrangement with square pixels, with the gaps removed. The even rows are offset horizontally by half a pixel.
The diamond arrangement with square pixels, with the gaps removed. The even columns are offset vertically by half a pixel.

Hmmm. OK, so we got back to square pixels, but we have a new problem: the aspect ratio of the image has changed. Remember that we had a bisymmetrical diamond: the X diameter was the same as the Y diameter. Now we have a diamond that is squished on one axis or the other. And we still have the previous problem, that this won't fit on a monitor with a plain (non-staggered) grid of pixels.

No problem. Working from the second image, we'll interpolate the even columns from two pixels each into three pixels each.

The even columns are back in alignment with the odd columns. However, the pixels in each even column have faded somewhat as a consequence of interpolation. Also, the middle column is still only three pixels high, though the middle row is five pixels across.

Ack. Not so good. And what do we do about that middle column? Suppose we stretch it out to five pixels: rows (1,2)→1, (1,2,3)→2, (2,3,4)→3, (3,4,5)→4, (4,5)→5.

Same interpolation applied to the middle column. The top and bottom output pixels in that column are blended from white and the top/bottom input pixel; the inner two output pixels are blended from white and two input pixels; the center output pixel is blended from three input pixels.

Interpolation has faded the colors of each pixel in the middle column, and the center pixel is now a faint brown, rather than pure 50% gray. Blurgh. There must be a better way.

Added 2009-01-30

Coming back to it now, I see my mistake: I tried to stretch out one of the hopscotch versions. Let's try working from the original diamond pattern instead. We'll interpolate the average value of the pixels surrounding each gap.

We start off with the four-pixel group at each corner of the diamond, and average them to get the fifth pixel in the center in the group.

That looks good. We haven't distorted the colors of any of the original pixels, and the colors we've filled in look reasonable. Let's turn the knob down to 2× magnification and see how it looks close to actual size.

Win.


2009-01-30 http://boredzo.org/koans/rotation
Valid XHTML 1.0! Valid CSS!