Some times you just have to derive it yourself

I've got my shared memory QEMU interface working really well. So well, in fact, that I'm looking for the next hard thing to do. One of the neatest features of my old QEMU GTK gui was that it supported software scaling using GDK pixbuf.

GDK pixbuf is kind of annoying though because it's a client side image. The scaling code in GDK is very pixbuf specific too. Also, I never was able to figure out how to do partial updates of a scaled image without getting artifacts.

Last night I started reading about bilinear scaling. The first thing I learned is that is not really scaling, but filtering, but not really filtering, actually interpolation. Last night I finally came across a site that gave a good explaination of it in terms of graphics but lacked the math. The only sites that I found that had the math provided it in either a heavily solved form (solving for different things that I was looking for mind you) or just made no sense at all.

This morning, I decided to see about deriving this myself so that I'd actually understand it. The idea is pretty simple, given a point of unknown color that lies in the middle of four points of known color, calculate relative distance from each known point to the unknown point. Then use the distances (with the total distance of all points normalized to 1) as a factor for each known color and simply sum the known colors to obtain the unknown colors.

This may sound obtuse but it's really intuitive when you see it in action. It's just saying that the closer an unknown point is to a known point, the more that known point's color should contribute to the unknown point's color.

Know that I understand the algorithm and have an implementation, I've thought of many interesting optimizations. For instance, the amount that a known point contributes to an unknown point is orthagonal to the actual color of the known points. This means it can be computed once. This reduces the actual operations per update to 4 multiples and 5 adds per pixel. This seems like the sort of thing that I should be doing with MMX so I'll be looking into that.

The other part of this algorithm that requires computation is determining which known points surround an unknown point. The cool thing here is that this not only independent of the color of the pixels but computing the X coordinates of the known points given an unknown point's X coordinate is independent of the Y coordinates of the unknown point and vice versa. This means that it can be precompute once for a single row and then once for a single column! That requires very little memory (which is good because I'm slightly concerned that caching the color factors will take up an enormous amount of memory).

Fun stuff!