pixman: Branch 'master' - 3 commits
Søren Sandmann Pedersen
sandmann at kemper.freedesktop.org
Thu Nov 29 03:51:30 PST 2012
pixman/pixman-bits-image.c | 8 +-
pixman/pixman-matrix.c | 10 +--
pixman/rounding.txt | 134 +++++++++++++++++++++++++++++++++++++++++++++
test/affine-test.c | 6 +-
test/rotate-test.c | 2
test/scaling-test.c | 6 +-
6 files changed, 150 insertions(+), 16 deletions(-)
New commits:
commit 978bab253d1d061b00b5e80aa45ab6986aac466f
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Wed Nov 21 11:43:31 2012 -0500
Add text file rounding.txt describing how rounding works
It is not entirely obvious how pixman gets from "location in the
source image" to "pixel value stored in the destination". This file
describes how the filters work, and in particular how positions are
rounded to samples.
diff --git a/pixman/rounding.txt b/pixman/rounding.txt
new file mode 100644
index 0000000..1a19f45
--- /dev/null
+++ b/pixman/rounding.txt
@@ -0,0 +1,134 @@
+*** General notes about rounding
+
+Suppose a function is sampled at positions [k + o] where k is an
+integer and o is a fractional offset 0 <= o < 1.
+
+To round a value to the nearest sample, breaking ties by rounding up,
+we can do this:
+
+ round(x) = floor(x - o + 0.5) + o
+
+That is, first subtract o to let us pretend that the samples are at
+integer coordinates, then add 0.5 and floor to round to nearest
+integer, then add the offset back in.
+
+To break ties by rounding down:
+
+ round(x) = ceil(x - o - 0.5) + o
+
+or if we have an epsilon value:
+
+ round(x) = floor(x - o + 0.5 - e) + o
+
+To always round *up* to the next sample:
+
+ round_up(x) = ceil(x - o) + o
+
+To always round *down* to the previous sample:
+
+ round_down(x) = floor(x - o) + o
+
+If a set of samples is stored in an array, you get from the sample
+position to an index by subtracting the position of the first sample
+in the array:
+
+ index(s) = s - first_sample
+
+
+*** Application to pixman
+
+In pixman, images are sampled with o = 0.5, that is, pixels are
+located midways between integers. We usually break ties by rounding
+down (i.e., "round towards north-west").
+
+
+-- NEAREST filtering:
+
+The NEAREST filter simply picks the closest pixel to the given
+position:
+
+ round(x) = floor(x - 0.5 + 0.5 - e) + 0.5 = floor (x - e) + 0.5
+
+The first sample of a pixman image has position 0.5, so to find the
+index in the pixel array, we have to subtract 0.5:
+
+ floor (x - e) + 0.5 - 0.5 = floor (x - e).
+
+Therefore a 16.16 fixed-point image location is turned into a pixel
+value with NEAREST filtering by doing this:
+
+ pixels[((y - e) >> 16) * stride + ((x - e) >> 16)]
+
+where stride is the number of pixels allocated per scanline and e =
+0x0001.
+
+
+-- CONVOLUTION filtering:
+
+A convolution matrix is considered a sampling of a function f at
+values surrounding 0. For example, this convolution matrix:
+
+ [a, b, c, d]
+
+is interpreted as the values of a function f:
+
+ a = f(-1.5)
+ b = f(-0.5)
+ c = f(0.5)
+ d = f(1.5)
+
+The sample offset in this case is o = 0.5 and the first sample has
+position s0 = -1.5. If the matrix is:
+
+ [a, b, c, d, e]
+
+the sample offset is o = 0 and the first sample has position s0 =
+-2.0. In general we have
+
+ s0 = (- width / 2.0 + 0.5).
+
+and
+
+ o = frac (s0)
+
+To evaluate f at a position between the samples, we round to the
+closest sample, and then we subtract the position of the first sample
+to get the index in the matrix:
+
+ f(t) = matrix[floor(t - o + 0.5) + o - s0]
+
+Note that in this case we break ties by rounding up.
+
+If we write s0 = m + o, where m is an integer, this is equivalent to
+
+ f(t) = matrix[floor(t - o + 0.5) + o - (m + o)]
+ = matrix[floor(t - o + 0.5 - m) + o - o]
+ = matrix[floor(t - s0 + 0.5)]
+
+The convolution filter in pixman positions f such that 0 aligns with
+the given position x. For a given pixel x0 in the image, the closest
+sample of f is then computed by taking (x - x0) and rounding that to
+the closest index:
+
+ i = floor ((x0 - x) - s0 + 0.5)
+
+To perform the convolution, we have to find the first pixel x0 whose
+corresponding sample has index 0. We can write x0 = k + 0.5, where k
+is an integer:
+
+ 0 = floor(k + 0.5 - x - s0 + 0.5)
+
+ = k + floor(1 - x - s0)
+
+ = k - ceil(x + s0 - 1)
+
+ = k - floor(x + s0 - e)
+
+ = k - floor(x - (width - 1) / 2.0 - e)
+
+And so the final formula for the index k of x0 in the image is:
+
+ k = floor(x - (width - 1) / 2.0 - e)
+
+Computing the result is then simply a matter of convolving all the
+pixels starting at k with all the samples in the matrix.
commit 74319e9d39f5d7f85cb75fcb91343f298b0e62e2
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Tue Nov 20 23:28:43 2012 -0500
Convolution filter: round color values instead of truncating
The pixel computed by the convolution filter should be rounded off,
not truncated. As a simple example consider a convolution matrix
consisting of five times 0x3333. If all five all five input pixels are
0xff, then the result of truncating will be
(5 * 0x3333 * 255) >> 16 = 254
But the real value of the computation is (5 * 0x3333 / 65536.0) * 254
= 254.9961, so the error is almost 1. If the user isn't very careful
about normalizing the convolution kernel so that it sums to one in
fixed point, such error might cause solid images to change color, or
opaque images to become translucent.
The fix is simply to round instead of truncate.
diff --git a/pixman/pixman-bits-image.c b/pixman/pixman-bits-image.c
index 085dd16..7787ef1 100644
--- a/pixman/pixman-bits-image.c
+++ b/pixman/pixman-bits-image.c
@@ -413,10 +413,10 @@ bits_image_fetch_pixel_convolution (bits_image_t *image,
}
}
- satot >>= 16;
- srtot >>= 16;
- sgtot >>= 16;
- sbtot >>= 16;
+ satot = (satot + 0x8000) >> 16;
+ srtot = (srtot + 0x8000) >> 16;
+ sgtot = (sgtot + 0x8000) >> 16;
+ sbtot = (sbtot + 0x8000) >> 16;
satot = CLIP (satot, 0, 0xff);
srtot = CLIP (srtot, 0, 0xff);
commit f0816ddaf4e61d9295de5b1cbe51f956db7fbd16
Author: Søren Sandmann Pedersen <ssp at redhat.com>
Date: Tue Nov 20 03:23:51 2012 -0500
Round fixed-point multiplication
After two fixed-point numbers are multiplied, the result is shifted
into place, but up until now pixman has simply discarded the low-order
bits instead of rounding to the closest number.
Fix that by adding 0x8000 (or 0x2 in one place) before shifting and
update the test checksums to match.
diff --git a/pixman/pixman-matrix.c b/pixman/pixman-matrix.c
index d2ab609..cd2f1b5 100644
--- a/pixman/pixman-matrix.c
+++ b/pixman/pixman-matrix.c
@@ -62,7 +62,7 @@ pixman_transform_point_3d (const struct pixman_transform *transform,
{
partial = ((pixman_fixed_48_16_t) transform->matrix[j][i] *
(pixman_fixed_48_16_t) vector->vector[i]);
- v += partial >> 16;
+ v += (partial + 0x8000) >> 16;
}
if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
@@ -96,16 +96,16 @@ pixman_transform_point (const struct pixman_transform *transform,
{
partial = ((pixman_fixed_32_32_t) transform->matrix[j][i] *
(pixman_fixed_32_32_t) vector->vector[i]);
- v[j] += partial >> 2;
+ v[j] += (partial + 2) >> 2;
}
}
- if (!(v[2] >> 16))
+ if (!((v[2] + 0x8000) >> 16))
return FALSE;
for (j = 0; j < 2; j++)
{
- quo = v[j] / (v[2] >> 16);
+ quo = v[j] / ((v[2] + 0x8000) >> 16);
if (quo > pixman_max_fixed_48_16 || quo < pixman_min_fixed_48_16)
return FALSE;
vector->vector[j] = (pixman_fixed_t) quo;
@@ -138,7 +138,7 @@ pixman_transform_multiply (struct pixman_transform * dst,
(pixman_fixed_32_32_t) l->matrix[dy][o] *
(pixman_fixed_32_32_t) r->matrix[o][dx];
- v += partial >> 16;
+ v += (partial + 0x8000) >> 16;
}
if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
diff --git a/test/affine-test.c b/test/affine-test.c
index 7bc28b4..daa86c8 100644
--- a/test/affine-test.c
+++ b/test/affine-test.c
@@ -310,11 +310,11 @@ test_composite (int testnum,
}
#if BILINEAR_INTERPOLATION_BITS == 8
-#define CHECKSUM 0x1EF2175A
+#define CHECKSUM 0x344413F0
#elif BILINEAR_INTERPOLATION_BITS == 7
-#define CHECKSUM 0x74050F50
+#define CHECKSUM 0xC8181A76
#elif BILINEAR_INTERPOLATION_BITS == 4
-#define CHECKSUM 0x4362EAE8
+#define CHECKSUM 0xD672A457
#else
#define CHECKSUM 0x00000000
#endif
diff --git a/test/rotate-test.c b/test/rotate-test.c
index d63a289..a0488ef 100644
--- a/test/rotate-test.c
+++ b/test/rotate-test.c
@@ -108,6 +108,6 @@ int
main (int argc, const char *argv[])
{
return fuzzer_test_main ("rotate", 15000,
- 0x03A24D51,
+ 0x5236FD9F,
test_transform, argc, argv);
}
diff --git a/test/scaling-test.c b/test/scaling-test.c
index 2736123..0354103 100644
--- a/test/scaling-test.c
+++ b/test/scaling-test.c
@@ -380,11 +380,11 @@ test_composite (int testnum,
}
#if BILINEAR_INTERPOLATION_BITS == 8
-#define CHECKSUM 0x8D3A7539
+#define CHECKSUM 0x107B67ED
#elif BILINEAR_INTERPOLATION_BITS == 7
-#define CHECKSUM 0x03A23E0C
+#define CHECKSUM 0x30EC0CF0
#elif BILINEAR_INTERPOLATION_BITS == 4
-#define CHECKSUM 0xE96D1A5E
+#define CHECKSUM 0x87B496BC
#else
#define CHECKSUM 0x00000000
#endif
More information about the xorg-commit
mailing list