pixman: Branch 'master' - 15 commits
Søren Sandmann Pedersen
sandmann at kemper.freedesktop.org
Sat Sep 3 19:01:28 UTC 2016
configure.ac | 13 ++
demos/scale.c | 143 ++++++++++++++++---------
demos/scale.ui | 42 +++++--
pixman/pixman-fast-path.c | 4
pixman/pixman-filter.c | 244 ++++++++++++++++++++++++++++++++-----------
pixman/pixman-image.c | 66 ++++++-----
pixman/rounding.txt | 1
test/Makefile.sources | 1
test/filter-reduction-test.c | 112 +++++++++++++++++++
9 files changed, 476 insertions(+), 150 deletions(-)
New commits:
commit 17c4ce2e393af597db3c04295c21afc7ce34aa22
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:15 2016 -0700
pixman-filter: Made Gaussian a bit wider
Expanded the size slightly (from ~4.25 to 5) to make the cutoff less
noticable. Previouly the value at the cutoff was
gaussian_filter(sqrt(2)*3/2) = 0.00626 which is larger than the
difference between 8-bit pixels (1/255 = 0.003921). New cutoff is
gaussian_filter(2.5) = 0.001089 which is smaller.
v11: added some math to commit message
v14: left SIGMA in there
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Acked-by: Oded Gabbay <oded.gabbay at gmail.com>
Reviewed-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index 3318893..5f3b752 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -143,7 +143,7 @@ static const filter_info_t filters[] =
{ PIXMAN_KERNEL_BOX, box_kernel, 1.0 },
{ PIXMAN_KERNEL_LINEAR, linear_kernel, 2.0 },
{ PIXMAN_KERNEL_CUBIC, cubic_kernel, 4.0 },
- { PIXMAN_KERNEL_GAUSSIAN, gaussian_kernel, 6 * SIGMA },
+ { PIXMAN_KERNEL_GAUSSIAN, gaussian_kernel, 5.0 },
{ PIXMAN_KERNEL_LANCZOS2, lanczos2_kernel, 4.0 },
{ PIXMAN_KERNEL_LANCZOS3, lanczos3_kernel, 6.0 },
{ PIXMAN_KERNEL_LANCZOS3_STRETCHED, nice_kernel, 8.0 },
commit d286078b28bdef15aa0498e6e7ec7da68a42bfeb
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:14 2016 -0700
pixman-filter: Nested polynomial for cubic
v11: Restored range checks
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index ee58045..3318893 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -109,14 +109,16 @@ general_cubic (double x, double B, double C)
if (ax < 1)
{
- return ((12 - 9 * B - 6 * C) * ax * ax * ax +
- (-18 + 12 * B + 6 * C) * ax * ax + (6 - 2 * B)) / 6;
+ return (((12 - 9 * B - 6 * C) * ax +
+ (-18 + 12 * B + 6 * C)) * ax * ax +
+ (6 - 2 * B)) / 6;
}
- else if (ax >= 1 && ax < 2)
+ else if (ax < 2)
{
- return ((-B - 6 * C) * ax * ax * ax +
- (6 * B + 30 * C) * ax * ax + (-12 * B - 48 * C) *
- ax + (8 * B + 24 * C)) / 6;
+ return ((((-B - 6 * C) * ax +
+ (6 * B + 30 * C)) * ax +
+ (-12 * B - 48 * C)) * ax +
+ (8 * B + 24 * C)) / 6;
}
else
{
commit 133142449b22fc2799d922479514e677ae91f0f5
Author: Søren Sandmann Pedersen <soren.sandmann at gmail.com>
Date: Fri Apr 8 22:32:30 2016 -0400
pixman-filter: Fix several issues related to normalization
There are a few bugs in the current normalization code
(1) The normalization is based on the sum of the *floating point*
values generated by integral(). But in order to get the sum to be
close to pixman_fixed_1, the sum of the rounded fixed point values
should be used.
(2) The multiplications in the normalization loops often round the
same way, so the residual error can fairly large.
(3) The residual error is added to the sample located at index
(width - width / 2), which is not the midpoint for odd widths (and
for width 1 is in fact outside the array).
This patch fixes these issues by (1) using the sum of the fixed point
values as the total to divide by, (2) doing error diffusion in the
normalization loop, and (3) putting any residual error (which is now
guaranteed to be less than pixman_fixed_e) at the first sample, which
is the only one that didn't get any error diffused into it.
Signed-off-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index 11e7d0e..ee58045 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -247,7 +247,7 @@ create_1d_filter (int width,
double frac = step / 2.0 + i * step;
pixman_fixed_t new_total;
int x, x1, x2;
- double total;
+ double total, e;
/* Sample convolution of reconstruction and sampling
* filter. See rounding.txt regarding the rounding
@@ -278,24 +278,31 @@ create_1d_filter (int width,
ihigh - ilow);
}
- total += c;
- *p++ = (pixman_fixed_t)(c * 65536.0 + 0.5);
+ *p = (pixman_fixed_t)floor (c * 65536.0 + 0.5);
+ total += *p;
+ p++;
}
- /* Normalize */
+ /* Normalize, with error diffusion */
p -= width;
- total = 1 / total;
+ total = 65536.0 / total;
new_total = 0;
+ e = 0.0;
for (x = x1; x < x2; ++x)
{
- pixman_fixed_t t = (*p) * total + 0.5;
+ double v = (*p) * total + e;
+ pixman_fixed_t t = floor (v + 0.5);
+ e = v - t;
new_total += t;
*p++ = t;
}
- if (new_total != pixman_fixed_1)
- *(p - width / 2) += (pixman_fixed_1 - new_total);
+ /* pixman_fixed_e's worth of error may remain; put it
+ * at the first sample, since that is the only one that
+ * hasn't had any error diffused into it.
+ */
+ *(p - width) += pixman_fixed_1 - new_total;
}
}
commit 3b46fce6fec566e93a8a6b90df113272d203aafc
Author: Søren Sandmann Pedersen <soren.sandmann at gmail.com>
Date: Tue Aug 30 22:03:12 2016 -0700
pixman-filter: Speed up BOX/BOX filter
The convolution of two BOX filters is simply the length of the
interval where both are non-zero, so we can simply return width from
the integral() function because the integration region has already
been restricted to be such that both functions are non-zero on it.
This is both faster and more accurate than doing numerical integration.
This patch is based on one by Bill Spitzak
https://lists.freedesktop.org/archives/pixman/2016-March/004446.html
with these changes:
- Rebased to not assume any changes in the arguments to integral().
- Dropped the multiplication by scale
- Added more details in the commit message.
Signed-off-by: Søren Sandmann <soren.sandmann at gmail.com>
Reviewed-by: Bill Spitzak <spitzak at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index 878cf9d..11e7d0e 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -160,11 +160,15 @@ integral (pixman_kernel_t kernel1, double x1,
pixman_kernel_t kernel2, double scale, double x2,
double width)
{
+ if (kernel1 == PIXMAN_KERNEL_BOX && kernel2 == PIXMAN_KERNEL_BOX)
+ {
+ return width;
+ }
/* The LINEAR filter is not differentiable at 0, so if the
* integration interval crosses zero, break it into two
* separate integrals.
*/
- if (kernel1 == PIXMAN_KERNEL_LINEAR && x1 < 0 && x1 + width > 0)
+ else if (kernel1 == PIXMAN_KERNEL_LINEAR && x1 < 0 && x1 + width > 0)
{
return
integral (kernel1, x1, kernel2, scale, x2, - x1) +
commit 8855b3a2a231ab348c02c0d92f0051b079eabfa3
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:11 2016 -0700
pixman-filter: integral splitting is only needed for triangle filter
Only the triangle is discontinuous at 0. The other filters resemble a
cubic closely enough that Simpsons integration works without
splitting.
Changes by Søren: Rebase without the changes to the integral function,
update comment to match the new code.
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Signed-off-by: Søren Sandmann <soren.sandmann at gmail.com>
Reviewed-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index ecff852..878cf9d 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -160,18 +160,17 @@ integral (pixman_kernel_t kernel1, double x1,
pixman_kernel_t kernel2, double scale, double x2,
double width)
{
- /* If the integration interval crosses zero, break it into
- * two separate integrals. This ensures that filters such
- * as LINEAR that are not differentiable at 0 will still
- * integrate properly.
+ /* The LINEAR filter is not differentiable at 0, so if the
+ * integration interval crosses zero, break it into two
+ * separate integrals.
*/
- if (x1 < 0 && x1 + width > 0)
+ if (kernel1 == PIXMAN_KERNEL_LINEAR && x1 < 0 && x1 + width > 0)
{
return
integral (kernel1, x1, kernel2, scale, x2, - x1) +
integral (kernel1, 0, kernel2, scale, x2 - x1, width + x1);
}
- else if (x2 < 0 && x2 + width > 0)
+ else if (kernel2 == PIXMAN_KERNEL_LINEAR && x2 < 0 && x2 + width > 0)
{
return
integral (kernel1, x1, kernel2, scale, x2, - x2) +
commit 6ae281fbb7a02b94a3900b6677a51cdd28096ed7
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:10 2016 -0700
pixman-filter: Correct Simpsons integration
Simpsons uses cubic curve fitting, with 3 samples defining each
cubic. This makes the weights of the samples be in a pattern of
1,4,2,4,2...4,1, and then dividing the result by 3.
The previous code was using weights of 1,2,0,6,0,6...,2,1.
With this fix the integration is accurate enough that the number of
samples could be reduced a lot. Multiples of 12 seem to work best.
v7: Merged with patch to reduce from 128 samples to 16
v9: Changed samples from 16 to 12
v10: Fixed rebase error that made it not compile
v11: minor whitespace change
v14: more whitespace changes
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>
Reviewed-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index c018a67..ecff852 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -189,13 +189,19 @@ integral (pixman_kernel_t kernel1, double x1,
}
else
{
- /* Integration via Simpson's rule */
-#define N_SEGMENTS 128
+ /* Integration via Simpson's rule
+ * See http://www.intmath.com/integration/6-simpsons-rule.php
+ * 12 segments (6 cubic approximations) seems to produce best
+ * result for lanczos3.linear, which was the combination that
+ * showed the most errors. This makes sense as the lanczos3
+ * filter is 6 wide.
+ */
+#define N_SEGMENTS 12
#define SAMPLE(a1, a2) \
(filters[kernel1].func ((a1)) * filters[kernel2].func ((a2) * scale))
double s = 0.0;
- double h = width / (double)N_SEGMENTS;
+ double h = width / N_SEGMENTS;
int i;
s = SAMPLE (x1, x2);
@@ -204,11 +210,14 @@ integral (pixman_kernel_t kernel1, double x1,
{
double a1 = x1 + h * i;
double a2 = x2 + h * i;
+ s += 4 * SAMPLE (a1, a2);
+ }
+ for (i = 2; i < N_SEGMENTS; i += 2)
+ {
+ double a1 = x1 + h * i;
+ double a2 = x2 + h * i;
s += 2 * SAMPLE (a1, a2);
-
- if (i >= 2 && i < N_SEGMENTS - 1)
- s += 4 * SAMPLE (a1, a2);
}
s += SAMPLE (x1 + width, x2 + width);
commit 6acaf2bcb1246529143c112dbce6dd9d6f7cb51e
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:09 2016 -0700
pixman-filter: reduce amount of malloc/free/memcpy to generate filter
Rearranged so that the entire block of memory for the filter pair
is allocated first, and then filled in. Previous version allocated
and freed two temporary buffers for each filter and did an extra
memcpy.
v8: small refactor to remove the filter_width function
v10: Restored filter_width function but with arguments changed to
match later patches
v11: Removed unused arg and pointer from filter_width function
Whitespace fixes.
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>
Acked-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index aa7bb80..c018a67 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -217,25 +217,17 @@ integral (pixman_kernel_t kernel1, double x1,
}
}
-static pixman_fixed_t *
-create_1d_filter (int *width,
+static void
+create_1d_filter (int width,
pixman_kernel_t reconstruct,
pixman_kernel_t sample,
double scale,
- int n_phases)
+ int n_phases,
+ pixman_fixed_t *p)
{
- pixman_fixed_t *params, *p;
double step;
- double size;
int i;
- size = scale * filters[sample].width + filters[reconstruct].width;
- *width = ceil (size);
-
- p = params = malloc (*width * n_phases * sizeof (pixman_fixed_t));
- if (!params)
- return NULL;
-
step = 1.0 / n_phases;
for (i = 0; i < n_phases; ++i)
@@ -250,8 +242,8 @@ create_1d_filter (int *width,
* and sample positions.
*/
- x1 = ceil (frac - *width / 2.0 - 0.5);
- x2 = x1 + *width;
+ x1 = ceil (frac - width / 2.0 - 0.5);
+ x2 = x1 + width;
total = 0;
for (x = x1; x < x2; ++x)
@@ -279,7 +271,7 @@ create_1d_filter (int *width,
}
/* Normalize */
- p -= *width;
+ p -= width;
total = 1 / total;
new_total = 0;
for (x = x1; x < x2; ++x)
@@ -291,10 +283,15 @@ create_1d_filter (int *width,
}
if (new_total != pixman_fixed_1)
- *(p - *width / 2) += (pixman_fixed_1 - new_total);
+ *(p - width / 2) += (pixman_fixed_1 - new_total);
}
+}
- return params;
+
+static int
+filter_width (pixman_kernel_t reconstruct, pixman_kernel_t sample, double size)
+{
+ return ceil (filters[reconstruct].width + size * filters[sample].width);
}
#ifdef PIXMAN_GNUPLOT
@@ -426,38 +423,31 @@ pixman_filter_create_separable_convolution (int *n_values,
{
double sx = fabs (pixman_fixed_to_double (scale_x));
double sy = fabs (pixman_fixed_to_double (scale_y));
- pixman_fixed_t *horz = NULL, *vert = NULL, *params = NULL;
+ pixman_fixed_t *params;
int subsample_x, subsample_y;
int width, height;
+ width = filter_width (reconstruct_x, sample_x, sx);
subsample_x = (1 << subsample_bits_x);
- subsample_y = (1 << subsample_bits_y);
- horz = create_1d_filter (&width, reconstruct_x, sample_x, sx, subsample_x);
- vert = create_1d_filter (&height, reconstruct_y, sample_y, sy, subsample_y);
+ height = filter_width (reconstruct_y, sample_y, sy);
+ subsample_y = (1 << subsample_bits_y);
- if (!horz || !vert)
- goto out;
-
*n_values = 4 + width * subsample_x + height * subsample_y;
params = malloc (*n_values * sizeof (pixman_fixed_t));
if (!params)
- goto out;
+ return NULL;
params[0] = pixman_int_to_fixed (width);
params[1] = pixman_int_to_fixed (height);
params[2] = pixman_int_to_fixed (subsample_bits_x);
params[3] = pixman_int_to_fixed (subsample_bits_y);
- memcpy (params + 4, horz,
- width * subsample_x * sizeof (pixman_fixed_t));
- memcpy (params + 4 + width * subsample_x, vert,
- height * subsample_y * sizeof (pixman_fixed_t));
-
-out:
- free (horz);
- free (vert);
+ create_1d_filter (width, reconstruct_x, sample_x, sx, subsample_x,
+ params + 4);
+ create_1d_filter (height, reconstruct_y, sample_y, sy, subsample_y,
+ params + 4 + width * subsample_x);
#ifdef PIXMAN_GNUPLOT
gnuplot_filter(width, subsample_x, params + 4);
commit d0e6c9f4f65e429058b97d2f947b048b445c17c4
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:08 2016 -0700
pixman-image: Added enable-gnuplot config to view filters in gnuplot
If enable-gnuplot is configured, then you can pipe the output of a
pixman-using program to gnuplot and get a continuously-updated plot of
the horizontal filter. This works well with demos/scale to test the
filter generation.
The plot is all the different subposition filters shuffled
together. This is misleading in a few cases:
IMPULSE.BOX - goes up and down as the subfilters have different
numbers of non-zero samples
IMPULSE.TRIANGLE - somewhat crooked for the same reason
1-wide filters - looks triangular, but a 1-wide box would be more
accurate
Changes by Søren: Rewrote the pixman-filter.c part to
- make it generate correct coordinates
- add a comment on how coordinates are generated
- in rounding.txt, add a ceil() variant of the first-sample
formula
- make the gnuplot output slightly prettier
v7: First time this ability was included
v8: Use config option
Moved code to the filter generator
Modified scale demo to not call filter generator a second time.
v10: Only print if successful generation of plots
Use #ifdef, not #if
v11: small whitespace fixes
v12: output range from -width/2 to width/2 and include y==0, to avoid misleading plots
for subsample_bits==0 and for box filters which may have no small values.
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
diff --git a/configure.ac b/configure.ac
index 6b2134e..e833e45 100644
--- a/configure.ac
+++ b/configure.ac
@@ -834,6 +834,19 @@ fi
AC_SUBST(PIXMAN_TIMERS)
dnl ===================================
+dnl gnuplot
+
+AC_ARG_ENABLE(gnuplot,
+ [AC_HELP_STRING([--enable-gnuplot],
+ [enable output of filters that can be piped to gnuplot [default=no]])],
+ [enable_gnuplot=$enableval], [enable_gnuplot=no])
+
+if test $enable_gnuplot = yes ; then
+ AC_DEFINE(PIXMAN_GNUPLOT, 1, [enable output that can be piped to gnuplot])
+fi
+AC_SUBST(PIXMAN_GNUPLOT)
+
+dnl ===================================
dnl GTK+
AC_ARG_ENABLE(gtk,
diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index b2bf53f..aa7bb80 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -297,6 +297,119 @@ create_1d_filter (int *width,
return params;
}
+#ifdef PIXMAN_GNUPLOT
+
+/* If enable-gnuplot is configured, then you can pipe the output of a
+ * pixman-using program to gnuplot and get a continuously-updated plot
+ * of the horizontal filter. This works well with demos/scale to test
+ * the filter generation.
+ *
+ * The plot is all the different subposition filters shuffled
+ * together. This is misleading in a few cases:
+ *
+ * IMPULSE.BOX - goes up and down as the subfilters have different
+ * numbers of non-zero samples
+ * IMPULSE.TRIANGLE - somewhat crooked for the same reason
+ * 1-wide filters - looks triangular, but a 1-wide box would be more
+ * accurate
+ */
+static void
+gnuplot_filter (int width, int n_phases, const pixman_fixed_t* p)
+{
+ double step;
+ int i, j;
+ int first;
+
+ step = 1.0 / n_phases;
+
+ printf ("set style line 1 lc rgb '#0060ad' lt 1 lw 0.5 pt 7 pi 1 ps 0.5\n");
+ printf ("plot [x=%g:%g] '-' with linespoints ls 1\n", -width*0.5, width*0.5);
+ /* Print a point at the origin so that y==0 line is included: */
+ printf ("0 0\n\n");
+
+ /* The position of the first sample of the phase corresponding to
+ * frac is given by:
+ *
+ * ceil (frac - width / 2.0 - 0.5) + 0.5 - frac
+ *
+ * We have to find the frac that minimizes this expression.
+ *
+ * For odd widths, we have
+ *
+ * ceil (frac - width / 2.0 - 0.5) + 0.5 - frac
+ * = ceil (frac) + K - frac
+ * = 1 + K - frac
+ *
+ * for some K, so this is minimized when frac is maximized and
+ * strictly growing with frac. So for odd widths, we can simply
+ * start at the last phase and go backwards.
+ *
+ * For even widths, we have
+ *
+ * ceil (frac - width / 2.0 - 0.5) + 0.5 - frac
+ * = ceil (frac - 0.5) + K - frac
+ *
+ * The graph for this function (ignoring K) looks like this:
+ *
+ * 0.5
+ * | |\
+ * | | \
+ * | | \
+ * 0 | | \
+ * |\ |
+ * | \ |
+ * | \ |
+ * -0.5 | \|
+ * ---------------------------------
+ * 0 0.5 1
+ *
+ * So in this case we need to start with the phase whose frac is
+ * less than, but as close as possible to 0.5, then go backwards
+ * until we hit the first phase, then wrap around to the last
+ * phase and continue backwards.
+ *
+ * Which phase is as close as possible 0.5? The locations of the
+ * sampling point corresponding to the kth phase is given by
+ * 1/(2 * n_phases) + k / n_phases:
+ *
+ * 1/(2 * n_phases) + k / n_phases = 0.5
+ *
+ * from which it follows that
+ *
+ * k = (n_phases - 1) / 2
+ *
+ * rounded down is the phase in question.
+ */
+ if (width & 1)
+ first = n_phases - 1;
+ else
+ first = (n_phases - 1) / 2;
+
+ for (j = 0; j < width; ++j)
+ {
+ for (i = 0; i < n_phases; ++i)
+ {
+ int phase = first - i;
+ double frac, pos;
+
+ if (phase < 0)
+ phase = n_phases + phase;
+
+ frac = step / 2.0 + phase * step;
+ pos = ceil (frac - width / 2.0 - 0.5) + 0.5 - frac + j;
+
+ printf ("%g %g\n",
+ pos,
+ pixman_fixed_to_double (*(p + phase * width + j)));
+ }
+ }
+
+ printf ("e\n");
+ fflush (stdout);
+}
+
+#endif
+
/* Create the parameter list for a SEPARABLE_CONVOLUTION filter
* with the given kernels and scale parameters
*/
@@ -346,5 +459,9 @@ out:
free (horz);
free (vert);
+#ifdef PIXMAN_GNUPLOT
+ gnuplot_filter(width, subsample_x, params + 4);
+#endif
+
return params;
}
diff --git a/pixman/rounding.txt b/pixman/rounding.txt
index b52b084..1c00019 100644
--- a/pixman/rounding.txt
+++ b/pixman/rounding.txt
@@ -160,6 +160,7 @@ which means the contents of the matrix corresponding to (frac) should
contain width samplings of the function, with the first sample at:
floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac
+ = ceil (frac - width / 2.0 - 0.5) + 0.5 - frac
This filter is called separable because each of the k x k convolution
matrices is specified with two k-wide vectors, one for each dimension,
commit 375f5ec5c5d2a6cc3586f57e36fdf08a3d0ac4e4
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:07 2016 -0700
demos/scale: Added pulldown to choose PIXMAN_FILTER_* value
This is very useful for comparing the results of SEPARABLE_CONVOLUTION
with BILINEAR and NEAREST.
v14: Removed good/best items
v15: Skip filter generation so gnuplot output continues showing previous value
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>
diff --git a/demos/scale.c b/demos/scale.c
index 0995ad0..0c6b533 100644
--- a/demos/scale.c
+++ b/demos/scale.c
@@ -127,6 +127,13 @@ typedef struct
int value;
} named_int_t;
+static const named_int_t filter_types[] =
+{
+ { "Separable", PIXMAN_FILTER_SEPARABLE_CONVOLUTION },
+ { "Nearest", PIXMAN_FILTER_NEAREST },
+ { "Bilinear", PIXMAN_FILTER_BILINEAR },
+};
+
static const named_int_t filters[] =
{
{ "Box", PIXMAN_KERNEL_BOX },
@@ -249,18 +256,29 @@ rescale (GtkWidget *may_be_null, app_t *app)
pixman_transform_from_pixman_f_transform (&transform, &ftransform);
pixman_image_set_transform (app->original, &transform);
- params = pixman_filter_create_separable_convolution (
- &n_params,
- sx * 65536.0 + 0.5,
- sy * 65536.0 + 0.5,
- get_value (app, filters, "reconstruct_x_combo_box"),
- get_value (app, filters, "reconstruct_y_combo_box"),
- get_value (app, filters, "sample_x_combo_box"),
- get_value (app, filters, "sample_y_combo_box"),
- gtk_adjustment_get_value (app->subsample_adjustment),
- gtk_adjustment_get_value (app->subsample_adjustment));
+ if (get_value (app, filter_types, "filter_combo_box") ==
+ PIXMAN_FILTER_SEPARABLE_CONVOLUTION)
+ {
+ params = pixman_filter_create_separable_convolution (
+ &n_params,
+ sx * 65536.0 + 0.5,
+ sy * 65536.0 + 0.5,
+ get_value (app, filters, "reconstruct_x_combo_box"),
+ get_value (app, filters, "reconstruct_y_combo_box"),
+ get_value (app, filters, "sample_x_combo_box"),
+ get_value (app, filters, "sample_y_combo_box"),
+ gtk_adjustment_get_value (app->subsample_adjustment),
+ gtk_adjustment_get_value (app->subsample_adjustment));
+ }
+ else
+ {
+ params = 0;
+ n_params = 0;
+ }
- pixman_image_set_filter (app->original, PIXMAN_FILTER_SEPARABLE_CONVOLUTION, params, n_params);
+ pixman_image_set_filter (app->original,
+ get_value (app, filter_types, "filter_combo_box"),
+ params, n_params);
pixman_image_set_repeat (
app->original, get_value (app, repeats, "repeat_combo_box"));
@@ -402,6 +420,7 @@ 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_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");
diff --git a/demos/scale.ui b/demos/scale.ui
index d498d26..7e999c1 100644
--- a/demos/scale.ui
+++ b/demos/scale.ui
@@ -192,12 +192,23 @@
<property name="column_spacing">8</property>
<property name="row_spacing">6</property>
<child>
+ <object class="GtkLabel" id="labelF">
+ <property name="visible">True</property>
+ <property name="xalign">1</property>
+ <property name="label" translatable="yes"><b>Filter:</b></property>
+ <property name="use_markup">True</property>
+ </object>
+ </child>
+ <child>
<object class="GtkLabel" id="label4">
<property name="visible">True</property>
<property name="xalign">1</property>
<property name="label" translatable="yes"><b>Reconstruct X:</b></property>
<property name="use_markup">True</property>
</object>
+ <packing>
+ <property name="top_attach">1</property>
+ </packing>
</child>
<child>
<object class="GtkLabel" id="label5">
@@ -207,7 +218,7 @@
<property name="use_markup">True</property>
</object>
<packing>
- <property name="top_attach">1</property>
+ <property name="top_attach">2</property>
</packing>
</child>
<child>
@@ -218,7 +229,7 @@
<property name="use_markup">True</property>
</object>
<packing>
- <property name="top_attach">2</property>
+ <property name="top_attach">3</property>
</packing>
</child>
<child>
@@ -229,7 +240,7 @@
<property name="use_markup">True</property>
</object>
<packing>
- <property name="top_attach">3</property>
+ <property name="top_attach">4</property>
</packing>
</child>
<child>
@@ -240,7 +251,7 @@
<property name="use_markup">True</property>
</object>
<packing>
- <property name="top_attach">4</property>
+ <property name="top_attach">5</property>
</packing>
</child>
<child>
@@ -251,7 +262,15 @@
<property name="use_markup">True</property>
</object>
<packing>
- <property name="top_attach">5</property>
+ <property name="top_attach">6</property>
+ </packing>
+ </child>
+ <child>
+ <object class="GtkComboBox" id="filter_combo_box">
+ <property name="visible">True</property>
+ </object>
+ <packing>
+ <property name="left_attach">1</property>
</packing>
</child>
<child>
@@ -260,6 +279,7 @@
</object>
<packing>
<property name="left_attach">1</property>
+ <property name="top_attach">1</property>
</packing>
</child>
<child>
@@ -268,7 +288,7 @@
</object>
<packing>
<property name="left_attach">1</property>
- <property name="top_attach">1</property>
+ <property name="top_attach">2</property>
</packing>
</child>
<child>
@@ -277,7 +297,7 @@
</object>
<packing>
<property name="left_attach">1</property>
- <property name="top_attach">2</property>
+ <property name="top_attach">3</property>
</packing>
</child>
<child>
@@ -286,7 +306,7 @@
</object>
<packing>
<property name="left_attach">1</property>
- <property name="top_attach">3</property>
+ <property name="top_attach">4</property>
</packing>
</child>
<child>
@@ -295,7 +315,7 @@
</object>
<packing>
<property name="left_attach">1</property>
- <property name="top_attach">4</property>
+ <property name="top_attach">5</property>
</packing>
</child>
<child>
@@ -306,7 +326,7 @@
</object>
<packing>
<property name="left_attach">1</property>
- <property name="top_attach">5</property>
+ <property name="top_attach">6</property>
</packing>
</child>
</object>
commit afee2adc1e0052795a6ca8195e09a597bebde834
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:06 2016 -0700
demos/scale: Default to locked axis
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/demos/scale.ui b/demos/scale.ui
index f6f6e89..d498d26 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>
commit 1e1af34d3b74808d08a4067ff9d093a020e25da5
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:05 2016 -0700
demos/scale: fix blank subsamples spin box
It now shows the initial value of 4 when the demo is started
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Søren Sandmann <soren.sandmann at gmail.com>
diff --git a/demos/scale.ui b/demos/scale.ui
index ee985dd..f6f6e89 100644
--- a/demos/scale.ui
+++ b/demos/scale.ui
@@ -301,6 +301,7 @@
<object class="GtkSpinButton" id="subsample_spin_button">
<property name="visible">True</property>
<property name="adjustment">subsample_adjustment</property>
+ <property name="value">4</property>
</object>
<packing>
<property name="left_attach">1</property>
commit 99b574109dabff9c3c6fa9296b3b0534411b6fdb
Author: Bill Spitzak <spitzak at gmail.com>
Date: Tue Aug 30 22:03:04 2016 -0700
demos/scale: Compute filter size using boundary of xformed ellipse
Instead of using the boundary of xformed rectangle, use the boundary
of xformed ellipse. This is much more accurate and less blurry. In
particular the filtering does not change as the image is rotated.
Signed-off-by: Bill Spitzak <spitzak at gmail.com>
Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>
Reviewed-by: Soren Sandmann <soren.sandmann at gmail.com>
diff --git a/demos/scale.c b/demos/scale.c
index d00307e..0995ad0 100644
--- a/demos/scale.c
+++ b/demos/scale.c
@@ -55,50 +55,70 @@ get_widget (app_t *app, const char *name)
return widget;
}
-static double
-min4 (double a, double b, double c, double d)
-{
- double m1, m2;
-
- m1 = MIN (a, b);
- m2 = MIN (c, d);
- return MIN (m1, m2);
-}
-
-static double
-max4 (double a, double b, double c, double d)
-{
- double m1, m2;
-
- m1 = MAX (a, b);
- m2 = MAX (c, d);
- return MAX (m1, m2);
-}
-
+/* Figure out the boundary of a diameter=1 circle transformed into an ellipse
+ * by trans. Proof that this is the correct calculation:
+ *
+ * Transform x,y to u,v by this matrix calculation:
+ *
+ * |u| |a c| |x|
+ * |v| = |b d|*|y|
+ *
+ * Horizontal component:
+ *
+ * u = ax+cy (1)
+ *
+ * For each x,y on a radius-1 circle (p is angle to the point):
+ *
+ * x^2+y^2 = 1
+ * x = cos(p)
+ * y = sin(p)
+ * dx/dp = -sin(p) = -y
+ * dy/dp = cos(p) = x
+ *
+ * Figure out derivative of (1) relative to p:
+ *
+ * du/dp = a(dx/dp) + c(dy/dp)
+ * = -ay + cx
+ *
+ * The min and max u are when du/dp is zero:
+ *
+ * -ay + cx = 0
+ * cx = ay
+ * c = ay/x (2)
+ * y = cx/a (3)
+ *
+ * Substitute (2) into (1) and simplify:
+ *
+ * u = ax + ay^2/x
+ * = a(x^2+y^2)/x
+ * = a/x (because x^2+y^2 = 1)
+ * x = a/u (4)
+ *
+ * Substitute (4) into (3) and simplify:
+ *
+ * y = c(a/u)/a
+ * y = c/u (5)
+ *
+ * Square (4) and (5) and add:
+ *
+ * x^2+y^2 = (a^2+c^2)/u^2
+ *
+ * But x^2+y^2 is 1:
+ *
+ * 1 = (a^2+c^2)/u^2
+ * u^2 = a^2+c^2
+ * u = hypot(a,c)
+ *
+ * Similarily the max/min of v is at:
+ *
+ * v = hypot(b,d)
+ *
+ */
static void
compute_extents (pixman_f_transform_t *trans, double *sx, double *sy)
{
- double min_x, max_x, min_y, max_y;
- pixman_f_vector_t v[4] =
- {
- { { 1, 1, 1 } },
- { { -1, 1, 1 } },
- { { -1, -1, 1 } },
- { { 1, -1, 1 } },
- };
-
- pixman_f_transform_point (trans, &v[0]);
- pixman_f_transform_point (trans, &v[1]);
- pixman_f_transform_point (trans, &v[2]);
- pixman_f_transform_point (trans, &v[3]);
-
- min_x = min4 (v[0].v[0], v[1].v[0], v[2].v[0], v[3].v[0]);
- max_x = max4 (v[0].v[0], v[1].v[0], v[2].v[0], v[3].v[0]);
- min_y = min4 (v[0].v[1], v[1].v[1], v[2].v[1], v[3].v[1]);
- max_y = max4 (v[0].v[1], v[1].v[1], v[2].v[1], v[3].v[1]);
-
- *sx = (max_x - min_x) / 2.0;
- *sy = (max_y - min_y) / 2.0;
+ *sx = hypot (trans->m[0][0], trans->m[0][1]) / trans->m[2][2];
+ *sy = hypot (trans->m[1][0], trans->m[1][1]) / trans->m[2][2];
}
typedef struct
commit b9ead7ddf7c2bb373808e59a4f625e2e732ef2e2
Author: Søren Sandmann Pedersen <soren.sandmann at gmail.com>
Date: Tue Aug 30 22:03:03 2016 -0700
More general BILINEAR=>NEAREST reduction
Generalize and simplify the code that reduces BILINEAR to NEAREST so
that the reduction happens for all affine transformations where
t00...t12 are integers and (t00 + t01) and (t10 + t11) are both
odd. This is a sufficient condition for the resulting transformed
coordinates to be exactly at the center of a pixel so that BILINEAR
becomes identical to NEAREST.
V2: Address some comments by Bill Spitzak
Signed-off-by: Søren Sandmann <soren.sandmann at gmail.com>
Reviewed-by: Bill Spitzak <spitzak at gmail.com>
diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
index 1ff1a49..681864e 100644
--- a/pixman/pixman-image.c
+++ b/pixman/pixman-image.c
@@ -335,37 +335,47 @@ compute_image_info (pixman_image_t *image)
{
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)
- )
- )
+ else if (flags & FAST_PATH_AFFINE_TRANSFORM)
{
- /* 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.
+ /* Suppose the transform is
+ *
+ * [ t00, t01, t02 ]
+ * [ t10, t11, t12 ]
+ * [ 0, 0, 1 ]
+ *
+ * and the destination coordinates are (n + 0.5, m + 0.5). Then
+ * the transformed x coordinate is:
+ *
+ * tx = t00 * (n + 0.5) + t01 * (m + 0.5) + t02
+ * = t00 * n + t01 * m + t02 + (t00 + t01) * 0.5
+ *
+ * which implies that if t00, t01 and t02 are all integers
+ * and (t00 + t01) is odd, then tx will be an integer plus 0.5,
+ * which means a BILINEAR filter will reduce to NEAREST. The same
+ * applies in the y direction
*/
- 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)
+ pixman_fixed_t (*t)[3] = image->common.transform->matrix;
+
+ if ((pixman_fixed_frac (
+ t[0][0] | t[0][1] | t[0][2] |
+ t[1][0] | t[1][1] | t[1][2]) == 0) &&
+ (pixman_fixed_to_int (
+ (t[0][0] + t[0][1]) & (t[1][0] + t[1][1])) % 2) == 1)
{
- flags |= FAST_PATH_NEAREST_FILTER;
+ /* 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.
+ */
+ 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;
+ }
}
}
break;
commit 76123690139a7f342776a885a7478a6c81712145
Author: Søren Sandmann Pedersen <soren.sandmann at gmail.com>
Date: Tue Aug 30 22:03:02 2016 -0700
Add new test of filter reduction from BILINEAR to NEAREST
This new test tests a bunch of bilinear downscalings, where many have
a transformation such that the BILINEAR filter can be reduced to
NEAREST (and many don't).
A CRC32 is computed for all the resulting images and compared to a
known-good value for both 4-bit and 7-bit interpolation.
V2: Remove leftover comment, some minor formatting fixes, use a
timestamp as the PRNG seed.
Signed-off-by: Søren Sandmann <soren.sandmann at gmail.com>
Reviewed-by: Bill Spitzak <spitzak at gmail.com>
diff --git a/test/Makefile.sources b/test/Makefile.sources
index 5d55e67..0a56231 100644
--- a/test/Makefile.sources
+++ b/test/Makefile.sources
@@ -21,6 +21,7 @@ TESTPROGRAMS = \
gradient-crash-test \
pixel-test \
matrix-test \
+ filter-reduction-test \
composite-traps-test \
region-contains-test \
glyph-test \
diff --git a/test/filter-reduction-test.c b/test/filter-reduction-test.c
new file mode 100644
index 0000000..705fa4b
--- /dev/null
+++ b/test/filter-reduction-test.c
@@ -0,0 +1,112 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "utils.h"
+
+static const pixman_fixed_t entries[] =
+{
+ pixman_double_to_fixed (-1.0),
+ pixman_double_to_fixed (-0.5),
+ pixman_double_to_fixed (-1/3.0),
+ pixman_double_to_fixed (0.0),
+ pixman_double_to_fixed (0.5),
+ pixman_double_to_fixed (1.0),
+ pixman_double_to_fixed (1.5),
+ pixman_double_to_fixed (2.0),
+ pixman_double_to_fixed (3.0),
+};
+
+#define SIZE 12
+
+static uint32_t
+test_scale (const pixman_transform_t *xform, uint32_t crc)
+{
+ uint32_t *srcbuf, *dstbuf;
+ pixman_image_t *src, *dest;
+
+ srcbuf = malloc (SIZE * SIZE * 4);
+ prng_randmemset (srcbuf, SIZE * SIZE * 4, 0);
+ src = pixman_image_create_bits (
+ PIXMAN_a8r8g8b8, SIZE, SIZE, srcbuf, SIZE * 4);
+
+ dstbuf = malloc (SIZE * SIZE * 4);
+ prng_randmemset (dstbuf, SIZE * SIZE * 4, 0);
+ dest = pixman_image_create_bits (
+ PIXMAN_a8r8g8b8, SIZE, SIZE, dstbuf, SIZE * 4);
+
+ pixman_image_set_transform (src, xform);
+ pixman_image_set_repeat (src, PIXMAN_REPEAT_NORMAL);
+ pixman_image_set_filter (src, PIXMAN_FILTER_BILINEAR, NULL, 0);
+
+ image_endian_swap (src);
+ image_endian_swap (dest);
+
+ pixman_image_composite (PIXMAN_OP_SRC,
+ src, NULL, dest,
+ 0, 0, 0, 0, 0, 0,
+ SIZE, SIZE);
+
+ crc = compute_crc32_for_image (crc, dest);
+
+ pixman_image_unref (src);
+ pixman_image_unref (dest);
+
+ free (srcbuf);
+ free (dstbuf);
+
+ return crc;
+}
+
+#if BILINEAR_INTERPOLATION_BITS == 7
+#define CHECKSUM 0x02169677
+#elif BILINEAR_INTERPOLATION_BITS == 4
+#define CHECKSUM 0xE44B29AC
+#else
+#define CHECKSUM 0x00000000
+#endif
+
+int
+main (int argc, const char *argv[])
+{
+ const pixman_fixed_t *end = entries + ARRAY_LENGTH (entries);
+ const pixman_fixed_t *t0, *t1, *t2, *t3, *t4, *t5;
+ uint32_t crc = 0;
+
+ prng_srand (0x56EA1DBD);
+
+ for (t0 = entries; t0 < end; ++t0)
+ {
+ for (t1 = entries; t1 < end; ++t1)
+ {
+ for (t2 = entries; t2 < end; ++t2)
+ {
+ for (t3 = entries; t3 < end; ++t3)
+ {
+ for (t4 = entries; t4 < end; ++t4)
+ {
+ for (t5 = entries; t5 < end; ++t5)
+ {
+ pixman_transform_t xform = {
+ { { *t0, *t1, *t2 },
+ { *t3, *t4, *t5 },
+ { 0, 0, pixman_fixed_1 } }
+ };
+
+ crc = test_scale (&xform, crc);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ if (crc != CHECKSUM)
+ {
+ printf ("filter-reduction-test failed! (checksum=0x%08X, expected 0x%08X)\n", crc, CHECKSUM);
+ return 1;
+ }
+ else
+ {
+ printf ("filter-reduction-test passed (checksum=0x%08X)\n", crc);
+ return 0;
+ }
+}
commit eb4a832ec22e4257b59cac752b02a1d27f4363bc
Author: Søren Sandmann Pedersen <soren.sandmann at gmail.com>
Date: Tue Aug 30 22:03:01 2016 -0700
pixman-fast-path.c: Pick NEAREST affine fast paths before BILINEAR ones
When a BILINEAR filter is reduced to NEAREST, it is possible for both
types of fast paths to run; in this case, the NEAREST ones should be
preferred as that is the simpler filter.
Signed-off-by: Soren Sandmann <soren.sandmann at gmail.com>
Reviewed-by: Bill Spitzak <spitzak at gmail.com>
diff --git a/pixman/pixman-fast-path.c b/pixman/pixman-fast-path.c
index 53d4a1f..b4daa26 100644
--- a/pixman/pixman-fast-path.c
+++ b/pixman/pixman-fast-path.c
@@ -3258,9 +3258,9 @@ static const pixman_iter_info_t fast_iters[] =
},
#define AFFINE_FAST_PATHS(name, format, repeat) \
- SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH(name, format, repeat) \
+ NEAREST_AFFINE_FAST_PATH(name, format, repeat) \
BILINEAR_AFFINE_FAST_PATH(name, format, repeat) \
- NEAREST_AFFINE_FAST_PATH(name, format, repeat)
+ SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH(name, format, repeat)
AFFINE_FAST_PATHS (pad_a8r8g8b8, a8r8g8b8, PAD)
AFFINE_FAST_PATHS (none_a8r8g8b8, a8r8g8b8, NONE)
More information about the xorg-commit
mailing list