qemu/pixman/pixman/rounding.txt

   1 *** General notes about rounding
   2
   3 Suppose a function is sampled at positions [k + o] where k is an
   4 integer and o is a fractional offset 0 <= o < 1.
   5
   6 To round a value to the nearest sample, breaking ties by rounding up,
   7 we can do this:
   8
   9    round(x) = floor(x - o + 0.5) + o
  10
  11 That is, first subtract o to let us pretend that the samples are at
  12 integer coordinates, then add 0.5 and floor to round to nearest
  13 integer, then add the offset back in.
  14
  15 To break ties by rounding down:
  16
  17     round(x) = ceil(x - o - 0.5) + o
  18
  19 or if we have an epsilon value:
  20
  21     round(x) = floor(x - o + 0.5 - e) + o
  22
  23 To always round *up* to the next sample:
  24
  25     round_up(x) = ceil(x - o) + o
  26
  27 To always round *down* to the previous sample:
  28
  29     round_down(x) = floor(x - o) + o
  30
  31 If a set of samples is stored in an array, you get from the sample
  32 position to an index by subtracting the position of the first sample
  33 in the array:
  34
  35     index(s) = s - first_sample
  36
  37
  38 *** Application to pixman
  39
  40 In pixman, images are sampled with o = 0.5, that is, pixels are
  41 located midways between integers. We usually break ties by rounding
  42 down (i.e., "round towards north-west").
  43
  44
  45 -- NEAREST filtering:
  46
  47 The NEAREST filter simply picks the closest pixel to the given
  48 position:
  49
  50     round(x) = floor(x - 0.5 + 0.5 - e) + 0.5 = floor (x - e) + 0.5
  51
  52 The first sample of a pixman image has position 0.5, so to find the
  53 index in the pixel array, we have to subtract 0.5:
  54
  55     floor (x - e) + 0.5 - 0.5 = floor (x - e).
  56
  57 Therefore a 16.16 fixed-point image location is turned into a pixel
  58 value with NEAREST filtering by doing this:
  59
  60     pixels[((y - e) >> 16) * stride + ((x - e) >> 16)]
  61
  62 where stride is the number of pixels allocated per scanline and e =
  63 0x0001.
  64
  65
  66 -- CONVOLUTION filtering:
  67
  68 A convolution matrix is considered a sampling of a function f at
  69 values surrounding 0. For example, this convolution matrix:
  70
  71         [a, b, c, d]
  72
  73 is interpreted as the values of a function f:
  74
  75         a = f(-1.5)
  76         b = f(-0.5)
  77         c = f(0.5)
  78         d = f(1.5)
  79
  80 The sample offset in this case is o = 0.5 and the first sample has
  81 position s0 = -1.5. If the matrix is:
  82
  83         [a, b, c, d, e]
  84
  85 the sample offset is o = 0 and the first sample has position s0 =
  86 -2.0. In general we have
  87
  88       s0 = (- width / 2.0 + 0.5).
  89
  90 and
  91
  92       o = frac (s0)
  93
  94 To evaluate f at a position between the samples, we round to the
  95 closest sample, and then we subtract the position of the first sample
  96 to get the index in the matrix:
  97
  98         f(t) = matrix[floor(t - o + 0.5) + o - s0]
  99
 100 Note that in this case we break ties by rounding up.
 101
 102 If we write s0 = m + o, where m is an integer, this is equivalent to
 103
 104         f(t) = matrix[floor(t - o + 0.5) + o - (m + o)]
 105              = matrix[floor(t - o + 0.5 - m) + o - o]
 106              = matrix[floor(t - s0 + 0.5)]
 107
 108 The convolution filter in pixman positions f such that 0 aligns with
 109 the given position x. For a given pixel x0 in the image, the closest
 110 sample of f is then computed by taking (x - x0) and rounding that to
 111 the closest index:
 112
 113         i = floor ((x0 - x) - s0 + 0.5)
 114
 115 To perform the convolution, we have to find the first pixel x0 whose
 116 corresponding sample has index 0. We can write x0 = k + 0.5, where k
 117 is an integer:
 118
 119          0 = floor(k + 0.5 - x - s0 + 0.5)
 120
 121            = k + floor(1 - x - s0)
 122
 123            = k - ceil(x + s0 - 1)
 124
 125            = k - floor(x + s0 - e)
 126
 127            = k - floor(x - (width - 1) / 2.0 - e)
 128
 129 And so the final formula for the index k of x0 in the image is:
 130
 131             k = floor(x - (width - 1) / 2.0 - e)
 132
 133 Computing the result is then simply a matter of convolving all the
 134 pixels starting at k with all the samples in the matrix.
 135
 136
 137 --- SEPARABLE_CONVOLUTION
 138
 139 For this filter, x is first rounded to one of n regularly spaced
 140 subpixel positions. This subpixel position determines which of n
 141 convolution matrices is being used.
 142
 143 Then, as in a regular convolution filter, the first pixel to be used
 144 is determined:
 145
 146         k = floor (x - (width - 1) / 2.0 - e)
 147
 148 and then the image pixels starting there are convolved with the chosen
 149 matrix. If we write x = xi + frac, where xi is an integer, we get
 150
 151         k = xi + floor (frac - (width - 1) / 2.0 - e)
 152
 153 so the location of k relative to x is given by:
 154
 155     (k + 0.5 - x) = xi + floor (frac - (width - 1) / 2.0 - e) + 0.5 - x
 156
 157                   = floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac
 158
 159 which means the contents of the matrix corresponding to (frac) should
 160 contain width samplings of the function, with the first sample at:
 161
 162        floor (frac - (width - 1) / 2.0 - e) + 0.5 - frac
 163
 164 This filter is called separable because each of the k x k convolution
 165 matrices is specified with two k-wide vectors, one for each dimension,
 166 where each entry in the matrix is computed as the product of the
 167 corresponding entries in the vectors.