[cairo] downscaling capabilities

[Bill Spitzak]

I'm not sure about calling this "prefiltering". I think it is generally 
done in a single step and that step replaces the current bilinear 
filtering. In a general sense:

For a given output pixel, the center point of that pixel (X+.5, Y+.5) is 
back-transformed to the input image location, and then .5 is subtracted 
from each to get the source x,y.

Also the derivatives of this back-transformation are used to figure out 
two vectors (these vectors when drawn from the x,y go to the 
back-transform of X+1,Y and X,Y+1)..

Then "some algorithim" is used to assign weights to the pixels near the 
center point based on the fractional value of the center point and the 
derivative vectors. This weighted sum is then returned as the value for 
the output pixel.

The "some algorithim" is the variable part:

The current bilinear algorithm appears to be: ignore the derivatives, 
and use the fractional part of the x/y to weigh the four pixels at 
floor() and ceil() of the x/y.

A very popular algorithim is box filtering, which has the primary 
advantage that it is identical to bilinear if the scale is 1, and only 
three weights for each direction need to be calculated:

The vectors are converted to an axis-aligned rectangle with the same 
area as the parallogram they define, and as much as possible the same 
shape. This is then centered on the x/y. The weight for a pixel is the 
area of it that intersects this rectangle, divided by the area of the 
rectangle.

Any real implementation does not literally do the above, but is 
optimized by doing a "two pass" algorithim: you apply the horizontal 
weight first to a bunch of rows, then apply the vertical weight only 
once to all those sums. Also any real implementation takes advantage of 
constant derivatives or fractional portions of x/y from one pixel to 
another.

It is extremely common to enlarge the rectangle to be at least 1 in each 
direction. This makes any scaling up identical to bilinear filtering. 
OS/X Quartz seems to *not* do this, however, and lots of people like 
that, it will produce large antialiased squares for the pixels rather 
than blurriness, and that appears to be much less objectionable. It's 
slower than bilinear so you may only want to do this if the scale is 
large enough that it looks better.

You will also see "filter functions" mentioned a lot. These use some 
method to convert the distance from the center of a pixel to the x,y 
position to a number, and that number is then passed through this 
function to get the weight. You will see truncated sync, gaussian, 
Mitchell, and all kinds of other ones, there are books full of these. 
Often for speed the source is reduced to a rectangle and the x/y are 
used independently in the filter formula and the two results multiplied 
to get the weight. For many filters this is quite close to the same 
result, and allows a much faster two-pass algorithim described above.

The other thing you are going to see is mip-mapping. This means you 
precalculate powers-of-two scales of the image (1/2, 1/4, etc). You then 
can bilinearly filter the one that is just below the size you want. The 
problem with this is that the precalculation takes time and memory and 
must be redone whenever the source changes, there are artifacts when the 
horizontal & vertical scale are different and when they pass thorough 
the powers of two, and that the padding must be pre-decided if the 
source is not a power of 2 in size. My belief is that mipmapping is a 
poor fit to Cairo and pixman's usage. However it is possible that 
mipmaping is what you are thinking of when you said "prefiltering".