[Pixman] Explaining bilinear in rounding.txt

[Pekka Paalanen]

On Sat, 12 Sep 2015 01:26:48 +0100
"Ben Avison" <bavison at riscosopen.org> wrote:

> On Fri, 11 Sep 2015 10:13:08 +0100, Pekka Paalanen <ppaalanen at gmail.com> wrote:
> > If you actually want to document things, then I think
> > pixman/rounding.txt would be the right place (and another patch). After
> > all, commit messages are only used to justify the patch, they are not
> > documentation people usually read.
> 
> Somehow, I don't remember ever having noticed that file! Perhaps it was
> because it was called rounding.txt that it never occurred to me that
> filtering might be documented there?

Yeah, it seems "rounding" also covers which pixel indices are chosen by
coordinates. rounding.txt is quite hidden between the source files. I think
Siarhei and Søren have pointed people to it before, which is why I know
about it.

> It's an odd omission that it doesn't talk about BILINEAR filtering,
> though. However, having briefly read through the text, even though some
> of it goes over my head a bit, I'd say it's describing from a strictly
> mathematical point of view. Discussion of exactly which pixels get loaded
>  from memory in order to reach this mathematical outcome feels outside the
> scope of that document to me.

Yes, it is from a very mathematical point of view, and talks mostly in
reference to 1-D images, assuming the generalization to 2-D is trivial
and separable.

A pixel image is seen as a set of regularly spaced point samples taken
from a (presumed continuous) function. This is in contrast to thinking
about an image consisting of solid-colored tiles. Thinking in point
samples allows one to define nearest and bilinear sampling as doing
point sampling at specific locations, rather than an integral over a
rectangle that is mapped from the destination pixel.

The pixel image itself is just a set of samples, whose labels
(positions) are [k + o]. You cannot read the image at any other
coordinates (labels) without first defining the filtering algorithm
that converts arbitrary sample coordinates to one or more labels, which
eventually get turned into pixel indices and memory addresses.

> Here's a draft section for BILINEAR filtering, comments welcome:
> 
> ---- 8< -----
> 
> -- BILINEAR filtering:
> 
> The BILINEAR filter calculates the linear interpolation between (i.e. a
> weighted mean of) the two closest pixels to the given position - one
> found by rounding down, one by rounding up.
> 
>       round_up(x) = ceil(x - o) + o
>       round_down(x) = floor(x - o) + o
> 
> The weight factor applied to each of these is given by
> 
>       1 - abs(round(x) - x)
> 
> except in the case where two to rounding functions amount to the same
> pixel - which only occurs if the given position aligns precisely with one
> pixel. In that case, that one pixel value is used directly.

I don't understand this. We have a definition for round(x) earlier and
used with NEAREST, but I don't think that is what you meant here.

Are you saying the weights would be:

	w1 = 1 - (round_up(x) - x)
	w2 = 1 - (x - round_down(x)).

And then the weigths do not sum to 1, when round_up(x) == x and
round_down(x) == x, because it leads to w1 = w2 = 1?

> 
> A common simplification, to avoid having to treat this case differently,
> is to define one (and only one) of the two round functions such that when
> the given positions aligns with a pixel, abs(round(x) - x) = 1, and hence
> the corresponding weight factor is 0. Either of the following pairs of
> definitions satisfy this requirement:
> 
>       round_down(x) = floor(x - o) + o
>       round_up(x) = round_down(x) + 1
> 
>       round_up(x) = ceil(x - o) + o
>       round_down(x) = round_up(x) - 1

How about the following:

---- 8< -----

-- BILINEAR filtering:

The BILINEAR filter calculates the linear interpolation between (i.e. a
weighted mean of) the two closest pixels at positions x1 and x2 to the
given position x - one found by rounding down, one by rounding up.

    x1 = round_down(x) = floor(x - o) + o
    x2 = round_up(x)   = ceil(x - o) + o

The weight factor applied to each of these is given by

    w1 = 1 - (x - x1)
    w2 = 1 - (x2 - x).

The weight of a source pixel is 1 at its original sampling position and
falls linearly to 0 at the positions of the neighboring samples. Here
we only care about one of the neighbors.

This definition has a special case at x = k + o, which leads to x1 = x2
= x and therefore w1 = w2 = 1. This is inconvenient as otherwise we
would have w1 + w2 = 1 which would be simpler for computing the
weighted mean.

To enforce w1 + w2 = 1, we can choose between two modifications to the
above choices of x1 and x2:

    x1 = round_down(x)
    x2 = x1 + 1

and

    x1 = x2 - 1
    x2 = round_up(x).

Both choices guarantee x2 - x1 = 1, and therefore

    w1 + w2 = 1 - (x - x1) + 1 - (x2 - x)
            = 1 - x + x1 + 1 - x2 + x
            = 2 - (x2 - x1)
            = 1

The resulting value after filtering in 1-D is

    w1 * pixel(x1) + w2 * pixel(x2).

Bilinear filtering in 2-D is separable.


*** Application to Pixman

As we have the choice of rounding x either up or down first, we
consider the other pixel to be the one before or after the first pixel,
respectively. This choice is directly connected to the definition of
FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR in Pixman.

Flag FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR signifies that bilinear
sampling will not read beyond the defined image contents so that repeat
modes can be ignored. As coordinates are transformed from destination
space to source space and rounded only once, the logic determining the
flag must assume whether the other pixel is before or after in each
dimension, and whether it will be read even if its weight is 0.

Pixman's choice is to assume that the other pixel is always after, and
it can be read even if the weight is 0. The rounding mode is therefore
round_down(x).

---- 8< -----

The last paragaphs may seem out of place, but I don't see any other
place atm. I'm fairly sure this stuff has not been documented anywhere
before, and it would be really good to have somewhere. OTOH,
rounding.txt does explain exactly which pixel gets loaded for NEAREST.


Thanks,
pq
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 811 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freedesktop.org/archives/pixman/attachments/20150914/ac044038/attachment.sig>