1 files changed, 134 insertions, 0 deletions
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.