1352564 - Write a version of Matrix4x4::Inverse() that doesn't require that the matrix is invertible

Status: RESOLVED FIXED

(Core :: Graphics: Layers, enhancement)

Description

[Botond Ballo [:botond]]

Currently we have two ways to invert a Matrix4x4:

  1) Invert(), which returns a boolean indicating whether the
     matrix is invertible, and modifies the matrix in-place if
     it is.

  2) Inverse(), which requires as a precondition that the matrix
     be invertible (asserting if it's not), and returns a new,
     inverted matrix.

In bug 1069417, we started annotating the types of matrices with the source and target coordinate spaces that they transform between. Since inverting a matrix makes it transform "bakwards" from the target coordinate system to the source, the return type of Inverse() is different (Matrix<Target, Source>) from the type of the object it's called on (Matrix<Source, Target>).

Invert() doesn't play nicely with this system, because it modifies the matrix in-place but you cannot (of course) change its type in-place.

It would be nice to have a method that could be used when you don't know if the matrix is invertible, but also plays nicely with the unit system. I'm thinking a new method that returns a Maybe<Matrix>.

Comment 1

[Dean Zhu]

So I am trying to look at the source code etc and I have a few questions:
1) Is there any reason Inverse() has to take a invertible matrix, would it be possible to make it check if it's invertible, and return a maybe in case it's not?
2) Is there any reason we have to invert the matrix when we check if it is invertible?

I would think 1) is a better idea, although I'm not sure if relaxing a precondition could cause any unintended behaviour.
Please let me know if there is any problem with this

Comment 2

[Dean Zhu]

Oh wait, the method Invesre we have right now doesnt allor to return a Maybe<matrix> right? Is it possible to make it return
Maybe<Matrix4x4Typed<TargetUnits, SourceUnits> >?

Comment 3

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #1)
> 1) Is there any reason Inverse() has to take a invertible matrix, would it
> be possible to make it check if it's invertible, and return a maybe in case
> it's not?

There are number of existing call sites of Inverse() in the codebase (at least 21 according to searchfox [1]), which would have to be modified to unwrap the Maybe.

Moreover, unwrapping a Maybe without checking it looks questionable to a reader, so we'd have to either add checks in those places, or add comments explaining why a check is not necessary.

Therefore, I wouldn't suggest this option.

> 2) Is there any reason we have to invert the matrix when we check if it is
> invertible?

I like this option. This is basically what Invert() does already: checks if the matrix is invertible, if not returns false, otherwise proceeds to invert.

The check to see if the matrix is invertible is just calling Determinant() and comparing it to zero. We could add a 'bool IsInvertible()' method for easier readability, and ask call sites to use that together with Inverse(). This way, we don't need to modify Inverse(), or add a new version of it.

Comment 4

[Botond Ballo [:botond]]

(In reply to Botond Ballo [:botond] from comment #3)
> There are number of existing call sites of Inverse() in the codebase (at
> least 21 according to searchfox [1])

Forgot the link here:

[1] http://searchfox.org/mozilla-central/search?q=symbol:_ZNK7mozilla3gfx14Matrix4x4Typed7InverseEv&redirect=false

Comment 5

[Botond Ballo [:botond]]

(In reply to Botond Ballo [:botond] from comment #3)
> > 2) Is there any reason we have to invert the matrix when we check if it is
> > invertible?
> 
> I like this option. This is basically what Invert() does already: checks if
> the matrix is invertible, if not returns false, otherwise proceeds to invert.
> 
> The check to see if the matrix is invertible is just calling Determinant()
> and comparing it to zero.

One thing I realized is that Inverse() still needs to compute the determinant as part of the inverse calculation. So, if we do it this way, then for invertible matrices we'll be computing the determinant twice: once to check if the matrix is invertible, and a second time to compute the inverse.

That's a bit suboptimal, although perhaps the compiler can optimize away the second computation.

> We could add a 'bool IsInvertible()' method for easier readability,

We already have IsSingular() with the opposite meaning ("not invertible"), so we can just use that instead of adding a new function.

Comment 6

[Dean Zhu]

Then, there is actually no need to implement IsInvertible() right? 
Although a method which returns a Maybe<Matrix> might be useful, it actually wouldn't differ much from calling inverse() and then casting it to the correct units. 
In bug1069417, we could have called IsSingular() and then Untransform, but as you mentioned that would require two calls to Determinant() and one cast, instead calling Inverse() once and then casting it.

I have also come up with some few doubts if you don't mind answering.
 1) Is there any disadvantage of using ToUnknownMatrix() and FromUnknownMatrix()?
 
 2) Is there any scenerio where it would benefit us not using a Maybe<T>

 3) And about the workflow, is there a need to run mach build everytime you want to compile the code or there is an alternative that I'm not aware of?

Comment 7

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #6)
> Then, there is actually no need to implement IsInvertible() right?

Right.

>  1) Is there any disadvantage of using ToUnknownMatrix() and
> FromUnknownMatrix()?

Assuming you're talking about using them at a call site like HitTestingTreeNode::Untransform(), the disadvantages are:

  - It's verbose compared to calling a function like Inverse().

  - The compiler doesn't check that we're converting to the
    right units. I could use these functions to convert a 
    Matrix<A, B> to a completely unrelated Matrix<C, D>, while
    for inverting we want to convert specifically to 
    Matrix<B, A>. By localizing the calls to these functions
    inside a function like Inverse(), we know the callers of
    Inverse() will use the correct units.

>  2) Is there any scenerio where it would benefit us not using a Maybe<T>

In cases where we know the matrix is invertible, it's more direct to just use the current Inverse() function that returns a matrix without wrapping it into a Maybe.

>  3) And about the workflow, is there a need to run mach build everytime you
> want to compile the code or there is an alternative that I'm not aware of?

If you've only modified C++ files (which should be the case for this bug), you can run |mach build binaries| which will be faster than |mach build|,

Comment 8

[Dean Zhu]

Thank you for the answers!
Is this bug closed or should I implement the method you mentioned at the beginning?

Comment 9

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #8)
> Is this bug closed or should I implement the method you mentioned at the
> beginning?

I think we should do *something* to make the code in HitTestingTreeNode::Untransform() better.

I think the options are:

  1) Use IsSingular() and the existing Inverse().
     Fod good measure, we can check if the compiler optimizes out
     the second determinant computation (if we find it doesn't,
     we may want to go with option #2 instead, because
     HitTestingTreeNode::Untransform() is a pretty hot code path).

  2) Write the new method mentioned at the beginning, and use it
     in HitTesingTreeNode::Untransform().

I'll let you pick which approach you prefer.

Comment 10

[Dean Zhu]

> we can check if the compiler optimizes out the second determinant computation
How can we check this?

Considering it being used all the time I think I agree with you, and we should use the second option proposed.

Comment 11

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #10)
> > we can check if the compiler optimizes out the second determinant computation
> How can we check this?

We could take a look at the assembly code of an optimized build.

> Considering it being used all the time I think I agree with you, and we
> should use the second option proposed.

Sounds good to me.

Comment 12

[Dean Zhu]

What should we name this new method?

Comment 13

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #12)
> What should we name this new method?

My first choice would be Inverse(), but C++ doesn't allow you to overload methods on their return type, so that won't work. TryInvert() reads well, but it may be confusing given that Invert() modifies the matrix in place and TryInvert() wouldn't. How about MaybeInverse()?

Comment 14

[Dean Zhu]

Yeah that's good.
I'm having some problems with the Maybe type. If Maybe<T> is the object I do not know how to call the methods of T, in this case being Inverse().
The other choice I have is creating the Maybe object after, and making it have the object T. I am trying to use emplace(T) but its compiling so I am not sure if it would work.

Comment 15

[Dean Zhu]

I'm going to leave now so I'll just leave a summary of my progress.

I managed to compile MaybeMatrix() but you might need to review the code as I am not too familiar with the Maybe class yet.
Then I went back to the HitTestingTreenode::Untransform() method and found out that Untransformby doesn't accept maybe<T> as an argument so that might be a problem.

I would Implementated as follows:

> Maybe<T> = maybeinverse();
> if(isNothing()) return Nothing();
> return Untransformby(T,apoint);

Is this correct?
I have come up with some few more doubts.
First I read on the other bug thread Inverse() is not typesafe, what does it mean?
As for the Implementation, how can we get the Object wrapped in the Maybe?

I'll leave the Matrix.h code aswell just in case.

> Maybe<Matrix4x4Typed<TargetUnits, SourceUnits> > MaybeInverse() const
>  {
>    typedef Matrix4x4Typed<TargetUnits, SourceUnits> InvertedMatrix;
>    InvertedMatrix clone = InvertedMatrix::FromUnknownMatrix(ToUnknownMatrix());
>    if (clone.Invert()) {
>      Maybe<InvertedMatrix> Cast;
>      Cast.emplace(clone);
>      return Cast;
>    }
>    return Nothing();
>  }

Thank you very much!

Comment 16

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #15)
> Then I went back to the HitTestingTreenode::Untransform() method and found
> out that Untransformby doesn't accept maybe<T> as an argument so that might
> be a problem.

Right, you'll need to unwrap the Maybe before passing it to UntransformBy().

You can do that by calling ref() on the Maybe, which returns a reference to the object stored inside.

> First I read on the other bug thread Inverse() is not typesafe, what does it
> mean?

I think you mean Invert(). Invert() is not typesafe in the sense that it inverts a Matrix<A,B> in-place, even though the inverted matrix is conceptually a Matrix<B,A>.

> >    if (clone.Invert()) {
> >      Maybe<InvertedMatrix> Cast;
> >      Cast.emplace(clone);
> >      return Cast;

This can be written more concisely as |return Some(clone)|. See [1] for a description of the main ways to interact with a Maybe.

[1] http://searchfox.org/mozilla-central/rev/fd99701cafa324669d950ced902d08a7450cd48b/mfbt/Maybe.h#28

Comment 17

[Dean Zhu]

I believe we can't call UntransformBy passing Nothing() as an argument right?
if so, I'm running into a problem storing the result in an object, what type would transform.MaybeInverse()[1] return?
I currently call an auto but I believe that's not a good workaround.

[1]https://dxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/HitTestingTreeNode.cpp?q=Untransform&redirect_type=direct#250

Comment 18

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #17)
> I believe we can't call UntransformBy passing Nothing() as an argument right?

Right. If the call to MaybeInverse() returns an empty Maybe, we wouldn't call UntransformBy(), we would just return Nothing() from HitTestingTreeNode::Untransform().

> if so, I'm running into a problem storing the result in an object, what type
> would transform.MaybeInverse()[1] return?

It would return Maybe<ParentLayerToLayerMatrix> (ParentLayerToLayerMatrix being a typedef for Matrix4x4Typed<ParentLayerPixel, LayerPixel> [1]).

[1] http://searchfox.org/mozilla-central/rev/fd99701cafa324669d950ced902d08a7450cd48b/layout/base/Units.h#186

Comment 19

[Dean Zhu]

Ohh, I tried using a LayertoParentLayerMatrix, ok gonna give it a shot.

Comment 20

[Dean Zhu]

Attachment: Bug1352564.patch

Comment 21

[Botond Ballo [:botond]]

Comment on attachment 8853776 [details] [diff] [review]
Bug1352564.patch

Review of attachment 8853776 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good, thanks! I have just a few cosmetic comments:

::: gfx/2d/Matrix.h
@@ +1235,5 @@
>      MOZ_ASSERT(inverted, "Attempted to get the inverse of a non-invertible matrix");
>      return clone;
>    }
>  
> +  Maybe<Matrix4x4Typed<TargetUnits, SourceUnits> > MaybeInverse() const

nit: there's no need to put a space between > > any more (since C++11)

@@ +1245,5 @@
> +    }
> +    return Nothing();
> +  }
> +
> +  

nit: one blank line between methods is sufficient

::: gfx/layers/apz/src/HitTestingTreeNode.cpp
@@ +254,5 @@
>        CompleteAsyncTransform(
>          mApzc
>        ? mApzc->GetCurrentAsyncTransformWithOverscroll(AsyncPanZoomController::NORMAL)
>        : AsyncTransformComponentMatrix());
> +  typedef Maybe<ParentLayerToLayerMatrix4x4> InvertedMatrix;

There's no need to introduce a typdef for this one use - just use the underlying type directly.

@@ +255,5 @@
>          mApzc
>        ? mApzc->GetCurrentAsyncTransformWithOverscroll(AsyncPanZoomController::NORMAL)
>        : AsyncTransformComponentMatrix());
> +  typedef Maybe<ParentLayerToLayerMatrix4x4> InvertedMatrix;
> +  InvertedMatrix clone = transform.MaybeInverse();

I would call this variable 'inverse'.

Comment 22

[Dean Zhu]

Attachment: Bug1352564.patch

This should be good now.

Comment 23

[Botond Ballo [:botond]]

Comment on attachment 8853778 [details] [diff] [review]
Bug1352564.patch

Review of attachment 8853778 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!

Comment 24

[Botond Ballo [:botond]]

Comment on attachment 8853778 [details] [diff] [review]
Bug1352564.patch

Review of attachment 8853778 [details] [diff] [review]:
-----------------------------------------------------------------

One thing I realized is that this patch does not apply on top of the patch in bug 1347157 - it applies on top of the code prior to that patch.

However, since the patch in bug 1347157 has not been committed yet, that's fine - I'm just not going to commit that patch, and will commit this instead.

Comment 26

[Botond Ballo [:botond]]

Pushed to Try server: https://treeherder.mozilla.org/#/jobs?repo=try&revision=3a952f514f6a7b59b2bf351e291278deeffa65a4

Comment 27

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6544bde4a06e
Add a method to invert a Matrix4x4 if it's invertible. r=botond

Comment 28

[Botond Ballo [:botond]]

(In reply to Pulsebot from comment #27)
> Pushed by [e-mail]:
> https://hg.mozilla.org/integration/mozilla-inbound/rev/6544bde4a06e
> Add a method to invert a Matrix4x4 if it's invertible. r=botond

^ I didn't notice that this patch didn't have you set as the author, so I accidentally committed it with me as the author. Sorry about that.

For future patch uploads, you may want to ensure the patch has you set as the author. (Let me know if you need help getting mercurial to do that.)

Comment 29

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/6544bde4a06e

Comment 30

[Dean Zhu]

> ^ I didn't notice that this patch didn't have you set as the author, so I
> accidentally committed it with me as the author. Sorry about that.
It's ok don't worry about that.

> For future patch uploads, you may want to ensure the patch has you set as
> the author. (Let me know if you need help getting mercurial to do that.)
Yeah please, I tried configuring my mercurial with no success. apart from ~/mercurial.ini and .hg/.hgrc in the local repo is there any file I should touch?

Comment 31

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #30)
> > For future patch uploads, you may want to ensure the patch has you set as
> > the author. (Let me know if you need help getting mercurial to do that.)
> Yeah please, I tried configuring my mercurial with no success. apart from
> ~/mercurial.ini and .hg/.hgrc in the local repo is there any file I should
> touch?

What command are you using to create the patch?

Comment 32

[Dean Zhu]

I used to the hg qnew thing and then tried using the hg commit you reccomended, but it popped me into an editor similar to vi/vim and I wasn't able to navigate that properly so in the end I ditched it.
But now that you mentioned it, it did write more information on the .patch, is there anyway to change the editor?

Comment 33

[Dean Zhu]

That was a bad question, got the answer after some googling.
As the header I have this: 

> # HG changeset patch
> # User Dean <[e-mail]>
> # Date 1491254705 -7200
> #      Mon Apr 03 23:25:05 2017 +0200
> # Node ID 4f492a999a45a5986b8f7d4aff79ea548ea60f5d
> # Parent  31810a9548fcede48be099fc9823fd2710616d64

Is it good?

Comment 34

[Dean Zhu]

And as a follow up, I have loads of doubts with how all the code interacts together and I've only seen a little part regarding the coordinate space etc. If a want to be a long term contributor, what do you reccommend I do? And at what point should I stop fixing the "easier" bugs?

Comment 35

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #33)
> > # HG changeset patch
> > # User Dean <[e-mail]>
> > # Date 1491254705 -7200
> > #      Mon Apr 03 23:25:05 2017 +0200
> > # Node ID 4f492a999a45a5986b8f7d4aff79ea548ea60f5d
> > # Parent  31810a9548fcede48be099fc9823fd2710616d64
> 
> Is it good?

Yup! It was that "User" line that was missing in the previous patches.

(In reply to Dean Zhu from comment #34)
> And as a follow up, I have loads of doubts with how all the code interacts
> together and I've only seen a little part regarding the coordinate space
> etc. 

That's normal. The Mozilla codebase is very large, there are many parts of it that I don't know, either :)

> If a want to be a long term contributor, what do you reccommend I do?

I would keep working on mentored bugs until you become more familiar with the codebase. We have mentored bugs with a variety of difficulty levels ranging from "good first bugs" like bug 1347157, to large projects that require an experienced contributor.

If you'd like some recommendations, let me know, or you can you can use this tool [1] to find some.

> And at what point should I stop fixing the "easier" bugs?

By this point, you probably don't want to work on "good first bugs" any more, you can go on slightly more difficult ones. Sometimes it's hard to estimate the difficulty of a bug just by reading the description, so you can ask the bug's mentor: "I've fixed bugs ___ and ___ so far, do you think this bug is a good fit for me?".

[1] https://www.joshmatthews.net/bugsahoy/

Comment 36

[Dean Zhu]

Got it, thank you very much for everything!

Comment 37

[Dean Zhu]

> If you'd like some recommendations, let me know, or you can you can use this tool [1] to find some
I did look at bugzilla, but I am not sure which bugs to take now. It would be awesome if you could reccommend me some other bugs. I'm mostly familiar with C++, but I have been in touch with java, js as well.
As a side question, if my main interests are data structures, algorithms (mostly the computaional branch of comp. science). Is there any specific team which focuses or is in touch with these areas in mozilla?

Comment 38

[Botond Ballo [:botond]]

(In reply to Dean Zhu from comment #37)
> I did look at bugzilla, but I am not sure which bugs to take now. It would
> be awesome if you could reccommend me some other bugs. I'm mostly familiar
> with C++, but I have been in touch with java, js as well.
> As a side question, if my main interests are data structures, algorithms
> (mostly the computaional branch of comp. science). Is there any specific
> team which focuses or is in touch with these areas in mozilla?

C++ bugs that touch on data structures and algorithms are most likely to be found in the Core component. You can look through the list of mentored bugs in the Core component [1] and see if anything catches your interest.

Through a brief look I found bug 820672 and bug 1142497, but there's probably plenty more.

[1] https://bugzilla.mozilla.org/buglist.cgi?emailtype1=regexp&resolution=---&email1=.%2B&emailbug_mentor1=1&product=Core&query_format=advanced

Comment 39

[Dean Zhu]

I'll make sure to check those up, thanks!