[cairo] [Pixman] Image downscaling

[Bill Spitzak]

Box/sync filtering does NOT require the transform to be axis-aligned.

The ideal/slow solution is this:

- The inverse transform is used to map the *corners* of the output pixel 
back to the input image space. This defines a quadrilateral in the input 
image. If perspective transforms are not allowed this quad will be the 
same shape for every output pixel, but it will be translated by 
non-integer amounts.

- This quadrilateral is used to scale and distort a filtering pattern. 
There is no ideal filtering pattern, but it's cross-section will 
resemble this, where the quad itself is from -.5 to +.5:
                            _
                           / \
                    __    /   \    __
             ------/--\--/-----\--/--\------------------
                       \/       \/
                  -3 -2 -1  0  1  2  3

   This is the sinc function. The integers are NOT pixels, but measured 
in the size of the quadrilateral. Also notice that this is not zero at 
the edges of the quad. It is zero at +/-1 (and all higher integers). 
Also note that it is infinitely large. The actual function is 
sin(pi*x)/(pi*x). The filter must integrate over it's entire range to 1.0.

- The source image is multiplied by this filter, and the integral of the 
entire result is the output pixel.

Okay, now here is how you get this to speed up:

- The quad is transformed to the closest axis-aligned rectangle *with 
the same area*. For non-perspective transforms the size of the rectangle 
can be figured out once from the transform matrix. This is only bad for 
extreme skews of the image.

- You only have to multiply an input pixel by the value of the filter 
exactly in the middle of it. This is reasonably close to the integral of 
the filter over the entire pixel.

- The filter is made the multiplication of two 1-d filters that are 
axis-aligned. This allows two-pass filtering.

- The filter is vastly simplified.
   - "sinc" filters are usually the above function multiplied by 
something that goes to zero at +/- 2 or 3.
   - "triangle" filters are similar to the sinc truncated at 1, they are 
1-abs(x) and 0 outside +/-1.
   - "box" filters are 1 from -.5 to +.5 and 0 everywhere else. This is 
the approach I recommend because it is by far the fastest and the 
quality is quite good.

- When scaling up the quad is, in effect, enlarged to be at least 1 unit 
in size. This will make the box filter identical to bilinear filtering 
for any scales >= 1. (however OS/X does not do this, the result is that 
the pixels in the source image turn into large anti-aliased squares, and 
many users prefer this).

- If you want anything more complex than box, you pre-compute the values 
of the filter at the center of pixels for a number of filter sizes and 
also a number of fractional offsets of these pixel sizes, putting the 
results in a table. The back-transform is rounded to the nearest entry 
in the table to find the filter. To keep the table reasonable size, I 
would switch to a box filter for any scales larger than 4 or so.