[Pixman] [PATCH v10 15/15] pixman-image: Implement PIXMAN_FILTER_GOOD/BEST as separable convolutions

Bill Spitzak spitzak at gmail.com
Thu Feb 4 20:10:27 PST 2016


On 02/04/2016 05:42 AM, Oded Gabbay wrote:
> On Tue, Feb 2, 2016 at 8:28 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
>
> Let's separate pixman core changes and demo changes. It's bad for
> bisectability and maintainability.
>
> Do the core changes first, then another patch for the scale demo.
>
>>
>>      Fixed divide-by-zero from all-zero matrix found by stress-test
>>
>> Signed-off-by: Bill Spitzak <spitzak at gmail.com>
>> ---
>>   demos/scale.c         |  10 +-
>>   demos/scale.ui        |   1 +
>>   pixman/pixman-image.c | 289 ++++++++++++++++++++++++++++++++++++--------------
>>   3 files changed, 216 insertions(+), 84 deletions(-)
>>
>> diff --git a/demos/scale.c b/demos/scale.c
>> index 881004e..3df4442 100644
>> --- a/demos/scale.c
>> +++ b/demos/scale.c
>> @@ -340,7 +340,7 @@ on_expose (GtkWidget *da, GdkEvent *event, gpointer data)
>>
>>   static void
>>   set_up_combo_box (app_t *app, const char *box_name,
>> -                  int n_entries, const named_int_t table[])
>> +                  int n_entries, const named_int_t table[], int active)
>>   {
>>       GtkWidget *widget = get_widget (app, box_name);
>>       GtkListStore *model;
>> @@ -366,7 +366,7 @@ set_up_combo_box (app_t *app, const char *box_name,
>>          gtk_list_store_set (model, &iter, 0, info->name, -1);
>>       }
>>
>> -    gtk_combo_box_set_active (GTK_COMBO_BOX (widget), 0);
>> +    gtk_combo_box_set_active (GTK_COMBO_BOX (widget), active);
>>
>>       g_signal_connect (widget, "changed", G_CALLBACK (rescale), app);
>>   }
>> @@ -374,7 +374,7 @@ set_up_combo_box (app_t *app, const char *box_name,
>>   static void
>>   set_up_filter_box (app_t *app, const char *box_name)
>>   {
>> -    set_up_combo_box (app, box_name, G_N_ELEMENTS (filters), filters);
>> +    set_up_combo_box (app, box_name, G_N_ELEMENTS (filters), filters, 0);
>>   }
>>
>>   static char *
>> @@ -422,14 +422,14 @@ app_new (pixman_image_t *original)
>>       widget = get_widget (app, "drawing_area");
>>       g_signal_connect (widget, "expose_event", G_CALLBACK (on_expose), app);
>>
>> -    set_up_combo_box (app, "filter_combo_box", G_N_ELEMENTS (filter_types), filter_types);
>> +    set_up_combo_box (app, "filter_combo_box", G_N_ELEMENTS (filter_types), filter_types, 3);
>>       set_up_filter_box (app, "reconstruct_x_combo_box");
>>       set_up_filter_box (app, "reconstruct_y_combo_box");
>>       set_up_filter_box (app, "sample_x_combo_box");
>>       set_up_filter_box (app, "sample_y_combo_box");
>>
>>       set_up_combo_box (
>> -        app, "repeat_combo_box", G_N_ELEMENTS (repeats), repeats);
>> +       app, "repeat_combo_box", G_N_ELEMENTS (repeats), repeats, 0);
>>
>>       g_signal_connect (
>>          gtk_builder_get_object (app->builder, "lock_checkbutton"),
>> diff --git a/demos/scale.ui b/demos/scale.ui
>> index 1e77f56..13e0e0d 100644
>> --- a/demos/scale.ui
>> +++ b/demos/scale.ui
>> @@ -177,6 +177,7 @@
>>                            id="lock_checkbutton">
>>                      <property name="label" translatable="yes">Lock X and Y Dimensions</property>
>>                      <property name="xalign">0.0</property>
>> +                   <property name="active">True</property>
>>                    </object>
>>                     <packing>
>>                       <property name="expand">False</property>
>> diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
>> index 1ff1a49..c381260 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,242 @@ 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;
>
> Again, here you have mixup of spaces and tabs using same indentation.
> Please fix this (and all other occurrences if there are any).

My mistake I did not fix my editor to use tabs.
>
>> +
>>          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)
>>          {
>>              flags |= FAST_PATH_AFFINE_TRANSFORM;
>>
>> -           if (image->common.transform->matrix[0][1] == 0 &&
>> -               image->common.transform->matrix[1][0] == 0)
>> +           if (m[0][1] == 0 && m[1][0] == 0)
> I don't mind using m instead of the long string, but please put them
> one below the other (as the original code did) so it would be
> immediately clear what we are comparing.

Will try to fix all of these.
>
>>              {
>> -               if (image->common.transform->matrix[0][0] == -pixman_fixed_1 &&
>> -                   image->common.transform->matrix[1][1] == -pixman_fixed_1)
>> +               flags |= FAST_PATH_SCALE_TRANSFORM;
>> +               if (abs(m[0][0]) == pixman_fixed_1 &&
>> +                   abs(m[1][1]) == pixman_fixed_1)
>>                  {
>> -                   flags |= FAST_PATH_ROTATE_180_TRANSFORM;
>> +                   nearest_ok = TRUE;
>> +                   if (m[0][0] < 0 && m[1][1] < 0)
>> +                       flags |= FAST_PATH_ROTATE_180_TRANSFORM;
>
> This is the same as the original code.
> if m[0][0] == 1 and m[1][1] == 1, then in the original code the
> condition equals false, but in your code it equals true. I guess this
> is because you want to mark nearest_ok as TRUE in both cases ?
> Could you please elaborate more what the new logic here does and why
> it changed ?

The change was so that any arrangement of ±1 turned on nearest_ok.

If both are -1 it turns on FAST_PATH_ROTATE_180_TRANSFORM as well. The 
earlier code only did this.
>
>
>>                  }
>> -               flags |= FAST_PATH_SCALE_TRANSFORM;
>>              }
>> -           else if (image->common.transform->matrix[0][0] == 0 &&
>> -                    image->common.transform->matrix[1][1] == 0)
>> +           else if (m[0][0] == 0 && m[1][1] == 0)
> Please put the conditions one below the other for readability

I will try to fix all of these.
>
>>              {
>> -               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;
>> +               if (abs(m[0][1]) == pixman_fixed_1 &&
>> +                   abs(m[1][0]) == pixman_fixed_1)
>> +               {
>> +                   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)
> Why did you put this entire switch statement inside the else section ?
> In the original code it was executed regardless of the result of the
> previous if.

This code is not used if there is no transform, because 
FAST_PATH_NEAREST_FILTER is turned on, so the filter choice is not needed.

>
>> -    {
>> -    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.
>>               */
>> -           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)
>> -           {
>> -               flags |= FAST_PATH_NEAREST_FILTER;
>> +           /* 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;
> Don't put assignment at the same line of the if statement
>
>> +           /* 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.
>> +            */
>> +           if (dx <= 4.0 / 3) {
>> +               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;
>> +           if (dy <= 4.0 / 3)
>> +               dy = 1.0;
>> +           else if (dy > 16.0) {
>> +               dy = 16.0;
>> +               bilinear_ok = FALSE;
>> +           } else if (bilinear_ok) {
>> +               if (dy > 1.999 && dy < 2.001 &&
>> +                   abs(m[1][0] * m[1][1]) < 4 &&
>> +                   abs(pixman_fixed_frac(m[1][2]) < 2))
>> +                   ;
>> +               else bilinear_ok = FALSE;
>> +           }
>> +           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;
> Don't put assignment at the same line of the if statement
>
>> +           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;
> Don't put assignment at the same line of the if statement
>
>> +           else if (dx >= 1.0) ;
> Don't write like this please. Add this as upper limit for next statement

It's a little trickier than that because it effects all later if 
statements, but it can be done by nesting them.

>
>> +            else if (dx >= 3.0/7) dx = 1.0;
> Don't put assignment at the same line of the if statement
>
>> +            else if (dx > 1.0/128) dx /= 1.0 - dx;
> Don't put assignment at the same line of the if statement
>
>> +            else dx = 1.0/127;
> Don't put assignment at the same line of the if statement
>
>> +
>> +           if (dy > 24.0) dy = 24.0;
> Don't put assignment at the same line of the if statement
>
>> +           else if (dy >= 1.0) ;
> Don't write like this please. Add this as upper limit for next statement
>
>> +            else if (dy >= 3.0/7) dy = 1.0;
> Don't put assignment at the same line of the if statement
>
>> +            else if (dy > 1.0/128) dy /= 1.0 - dy;
> Don't put assignment at the same line of the if statement
>
>> +            else dy = 1.0/127;
> Don't put assignment at the same line of the if statement
>
>> +
>> +           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;
>>
>> -    default:
>> -       flags |= FAST_PATH_NO_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