| *** 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. |
| |
| |
| --- SEPARABLE_CONVOLUTION |
| |
| For this filter, x is first rounded to one of n regularly spaced |
| subpixel positions. This subpixel position determines which of n |
| convolution matrices is being used. |
| |
| Then, as in a regular convolution filter, the first pixel to be used |
| is determined: |
| |
| k = floor (x - (width - 1) / 2.0 - e) |
| |
| and then the image pixels starting there are convolved with the chosen |
| matrix. If we write x = xi + frac, where xi is an integer, we get |
| |
| k = xi + floor (frac - (width - 1) / 2.0 - e) |
| |
| so the location of k relative to x is given by: |
| |
| (k + 0.5 - x) = xi + floor (frac - (width - 1) / 2.0 - e) + 0.5 - x |
| |
| = floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac |
| |
| 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, |
| where each entry in the matrix is computed as the product of the |
| corresponding entries in the vectors. |