[Pixman] [PATCH 1/4] Change conditions for setting FAST_PATH_SAMPLES_COVER_CLIP flags

[Ben Avison]

On Mon, 14 Sep 2015 19:52:18 +0100, Søren Sandmann <soren.sandmann at gmail.com> wrote:
> My take on the question is that conceptually the BILINEAR filter works
> by loading four pixels surrounding the sample locations, and then
> convolving them with a 2 x 2 matrix where the entries are determined by
> the fractional part of the sample position. The question then is: How do
> you determine the North-West pixel? And the answer is that you round
> down.

For what it's worth, my experience has been that treating the operation
as a two-pass operation (separable into horizontal/vertical passes)
generally outperforms the 2x2 convolution filter approach by a wide
margin. But let's say we still try to describe it in those terms.

You're making an assumption that the coefficients of that 2x2 matrix are

/ (1 - frac(x)) . (1 - frac(y))     frac(x) . (1 - frac(y)) \
|                                                           |
\ (1 - frac(x)) . frac(y)           frac(x) . frac(y)       /

However, other definitions will work, such as

/ frac(-x) . frac(-y)               (1 - frac(-x)) . frac(-y)       \
|                                                                   |
\ frac(-x) . (1 - frac(-y))         (1 - frac(-x)) . (1 - frac(-y)) /

These matrix coefficients are not part of the public Pixman API, but they
do affect how you align the matrix. In the first case, the position of
the NW coefficient is always found by rounding *down* the coordinates, as
you say; in the second, the position of the SE coefficient is always
found by rounding *up* the coordinates.

You might think this makes little difference, but as I've described
previously, there are benefits to the latter approach.

My problem is that by assuming the former approach is the one being used,
Pixman is being actively hostile to any other approaches. This is most
easily seen by examining the interval into which all coordinates (in
source space) must fall in order to qualify for the
FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR flag to be set.

Current definition (with 8*e border removed):
    [ 0.5 , width - 0.5 )   - inclusive at low end, exclusive at high end

What you would need in order to implement the alternate matrix definition
above, in the absence of any range checking within the fast path itself:
    ( 0.5 , width - 0.5 ]   - exclusive at low end, inclusive at high end

What I'm proposing:
    [ 0.5 , width - 0.5 ]   - inclusive at both ends

In this sense, Siarhei's naming suggestion of a name for my flag -
involving the word "TIGHT" - looks kind of inappropriate, as it's
actually the most inclusive. But I'm not going to quibble over the name.

If you're only going to have one flag, it makes sense for it to be the
most inclusive one. That way, any given fast path can always add
additional checks to detect cases they can't handle and pass them on to a
secondary routine. This is effectively the approach I took here:

http://lists.freedesktop.org/archives/pixman/2015-September/003946.html

It can't be done the other way round - once we have filtered out an
operation for consideration of bilinear fast paths, there's no way a fast
path can say "actually, yes I could have handled that if you had asked
me".

> A separate possibility is a flag that says "all pixels whose weights are
> non-zero are inside the borders of the source image". Is this useful
> information? It might be, and if so, it could be conveyed through some
> new flag, though I'd echo Siarhei's comment about whether this is
> something that happens in practice.

Here's an example I've just thought of which nicely illustrates how the
existing scheme leads to a suboptimal solution. Say we are aiming to plot
an image such that it is reduced in size vertically by a factor of 2, but
left unchanged horizontally. The overall effect desired is to find the
mean of each two vertically neighbouring pixels.

The set of Y coordinates, once transformed into source space, would be
   1.0, 3.0, 5.0, ... (height * 2 - 1.0)
The set of X coordinates, once transformed into source space, would be
   0.5, 1.5, 2.5, ... (width - 0.5)

Under the existing scheme, this would not be passed to any COVER fast
paths - because it involves the X coordinate at exactly (width - 0.5).
And yet it's obvious to a human that no pixels outside the source image
are involved. To slightly reduce the X increment to avoid this would
be highly undesirable, as it could lead to a marked softening and/or
sharpening as you move from left to right across the image. Trimming off
the rightmost pixel might also reasonably be frowned upon, so we'd be
left with having to use a slower fast path, for no good reason.

Ben