[PULL] Matrix inversion and tests v1
Kristian Høgsberg
krh at bitplanet.net
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
More information about the wayland-devel
mailing list