[Pixman] Image downscaling

[Krzysztof Kosiński]

W dniu 22 lipca 2011 14:44 użytkownik Jonathan Morton
<jonathan.morton at movial.com> napisał:
> On Fri, 2011-07-22 at 04:51 +0200, Krzysztof Kosiński wrote:
> 1) Trilinear or tricubic filtering on a mipmapped image.  The mipmaps
> are generated by box-filtering 2x2 pixels at a time, which is trivial to
> compute.  This is fast and general enough to be used universally for
> realtime 3D graphics, but requires extra memory to store the mipmaps,
> which also need to be updated with the base image.

Mipmaps + trilinear filtering would be a good addition, as they would
give a performance improvement for tasks such as resizing a bitmap on
the canvas in Inkscape (the bitmap doesn't change but we have to
render it hundreds of times with different transforms). However, they
are orthogonal to the bigger problem of perfoming a one-time,
completely generic image transform.

> 2) Straight box filtering based on pixel coverage.  This can be faster
> and cheaper than method 1, but usually only if the images are
> axis-aligned.

That's simple to implement but it could only function as a fast path.

> 3) Sinc filtering.  This is a common technique for high-quality audio
> sample rate conversion, which is quite easy to apply to 2D images,
> especially as it is not necessary to limit the filter support to achieve
> reasonable performance.  Just resize each row, then each column of the
> result.  Again, this only really works for axis-aligned resizing.

Ditto - this could be a fast path for axis-aligned scaling.

For a 100% generic algorithm, I though about something like this:
1. Find which source pixels are within the filter support region using
the image's transform matrix.
2. Compute inverse transformation matrix.
3. For each source pixel in the filter support region, multiply its
coordinates by the inverse matrix.
4. Compute the filter value corresponding to the source pixel's
position in the destination coordinate space.
5. Multiply the source pixel value with the computed filter value and
store it for later.
6. Add all those values together.

The problem is, I'm not sure how to do steps 1 and 2, mainly because
Pixman supports projective transformations.

Regards, Krzysztof