Do we really need to check if (determinant < threshold) for matrix inversion?

[Shawn Singh]

In SkMatrix44.cpp, a matrix is considered uninvertible when its
determinant is smaller than 1e-8. This is an arbitrary absolute
threshold, and valid invertible matrices can have a tiny determinant
which then makes the matrix appear uninvertible. This causes layers
in chromium to disappear because compositor thinks they can't be drawn
validly. --> https://code.google.com/p/chromium/issues/detail?id=222926

One possible bold solution - always decide the matrix is invertible,
unless the determinant is NaN or Inf (i.e. check
isfinite(determinant) or equivalent).

I tried this, and empirically, the world still seems to work. I
checked manually on various sites, ui_unittests, cc_unittests, and
compositing/transform layout tests. Only a few unit tests would need
updating.

Caveats if we would do this:
- may need to deal with some platform-dependent annoyance to get
isfinite() equivalents everywhere.
- catastrophic cancellation could occur. But I'm not seeing why this
would actually be a problem!


So I think it boils down to this: Is catastrophic cancellation really
an important issue for chromium/skia use case? Has anyone seen this
issue in chrome that motivated the arbitrary 1e-8 absolute threshold?

It seems to me that when catastrophic cancellation really does occur
in a 3d geometry scene, it's actually reasonable that the huge value
dominates and the small values get lost. We're not computing anything
in an iterative feedback loop, so cancellation errors would not
accumulate across frames of an animation. Within one frame, values
for bounding rects or transformed points that become obscenely large
is something we would need to handle correctly anyway, since they can
occur even without these "uninvertible" matrices. But to aggressively
say a matrix is not invertible just to avoid that issue seems to be
causing issues that actually don't exist?

thoughts?

~Shawn

[Antoine Labour]

I'm highly supportive of removing this sort of arbitrary limit. 1e-9*identity is perfectly invertible with no loss of precision. Even when badly conditioned, a finite matrix with poor precision is likely better than no matrix.

I'd be wary of infinite/NaN/0 values, because those, especially NaNs propagate everywhere, even possibly unrelated places.

Antoine

 

~Shawn

[Tien-Ren Chen]

I think the determinant method is correct. A matrix is invertible if and only if the determinant is 0. For any valid matrix (all the element being not NaN or Inf), the determinant can never be NaN or Inf. For very small determinant value (< 1e-8), although the matrix is technically invertible, there maybe numerical stability issue with it.

I think the real problem is that in some cases we don't need the matrix to be invertible in order to draw a layer, or to do correct hit testing. A notable example is a matrix that has all zero z-column, although the matrix is non-invertible, it is perfectly fine as all it does is to flatten along the z-axis.

On Tue, Aug 13, 2013 at 3:41 PM, Shawn Singh <shawn...@chromium.org> wrote:

[Tien-Ren Chen]

Are you sure there is no other bug with matrix calculation?

No matter how I see it, the determinant for the transformation matrix should be always -1 for the sample page in the bug report.

[Antoine Labour]

On Tue, Aug 13, 2013 at 3:55 PM, Tien-Ren Chen <trc...@chromium.org> wrote:

I think the determinant method is correct. A matrix is invertible if and only if the determinant is 0. For any valid matrix (all the element being not NaN or Inf), the determinant can never be NaN or Inf.

Technically, it can be Inf, or even NaN (Inf-Inf) with overflow (think a 2x2 matrix with FLT_MAX in each component).

 

For very small determinant value (< 1e-8), although the matrix is technically invertible, there maybe numerical stability issue with it.

But there may also not be.

First, the scale is largely independent of the precision unless you reach denorms. If you want this sort of heuristics to detect if the matrix is degenerate modulo precision, you should compare the determinant to the norm of the matrix, not as an absolute value.

But second, even a matrix with a loss of precision is more useful than no matrix, until you have no significant digit.

Antoine

[Shawn Singh]

Thanks for the feedback so far. =)

Tien-Ren, with 4x4 matrices as operators on homogeneous coordinates,
multiple different matrices can have the exact same 3d effect - just
scale all elements of the matrix by the same factor. This works
because of divide-by-w. However, the determinant of such 4x4
matrices can vary wildly depending on what scaling factor you use. So
it wouldn't necessarily always be -1.

In fact, I already tried making a patch that "normalizes" the matrix
determinant before checking for invertibility. However, ultimately
this is still just as arbitrary as the absolute threshold, and doesn't
really solve the root issue.

When you talk about "numerical stability" --> that's what I was
referring to as catastrophic cancellation in my previous post. Are
there any other instabilities that might occur that I haven't thought
about? What's your opinion about my reasoning about catastrophic
cancellation being acceptable?

And finally - I did also look into how we might be able to deal with
uninvertible transforms in the compositor code. for painting, we
would need to tell the visible_content_rect that it is full layer's
bounds, rather than an empty rect. One liner code change, and
probably should be done anyway. For drawing, the only issue might be
that we transform + inverse-transform a quad in order to determine
it's antialiasing. If we can determine antialiasing some other way
without knowing about target-space coordinates (unlikely?), then we
can render uninvertible transforms with AA, too.

Thanks!

[Tien-Ren Chen]

Oh sorry please disregard my last message. I didn't look at the matrices of the sub elements.

So basically what the page trying to do is to minify the contents to a very small layer, then put the layer very close to the observer. The matrix in question is the minifying matrix. Now I see why 1e-8 is an arbitrary limit. Yes now I agree removing the check is the right thing to do, as long as we make sure the result won't overflow to Inf.

As a less-important side question: should we try to solve the problem with all zero z-column or z-row? Technically those matrix should still render and should be considered valid, but we can't invert those by determinant method. Should we fall back to Gaussian elimination in this case?

[Shawn Singh]

When drawing, there is a flattenTo2d() opeartion that eliminates
exactly the z column and z row of the matrix, before we decide whether
it's usable/invertible or not. So I think what you're suggesting is
already accounted for =)

[Tien-Ren Chen]

Not sure if we caught all the corner cases. Here is an example that demostrate the problem:

<html>

<body>

<div style="width:5000px;height:5000px;-webkit-transform:matrix3d(1,0,0,0, 0,1,0,0, 0,0,0,0, 0,0,0,1)">

Hello Transform

</div>

</body>

</html>

Expect: "Hello Transform" shows as if there is no transform.

Actual: "Hello Transform" disappeared. Scroll range of the main frame is calculated correctly though.

Tried on both ToT and stable channel.

Interestingly, if the size of the layer is smaller, say 500x500, then the text renders correctly. Can't explain why this problem only affects big layers. Looks like it has something to do with the size of the main frame.

[Shawn Singh]

I've confirmed that the 5000x5000 version works correctly if we use
the one-liner fix I mentioned for painting. I'll try to get a patch
soon for that... and this indicates that the flattenTo2d() part that
is used when drawing quads seems to hold up correctly to your example.

But for now I would like to steer the conversation back to checking
determinant < threshould on SkMatrix. I feel like I should definitely
listen to any concerns that come up about it. =)

[Manfred Ernst]

In one of my previous companies, we used the same 4x4 matrix inversion algorithm that Skia uses, but with a threshold of zero, i.e. the matrix was only considered un-invertible, if the determinant was actually 0.0. For preventing NaNs, this is the only condition you need to check, as this algorithm can only generate a NaN when dividing by a zero determinant. Of course there is possibly a loss of precision, if the Matrix is ill conditioned, but from my experience with using the algorithm in a scenegraph on thousands of CAD models, this has never been an issue. I would suggest setting the threshold to 0 and see how it works for web content.

[W. James MacLean]

Isn't it the condition number we should be looking at? For example, 1e-8 * I_{44} has a determinant of 1e-32, but is reliably invertible as 1e8 I_{44} as it's condition number is 1.0, where I_{44} is the 4x4 identity matrix. Yes, we need determinant != 0, but it's the eigenvalue separation (captured by the condition number) that determines the numerical stability.

[Antoine Labour]

On Wed, Aug 14, 2013 at 10:30 AM, Manfred Ernst <ern...@google.com> wrote:

In one of my previous companies, we used the same 4x4 matrix inversion algorithm that Skia uses, but with a threshold of zero, i.e. the matrix was only considered un-invertible, if the determinant was actually 0.0. For preventing NaNs, this is the only condition you need to check, as this algorithm can only generate a NaN when dividing by a zero determinant.

... or a NaN (you can get a NaN determinant because of overflow, see above), or an infinity if any of the cofactors also overflow to infinity.

Agreed, the cases for which this happens is a very bad (though finite) matrix to start with.

Antoine

[Shawn Singh]

So it seems like the general consensus is that we can move forward
with simply (isfinite(det) && det != 0). I hope Skia folks will
accept it =)

