[Pixman] [PATCH 1/2] Remove the 8e extra safety margin in COVER_CLIP analysis
Siarhei Siamashka
siarhei.siamashka at gmail.com
Sun Sep 20 22:32:48 PDT 2015
On Fri, 11 Sep 2015 14:30:23 +0300
Pekka Paalanen <ppaalanen at gmail.com> wrote:
> From: Ben Avison <bavison at 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 |
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 <bavison at riscosopen.org>
> [Pekka: adjusted commit message, left affine-bench changes for another patch]
> Signed-off-by: Pekka Paalanen <pekka.paalanen at 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.siamashka at 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
More information about the Pixman
mailing list