[PULL] Matrix inversion and tests v1

[Pekka Paalanen]

Hi Kristian,

this patch series implements inversion for 4x4 matrices, specifically
for struct weston_matrix. It comes with a test application for both
correctness and performance.

The series starts with an irrelevant build fix, then has the
transformation stack patch I sent to the mailing list earlier. All
matrix related code is moved into matrix.[ch] files, so we can nicely
build unit tests for them. Matrix inversion is based on
LU-decomposition with partial pivoting.

I add a new type for the inverse transformation, struct
weston_inverse_matrix, that contains the decomposition. This gives us a
chance to save some cycles, if the inverse is used only few times, and
computing the actual inverse matrix would be extra work. I probably
need to add a function for getting the real inverse matrix later, since
I think it will be useful.

The LU-decomposition and the test app have some thresholds, since we
deal with imprecise computations. Currently they are adjusted for using
the weston_inverse_matrix directly, as computing the inverse matrix
into a weston_matrix will lose some precision. This is my sample of the
correctness test of inverting and verifying random matrices with
+-exponential elements:

Running a test loop for 10 seconds...
test fail, det: -0.00464805, error sup: inf
test fail, det: -0.0424053, error sup: 1.30787e-06
test fail, det: 5.15191, error sup: 1.15956e-06
tests: 6803097 ok, 1 not invertible but ok, 3 failed.
Total: 6803101 iterations.

"error sup: inf" means that the algorithm failed to invert it. The
other maximum errors are very small still, even though they exceed the
set limit of 1e-6.

The speed tests:

Running 3 s test on weston_matrix_transform()...
102412657 iterations in 2.999998 seconds, avg. 29.3 us/iter.

Running 3 s test on weston_matrix_inverse_transform()...
67685597 iterations in 3.000006 seconds, avg. 44.3 us/iter.

Running 3 s test on weston_matrix_invert()...
33456294 iterations in 3.000006 seconds, avg. 89.7 ns/iter.

Running 3 s test on computing the explicit inverse matrix...
15799110 iterations in 3.000006 seconds, avg. 189.9 ns/iter.

From these we can infer, that if we need to use the inverse matrix for
more than 7 point transformations, we are better off computing the
inverse matrix explicitly first. Total time for invert and transform N
points is, in theory:

- explicit inverse: 190 ns + N * 29 ns
- weston_matrix_invert: 90 ns + N * 44 ns

That is for my machine, and of course ignoring possible precision
problems.

Since we should never encounter near-singular matrices, we should not
have precision problems, I hope.

Since transformations are rarely used in the compositor, and the
inverse tranformation is never used, this patch set should not have any
ill effects. My testing for regressions was fairly quick, zoom still
works.


The following changes since commit 643eac56e7b0a77165e7b9d5bdb41df6f306fbd1:

  evdev: Correct warning on missing input device (2012-01-15 16:20:49 -0500)

are available in the git repository at:
  git://git.collabora.co.uk/git/user/pq/wayland-demos.git matrices-v1

Pekka Paalanen (8):
      window: remove duplicate widget_resize_handler_t
      compositor: implement a stack of surface transformations
      util: document matrices
      compositor: move matrix code to separate files
      compositor: drop inverse matrix from weston_transform
      compositor: implement inverse matrix transformation
      tests: add matrix-test
      update git ignores

 Makefile.am         |    2 +-
 clients/.gitignore  |    5 +-
 clients/window.h    |    3 -
 configure.ac        |    6 +-
 src/.gitignore      |    2 +-
 src/Makefile.am     |    2 +
 src/compositor.c    |   45 +++++-
 src/compositor.h    |   31 ++---
 src/matrix.c        |  229 +++++++++++++++++++++++++++
 src/matrix.h        |   59 +++++++
 src/util.c          |   74 +--------
 tests/.gitignore    |    2 +
 tests/Makefile.am   |   15 ++
 tests/matrix-test.c |  434 +++++++++++++++++++++++++++++++++++++++++++++++++++
 14 files changed, 806 insertions(+), 103 deletions(-)
 create mode 100644 src/matrix.c
 create mode 100644 src/matrix.h
 create mode 100644 tests/.gitignore
 create mode 100644 tests/Makefile.am
 create mode 100644 tests/matrix-test.c


Thanks,
pq