Jump to content
The Dark Mod Forums

Recommended Posts

I have switched our Matrix4 class to use the Eigen library internally (more specifically, an Eigen::Transform which can represent geometric transformations which decompose to a 4x4 Matrix). The advantages of Eigen are:

  1. It's a well-tested and respected linear algebra library, which means we don't need to maintain our own code to perform already-solved problems like matrix multiplication.
  2. It can potentially use SIMD instructions (SSE, AVX etc) to improve performance. I haven't yet looked into whether this happens automatically or whether we have to explicitly enable these optimisations.
  3. It is header-only, so should not present any build issues on the various platforms.

Our Matrix4 class still exists but it is now just a syntactic wrapper around the Eigen implementation, and several methods which performed matrix maths manually have now been changed to forward directly to Eigen methods like inverse(), transpose() etc. Since Matrix4 is now well covered by unit tests, I am pretty confident that nothing is broken because of this change, although it's still possible of course.

@greebo Next time you pull from my master branch, you will need to do two things:

  1. Issue the git submodule update -i command (or GUI equivalent, if you're using one) to populate the external/eigen directory with the Eigen git repository.
  2. Update include paths in the VS project so that external/eigen is added to the header file search paths.

Since it's already cross-platform and header-only, and the only current usage is with an existing class wrapper, I hope no other changes should be required on Windows.

  • Like 2
Link to post
Share on other sites

Nice, and interesting too. Thanks for the heads up, I'll be happy to do the necessary steps in studio once I'm updating the master again. Plus thanks for carving out all the unit tests, the test suite is really starting to grow!

With regards to the external submodule, is there a strong reason to include it through git? So far all the third-party libs have been specified as (cmake) package dependency (like libpng, libvorbis, etc.), and the Windows side has been handled by extracting the windeps zip to the working tree. Has Eigen different requirements? Or should we move more stuff to submodules?

  • Like 1
Link to post
Share on other sites
1 hour ago, greebo said:

With regards to the external submodule, is there a strong reason to include it through git? So far all the third-party libs have been specified as (cmake) package dependency (like libpng, libvorbis, etc.), and the Windows side has been handled by extracting the windeps zip to the working tree. Has Eigen different requirements? Or should we move more stuff to submodules?

There is no specific requirement for it to be a submodule — there is a package available on Ubuntu through APT, and the headers could of course be included in the windeps package. But given that it is header-only and never requires any actual library file or changes to compile/link flags, it seemed simpler to me to include it (in)directly in the source much as we do already with the libfmt library, rather than requiring changes to the windeps package. With a submodule it is very easy to update to a new version just by changing the commit hash of the submodule to point to a new tag, whereas other approaches would require more maintenance at our end (either regenerating windeps or copying a complete new Eigen tree into the source if we were using source inclusion without a submodule).

I don't suggest moving to submodules for everything though. This would not work well for things that require an actual library like libpng (and we certainly don't want to build everything from source[1]), so the windeps approach is still ideal here. It would be possible to make libfmt a submodule too, but given that it is small and unlikely to need much updating, there isn't a strong reason to do so. And of course if we find that submodules cause some unanticipated headaches, like changing their GitHub URL or regularly rewriting their history so our target commit hash no longer works, it will always be an option to fall back to treating Eigen like any other dependency (just without a library file).

[1] It has crossed my mind that perhaps we should include wxWidgets as a submodule and build it from source, given the slow release cycle on Linux and the variety of annoying GTK-related bugs. But that's a big can of worms.

Link to post
Share on other sites

Ok, I'll also update the wiki compilation articles then, because including the submodules while cloning is something I tend to forget myself. It left me scratching my head two times when trying to build something from source in the past, until I realized I might be missing something the sources expect to be there from the start.

Re libfmt: in this case I was forced to include it in the source tree, because I couldn't get it to compile with the Ubuntu libfmt package. It can be configured as header-only (by #DEFINE) or as static library, but the debian package somehow had conflicting linker flags, and I couldn't get it to link (I think it was due to the -fPIC setting).

