[cairo] [Pixman] Better quality downsampling in cairo/pixman

[Bill Spitzak]

Soeren Sandmann wrote:

> We need to modify this algorithm to work like this:
> 
> For each destination pixel, several transformed source/mask
> locations are computed corresponding to a subpixel grid in the
> destination pixel. The interpolated values for these locations are
> then averaged together before being composited.

I think this is a poor explanation. The source pixels are not completely 
random and approaching it this way will produce a very slow algorithm.

A much better explanation is that for each destination pixel a single 
source *AREA* is defined. For the 6-element matrix being used by Cairo, 
this source area has 6 degrees of freedom, and can be defined as a 
parallelogram mapped to somewhere in the source image (for an arbitrary 
3D transform, this source area has 8 degrees of freedom and is an 
arbitrary convex quadralateral).

This source area is used to calculate the weighing for all the pixels 
from the source image, these weighted values are added to get the 
destination pixel. "Filtering" is the algorithm by which the weights are 
calculated, a possible one is that the weight is the percentage of the 
area that the source pixel intersects, but there are both much better 
ones and much faster ones. In particular the weights may be non-zero for 
pixels outside the area.

It is very common that the source area is reduced to a simpler object by 
throwing away some of the degrees of freedom, before figuring out the 
weights. For instance the current implementation is equivalent to 
throwing away all the information except the xy center of the shape, and 
then calculating the weight as the ratios of the Manhattan distances to 
the nearest pixels. This is obviously not good enough.

I think acceptable results are achieved by reducing the shape to the 
closest axis-aligned rectangle or ellipse (thus 4 degrees of freedom) 
before using it. Some algorithims go further and reduce it to a circle 
(3 degrees of freedom), some keep the angle of the ellipse (5 degrees of 
freedom). A more restricted shape makes the filtering algorithm much 
simpler and thus faster and very often worth it.

I still feel the best approach for Cairo is for the source images to 
keep track of a single "scaled" version. This is an integer down-rez of 
the original image, the scale selected so that it is the next larger 
1/integer over the actual transform. This image is then linearly 
interpolated by an unchanged Pixman to produce the final image. The 
image is only recalculated if the integer scale changes. This will allow 
drawing the same image repeatedly and with changes such as rotation with 
the same speed as it has now. Note that this is similar to mip-mapping 
but produces better results and may be much more appropriate for the use 
of Cairo, especially if 3D transforms are not being supported anyway.

There also needs to be a fix for how Cairo does scale-up. It needs to do 
non-fuzzy edges when the source is black-padded, and I now think it 
should also render the pixels as rectangles. This will require 
alterations to how Pixman does it's linear interpolation.