[Pixman] Explaining bilinear in rounding.txt
On Sat, 12 Sep 2015 01:26:48 +0100 "Ben Avison"wrote: > On Fri, 11 Sep 2015 10:13:08 +0100, Pekka Paalanen > 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 *
Re: [Pixman] [PATCH 1/4] Change conditions for setting FAST_PATH_SAMPLES_COVER_CLIP flags
On Mon, Sep 14, 2015 at 11:52 AM, Søren Sandmannwrote: > > 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. > I believe this *is* what happens in practice, much more often. The clip regions are not random, they are chosen by programmers for specific purposes. One thing that is wanted is to scale images up and preserve sharp edges. In Cairo this requires trimming the partial pixels off the edge. This will produce a clip that will turn on this flag. The alternative version of the flag will require the program to clip off at least one opaque pixel from two edges for scale factors less than 2. There is far less reason for a program to do that. Therefore I think this version of the flag will actually be used far more often, easily making up for the expense of adding the test for the zero-weight pixel to the bilinear fast paths. ___ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman
Re: [Pixman] [PATCH 1/4] Change conditions for setting FAST_PATH_SAMPLES_COVER_CLIP flags
Ben Avisonwrites: > 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. 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. The other three pixels are then found by adding 1 to one or both of the North-West pixel's coordinates. The CONVOLUTION filter works this way too, except the matrix may be bigger than 2x2 and is given explicitly rather than implicitly. It is important to note that a pixman image is not undefined outside its borders because the repeat mode always says what happens if you ask for such a sample. Now, of course, if the sample position is exactly on top of a pixel, some of the weights in the matrix will be zero and so a possible optimization is to eliminate those memory references. But I think this should be considered an optimization and not the specification. > 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 ^^ I really don't like to have a exceptions in the specifications for filters. Instead, I'd just say that the first pixel is found by rounding down, the second by adding 1 to the first pixel. The weights are given by 1 - (x - x0) and (x1 - x). > pixel - which only occurs if the given position aligns precisely with one > pixel. In that case, that one pixel value is used directly. > > 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: When described as a above, this simplification is simply a description of how BILINEAR works in all cases. I think this is my basic concern: In my mind BILINEAR_COVER_CLIP says "if[1] the filter is BILINEAR, then all pixels required for the operation (regardless of weight) are inside the borders of the source image". This is useful information for the implementations because it means they can elide the border-checking logic. 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. Søren [1] A subtle, but mostly irrelevant for this discussion, point is that the flag can be set even if the filter in question is not actually BILINEAR. ___ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman