diff options
Diffstat (limited to 'pixman')
| -rw-r--r-- | pixman/pixman/pixman-bits-image.c | 8 | ||||
| -rw-r--r-- | pixman/pixman/pixman-matrix.c | 10 | ||||
| -rw-r--r-- | pixman/pixman/rounding.txt | 134 | ||||
| -rw-r--r-- | pixman/test/affine-test.c | 6 | ||||
| -rw-r--r-- | pixman/test/rotate-test.c | 2 | ||||
| -rw-r--r-- | pixman/test/scaling-test.c | 6 |
6 files changed, 150 insertions, 16 deletions
diff --git a/pixman/pixman/pixman-bits-image.c b/pixman/pixman/pixman-bits-image.c index 085dd1606..7787ef1b8 100644 --- a/pixman/pixman/pixman-bits-image.c +++ b/pixman/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); diff --git a/pixman/pixman/pixman-matrix.c b/pixman/pixman/pixman-matrix.c index d2ab609dc..cd2f1b5b8 100644 --- a/pixman/pixman/pixman-matrix.c +++ b/pixman/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/pixman/pixman/rounding.txt b/pixman/pixman/rounding.txt new file mode 100644 index 000000000..1a19f450f --- /dev/null +++ b/pixman/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. diff --git a/pixman/test/affine-test.c b/pixman/test/affine-test.c index 7bc28b4cd..daa86c81d 100644 --- a/pixman/test/affine-test.c +++ b/pixman/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/pixman/test/rotate-test.c b/pixman/test/rotate-test.c index d63a28947..a0488ef22 100644 --- a/pixman/test/rotate-test.c +++ b/pixman/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/pixman/test/scaling-test.c b/pixman/test/scaling-test.c index 273612395..035410333 100644 --- a/pixman/test/scaling-test.c +++ b/pixman/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 |