[PATCH renderproto] Add floating point transforms

[Siarhei Siamashka]

On Fri, 15 Aug 2014 08:55:18 -0700
Keith Packard <keithp at keithp.com> wrote:

> Fixed point coordinates don't provide reasonable precision for
> transformation operations; the resulting transforms are often off by
> several pixels.

Do you have a reproducible testcase for this problem? Being off by
several pixels seems to be very wrong. Especially if this happens often.

> Allow clients to represent the transformation using either fixed point
> or floating point.
> 
> Signed-off-by: Keith Packard <keithp at keithp.com>

The 16.16 fixed point format should be pixel accurate for the whole
range of coordinates supported by XRENDER (from -32K to 32K). At least
for affine transformations. Projective transformations are a somewhat
special case and don't seem to be used in practice (Cairo does not
use them).

When we are doing matrix multiplications, each transformed coordinate
is a sum of three multiplications. For affine transformations it is
effectively a sum of just two multiplications. Assuming that a perfectly
accurate matrix is getting converted to the 16.16 fixed point format,
we get some rounding errors. In the worst case, the rounding error
for each of the matrix coefficients is 1/65536 (the granularity of
fixed point values) divided by two (because we are rounding to
nearest). Also in the worst case, the coordinates before transformation
can be as large as 32768. So the worst case absolute error is
1/65536/2 * 32768 * 2 = 0.5 pixels for affine transformations.
And the error is naturally smaller than this on average.

32-bit floating point values use the same number of bits as 16.16 fixed
point values for data storage. But the key difference is that the
accuracy of the floating point values is seriously non-uniform. It
tends to be better when the values are close to zero, but degrades
significantly (less bits are allocated to the fractional part) when
the pixel coordinates move further away from zero. In general, floating
point calculations are not associative and this causes additional
headaches. For example, repeating N times "x += dx" does not
necessarily produce the same result as "x += dx * N".

Floating point format supports a wider range of values (unnecessary
if the rest of XRENDER remains restricted to 16-bit coordinates) but
has much worse accuracy in corner cases and is poorly predictable.
The 32-bit floating point format does not look like an obvious
upgrade over 16.16 fixed point.

IMHO this problem needs a bit more debugging before taking any
actions with serious consequences (such as extending the protocol).

-- 
Best regards,
Siarhei Siamashka