[cairo] [Pixman] Image downscaling

[Bill Spitzak]

I want to describe another scheme I have been thinking of, and posted 
here before.

This is not going to produce ideal downscale filtering, however I think 
it may be quite close enough. It is definitely better than bilinear 
filtering of a mipmap. It is difficult to say if it is better than 
trilinear filtering of a mipmap. A huge advantage is all the work on the 
existing bilinear filtering in pixman is reused. Also it looks far 
faster than any other scheme I can think of.

It shares with the mipmap the need to create the intermediate filtered 
image. Changes to the source image must invalidate this image so it is 
recreated next time a scaled drawing is requested. An advantage over the 
mipmap is that it is much quicker to create this intermediate image as 
only a single 1/integer scale operation is done. Another advantage is 
that all the existing bilinear filtering code in pixman can be reused as 
the final step. Another advantage is that non-square scales are better 
supported. A disadvantage is that the intermediate image must be 
recreated if the scale changes more than a small amount.

The technique is this:

1. Take the inverse transform matrix and decompose it into two 
matricies. N and M are positive integers, and the determinant^2 of the 
other matrix (AD-BC)^2 is as close to 1 as possible.

		[ A B 0 ]   [ N 0 0 ]
	T =	[ C D 0 ] * [ 0 M 0 ]
		[ X Y 1 ]   [ 0 0 1 ]

2. if N and M are both 1 then use the normal bilinear filtering from the 
original image.

3. Otherwise we need to make an intermediate image that is scaled in x 
by 1/N and in y by 1/M. First check if you already have it. If not you 
must create it and keep it with the source image. Creation is very fast 
because each output pixel is the average of a NxM rectangle of input 
pixels (assuming a box filter). With appropriate locking, etc, you can 
also throw away old intermediate images.

4. Take the intermediate image and the left-hand matrix and use them in 
the normal bilinear filtering algorithim.

5. If the image is changed by drawing operations on it, dispose of or 
invalidate all the intermediate images (same as what needs to be done 
for a mipmap).