On a related note, I obviously haven't googled yet, but would it be possible to configure the windeps as optional submodule and have Windows coders check it out on purpose? I have all the binaries in a separate repository, so this would make the compilation instructions a bit easier.

Link to post
Share on other sites

Not sure that Eigen is needed.

If you wanted to compute SVD of NxM matrix, then indeed writing it yourself would be a problem.
But what problems you can't solve easily with a 4x4 matrix? Do you perform something like Principal Components Analysis?
Does 4x4 matrix multiplication pose a problem to anyone? 😲

I'm very skeptical about any performance improvements due to this change.
Yes, you have 4xfloat and 2xdouble with SSE2, but it seriously matters only when you have arrays of data and do purely numeric operations with them.

The submodule is of course a nuisance. For instance, having a submodule breaks GitHub's integration with Hg and Svn: only Git client can fetch them.
Luckily, nobody will need to actually work with the submodule, so it won't add much confusion.

To me it looks like adding dependency without reason.

Link to post
Share on other sites
2 hours ago, greebo said:

Re libfmt: in this case I was forced to include it in the source tree, because I couldn't get it to compile with the Ubuntu libfmt package. It can be configured as header-only (by #DEFINE) or as static library, but the debian package somehow had conflicting linker flags, and I couldn't get it to link (I think it was due to the -fPIC setting).

Right, I recall having to set a #define to get it to work as header-only when I was setting up the CMake build. I think the current arrangement is fine, since it is small enough that including it in the main source tree isn't a problem.

2 hours ago, greebo said:

On a related note, I obviously haven't googled yet, but would it be possible to configure the windeps as optional submodule and have Windows coders check it out on purpose? I have all the binaries in a separate repository, so this would make the compilation instructions a bit easier.

Yes, that would certainly be an option, although Git isn't particularly suited to maintaining large binary files (checking out could become very heavy since the entire history would be downloaded, and there isn't an efficient way of tracking diffs between binaries). I don't know how large the current windeps archive is, but as a Git repository it would grow over time, and I could imagine it becoming quite large after several major updates like switching to a new wxWidgets version.

Of course if you're already maintaining the archive in a Git repository and don't encounter any problem with size, then these concerns are less relevant, but it might still make things slightly more complicated to checkout (Linux users would not want the windeps at all, but if they ran "git submodule update -i" they would get everything).

Link to post
Share on other sites
49 minutes ago, stgatilov said:

Not sure that Eigen is needed. To me it looks like adding dependency without reason.

