[PATCH 2/2] glamor: Use float matrix for render transformations

[Siarhei Siamashka]

On Mon, 18 Aug 2014 15:15:28 -0700
Keith Packard <keithp at keithp.com> wrote:

> Siarhei Siamashka <siarhei.siamashka at gmail.com> writes:
> 
> > Okay, now I see what's going on. The old glamor code used to convert
> > the 16.16 fixed point values to 32-bit floats. This is definitely not
> > great because of http://en.wikipedia.org/wiki/Rounding#Double_rounding
> > on the "64-bit float" -> "16.16 fixed point" -> "32-bit float"
> > conversion path. Directly passing 32-bit floats to XRENDER should
> > somewhat mitigate the accuracy loss, but not totally eliminate it.
> 
> You need to separate the coordinate representation issues from the
> transformation representation issues. For coordinates, yes, 32-bit
> floats would lose some of the low bits. For transformation matrices,
> the values aren't coordinates; they're all scaling factors for the
> coordinates.
> 
>         | A B C |
>         | D E F |
>         | G H J |
> 
> For affine transforms, A, B, D, E generally have small values, related
> to the overall image scaling factor. C and F are the translation while G
> and H are zero and J is one. The small values (A, B, D, E) are
> multiplied by coordinates, the large values (C, F) are multiplied by
> one. Having 24 bits of mantissa for all of these values offers the
> maximum precision for the resulting values.

Software development just does not work this way. You can't rely on
assumptions like "For affine transforms, A, B, D, E generally have
small values", "the user always provides correct input", "this race
condition is so rare that it is unlikely to crash our software" and
anything of this sort.

Fixed point 16.16 format at least has predictable good accuracy (less
than 0.5 pixel absolute error in the worst case) for any affine
transformation when working with the coordinates and matrices within
the valid range supported by XRENDER.

Single precision floating point format has much less reliable accuracy
for affine transformations. That's the fact.

> Let's try to construct a really bad case. That's where your matrix
> has values which are just less than 0.5 ULP (1/2**17)
> 
>         A * x + B * y + C
>   x' =  -----------------
>         G * x + H * y + J
> 
> so, the maximum error here would be where the denominator was small, and
> the maximum magnitude of the matrix values was large so as to keep us
> From scaling the matrix up to provide precision for the smallest
> members.
> 
> Here's a matrix which almost reflects in X with a tiny amount of
> non-affine adjustment
> 
>         | -1    0    32767 |
>         |  0    1        0 |
>         |  e    0        1 |
> 
> Set e to 1/2 ULP - epsilon (a tiny bit less than 1/2**17) so that the
> fixed point matrix has a zero there and the floating point matrix has a
> non-zero value. For x, y of -2000,2000:
> 
>       -1 * -2000 + 0 * 2000 + 32767    34767
> x' =  ----------------------------- = ------- = 35305.72
>        e * -2000 + 0 * 2000 + 1       0.98474
> 
>       -1 * -2000 + 0 * 2000 + 32767    34767
> x' ~= ----------------------------- = ------- = 34767
>        0 * -2000 + 0 * 2000 + 1          1
> 
> This has an error of about 539 pixels.
> 
> > Is the accuracy actually good enough with this patch applied and solves
> > the "off by several pixels" problem? The patch still looks messed up
> > with the use of a mix of double and float.
> 
> The example above is contrived, but shows that fixed point
> introduces considerable inaccuracy when used in the transformation matrix.

Let's consider that

   e = 1.0 / (1 << 10)

And then try to do the following transform in 3 different ways:

   | 32767 + e    -32767 + e    0 |   | 32767 |
   | 0            1             0 | * | 32767 |
   | 0            0             1 |   | 1     |

a) If we use double precision for everything, then the resulting value
         x = 63.998047
b) If we convert the matrix to 16.16 fixed point format and back to
   double precision, then the resulting value
         x = 63.998047
c) If we convert the matrix to single precision floating point format
   and back to double precision, then the resulting value
         x = 0.000000

The example above is contrived, but shows that single precision
floating point introduces considerable inaccuracy when used in the
transformation matrix. Moreover, this is an *affine* transformation.
Unlike the *projective* transformation from your contrived example.

The vast majority of the existing XRENDER users are only ever doing
affine transformations. This is what matters in the real world.

We have only a single real world example of the use of XRENDER
projective transformations (if you know more, please tell me). And
this example is the xrandr tool, where the transformation accuracy
apparently was never considered to be a (serious) problem until now.
If the xrandr developers really cared about the accuracy, they would
have at least tried to implement correct rounding there. IMHO the ugly
protocol level hack is a bit of an overkill for the xrandr problem,
especially considering that an alternative solution exists:
    http://lists.x.org/archives/xorg-devel/2014-August/043644.html

Both 16.16 fixed point format and single precision floating point
format have problems and are not great choices for the transformation
matrix. But the key difference is that XRENDER already supports the
16.16 fixed point format and it is too late to remove it. While the
single precision format is just a protocol extension proposal under
review.

-- 
Best regards,
Siarhei Siamashka