[Pixman] [PATCH v10 15/15] pixman-image: Implement PIXMAN_FILTER_GOOD/BEST as separable convolutions
Oded Gabbay
oded.gabbay at gmail.com
Thu Feb 4 05:42:43 PST 2016
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).
> +
> 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.
> {
> - 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 ?
> }
> - 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
> {
> - 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.
> - {
> - 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
> + 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