[cairo] [Pixman] Better quality downsampling in cairo/pixman
spitzak at gmail.com
Thu Jul 15 11:25:33 PDT 2010
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.
More information about the cairo