X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=qemu%2Fpixman%2Fpixman%2Frounding.txt;fp=qemu%2Fpixman%2Fpixman%2Frounding.txt;h=b52b084394d584e2c3a62d563501821f673d375c;hb=e44e3482bdb4d0ebde2d8b41830ac2cdb07948fb;hp=0000000000000000000000000000000000000000;hpb=9ca8dbcc65cfc63d6f5ef3312a33184e1d726e00;p=kvmfornfv.git

diff --git a/qemu/pixman/pixman/rounding.txt b/qemu/pixman/pixman/rounding.txt
new file mode 100644
index 000000000..b52b08439
--- /dev/null
+++ b/qemu/pixman/pixman/rounding.txt
@@ -0,0 +1,167 @@
+*** 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
+
+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.