[Pixman] New separable filter generator
Bill Spitzak
spitzak at gmail.com
Wed Jun 18 11:50:43 PDT 2014
This patch is for Cairo but I now feel the correct solution is to place
this in pixman (and thus into XRender). Although the patch is for Cairo
it primarily consists of a replacement for pixman_generate_separable_filter
and changes to how it is called for the GOOD and BEST settings. I could
try to rewrite it as a pixman patch if desired.
Would appreciate any feedback at all on this. Thank you!
This code contains an all-new filter generator to replace the one that is
in pixman. Results in 222 pass/298 failed image tests, which is much better
than the previous versions of this patch.
Filter generator (which should probably be in pixman):
- Single filter, no "reconstruction" and "sample" filter
- Filters for derivative < 1 work
- Fixed IMPULSE and BOX
- Added TRIANGLE, CATMULL, NOTCH. Remove LANZCOS2.
- Renamed CUBIC to MITCHELL
Cairo's filter settings:
- CAIRO_FILTER_GOOD: uses BOX filter for scales less than .75 in either
direction. Uses PIXMAN_FILTER_GOOD (ie BILINEAR) otherwise.
- CAIRO_FILTER_BEST: uses CATMULL filter always. Upscaling more than 2x will
produce anti-aliased square pixels, similar to OS/X.
- CAIRO_FILTER_GAUSSIAN: this obsolete value is used to test other filters.
The program must declare and poke the filter into the static varialbe
ikernel. This should be removed for production code.
NYI: This version uses the fallback for xlib always. The xlib and xcb backends
must be rewritten to use the fallback version if filtering is needed. Or the
filtering code must be moved to XRender.
---
src/cairo-image-source.c | 435 +++++++++++++++++++++++++++++++++++++++++++++-
src/cairo-xlib-display.c | 2 +-
2 files changed, 432 insertions(+), 5 deletions(-)
diff --git a/src/cairo-image-source.c b/src/cairo-image-source.c
index c5bd228..aceb846 100644
--- a/src/cairo-image-source.c
+++ b/src/cairo-image-source.c
@@ -526,6 +526,379 @@ _pixel_to_solid (cairo_image_surface_t *image, int x, int y)
}
}
+/* ========================================================================== */
+/* This portion should probably be in pixman */
+
+/* Produce contribution of a filter of size r for pixel centered on x.
+ For a typical low-pass function this evaluates the function at x/r.
+ If the frequency is higher than 1/2, such as when r is less than 1,
+ this may need to integrate several samples, see cubic for examples.
+*/
+typedef double (* kernel_func_t) (double x, double r);
+
+/* Return maximum number of pixels that will be non-zero. Except for
+ impluse this is the maximum of 2 and the width of the non-zero part
+ of the filter rounded up to the next integer.
+*/
+typedef int (* kernel_width_func_t) (double r);
+
+/* Index into filter table */
+typedef enum
+{
+ KERNEL_IMPULSE,
+ KERNEL_BILINEAR,
+ KERNEL_BOX,
+ KERNEL_TRIANGLE,
+ KERNEL_CATMULL,
+ KERNEL_MITCHELL,
+ KERNEL_LANCZOS3,
+ KERNEL_NOTCH
+} kernel_t;
+
+/* Table of filters */
+typedef struct
+{
+ kernel_func_t func;
+ kernel_width_func_t width;
+ const char* name;
+} filter_info_t;
+
+/* Helper functions */
+static double _min(double a, double b) { return a < b ? a : b; }
+static double _max(double a, double b) { return a > b ? a : b; }
+
+/* IMPULSE: Returns pixel nearest the center. This matches
+ CAIRO_FILTER_NEAREST. This is useful if you wish to combine nearest
+ filter in one direction with another filter in the other.
+*/
+
+static double
+impulse_kernel (double x, double r)
+{
+ return x >= -0.5 && x < 0.5 ? 1.0 : 0.0;
+}
+
+static int
+impulse_width (double r)
+{
+ return 1;
+}
+
+/* BILINEAR: Weighted sum of the two pixels nearest the center, or a
+ triangle of width 2. This matches CAIRO_FILTER_BILINEAR. This is
+ useful if you wish to combine bilinear filter in one direction with
+ another filter in the other.
+
+ At r == 1 this is equal to BOX and TRIANGLE, allowing filters to be
+ changed at this point.
+*/
+
+static double
+bilinear_kernel (double x, double r)
+{
+ return _max(1.0 - fabs(x), 0.0);
+}
+
+static int
+bilinear_width (double r)
+{
+ return 2;
+}
+
+/* BOX: Intersection of a box of width r with square pixels. This is
+ the smallest possible filter such that the output image contains an
+ equal contribution from all the input pixels. Lots of software uses
+ this. The function is a trapazoid of width r+1, not a box.
+
+ At r == 1 this is equal to BILINEAR and TRIANGLE, allowing filters to be
+ changed at this point.
+*/
+
+static double
+box_kernel (double x, double r)
+{
+ return _max (0.0, _min (_min (r, 1.0),
+ _min ((r + 1) / 2 - x, (r + 1) / 2 + x)));
+}
+
+static int
+box_width (double r)
+{
+ return r < 1.0 ? 2 : ceil(r + 1);
+}
+
+/* TRIANGLE: Triangle of width 2r. Lots of software uses this as a
+ "better" filter, twice the size of a box but smaller than a cubic.
+
+ At r == 1 this is equal to BILINEAR and BOX, allowing filters to be
+ changed at this point.
+*/
+
+static double
+triangle_kernel (double x, double r)
+{
+ if (r < 1.0)
+ return box_kernel(x, r);
+ else
+ return _max (1.0 - fabs(x / r), 0.0);
+}
+
+static int
+triangle_width (double r)
+{
+ return r < 1.0 ? 2 : ceil(2 * r);
+}
+
+/* Cubic functions described in the Mitchell-Netravali paper.
+ http://mentallandscape.com/Papers_siggraph88.pdf. This describes
+ all possible cubic functions that can be used for sampling.
+*/
+
+static double
+general_cubic_i (double a, double B, double C)
+{
+ double ax = fabs(a);
+
+ if (ax < 1)
+ {
+ return (((12 - 9 * B - 6 * C) * ax +
+ (-18 + 12 * B + 6 * C)) * ax * ax
+ + (6 - 2 * B)) / 6;
+ }
+ else if (ax < 2)
+ {
+ return ((((-B - 6 * C) * ax +
+ (6 * B + 30 * C)) * ax +
+ (-12 * B - 48 * C)) * ax +
+ (8 * B + 24 * C)) / 6;
+ }
+ else
+ {
+ return 0.0;
+ }
+}
+
+static double
+general_cubic (double x, double r, double B, double C)
+{
+ if (r < 1.0)
+ return
+ general_cubic(x * 2 - .5, r * 2, B, C) +
+ general_cubic(x * 2 + .5, r * 2, B, C);
+ else
+ return
+ general_cubic_i(x / r, B, C);
+}
+
+static int
+cubic_width (double r)
+{
+ return _max(2.0, ceil (r * 4));
+}
+
+/* CATMULL: Catmull-Rom interpolation. Often called "cubic interpolation",
+ "b-spline", or just "cubic" by other software. This filter has
+ negative values so it can produce ringing and output pixels outside
+ the range of input pixels. This is very close to lanczos2 so there
+ is no reason to supply that as well.
+*/
+
+static double
+catmull_kernel (double x, double r)
+{
+ return general_cubic (x, r, 0.0, 0.5);
+}
+
+/* MITCHELL: Cubic recommended by the Mitchell-Netravali paper.
+ This has negative values and because the values at +/-1 are not
+ zero it does not interpolate the pixels, meaning it will change
+ an image even if there is no translation.
+
+ Note that Pixman calls this "CUBIC", which is misleading as almost
+ all other software uses the word "CUBIC" to mean an interpolating
+ function such as CATMULL.
+*/
+
+static double
+mitchell_kernel (double x, double r)
+{
+ return general_cubic (x, r, 1/3.0, 1/3.0);
+}
+
+/* NOTCH: Cubic recommended by the Mitchell-Netravali paper to
+ remove postaliasing artifacts. Note this does not remove aliasing
+ already present in the source image, though it may appear to due
+ to it's excessive blurriness. In any case this is more useful
+ than gaussian for image reconstruction.
+*/
+
+static double
+notch_kernel (double x, double r)
+{
+ return general_cubic (x, r, 1.5, -0.25);
+}
+
+/* LANCZOS3: lanczos windowed sinc function from -3 to +3. Very
+ popular with high-end software though I think any advantage over
+ cubics is hidden by quantization and programming mistakes. You
+ will see LANCZOS5 or even 7 sometimes.
+*/
+
+static double
+sinc (double x)
+{
+ return x ? sin (M_PI * x) / (M_PI * x) : 1.0;
+}
+
+static double
+lanczos (double x, int n)
+{
+ return fabs(x) < n ? sinc (x) * sinc (x * (1.0 / n)) : 0.0;
+}
+
+static double
+lanczos3_kernel (double x, double r)
+{
+ if (r < 1.0)
+ return
+ lanczos3_kernel(x * 2 - .5, r * 2) +
+ lanczos3_kernel(x * 2 + .5, r * 2);
+ else
+ return lanczos (x / r, 3);
+}
+
+static int
+lanczos3_width (double r)
+{
+ return _max(2.0, ceil (r * 6));
+}
+
+static const filter_info_t filters[] =
+{
+ { impulse_kernel, impulse_width, "IMPULSE" },
+ { bilinear_kernel, bilinear_width, "BILINEAR" },
+ { box_kernel, box_width, "BOX" },
+ { triangle_kernel, triangle_width, "TRIANGLE" },
+ { catmull_kernel, cubic_width, "CATMULL" },
+ { mitchell_kernel, cubic_width, "MITCHELL" },
+ { lanczos3_kernel, lanczos3_width, "LANCZOS3" },
+ { notch_kernel, cubic_width, "NOTCH" }
+};
+
+/* Returns the number of samples in filter array, computes width & subsample.
+ * Clip is maximum number of samples per filter, if the filter is larger
+ * only the center is calculated, this will approach a box of clip size
+ * as r gets larger.
+ */
+static int get_sizes(kernel_t filter, double r, int clip,
+ int* width, int* subsample)
+{
+ int s, w;
+ w = filters[filter].width(r);
+ if (w > clip) w = clip;
+ s = 0;
+ if (w > 1) /* no subsamples needed for impulse filter */
+ while (r * (1 << s) <= 128.0) s++;
+ *width = w;
+ *subsample = s;
+ return (1 << s) * w;
+}
+
+/* Fills in one dimension of the filter array */
+static void get_filter(kernel_t filter, double r, int width, int subsample,
+ pixman_fixed_t* out)
+{
+ int i;
+ pixman_fixed_t *p;
+ int n_phases;
+ double step;
+ kernel_func_t func;
+
+ p = out;
+ n_phases = 1 << subsample;
+ step = 1.0 / n_phases;
+ func = filters[filter].func;
+
+ /* special-case the impulse filter: */
+ if (width <= 1) {
+ for (i = 0; i < n_phases; ++i)
+ *p++ = pixman_fixed_1;
+ return;
+ }
+
+ for (i = 0; i < n_phases; ++i) {
+ double frac = (i + .5) * step;
+ /* Center of left-most pixel: */
+ double x1 = ceil (frac - width / 2.0 - 0.5) - frac + 0.5;
+ pixman_fixed_t new_total;
+ double total;
+ int j;
+
+ total = 0;
+ for (j = 0; j < width; ++j) {
+ double c = func(x1 + j, r);
+ total += c;
+ p[j] = (pixman_fixed_t)(c * 65536.0 + 0.5);
+ }
+
+ /* Normalize */
+ total = 1 / total;
+ new_total = 0;
+ for (j = 0; j < width; ++j) {
+ pixman_fixed_t t = p[j] = p[j] * total + 0.5;
+ new_total += t;
+ }
+
+ if (new_total != pixman_fixed_1)
+ p[width / 2] += (pixman_fixed_1 - new_total);
+ p += width;
+ }
+}
+
+
+/* Create the parameter list for a SEPARABLE_CONVOLUTION filter
+ * with the given kernels and scale parameters.
+ */
+static pixman_fixed_t *
+create_separable_convolution (int *n_values,
+ kernel_t xfilter,
+ double xr,
+ int xclip,
+ kernel_t yfilter,
+ double yr,
+ int yclip)
+{
+ int xwidth, xsubsample, ywidth, ysubsample;
+ int size_x = get_sizes(xfilter, xr, xclip, &xwidth, &xsubsample);
+ int size_y = get_sizes(yfilter, yr, yclip, &ywidth, &ysubsample);
+ pixman_fixed_t *params;
+
+ *n_values = 4 + size_x + size_y;
+ params = malloc (*n_values * sizeof (pixman_fixed_t));
+ if (!params) return 0;
+
+ params[0] = pixman_int_to_fixed (xwidth);
+ params[1] = pixman_int_to_fixed (ywidth);
+ params[2] = pixman_int_to_fixed (xsubsample);
+ params[3] = pixman_int_to_fixed (ysubsample);
+
+ get_filter(xfilter, xr, xwidth, xsubsample, params + 4);
+ get_filter(yfilter, yr, ywidth, ysubsample, params + 4 + size_x);
+
+ return params;
+}
+
+/* THIS IS FOR TESTING ONLY. Selects kernel used by "GAUSSIAN" */
+int ikernel = KERNEL_NOTCH;
+void inckernel(void)
+{
+ ikernel++;
+ if (ikernel > KERNEL_NOTCH) ikernel = KERNEL_IMPULSE;
+ printf("kernel is %s\n", filters[ikernel].name);
+}
+
+/* ========================================================================== */
+
static cairo_bool_t
_pixman_image_set_properties (pixman_image_t *pixman_image,
const cairo_pattern_t *pattern,
@@ -555,16 +928,58 @@ _pixman_image_set_properties (pixman_image_t *pixman_image,
else
{
pixman_filter_t pixman_filter;
+ kernel_t kernel;
+ double dx, dy;
+ int clip;
+
+ /* Compute scale factors from the pattern matrix. These scale
+ * factors are from user to pattern space, and as such they
+ * are greater than 1.0 for downscaling and less than 1.0 for
+ * upscaling. The factors are the size of an axis-aligned
+ * rectangle with the same area as the parallelgram a 1x1
+ * square transforms to.
+ */
+ dx = hypot (pattern->matrix.xx, pattern->matrix.xy);
+ dy = hypot (pattern->matrix.yx, pattern->matrix.yy);
+
+ /* Clip at maximum pixman_fixed number. Besides making it
+ * passable to pixman, this avoids errors from inf and nan.
+ */
+ if (! (dx < 0x7FFF)) dx = 0x7FFF;
+ if (! (dy < 0x7FFF)) dy = 0x7FFF;
switch (pattern->filter) {
case CAIRO_FILTER_FAST:
pixman_filter = PIXMAN_FILTER_FAST;
break;
case CAIRO_FILTER_GOOD:
+ default:
pixman_filter = PIXMAN_FILTER_GOOD;
+ if (dx > 1.35 || dy > 1.35) {
+ pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
+ kernel = KERNEL_BOX;
+ clip = 16; /* could be 256 if 2-pass filtering is done */
+ /* Match the bilinear filter for dimension scaling up: */
+ if (dx < 1.0) dx = 1.0;
+ if (dy < 1.0) dy = 1.0;
+ }
break;
case CAIRO_FILTER_BEST:
pixman_filter = PIXMAN_FILTER_BEST;
+ pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
+ kernel = KERNEL_CATMULL; /* LANCZOS3 is better but not much */
+ clip = 16;
+ /* blur up to 2x scale, then blend to square pixels for larger: */
+ if (dx < 1.0) {
+ if (dx < 1.0/128) dx = 1.0/128;
+ else if (dx < 0.5) dx = 1.0 / (1.0 / dx - 1.0);
+ else dx = 1.0;
+ }
+ if (dy < 1.0) {
+ if (dy < 1.0/128) dy = 1.0/128;
+ else if (dy < 0.5) dy = 1.0 / (1.0 / dy - 1.0);
+ else dy = 1.0;
+ }
break;
case CAIRO_FILTER_NEAREST:
pixman_filter = PIXMAN_FILTER_NEAREST;
@@ -577,12 +992,24 @@ _pixman_image_set_properties (pixman_image_t *pixman_image,
* whatsoever, so it was really a mistake to have it in the
* API. We could fix this by officially deprecating it, or
* else inventing semantics and providing an actual
- * implementation for it. */
- default:
- pixman_filter = PIXMAN_FILTER_BEST;
+ * implementation for it. For now used as a test of
+ * all the kernels. */
+ pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
+ kernel = (kernel_t)ikernel;
+ clip = 64; /* !! */
}
- pixman_image_set_filter (pixman_image, pixman_filter, NULL, 0);
+ if (pixman_filter == PIXMAN_FILTER_SEPARABLE_CONVOLUTION) {
+ int n_params;
+ pixman_fixed_t *params;
+ params = create_separable_convolution
+ (&n_params, kernel, dx, clip, kernel, dy, clip);
+ pixman_image_set_filter (pixman_image, pixman_filter,
+ params, n_params);
+ free (params);
+ } else {
+ pixman_image_set_filter (pixman_image, pixman_filter, NULL, 0);
+ }
}
{
diff --git a/src/cairo-xlib-display.c b/src/cairo-xlib-display.c
index c7708c5..a073d08 100644
--- a/src/cairo-xlib-display.c
+++ b/src/cairo-xlib-display.c
@@ -151,7 +151,7 @@ static const cairo_device_backend_t _cairo_xlib_device_backend = {
static void _cairo_xlib_display_select_compositor (cairo_xlib_display_t *display)
{
-#if 1
+#if 0
if (display->render_major > 0 || display->render_minor >= 4)
display->compositor = _cairo_xlib_traps_compositor_get ();
else if (display->render_major > 0 || display->render_minor >= 0)
--
1.7.9.5
More information about the Pixman
mailing list