ssvb xrandr: Rescale matrix to improve projective transformations accuracy
0da43a8 Aug 21, 2014
xrandr: Rescale matrix to improve projective transformations accuracy
When using projective transformations and homogenous coordinates, we
can freely multiply the transformation matrix by a constant. Optimal
selection of this constant has a huge impact on accuracy.

A naive approach is just to upscale the matrix by the largest possible
factor, only ensuring that the matrix coefficints don't excees 32767.
This somewhat reduces the relative error caused by rounding, but is
still not a silver bullet.

A more advanced approach is to focus specifically on G and H
coefficients, because they are contributing to the divisor value
and the rounding errors in them may be scaled manyfold in the
final result.

A simplified variant of this approach is to pick either G or H
coefficient, round it to the nearest value which fits 16.16 fixed
point format and use the ratio between the rounded and the original
coefficient as the constant for rescaling the matrix. After this is
done, either G or H coefficient becomes perfectly accurate and has
no rounding error on the conversion to 16.16 fixed point format.

A better solution is to try minimizing rounding errors for both
G and H at once. This patch is implementing a simple bruteforce
search for the optimal rescaling constant. The performance
should not be an issue for the xrandr command line tool, because
this is done only once per tool run.

Matrices are dumped to the console when using the '--verbose' command
line option and the accuracy can be evaluated. For example, using
the matrix coefficients from
    http://lists.x.org/archives/xorg-devel/2014-August/043624.html
provides the following results:

octave:1> {paste the original_matrix and the adjusted_matrix data}

octave:3> x = [2560 ; 1600 ; 1]
octave:4> p1 = original_matrix * x ; p2 = adjusted_matrix * x
octave:5> difference_between_p1_and_p2 = p1 / p1(3) - p2 / p2(3)

   0.0046335
   0.0024114
   0.0000000

The top two values are showing the absolute error for X and Y
coordinates. The accuracy remains good up to something like
7000x7000, but then degrades quickly.

Signed-off-by: Siarhei Siamashka <siarhei.siamashka@gmail.com>
0da43a8