[cairo] [Pixman] Supersampling - 2nd attempt

[Soeren Sandmann]

Bill Spitzak <spitzak at gmail.com> writes:

> >         - interpolate to define the image on a continuous domain
> >         - transform
> >         - resample
> 
> The problem I am having is that this does not match how filtering of
> transforms is done in any image processing software I am familiar with.
> 
> This is how all software I am familiar with works, this replaces the
> three steps you show above:
> 
> 	- Figure out the INVERSE transform
> 
> 	- For each output pixel, the x, y, and inverse transform
> figures out a weighing factor for every pixel in the input
> image. These are weights for input PIXELS, not weights for input
> "points".
> 
> 	- Multiply input pixels by these weights and sum to get output
> 	pixel.

It is important to distinguish the *what* from the *how*. Obviously,
pixman is not implemented in the naive way that the pipeline would
suggest. The transform is stored in the inverse form, and there is
never an explicit 'continuous' representation of the source. Very
simplified, the pixman implementation does this:

        for each destination pixel

                Use transformation to find corresponding source point

                Find pixel locations surrounding that point

                Use repeat setting to map locations into the available
                samples

                Use filter setting to interpolate at the source point

                Composite with destination pixel into destination

Pixman has all kinds of optimizations and special cases where most of
the steps in the pipeline have vanished completely from the
implementation. But the pipeline is still an accurate description of
*what* is being computed.

Similarly, there is no requirement that the resample, transform and
interpolate steps have to be separate pieces of code as long as the
correct output is being computed.

One way to collapse the three steps into one is indeed to generate a
set of coefficients and use them to compute a weighted sum of the
input pixels. Owen has described this process in these notes:

        http://www.daimi.au.dk/~sandmann/pixbuf-transform-math.pdf

In those notes, the resampling is based on an integral over an image
defined on a continuous domain which in turn was the result of an
interpolation operation. Ie., precisely what pixman does.

There is nothing stopping the pixman implementation from using such a
table to compute the output of the interpolation + transform +
supersampling. (Except that the tables can become huge in some cases).

Basically, the table-of-weights is a (valid) implementation of various
resampling algorithms; it is not a fully-specified algorithm by
itself.

> I suspect you think you are describing mip-mapping, but a "sample" in
> a mipmap is not just an X/Y position, but also a "which scaled image"
> number. Mipmap is instead a compression scheme for weighted pixel
> samples, where the same weight for a square of 4 sample pixels can
> instead be specified as 4x weight of a single pixel in the 1/2 sized
> image. (In addition I do not think mipmapping is correct for Cairo:
> the filtering is very poor for non-square transforms, and the overhead
> is high if the samples all come from only one or two of the scaled
> images.)

I'm aware that I'm not describing mip-mapping. It could make sense to
add it at some point. To get acceptable quality out of it, you'd want
to use trilinear filtering where sampling some location consists of
finding the two nearest mipmaps, bilinearly interpolate in both, and
then linearly interpolate between the two results.


Soren