On Wed, 23 Sep 2015 11:40:32 +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. No projective > transform routines use the COVER_CLIP flags, so they cannot be affected. > > Proof by Siarhei Siamashka: > > 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 = | d | > | 0 | > > 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. > > ** proof ends > > 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; > When you write a COVER path, you take advantage of the assumption that > both x1 and x2 fall in the interval [0, width). > > 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. > > Cc: Siarhei Siamashka <siarhei.siamas...@gmail.com> > Signed-off-by: Ben Avison <bavi...@riscosopen.org> > [Pekka: adjusted commit message, left affine-bench changes for another patch] > [Pekka: add commit message parts from Siarhei] > Signed-off-by: Pekka Paalanen <pekka.paala...@collabora.co.uk> > > --- > > v2 is part 1/2 of the patch "Change conditions for setting > FAST_PATH_SAMPLES_COVER_CLIP flags". > > This is v3 with a yet more bikeshedded commit message. > > Ben, Siarhei, > > for the record, gentlemen, please give your reviewed-by's > so I can just push these two out without any confusion. :-) Yes, sure. Even the older commit message already included a link to the mailing list archive, so I did not have any problems with it. This final revision is also fine. Reviewed-by: Siarhei Siamashka <siarhei.siamas...@gmail.com> -- Best regards, Siarhei Siamashka _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman