# [cairo] downscaling capabilities

Bill Spitzak spitzak at thefoundry.co.uk
Fri Apr 18 14:46:10 PDT 2008

```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".

```