Anyone who is not interested in condition numbers can stop reading here =)
-----------

I spent the past few hours trying to analyze condition numbers of
typical matrices in our code.

At a glance, it does indeed seem that condition number is the
rigorously correct value we want to check. But we have to remember
that the specific formula to compute the condition number depends on
the exact operation for which we're trying to measure the error, and
even worse, in the nonlinear case, a reasonable estimate of error
depends on the value of the input, too. The canonical condition
number defined as norm(A) * norm(Ainverse) is specifically geared to
measure error for the pure linear equation Ax = b solving for x.
Technically, in our code, we are actually doing a nonlinear operation
on 3d cartesian points (to be clear: cartesian coordinates !=
homogeneous coordinates). In the 3d cartesian world, the 4x4 matrix
operations we implement are nonlinear for translations and
perspective. I suspect that deriving the theoretically correct
condition number formula is not practical since we don't want to
assume what the inputs would be - and even then it's likely to be too
computationally costly to compute (the norm would add 12 to 16 more
std::abs() and floating-point additions, and we would have to compute
two of these norms.)

For completeness, I also tried to measure the canonical condition
number, norm(A) * norm(Ainverse), to get a rough histogram. I tried
this on poster circle - an innocent page that renders perfectly fine -
and it turns out that these animating layers are very often
"ill-conditoned" because of large translations. Very commonly the
condition number is larger than 1 million, generally agreed to be
"unstable". I even tried computing a norm that ignored the 4th column
- since technically our input is constant for the 4th column so it
shouldn't be part of the error measurement, and there were still a
decent number of ill-conditioned matrices due to perspective.

The inner 3x3 affine portion of the matrix was always extremely
well-conditioned on pages I tried, though.

Given this analysis plus the overhead of computing such condition
numbers, I think it's not worth doing. I agree with Manfred and
Antoine that truly ill-conditioned matrices (for the real
hard-to-define condition number on our nonlinear operation) are going
to be very rare and tolerable when they do exist.

[Tien-Ren Chen]

Should we also check each element of the inverted matrix, i.e. inverse->fMat[0~3][0~3]?

[Jared Duke]

On a semi-related note, I noticed that our 4x4 inversion routine lacks any special treatment of the general affine case; we check only for identity or scale + translate, then skip to the full 4x4 inversion.  Perhaps affine inversion is not common enough in our pipeline to consider the (modest) flop count reduction?

[Shawn Singh]

On Wed, Aug 14, 2013 at 5:30 PM, Jared Duke <jdd...@google.com> wrote:
> On a semi-related note, I noticed that our 4x4 inversion routine lacks any
> special treatment of the general affine case; we check only for identity or
> scale + translate, then skip to the full 4x4 inversion. Perhaps affine
> inversion is not common enough in our pipeline to consider the (modest) flop
> count reduction?

Ohh, nice catch - It's definitely worth benchmarking to find out. I
predict it would be a solid gain.

> On Wed, Aug 14, 2013 at 4:36 PM, Tien-Ren Chen <trc...@chromium.org> wrote:
>>
>> Should we also check each element of the inverted matrix, i.e.
>> inverse->fMat[0~3][0~3]?
>>

The condition number I was looking at is computed by inspecting
elements of both the matrix and its inverse. Is that what you had in
mind?

[Jim Van Verth]

I suspect the 3x4 affine invert would be a win as well.

As far as the determinant < threshold check, we in Skia had come a similar conclusion -- that in general checking against zero is enough. The only other suggestion would be to do the 1/det calculation, and then check to see if that's infinite instead, just to catch any denormals which are too small to be inverted.

[Shawn Singh]

Thanks for the input - we did have a brief discussion about condition
numbers earlier in this thread. At this time our conclusion was that
it's not worth the computation overhead to estimate a condition
number. We can find out the hard way and re-evaluate if
ill-conditioned matrices arise that really do need to be addressed.
Definitely open to hearing if there are any issues with my earlier
analysis =)

On Mon, Aug 19, 2013 at 1:22 PM, <wh...@google.com> wrote:
> The precision of invertability is related to the condition number of the matrix: http://en.wikipedia.org/wiki/Condition_number . Matrices with good condition numbers will invert well. 1e-9 * Identity has a condition number of 1 (perfect) and should invert w/o loss of precision. You can evaluate the condition number of a matrix (after checking inf/nan) to see if you got a good inverse.
>
> -Warren