[Pixman] Explaining bilinear in rounding.txt

[Pekka Paalanen]

On Tue, 15 Sep 2015 15:58:12 +0100
"Ben Avison" <bavison at riscosopen.org> wrote:

> On Mon, 14 Sep 2015 12:53:15 +0100, Pekka Paalanen <ppaalanen at gmail.com> wrote:
> 
> > On Sat, 12 Sep 2015 01:26:48 +0100
> > "Ben Avison" <bavison at riscosopen.org> wrote:
> >
> >> -- 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.
> 
> My interpretation was that the notation "round(x)" wasn't tied to a
> specific definition. It had already been used for two different purposes
> by that point in the document - for round to nearest with ties to plus
> and minus infinity. Here I was just using it as a catch-all for the two
> functions round_up(x) and round_down(x) whose unambiguous definitions I'd
> repeated in the preceding paragraph.

I perhaps would have understood using round_*(x), but I was also
confused by giving only one equation for two weights that obviously
need to be different.

> Perhaps we should go back and rename the existing uses of round(x) to
> round_nearest_ties_up(x) and round_nearest_ties_down(x) since it seems
> this wasn't obvious?

No, there was no confusion there. Immediately following the general
discussion it is said that Pixman rounds down, and that sets the
definition of round(x) for the rest of the doc.

> > 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?
> 
> Yes, that was what I was trying to say, but more concisely.
> 
> > How about the following:
> [...]
> > 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).
> 
> While this second pair of equalities are mathematically true, they do
> need to be evaluated in the opposite order, which might be worth
> noting.

This isn't code, this is a mathematical notation where order does not
matter, but I'm lacking a clear way to denote a set of equations. I can
just flip these around.

> 
> > *** Application to Pixman
> 
> I didn't quite follow the document structuring here. I took lines
> prefixed with "***" to be top-level headings and lines prefixed with
> "--" to be subheadings, but I think you've assumed the existing
> "Application to Pixman" section to be a subsection of "General notes
> on rounding" which stops before you get to "NEAREST filtering" and
> you're adding a new "Application to Pixman" subsection under
> "BILINEAR filtering"? Perhaps numbering the sections would make this
> clearer.

Yeah, I totally misunderstood the heading levels there. Somehow I
thought "application to pixman" was just that one paragraph that
explained the choice of the constants.

> > 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.
> 
> All the rest of the document is a functional specification - if you
> changed the rounding mode used for NEAREST filtering, even to round
> nearest-with-ties-up, then you'd be having a material effect on what
> Pixman does, the test harnesses would fail, and it would hopefully be
> considered a bug.
> 
> This subsection is a design specification - the COVER_CLIP flags are a
> contract between one internal part of Pixman (the operation
> dispatcher) and another internal part of Pixman (the fast paths and
> iterators). It can be changed without affecting Pixman's correctness
> (although its speed may well be affected by any such changes).
> 
> I think I'd be tempted to put the description - either the last
> paragraph or the entire subsection - in a large source code comment
> instead - say, alongside the #define of
> FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR. Hiding it away in a text file
> increases the likelihood of it not being kept up-to- date.

Right.

I can do that, once there is some concensus on how BILINEAR should be
described from a mathematical point of view in the first place. I
really would not like to start talking about convolution there.


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/20150916/9af525cf/attachment.sig>