On Mon, 21 Sep 2015 08:32:48 +0300 Siarhei Siamashka <siarhei.siamas...@gmail.com> wrote:
> On Fri, 11 Sep 2015 14:30:23 +0300 > Pekka Paalanen <ppaala...@gmail.com> wrote: > > > From: Ben Avison <bavi...@riscosopen.org> > > > > As discussed in > > http://lists.freedesktop.org/archives/pixman/2015-August/003905.html > > > > the 8 * pixman_fixed_e (8e) adjustment which was applied to the transformed > > coordinates is a legacy of rounding errors which used to occur in old > > versions of Pixman, but which no longer apply. For any affine transform, > > you are now guaranteed to get the same result by transforming the upper > > coordinate as though you transform the lower coordinate and add (size-1) > > steps of the increment in source coordinate space. > > That's actually what I wanted too see proven. Let's take a look at the > following affine transformation matrix (with 16.16 fixed point values) > and two vectors: > > | a b c | > M = | d e f | > | 0 0 0x10000 | > > | x_dst | > P = | y_dst | > | 0x10000 | > > | 0x10000 | > ONE_X = | 0 | > | 0 | > > The current matrix multiplication code does the following calculations: > > | (a * x_dst + b * y_dst + 0x8000) / 0x10000 + c | > M * P = | (d * x_dst + e * y_dst + 0x8000) / 0x10000 + f | > | 0x10000 | > > These calculations are not perfectly exact and we may get rounding > because the integer coordinates are adjusted by 0.5 (or 0x8000 in the > 16.16 fixed point format) before doing matrix multiplication. For > example, if the 'a' coefficient is an odd number and 'b' is zero, > then we are losing some of the least significant bits when dividing by > 0x10000. > > So we need to strictly prove that the following expression is always > true even though we have to deal with rounding: > > | a | > M * (P + ONE_X) - M * P = M * ONE_X = | 0 | > | 0 | Sorry, this should be: | a | M * (P + ONE_X) - M * P = M * ONE_X = | d | | 0 | It does not change anything though ('d' treatment is not very much different from how we deal with 'a'). > or > > ((a * (x_dst + 0x10000) + b * y_dst + 0x8000) / 0x10000 + c) > - > ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c) > = > a > > It's easy to see that this is equivalent to > > a + ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c) > - ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c) > = > a > > Which means that stepping exactly by one pixel horizontally in the > destination image space (advancing 'x_dst' by 0x10000) is the same as > changing the transformed 'x_src' coordinate in the source image space > exactly by 'a'. The same applies to the vertical direction too. > Repeating these steps, we can reach any pixel in the source image > space and get exactly the same fixed point coordinates as doing > matrix multiplications per each pixel. > > By the way, the older matrix multiplication implementation, which was > relying on less accurate calculations with three intermediate roundings > "((a + 0x8000) >> 16) + ((b + 0x8000) >> 16) + ((c + 0x8000) >> 16)", > also has the same properties. However reverting > > http://cgit.freedesktop.org/pixman/commit/?id=ed39992564beefe6b12f81e842caba11aff98a9c > and applying this "Remove the 8e extra safety margin in COVER_CLIP > analysis" patch makes the cover test fail. The real reason why it fails > is that the old pixman code was using "pixman_transform_point_3d()" > function > > http://cgit.freedesktop.org/pixman/tree/pixman/pixman-matrix.c?id=pixman-0.28.2#n49 > for getting the transformed coordinate of the top left corner pixel > in the image scaling code, but at the same time using a different > "pixman_transform_point()" function > > http://cgit.freedesktop.org/pixman/tree/pixman/pixman-matrix.c?id=pixman-0.28.2#n82 > in the extents calculation code for setting the cover flag. And these > functions did the intermediate rounding differently. That's why the 8e > safety margin was needed. > > Since we are trying to justify the 8e extra safety margin removal in > the context of this patch, this is what I wanted to see explained in > the commit message. But maybe I'm just bad at math and it was perfectly > obvious to everyone else without any special proof. > > > No projective transform routines use the COVER_CLIP flags, so they > > cannot be affected. > > > > However, for COVER_CLIP_NEAREST, the actual margins added were not 8e. > > Because the half-way cases round down, that is, coordinate 0 hits pixel > > index -1 while coordinate e hits pixel index 0, the extra safety margins > > were actually 7e to the left and up, and 9e to the right and down. This > > patch removes the 7e and 9e margins and restores the -e adjustment > > required for NEAREST sampling in Pixman. For reference, see > > pixman/rounding.txt. > > > > For COVER_CLIP_BILINEAR, the margins were exactly 8e as there are no > > additional offsets to be restored, so simply removing the 8e additions > > is enough. > > > > Proof: > > > > All implementations must give the same numerical results as > > bits_image_fetch_pixel_nearest() / bits_image_fetch_pixel_bilinear(). > > > > The former does > > int x0 = pixman_fixed_to_int (x - pixman_fixed_e); > > which maps directly to the new test for the nearest flag, when you consider > > that x0 must fall in the interval [0,width). > > > > The latter does > > x1 = x - pixman_fixed_1 / 2; > > x1 = pixman_fixed_to_int (x1); > > x2 = x1 + 1; > > but then x2 is brought back in range by the repeat() function, so it can't > > stray beyond the end of the source line. > > The wording does not look very good here. It seems to imply that the > repeat() function has some special use in the latter (BILINEAR) case. > But the repeat handling is exactly the same for NEAREST and BILINEAR. > Also for NONE repeat and fetching pixels from the outside of the source > image bounds, we are not bringing the coordinate back into range but > interpreting the pixel value as zero. > > > When you write a COVER path, you are effectively omitting the repeat() > > function. > > > > As samplers are allowed to fetch the pixel at x2 unconditionally, we > > require > > x1 >= 0 > > x2 < width > > so > > x - pixman_fixed_1 / 2 >= 0 > > x - pixman_fixed_1 / 2 + pixman_fixed_1 < width * pixman_fixed_1 > > so > > pixman_fixed_to_int (x - pixman_fixed_1 / 2) >= 0 > > pixman_fixed_to_int (x + pixman_fixed_1 / 2) < width > > which matches the source code lines for the bilinear case, once you delete > > the lines that add the 8e margin. > > Thanks for explaining this. It was not the part that I was worried > about, but it is still good to have it nonetheless. > > > Signed-off-by: Ben Avison <bavi...@riscosopen.org> > > [Pekka: adjusted commit message, left affine-bench changes for another > > patch] > > Signed-off-by: Pekka Paalanen <pekka.paala...@collabora.co.uk> > > > > --- > > > > This is v2 part 1/2 of the patch "Change conditions for setting > > FAST_PATH_SAMPLES_COVER_CLIP flags". > > --- > > pixman/pixman.c | 17 ++++------------- > > 1 file changed, 4 insertions(+), 13 deletions(-) > > > > diff --git a/pixman/pixman.c b/pixman/pixman.c > > index a07c577..f932eac 100644 > > --- a/pixman/pixman.c > > +++ b/pixman/pixman.c > > @@ -497,21 +497,12 @@ analyze_extent (pixman_image_t *image, > > if (!compute_transformed_extents (transform, extents, &transformed)) > > return FALSE; > > > > - /* Expand the source area by a tiny bit so account of different > > rounding that > > - * may happen during sampling. Note that (8 * pixman_fixed_e) is very > > far from > > - * 0.5 so this won't cause the area computed to be overly pessimistic. > > - */ > > - transformed.x1 -= 8 * pixman_fixed_e; > > - transformed.y1 -= 8 * pixman_fixed_e; > > - transformed.x2 += 8 * pixman_fixed_e; > > - transformed.y2 += 8 * pixman_fixed_e; > > - > > if (image->common.type == BITS) > > { > > - if (pixman_fixed_to_int (transformed.x1) >= 0 && > > - pixman_fixed_to_int (transformed.y1) >= 0 && > > - pixman_fixed_to_int (transformed.x2) < image->bits.width && > > - pixman_fixed_to_int (transformed.y2) < image->bits.height) > > + if (pixman_fixed_to_int (transformed.x1 - pixman_fixed_e) >= 0 > > && > > + pixman_fixed_to_int (transformed.y1 - pixman_fixed_e) >= 0 > > && > > + pixman_fixed_to_int (transformed.x2 - pixman_fixed_e) < > > image->bits.width && > > + pixman_fixed_to_int (transformed.y2 - pixman_fixed_e) < > > image->bits.height) > > { > > *flags |= FAST_PATH_SAMPLES_COVER_CLIP_NEAREST; > > } > > Acked-by: Siarhei Siamashka <siarhei.siamas...@gmail.com> > > It's up to you whether to update the commit message or not. Maybe the > already existing reference to the mailing list archive is already > sufficient. > -- Best regards, Siarhei Siamashka _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman