[PULL] Matrix inversion and tests v1

Mon Jan 16 18:19:32 PST 2012

On Mon, Jan 16, 2012 at 10:20 AM, Pekka Paalanen <ppaalanen at gmail.com> wrote:
> 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.

Hi Pekka,

The series look good, I like where it's going.  I cherry-picked the
build fix for now (btw, I don't get the error, I don't even get a
warning, not sure what's going on...).

I'll hold off on merging the series for a little bit yet.  Right now
I'm trying to stabilize the code toward a snapshot release in a couple
of weeks.  If that gets unbearable, I'll just branch it and we can
continue feature work on master, but for now I'll just try to cool
down master a bit.

The other thing is that I'd like to see this series concluded with
actually using the transform for converting input and damage
coordinates.  Maybe we can even do a test-case where we can rotate or
scale a surface and verify that the input events and damage are
processed correctly.

> 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.

Very nice, very thorough work.  I'm thinking that we probably want to
just always go fo the explicit inverse though.  Typically, we'll
always need a few inverse transformation (pointer motion typically
comes in bursts) and I don't think we have a pattern where we need to
continuously update the matrix and then only compute a couple of
transform for each matrix.And I much prefer to keep it simpler and
just have the one matrix type.

> 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.

Right, the series as it is now can't cause any trouble, but I'd like
to see a few more patches to actually switch us over to using the
transforms.

Kristian

>
>
> 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