You're right, it's definitely not needed, and I am aware of your dislike for external dependencies (which is why I'm certainly not suggesting incorporating Eigen or anything else into the main game).

However:

  • It's header-only, so we don't pay for anything we don't use at either compile or runtime.
  • I really, really don't like re-inventing wheels (or maintaining badly-reinvented wheels by others).
  • It simplifies the code at our end, since we don't need our own implementation of common functionality. Until a few weeks ago we didn't even have an operator* for matrix multiplication (I had to add one), and I'm still not sure if we have an operator+. None of these are difficult or complicated but it's just more lines of code that we shouldn't need to write because it's already a well-understood problem.
  • It has the potential to be faster due to the use of SIMD instructions. Again, we could do this ourselves but I'd rather have experts work on it rather than risk screwing it up myself.

Still, it's somewhat experimental at this stage and if it does turn out to cause some unexpected difficulties we can always back it out. I hope that won't be necessary though, since all the unit tests pass and we actually use Eigen at work so I know it is fully supported cross-platform.

49 minutes ago, stgatilov said:

If you wanted to compute SVD of NxM matrix, then indeed writing it yourself would be a problem.
But what problems you can't solve easily with a 4x4 matrix? Do you perform something like Principal Components Analysis?
Does 4x4 matrix multiplication pose a problem to anyone? 😲

It's not just the basic multiplication functionality that can be/has been replaced. This is what our getInverse() method (which calculates the affine inverse, not the matrix inverse) used to look like:

Matrix4 Matrix4::getInverse() const
{
  Matrix4 result;

  // determinant of rotation submatrix
  double det
    = _m[0] * ( _m[5]*_m[10] - _m[9]*_m[6] )
    - _m[1] * ( _m[4]*_m[10] - _m[8]*_m[6] )
    + _m[2] * ( _m[4]*_m[9] - _m[8]*_m[5] );

  // throw exception here if (det*det < 1e-25)

  // invert rotation submatrix
  det = 1.0f / det;

  result[0] = (  (_m[5]*_m[10]- _m[6]*_m[9] )*det);
  result[1] = (- (_m[1]*_m[10]- _m[2]*_m[9] )*det);
  result[2] = (  (_m[1]*_m[6] - _m[2]*_m[5] )*det);
  result[3] = 0;
  result[4] = (- (_m[4]*_m[10]- _m[6]*_m[8] )*det);
  result[5] = (  (_m[0]*_m[10]- _m[2]*_m[8] )*det);
  result[6] = (- (_m[0]*_m[6] - _m[2]*_m[4] )*det);
  result[7] = 0;
  result[8] = (  (_m[4]*_m[9] - _m[5]*_m[8] )*det);
  result[9] = (- (_m[0]*_m[9] - _m[1]*_m[8] )*det);
  result[10]= (  (_m[0]*_m[5] - _m[1]*_m[4] )*det);
  result[11] = 0;

  // multiply translation part by rotation
  result[12] = - (_m[12] * result[0] +
    _m[13] * result[4] +
    _m[14] * result[8]);
  result[13] = - (_m[12] * result[1] +
    _m[13] * result[5] +
    _m[14] * result[9]);
  result[14] = - (_m[12] * result[2] +
    _m[13] * result[6] +
    _m[14] * result[10]);
  result[15] = 1;

  return result;

versus what it now looks like:

Matrix4 Matrix4::getInverse() const
{
    return Matrix4(_transform.inverse(Eigen::Affine));
}

Reducing dozens of lines to a single line is a big win in my book. Of course I am aware that the code still exists somewhere, but it's no longer code that we ourselves have to maintain (or even read).

49 minutes ago, stgatilov said:

I'm very skeptical about any performance improvements due to this change.
Yes, you have 4xfloat and 2xdouble with SSE2, but it seriously matters only when you have arrays of data and do purely numeric operations with them.

I'm not expecting any massive performance improvements either. Performance is only a secondary concern. Even if the code runs at exactly the same speed I will be happy with the LoC reduction and the improved maintainability at our end. If a few SSE instructions here and there can slightly improve the performance of a particular operation, that's just icing on the cake.

49 minutes ago, stgatilov said:

The submodule is of course a nuisance. For instance, having a submodule breaks GitHub's integration with Hg and Svn: only Git client can fetch them.
Luckily, nobody will need to actually work with the submodule, so it won't add much confusion.

As Greebo and I discussed earlier, avoiding the submodule and using the existing dependency mechanism would be possible if it turns out to be a problem. And honestly if people are trying to interact with our Git repository using something other than Git, that's really their problem. I don't think we should avoid useful Git features just because someone somewhere might still think it's 2008 and want to check out our code using their SVN client.

Link to post
Share on other sites
30 minutes ago, OrbWeaver said:

Linux users would not want the windeps at all, but if they ran "git submodule update -i" they would get everything

That was my main concern. The whole reason the windeps are kept separate is that Linux users don't need to check out all these windows binaries. If there is no easy distinction and Linux users have to unconditionally checkout all submodules, then the point is moot.

Link to post
Share on other sites
1 minute ago, greebo said:

That was my main concern. The whole reason the windeps are kept separate is that Linux users don't need to check out all these windows binaries. If there is no easy distinction and Linux users have to unconditionally checkout all submodules, then the point is moot.

They don't have to, but there does not seem to be a convenient way for us to specify which modules should be checked out by default and which shouldn't. Either you run the command to checkout everything, or you would have to manually specify which ones to checkout (e.g. "git submodule update -i externals/eigen"), which would rapidly become annoying if we ever had more than one submodule. So I agree that it would be preferable to keep the dependency package separate for now.

Link to post
Share on other sites
  • 2 weeks later...

Ok, got everything merged, and as a bonus, it's even compiling now. 😑

That submodule is *huge*, it took me 2 minutes to get it fetched and checked out. Not sure I really like that huge tree lying around, it reminds me a bit of the boost times. But I can live with it.

For VC++ I added a pre-build script to check for the eigen sources, and if they're not present in the expected path, it will try to init the submodule itself by calling git submodule update -i. The wiki articles and the README.md file have been adjusted too for clarification.

Link to post
Share on other sites
15 minutes ago, greebo said:

That submodule is *huge*, it took me 2 minutes to get it fetched and checked out. Not sure I really like that huge tree lying around, it reminds me a bit of the boost times. But I can live with it.

That's odd, it shouldn't be that big. I just did a clean clone of Eigen into a temporary directory and it takes me just under 17 seconds, with a total of 101.68 MB downloaded (which I agree is a little heavy for some linear algebra headers). But I guess this is heavily affected by internet speed and disk performance.

However, if I do a "shallow clone" with "git clone --depth 1" it makes a huge difference: 2.4 seconds to download and only 3.14 MB. I wonder if we can make the submodule shallow by default.

Link to post
Share on other sites

I felt the urge to check the network activity when it kept me waiting, to make sure it didn't just stall - I got around 500k/sec cloning from gitlab. I probably just ran into a bad mirror.

A shallow clone of the submodule is probably a good move, since we're not really interested in the history anyway, count +1 for that. But it's not just the git pack, it's also the checkout which is fairly large, it's 1600 files (14 MB). As you put it, it's not exactly on the lightweight side for algebra :) I guess we're not really using all of that tree, are we?

Link to post
Share on other sites
1 hour ago, greebo said:

A shallow clone of the submodule is probably a good move, since we're not really interested in the history anyway, count +1 for that. But it's not just the git pack, it's also the checkout which is fairly large, it's 1600 files (14 MB). As you put it, it's not exactly on the lightweight side for algebra :) I guess we're not really using all of that tree, are we?

No, we really don't want anything outside of the top-level Eigen directory, where the headers are. But you are right, the repo contains a lot of other crud: an entire "unsupported" directory with another copy of the whole header tree, 2 megabytes of documents, tests, demos, a directory full of Fortran files...

To be honest, the main reason I went for a submodule was for simplicity, and the fact that I wouldn't be imposing extra work on you to update the dependencies package on Windows. But if you're happy to do that and would rather avoid the cruft involved in importing a whole external repo into the source tree, I'm fine with treating Eigen just like any other external dependency and skipping the submodule entirely. I'll need to check that the Ubuntu package provides what we need, but if so it should be pretty easy to update the CMake scripts to check for this rather than looking in the external/eigen directory.

Link to post
Share on other sites

That was very straightforward. As expected, the Ubuntu package worked fine and updating the CMake was trivial, since we can just use pkg-config to locate the headers. As of 131139539c3a799540 the submodule is gone (i.e. I deleted the .gitmodules, but you may still need to manually delete the external/eigen directory if it's checked out at your end).

Link to post
Share on other sites

DarkRadiant is not compiling for me:

In file included from /home/thebigh/Games/DarkRadiant/libs/math/AABB.cpp:4:
/home/thebigh/Games/DarkRadiant/libs/math/Matrix4.h:18:10: fatal error: Eigen/Geometry: No such file or directory
   18 | #include <Eigen/Geometry>
      |          ^~~~~~~~~~~~~~~~
compilation terminated.
make[2]: *** [libs/math/CMakeFiles/math.dir/build.make:63: libs/math/CMakeFiles/math.dir/AABB.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:430: libs/math/CMakeFiles/math.dir/all] Error 2
make: *** [Makefile:130: all] Error 2

 

Is Eigen now something I need to obtain on my end? I'm on Ubuntu 20. I already have libeigen3-dev installed.

Edited by thebigh
add

{ 0 | 🞵 } = funk_tastic

My missions:          the Factory Heist

Link to post
Share on other sites

In case you cloned my repository, I haven't integrated the latest changes yet, so you still need to update the submodule first. This step can be skipped once I integrated OrbWeaver's master branch.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...