7:10 a.m.
Hi,
I've traced the problem with the broken feImage filter primitive (see
https://bugs.launchpad.net/inkscape/+bug/382313 ) to a problem with
lib2geom. More specifically, Geom::Matrix.inverse() returns an incorrect
matrix. I run this simple test program:
#include <iostream>
#include <2geom/matrix.h>
int main() {
Geom::Matrix test_matrix1( 0.003333, 0.000000, 0.000000, 0.003333,
0.083333, 0.083333 );
Geom::Matrix test_inverse1 = test_matrix1.inverse();
std::cout << "Test input" << std::endl;
std::cout << test_matrix1 << std::endl;
std::cout << "Test output" << std::endl;
std::cout << test_inverse1 << std::endl;
Geom::Matrix test_matrix2( 0.003077, 0.000000, 0.000000, 0.003077,
0.076923, 0.076923 );
Geom::Matrix test_inverse2 = test_matrix2.inverse();
std::cout << "Test input" << std::endl;
std::cout << test_matrix2 << std::endl;
std::cout << "Test output" << std::endl;
std::cout << test_inverse2 << std::endl;
}
The output I see is:
Test input
A: 0.003333 C: 0 E: 0.083333
B: 0 D: 0.003333 F: 0.083333
Test output
A: 300.03 C: -0 E: -25.0024
B: -0 D: 300.03 F: -25.0024
Test input
A: 0.003077 C: 0 E: 0.076923
B: 0 D: 0.003077 F: 0.076923
Test output
A: 1 C: 0 E: 0
B: 0 D: 1 F: 0
You can see that the first matrix inversion is correct but the second is
wrong. This was tested with SVN as of yesterday on Linux.
Tav
9:20 a.m.
A bit more info.
On Sun, 2009-08-30 at 13:10 +0200, Tavmjong Bah wrote:
Hi,
I've traced the problem with the broken feImage filter primitive (see
https://bugs.launchpad.net/inkscape/+bug/382313 ) to a problem with
lib2geom. More specifically, Geom::Matrix.inverse() returns an incorrect
matrix.
In Geom::Matrix::inverse() the matrix determinate is calculated and then
compared to the constant EPSILON which is defined as 10^-5 (in coord.h).
If it is less than EPSILON the matrix is set to unity. This EPSILON is
clearly way too large for use in inverse(). For some reason a value of
10^-18 in commented out in coord.h. My guess is that the value 10^-5 was
selected for comparing pixel positions to each other but it is being
used for other purposes in the lib2geom library.
Tav
8:39 p.m.
On Sun, Aug 30, 2009 at 03:20:44PM +0200, Tavmjong Bah wrote:
> ... https://bugs.launchpad.net/inkscape/+bug/382313 ...
> More specifically, Geom::Matrix.inverse() returns an incorrect
> matrix.
In Geom::Matrix::inverse() the matrix determinate is calculated and then
compared to the constant EPSILON which is defined as 10^-5 (in coord.h).
If it is less than EPSILON the matrix is set to unity. This EPSILON is
clearly way too large for use in inverse().
njh thinks that EPSILON shouldn't be smaller than 1e-8 with the current code
& callers.
Sorry for not checking myself (I'm just about to leave), but is changing
EPSILON to 1.5e-8 enough to make this test case work?
pjrm.
2:39 a.m.
On Tue, 2009-09-01 at 10:39 +1000, Peter Moulder wrote:
On Sun, Aug 30, 2009 at 03:20:44PM +0200, Tavmjong Bah wrote:
> > ... https://bugs.launchpad.net/inkscape/+bug/382313 ...
> > More specifically, Geom::Matrix.inverse() returns an incorrect
> > matrix.
>
> In Geom::Matrix::inverse() the matrix determinate is calculated and then
> compared to the constant EPSILON which is defined as 10^-5 (in coord.h).
> If it is less than EPSILON the matrix is set to unity. This EPSILON is
> clearly way too large for use in inverse().
njh thinks that EPSILON shouldn't be smaller than 1e-8 with the current code
& callers.
Sorry for not checking myself (I'm just about to leave), but is changing
EPSILON to 1.5e-8 enough to make this test case work?
The inverse() function is used to find the bounding box of the image in
drawing coordinates. Setting EPSILON to 1.5e-8 would make this test case
work but would cause trouble if anybody wanted to use the feImage filter
with an image greater than 8000x8000 px (not common... but you never
know). (There is the question of why a matrix inversion is necessary in
the first place to find the bounding box but that is a separate issue
for a filters expert.)
Fundamentally, I think having one value of EPSILON used everywhere in
lib2geom is wrong as the way it is used is different in different
functions. Not knowing much about lib2geom, I would guess that using
EPISLON^2 in the matrix inverse function would be more reasonable.
Tav
4:08 a.m.
On Tue, Sep 01, 2009 at 08:39:35AM +0200, Tavmjong Bah wrote:
The inverse() function is used to find the bounding box of the image
in
drawing coordinates. Setting EPSILON to 1.5e-8 would make this test case
work but would cause trouble if anybody wanted to use the feImage filter
with an image greater than 8000x8000 px (not common... but you never
know). (There is the question of why a matrix inversion is necessary in
the first place to find the bounding box but that is a separate issue
for a filters expert.)
If we're literally talking px in the CSS sense (1px = 1/2688 of expected
viewing distance) then it is indeed OK not to work on images wider than about
4/3 of viewing distance (3584px) wide. The number 4/3 is one I just made up
based on trying to look at a picture and deciding how far away I need to move
from a picture for it to be comfortable to look at the whole picture;
certainly 8000px (112°) is too big for me to take in the whole picture,
even though my peripheral vision extends beyond that.
Of course it's still useful to have an error margin for e.g. zoom-related uses,
preferably an error margin bigger than a factor of 8000/3584, it's just a
question of what costs we're willing to take to do so.
Fundamentally, I think having one value of EPSILON used everywhere
in
lib2geom is wrong as the way it is used is different in different
functions.
Agreed. Presumably it arises because it's difficult to come up with the right
number to use :) .
Anyway, note that njh has now changed the calculation a little (in upstream
2geom at least), so the best number to use may now be different again.
pjrm.
5:26 a.m.
On Tue, 2009-09-01 at 18:08 +1000, Peter Moulder wrote:
On Tue, Sep 01, 2009 at 08:39:35AM +0200, Tavmjong Bah wrote:
> The inverse() function is used to find the bounding box of the image in
> drawing coordinates. Setting EPSILON to 1.5e-8 would make this test case
> work but would cause trouble if anybody wanted to use the feImage filter
> with an image greater than 8000x8000 px (not common... but you never
> know). (There is the question of why a matrix inversion is necessary in
> the first place to find the bounding box but that is a separate issue
> for a filters expert.)
If we're literally talking px in the CSS sense (1px = 1/2688 of expected
viewing distance) then it is indeed OK not to work on images wider than about
4/3 of viewing distance (3584px) wide. The number 4/3 is one I just made up
based on trying to look at a picture and deciding how far away I need to move
from a picture for it to be comfortable to look at the whole picture;
certainly 8000px (112°) is too big for me to take in the whole picture,
even though my peripheral vision extends beyond that.
While it's probably not common, one might use Inkscape to create a
picture that is meant to be looked at piece by piece (Chinese scrolls,
for example). Also, remember that one might want to use create a drawing
with higher resolution to avoid sampling errors upon export at different
resolutions.
Of course it's still useful to have an error margin for e.g.
zoom-related uses,
preferably an error margin bigger than a factor of 8000/3584, it's just a
question of what costs we're willing to take to do so.
> Fundamentally, I think having one value of EPSILON used everywhere in
> lib2geom is wrong as the way it is used is different in different
> functions.
Agreed. Presumably it arises because it's difficult to come up with the right
number to use :) .
Anyway, note that njh has now changed the calculation a little (in upstream
2geom at least), so the best number to use may now be different again.
Can someone please see that this gets patched into Inkscape 0.47 before
release. I will be gone for a week with little if any Internet
connection so I won't be able to help. Thanks.
pjrm.
Tav
6:41 a.m.
Peter Moulder wrote:
On Tue, Sep 01, 2009 at 08:39:35AM +0200, Tavmjong Bah wrote:
> Fundamentally, I think having one value of EPSILON used everywhere in
> lib2geom is wrong as the way it is used is different in different
> functions.
Agreed. Presumably it arises because it's difficult to come up with the right
number to use :) .
Might I suggest to do it in a fundamentally different way in this
particular case (matrix inverse). There are a number of different
options that come to mind that would sound a lot more reasonable than
any arbitrary constant:
- Use range arithmetic. If you using different rounding modes for the
determinant can get you numbers in a range that straddles zero I'd
say it's fair to say the matrix is essentially singular.
- If changing rounding modes is too problematic, we could always do a
poor man's version of range arithmetic using nextafter/nexttoward.
- We compute 1.0/det. If det is so small that this (or the value in the
resulting matrix with the largest magnitude) is inf(inite) there
wouldn't be much sense in computing the inverse, as we can't
represent it.
12:58 p.m.
Jasper van de Gronde wrote:
- Use range arithmetic. If you using different rounding modes for the
determinant can get you numbers in a range that straddles zero I'd
say it's fair to say the matrix is essentially singular.
This is not going to work, because a small determinant will always round to
0 regardless of the rounding mode. Rounding modes only affect what is done
to halfway cases like 0.5 when nearbyint() is called; it doesn't affect
round() or trunc().
- If changing rounding modes is too problematic, we could always do
a
poor man's version of range arithmetic using nextafter/nexttoward.
Won't work for the same reason as above; rounding has little to do with this
issue.
- We compute 1.0/det. If det is so small that this (or the value in
the
resulting matrix with the largest magnitude) is inf(inite) there
wouldn't be much sense in computing the inverse, as we can't
represent it.
I think this is the correct way to fix this (and of course review the way
EPSILON is used). We could use some more unit tests (right now I don't even
know how to run the existing ones...)
Regards, Krzysztof
--
View this message in context:
http://www.nabble.com/Broken-feImage-and-lib2geom-matrix-inversion-tp2521...
Sent from the Inkscape - Dev mailing list archive at Nabble.com.
5146
days inactive
5148
days old
inkscape-devel@lists.inkscape.org
7 comments
4 participants
participants (4)
-
Jasper van de Gronde -
Krzysztof Kosiński -
Peter Moulder -
Tavmjong Bah