[Pixman] [PATCH v11 13/14] pixman-image: Implement PIXMAN_FILTER_GOOD/BEST as separable convolutions

Oded Gabbay oded.gabbay at gmail.com
Sun Feb 7 14:10:18 CET 2016


On Fri, Feb 5, 2016 at 9:49 AM,  <spitzak at gmail.com> wrote:
> From: Bill Spitzak <spitzak at gmail.com>
>
> Detects and uses PIXMAN_FILTER_NEAREST for all 8 90-degree rotations and
> reflections when the scale is 1.0 and integer translation.
>
> GOOD uses:
>
>  scale < 1/16 : BOX.BOX at size 16
>  scale < 3/4 : BOX.BOX at size 1/scale
>  larger : BOX.BOX at size 1
>
>  If both directions have a scale >= 3/4 or a scale of 1/2 and an integer
>  translation, the faster PIXMAN_FILTER_BILINEAR code is used. This is
>  compatable at these scales with older versions of pixman where bilinear
>  was always used for GOOD.
>
> BEST uses:
>
>  scale < 1/24 : BOX.BOX at size 24
>  scale < 1/16 : BOX.BOX at size 1/scale
>  scale < 1 : IMPULSE.LANCZOS2 at size 1/scale
>  scale < 2.333 : IMPULSE.LANCZOS2 at size 1
>  scale < 128 : BOX.LANCZOS2 at size 1/(scale-1) (antialiased square pixels)
>  larger : BOX.LANCZOS2 at size 1/127 (antialias blur gets thicker)
>
> v8: Cutoff in BEST between IMPULSE.LANCZOS2 and BOX.LANCZOS2 adjusted for
>     a better match between the filters.
>
> v9: Use the new negative subsample controls to scale the subsamples. These
>     were chosen by finding the lowest number that did not add visible
>     artifacts to the zone plate image.
>
>     Scale demo altered to default to GOOD and locked-together x+y scale
>
>     Fixed divide-by-zero from all-zero matrix found by stress-test
>
> v11: Whitespace and formatting fixes
>      Moved demo changes to a later patch
>
> Signed-off-by: Bill Spitzak <spitzak at gmail.com>
> ---
>  pixman/pixman-image.c | 323 +++++++++++++++++++++++++++++++++++++-------------
>  1 file changed, 241 insertions(+), 82 deletions(-)
>
> diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
> index 1ff1a49..92ed68b 100644
> --- a/pixman/pixman-image.c
> +++ b/pixman/pixman-image.c
> @@ -28,6 +28,7 @@
>  #include <stdio.h>
>  #include <string.h>
>  #include <assert.h>
> +#include <math.h>
>
>  #include "pixman-private.h"
>
> @@ -274,112 +275,270 @@ compute_image_info (pixman_image_t *image)
>                   FAST_PATH_X_UNIT_POSITIVE     |
>                   FAST_PATH_Y_UNIT_ZERO         |
>                   FAST_PATH_AFFINE_TRANSFORM);
> +       switch (image->common.filter)
> +       {
> +       case PIXMAN_FILTER_CONVOLUTION:
> +           break;
> +       case PIXMAN_FILTER_SEPARABLE_CONVOLUTION:
> +           flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
> +           break;
> +       default:
> +           flags |= (FAST_PATH_NEAREST_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +           break;
> +       }
>      }
>      else
>      {
> +       pixman_fixed_t (*m)[3] = image->common.transform->matrix;
> +       double dx, dy;
> +       int nearest_ok, bilinear_ok;
> +
>         flags |= FAST_PATH_HAS_TRANSFORM;
>
> -       if (image->common.transform->matrix[2][0] == 0                  &&
> -           image->common.transform->matrix[2][1] == 0                  &&
> -           image->common.transform->matrix[2][2] == pixman_fixed_1)
> -       {
> +       nearest_ok = FALSE;
> +       bilinear_ok = FALSE;
> +
> +       if (m[2][0] == 0                        &&
> +           m[2][1] == 0                        &&
> +           m[2][2] == pixman_fixed_1)
> +       { /* no perspective */

Err, please put comment in a new line, this is just plain ugly.

>             flags |= FAST_PATH_AFFINE_TRANSFORM;
>
> -           if (image->common.transform->matrix[0][1] == 0 &&
> -               image->common.transform->matrix[1][0] == 0)
> -           {
> -               if (image->common.transform->matrix[0][0] == -pixman_fixed_1 &&
> -                   image->common.transform->matrix[1][1] == -pixman_fixed_1)
> -               {
> -                   flags |= FAST_PATH_ROTATE_180_TRANSFORM;
> -               }
> +           if (m[0][1] == 0 &&
> +               m[1][0] == 0)
> +           { /* no tilt of either axis */
comment in new line please

>                 flags |= FAST_PATH_SCALE_TRANSFORM;
> +               if (abs(m[0][0]) == pixman_fixed_1 &&
> +                   abs(m[1][1]) == pixman_fixed_1)
> +               { /* no scaling */
comment in new line please

> +                   nearest_ok = TRUE;
> +                   if (m[0][0] < 0 && m[1][1] < 0)
> +                       flags |= FAST_PATH_ROTATE_180_TRANSFORM;
> +               }
>             }
> -           else if (image->common.transform->matrix[0][0] == 0 &&
> -                    image->common.transform->matrix[1][1] == 0)
> -           {
> -               pixman_fixed_t m01 = image->common.transform->matrix[0][1];
> -               pixman_fixed_t m10 = image->common.transform->matrix[1][0];
> -
> -               if (m01 == -pixman_fixed_1 && m10 == pixman_fixed_1)
> -                   flags |= FAST_PATH_ROTATE_90_TRANSFORM;
> -               else if (m01 == pixman_fixed_1 && m10 == -pixman_fixed_1)
> -                   flags |= FAST_PATH_ROTATE_270_TRANSFORM;
> +           else if (m[0][0] == 0 &&
> +                    m[1][1] == 0)
> +           { /* x/y axis are swapped, 90 degree rotation */
comment in new line please

> +               if (abs(m[0][1]) == pixman_fixed_1 &&
> +                   abs(m[1][0]) == pixman_fixed_1)
> +               { /* no scaling */
comment in new line please

> +                   nearest_ok = TRUE;
> +                   if (m[0][1] < 0 && m[1][0] > 0)
> +                       flags |= FAST_PATH_ROTATE_90_TRANSFORM;
> +                   else if (m[0][1] > 0 && m[1][0] < 0)
> +                       flags |= FAST_PATH_ROTATE_270_TRANSFORM;
> +               }
>             }
>         }
>
> -       if (image->common.transform->matrix[0][0] > 0)
> +       if (nearest_ok)
> +       {
> +           /* reject non-integer translation: */
> +           if (pixman_fixed_frac (m[0][2] | m[1][2]))
> +               nearest_ok = FALSE;
> +           /* FIXME: there are some affine-test failures, showing
> +            * that handling of BILINEAR and NEAREST filter is not
> +            * quite equivalent when getting close to 32K for the
> +            * translation components of the matrix. That's likely
> +            * some bug, but for now just skip BILINEAR->NEAREST
> +            * optimization in this case.
> +            */
> +           else if (abs(m[0][2] | m[1][2]) > pixman_int_to_fixed (30000))
> +               nearest_ok = FALSE;
> +       }
> +
> +       if (m[0][0] > 0)
>             flags |= FAST_PATH_X_UNIT_POSITIVE;
>
> -       if (image->common.transform->matrix[1][0] == 0)
> +       if (m[1][0] == 0)
>             flags |= FAST_PATH_Y_UNIT_ZERO;
> -    }
>
> -    /* Filter */
> -    switch (image->common.filter)
> -    {
> -    case PIXMAN_FILTER_NEAREST:
> -    case PIXMAN_FILTER_FAST:
> -       flags |= (FAST_PATH_NEAREST_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> -       break;
> +       switch (image->common.filter)
> +       {
> +       case PIXMAN_FILTER_NEAREST:
> +       case PIXMAN_FILTER_FAST:
> +           flags |= (FAST_PATH_NEAREST_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +           break;
>
> -    case PIXMAN_FILTER_BILINEAR:
> -    case PIXMAN_FILTER_GOOD:
> -    case PIXMAN_FILTER_BEST:
> -       flags |= (FAST_PATH_BILINEAR_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +       case PIXMAN_FILTER_BILINEAR:
> +           if (nearest_ok)
> +               flags |= (FAST_PATH_NEAREST_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +           else
> +               flags |= (FAST_PATH_BILINEAR_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +           break;
>
> -       /* Here we have a chance to optimize BILINEAR filter to NEAREST if
> -        * they are equivalent for the currently used transformation matrix.
> -        */
> -       if (flags & FAST_PATH_ID_TRANSFORM)
> -       {
> -           flags |= FAST_PATH_NEAREST_FILTER;
> -       }
> -       else if (
> -           /* affine and integer translation components in matrix ... */
> -           ((flags & FAST_PATH_AFFINE_TRANSFORM) &&
> -            !pixman_fixed_frac (image->common.transform->matrix[0][2] |
> -                                image->common.transform->matrix[1][2])) &&
> -           (
> -               /* ... combined with a simple rotation */
> -               (flags & (FAST_PATH_ROTATE_90_TRANSFORM |
> -                         FAST_PATH_ROTATE_180_TRANSFORM |
> -                         FAST_PATH_ROTATE_270_TRANSFORM)) ||
> -               /* ... or combined with a simple non-rotated translation */
> -               (image->common.transform->matrix[0][0] == pixman_fixed_1 &&
> -                image->common.transform->matrix[1][1] == pixman_fixed_1 &&
> -                image->common.transform->matrix[0][1] == 0 &&
> -                image->common.transform->matrix[1][0] == 0)
> -               )
> -           )
> -       {
> -           /* FIXME: there are some affine-test failures, showing that
> -            * handling of BILINEAR and NEAREST filter is not quite
> -            * equivalent when getting close to 32K for the translation
> -            * components of the matrix. That's likely some bug, but for
> -            * now just skip BILINEAR->NEAREST optimization in this case.
> +       case PIXMAN_FILTER_GOOD:
> +           if (nearest_ok)
> +           {
> +               flags |= (FAST_PATH_NEAREST_FILTER | FAST_PATH_NO_CONVOLUTION_FILTER);
> +               break;
> +           }
> +
> +           /* Compute filter sizes. This is the bounding box of a
> +            * diameter=1 circle transformed by the matrix. Scaling
> +            * down produces values greater than 1. See comment in
> +            * ../demos/scale.c for proof hypot is correct.
> +            *
> +            * For non-affine the circle is centered on one of the 4
> +            * points 1,1 away from the origin. Which one depends on
> +            * the signs of the values in the last row of the matrix,
> +            * chosen to avoid dividing by zero.
> +            */
> +           /* This division factor both accounts for the w component
> +            * and converts from fixed to float.
> +            */
> +           dy = abs(m[2][0]) + abs(m[2][1]) + abs(m[2][2]);
> +           if (dy)
> +               dy = 1.0 / dy;
> +           /* There are some signs that hypot is faster with numbers near 1
> +            * so the division is done first. Mathematically it should work
> +            * to divide afterwards.
> +            */
> +           dx = hypot (m[0][0] * dy, m[0][1] * dy);
> +           dy = hypot (m[1][0] * dy, m[1][1] * dy);
> +
> +           /* scale < 1/16 : BOX.BOX at size 16
> +            * scale < 3/4 : BOX.BOX at size 1/scale
> +            * larger : BOX.BOX at size 1
> +            *
> +            * If both directions have a scale >= 3/4 or a scale of
> +            * 1/2 and an integer translation, the faster
> +            * PIXMAN_FILTER_BILINEAR code is used.
> +            *
> +            * Filter size is clamped to 16 to prevent extreme slowness.
>              */
> -           pixman_fixed_t magic_limit = pixman_int_to_fixed (30000);
> -           if (image->common.transform->matrix[0][2] <= magic_limit  &&
> -               image->common.transform->matrix[1][2] <= magic_limit  &&
> -               image->common.transform->matrix[0][2] >= -magic_limit &&
> -               image->common.transform->matrix[1][2] >= -magic_limit)
> +           if (dx <= 4.0 / 3)
>             {
> -               flags |= FAST_PATH_NEAREST_FILTER;
> +               dx = 1.0;
> +               bilinear_ok = TRUE;
> +           }
> +           else if (dx > 16.0)
> +           {
> +               dx = 16.0;
> +           }
> +           else if (dx > 1.999 && dx < 2.001 &&
> +                    abs(m[0][0] * m[0][1]) < 4 &&
> +                    abs(pixman_fixed_frac(m[0][2]) < 2))
> +           {
> +               bilinear_ok = TRUE;
> +           }
I suggest an empty new line here to make it clear next if is not part
of previous if.

> +           if (dy <= 4.0 / 3)
> +           {
> +               dy = 1.0;
> +           }
> +           else if (dy > 16.0)
> +           {
> +               dy = 16.0;
> +               bilinear_ok = FALSE;
> +           }
> +           else if (bilinear_ok)
> +           {
> +               bilinear_ok =
> +                   (dy > 1.999 && dy < 2.001 &&
> +                    abs(m[1][0] * m[1][1]) < 4 &&
> +                    abs(pixman_fixed_frac(m[1][2]) < 2));
> +           }
I suggest an empty new line here to make it clear next if is not part
of previous if.

> +           if (bilinear_ok)
> +           {
> +               flags |= (FAST_PATH_BILINEAR_FILTER |
> +                         FAST_PATH_NO_CONVOLUTION_FILTER);
> +               break;
>             }
> -       }
> -       break;
>
> -    case PIXMAN_FILTER_CONVOLUTION:
> -       break;
> +           if (image->common.filter_params)
> +               free (image->common.filter_params);
> +
> +           image->common.filter_params =
> +               pixman_filter_create_separable_convolution
> +               ( & image->common.n_filter_params,
> +                 pixman_double_to_fixed(dx),
> +                 pixman_double_to_fixed(dy),
> +                 PIXMAN_KERNEL_BOX,
> +                 PIXMAN_KERNEL_BOX,
> +                 PIXMAN_KERNEL_BOX,
> +                 PIXMAN_KERNEL_BOX,
> +                 -12, -12);
> +
> +           flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
> +           break;
>
> -    case PIXMAN_FILTER_SEPARABLE_CONVOLUTION:
> -       flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
> -       break;
> +       case PIXMAN_FILTER_BEST:
> +           if (nearest_ok)
> +           {
> +               flags |= (FAST_PATH_NEAREST_FILTER |
> +                         FAST_PATH_NO_CONVOLUTION_FILTER);
> +               break;
> +           }
> +           /* See notes above about filter sizes */
> +           dy = abs(m[2][0]) + abs(m[2][1]) + abs(m[2][2]);
> +           if (dy) dy = 1.0 / dy;
put assignment on new line please

> +           dx = hypot (m[0][0] * dy, m[0][1] * dy);
> +           dy = hypot (m[1][0] * dy, m[1][1] * dy);
> +
> +           /* scale < 1/24 : BOX.BOX at size 24
> +            * scale < 1/16 : BOX.BOX at size 1/scale
> +            * scale < 1 : IMPULSE.LANCZOS2 at size 1/scale
> +            * scale < 2.333 : IMPULSE.LANCZOS2 at size 1
> +            * scale < 128 : BOX.LANCZOS2 at size 1/(scale-1)
> +            * larger : BOX.LANCZOS2 at size 1/127
> +            *
> +            * Filter switches to box and then clamps at 24 to prevent
> +            * extreme slowness.
> +            *
> +            * When enlarging this produces square pixels with an
> +            * anti-aliased border between them.  At scales larger
> +            * than 128x the antialias blur is increased to avoid
> +            * making lots of subsamples.
> +            */
> +           if (dx > 24.0)
> +               dx = 24.0;
if the else part has {} then the if part must have them as well

> +           else if (dx < 1.0)
> +           {
> +               if (dx >= 3.0/7)
> +                   dx = 1.0;
> +               else if (dx > 1.0/128)
> +                   dx /= 1.0 - dx;
> +               else
> +                   dx = 1.0/127;
> +           }
>
> -    default:
> -       flags |= FAST_PATH_NO_CONVOLUTION_FILTER;
> -       break;
> +           if (dy > 24.0)
> +               dy = 24.0;
if the else part has {} then the if part must have them as well

> +           else if (dy < 1.0)
> +           {
> +               if (dy >= 3.0/7)
> +                   dy = 1.0;
> +               else if (dy > 1.0/128)
> +                   dy /= 1.0 - dy;
> +               else
> +                   dy = 1.0/127;
> +           }
> +
> +           image->common.filter_params =
> +               pixman_filter_create_separable_convolution
> +               ( & image->common.n_filter_params,
> +                 pixman_double_to_fixed(dx),
> +                 pixman_double_to_fixed(dy),
> +                 dx >= 1.0 && dx < 16.0 ? PIXMAN_KERNEL_IMPULSE : PIXMAN_KERNEL_BOX,
> +                 dy >= 1.0 && dy < 16.0 ? PIXMAN_KERNEL_IMPULSE : PIXMAN_KERNEL_BOX,
> +                 dx < 16.0 ? PIXMAN_KERNEL_LANCZOS2 : PIXMAN_KERNEL_BOX,
> +                 dy < 16.0 ? PIXMAN_KERNEL_LANCZOS2 : PIXMAN_KERNEL_BOX,
> +                 -14, -14);
> +
> +           flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
> +           break;
> +
> +       case PIXMAN_FILTER_CONVOLUTION:
> +           break;
> +
> +       case PIXMAN_FILTER_SEPARABLE_CONVOLUTION:
> +           flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
> +           break;
> +
> +       default:
> +           flags |= FAST_PATH_NO_CONVOLUTION_FILTER;
> +           break;
> +       }
>      }
>
>      /* Repeat mode */
> --
> 1.9.1
>
> _______________________________________________
> Pixman mailing list
> Pixman at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/pixman


More information about the Pixman mailing list