[cairo] [PATCH pixman 3/3] Implement PIXMAN_FILTER_GOOD/BEST as separable convolutions

Bill Spitzak spitzak at gmail.com
Mon Aug 18 19:51:09 PDT 2014


GOOD uses the BOX filter, and uses BILINEAR for all scales > 1/1.35.

BEST uses the LANCZOS2 filter. The size is chosen to produce normal
filtering up to a scale of 2, and square pixels with only slight
blurry borders beyond that. I think it looks really nice.

Uses NEAREST instead of BILINEAR, GOOD, or BEST if possible. Including
reflections, which the previous code did not check for.

This works with either my new one or the older version of the filter
generator.
---
 pixman/pixman-image.c |  275 +++++++++++++++++++++++++++++++++++--------------
 1 file changed, 196 insertions(+), 79 deletions(-)

diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
index 1ff1a49..01a59a9 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,228 @@ 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 xsubsample, ysubsample;
+	int nearest_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;
+
+	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)
 	    {
-		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;
 		}
-		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)
 	    {
-		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)
-    {
-    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.
+	     *
+	     * 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.
 	     */
-	    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;
+	    dy = 1.0 / (abs(m[2][0]) + abs(m[2][1]) + abs(m[2][2]));
+	    /* 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);
+
+	    /* At scales above 1/1.35 this uses the bilinear filter.
+	     * This is identical to box at size 1, and I judged the
+	     * artifacts for the smaller scales to not be worse than
+	     * the box filter.
+	     *
+	     * Filters size is clamped to 16 to prevent extreme slowness.
+	     */
+	    if (dx <= 1.35) {
+		if (dy <= 1.35) {
+		    flags |= (FAST_PATH_BILINEAR_FILTER |
+			      FAST_PATH_NO_CONVOLUTION_FILTER);
+		    break;
+		}
+		dx = 1.0;
+	    } else if (dx > 16.0)
+		dx = 16.0;
+	    if (dy <= 1.35)
+		dy = 1.0;
+	    else if (dy > 16.0)
+		dy = 16.0;
+
+	    xsubsample = 0;
+	    while (dx * (1 << xsubsample) <= 128.0) xsubsample++;
+	    ysubsample = 0;
+	    while (dy * (1 << ysubsample) <= 128.0) ysubsample++;
+
+	    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,
+		  xsubsample, ysubsample);
+
+	    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 = 1.0 / (abs(m[2][0]) + abs(m[2][1]) + abs(m[2][2]));
+	    dx = hypot (m[0][0] * dy, m[0][1] * dy);
+	    dy = hypot (m[1][0] * dy, m[1][1] * dy);
+
+	    /* To prevent extreme slowness this switches to BOX at
+	     * 1/16 scale and stops making the filter larger at 1/24
+	     * scale.
+	     *
+	     * When enlarging this produces normal blur up to 2x, then
+	     * square pixels with a 1-pixel blurry border between them
+	     * for larger sizes.  At scales larger than 128x the blur
+	     * is increased to avoid making lots of subsamples.
+	     */
+	    if (dx > 24.0) dx = 24.0;
+	    else if (dx < 1.0) {
+		if (dx >= 0.5) dx = 1.0;
+		else if (dx > 1.0/128) dx = 1.0 / (1.0 / dx - 1.0);
+		else dx = 1.0/127;
+	    }
+	    if (dy > 24.0) dy = 24.0;
+	    else if (dy < 1.0) {
+		if (dy >= 0.5) dy = 1.0;
+		else if (dy > 1.0/128) dy = 1.0 / (1.0 / dy - 1.0);
+		else dy = 1.0/127;
 	    }
-	}
-	break;
 
-    case PIXMAN_FILTER_CONVOLUTION:
-	break;
+	    xsubsample = 0;
+	    while (dx * (1 << xsubsample) <= 128.0) xsubsample++;
+	    ysubsample = 0;
+	    while (dy * (1 << ysubsample) <= 128.0) ysubsample++;
+
+	    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 ? PIXMAN_KERNEL_BOX : PIXMAN_KERNEL_IMPULSE,
+		  dy < 1.0 ? PIXMAN_KERNEL_BOX : PIXMAN_KERNEL_IMPULSE,
+		  dx < 16.0 ? PIXMAN_KERNEL_LANCZOS2 : PIXMAN_KERNEL_BOX,
+		  dy < 16.0 ? PIXMAN_KERNEL_LANCZOS2 : PIXMAN_KERNEL_BOX,
+		  xsubsample, ysubsample);
+
+	    flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
+	    break;
 
-    case PIXMAN_FILTER_SEPARABLE_CONVOLUTION:
-	flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
-	break;
+	case PIXMAN_FILTER_CONVOLUTION:
+	    break;
 
-    default:
-	flags |= FAST_PATH_NO_CONVOLUTION_FILTER;
-	break;
+	case PIXMAN_FILTER_SEPARABLE_CONVOLUTION:
+	    flags |= FAST_PATH_SEPARABLE_CONVOLUTION_FILTER;
+	    break;
+
+	default:
+	    flags |= FAST_PATH_NO_CONVOLUTION_FILTER;
+	    break;
+	}
     }
 
     /* Repeat mode */
-- 
1.7.9.5



More information about the cairo mailing list