Future of Math in Ogre

[drwbns]

Could we speed up debug's slowness with a sceneManager redesign, or does that have nothing or little to do with it?

[Klaim]

Could we speed up debug's slowness with a sceneManager redesign, or does that have nothing or little to do with it?

As the slowness is from the template usage in eigen, (which prevent the compiler to remove symbols when debugging) it would have nothing to do with it.

[spookyboo]

I was also looking into Bullets' math library. It it smaller than Eigen but seems fast enough (at least enough for the Playstation). Maybe also worth considering.

[vitefalcon]

I guess I will be playing the role of 'devil's advocate here . Anyhoo, I think in the end it's all for the benefit for Ogre3D

Well, it's the Eigen official docs that say explicitly that A = A.transpose() will fail due to aliasing issues.
If you want test code to show it breaking, take a look at: http://eigen.tuxfamily.org/dox/TopicAliasing.html
The second example is a = a.transpose() failing.

The point you're trying to make sounds like there's no workaround for that or that there are no solutions for it. But there is. But before that allow me to explain what 'aliasing' is to others in this context and how does that happen in Eigen.

The case in question comes from mutable matrix operation on the same instance:

Code: Select all

MatrixXi mat(3,3);
mat << 1, 2, 3, 4, 5, 6, 7, 8, 9;
cout << "Here is the matrix mat:\n" << mat << endl;
// This assignment shows the aliasing problem
mat.bottomRightCorner(2,2) = mat.topLeftCorner(2,2);
cout << "After the assignment, mat = \n" << mat << endl;

The original matrix is in the form:

Code: Select all

1 2 3
4 5 6
7 8 9

mat.bottomRightCorner(2,2) is:

Code: Select all

5 6
8 9

while, mat.topLeftCorner(2,2) is:

Code: Select all

1 2
4 5

when you do mat.bottomRightCorner(2,2) = mat.topLeftCorner(2,2); you would expect the end-result of the matrix to be:

Code: Select all

1 2 3
4 1 2
7 4 5

But, Eigen will compute that to:

Code: Select all

1 2 3
4 1 2
7 4 1

NOTE: Instead of 5 at the bottom-right corner, it is '1'. I would say this is expected because the operation is on the same 'mutable' matrix, and the value of mat(1, 1) had already been set to '1', before setting mat(2, 2) and hence the '1' is repeated in that position. This is more of a common-sense than a problem with Eigen. But Eigen can be partially blamed for its lazy evaluation, which causes this issue.

Considering this kind of operation is required by Ogre, the solution is to either use a different matrix to hold the result or use eval() to grab all values in advance, before assigning it to the same matrix like this:

Code: Select all

mat.bottomRightCorner(2, 2) = mat.topLeftCorner(2, 2).eval();

Details about this can be found here: http://eigen.tuxfamily.org/dox/TopicAli ... ngSolution

Now, let us look into transpose. The code in question would look something like this:

Code: Select all

Matrix2i a; a << 1, 2, 3, 4;
cout << "Here is the matrix a:\n" << a << endl;
a = a.transpose(); // !!! do NOT do this !!!
cout << "and the result of the aliasing effect:\n" << a << endl;

This will cause a runtime assertion like this:

void Eigen::DenseBase<Derived>::checkTransposeAliasing(const OtherDerived&) const
[with OtherDerived = Eigen::Transpose<Eigen::Matrix<int, 2, 2, 0, 2, 2> >, Derived = Eigen::Matrix<int, 2, 2, 0, 2, 2>]:
Assertion `(!internal::check_transpose_aliasing_selector<Scalar,internal::blas_traits<Derived>::IsTransposed,OtherDerived>::run(internal::extract_data(derived()), other))
&& "aliasing detected during tranposition, use transposeInPlace() or evaluate the rhs into a temporary using .eval()"' failed.

So it is not like the aliasing issues with transpose() is going to be uncaught, rather it does explicitly check for that situation and warns the user with the issue.

Now what is the solution? Use transposeInPlace().

Yes, this sort of violates the 'normal' usage of matrices, but it's not like that is a terrible blocker and they have no solutions.

It's not the size that matters, it's the performance. Expression templates to remove temporaries will make debug builds run slower. How much depends on the library itself.
Of course testing to see what hit it really has is the best thing to do. I've never used eigen, I've just used similarly written libs.

This, I have no idea myself as I haven't ever tested this. But I would be interested to try it out and see for myself the drop in FPS it causes.

I would like to point out IronNerd's post. That post sounded more like we're developing a math library rather than Ogre3D. Not that I'm condemning him or something. Those are perfectly valid points he have there. But do we want to invest time in building a cross-platform math library or module or component with support for SIMD/NEON/other platform specific methods, while other libraries have specifically solved that. Let me stress here that I am NOT trying to push Eigen. I am trying to push the usage of existing math library that has already solved our requirements and does not conflict with users having to use it for their free/hobby/commercial projects.

[masterfalcon]

I tend to agree with vitefalcon. While it would be a great achievement to write our own math library it detracts from the focus on improving the Rendering aspect of Ogre. I've reimplemented a large amount of the math using NEON and it was fun but I'm positive that there's a better way.

From what I've seen of other math libraries Eigen does certainly stand out. As long as the license is compatible(which is sounds like it is) and there are no insurmountable issues with integration I'd give it a +1.

EDIT: I can go ahead and start on this if we decide to go that way.

[vitefalcon]

I tend to agree with vitefalcon. While it would be a great achievement to write our own math library it detracts from the focus on improving the Rendering aspect of Ogre. I've reimplemented a large amount of the math using NEON and it was fun but I'm positive that there's a better way.

From what I've seen of other math libraries Eigen does certainly stand out. As long as the license is compatible(which is sounds like it is) and there are no insurmountable issues with integration I'd give it a +1.

Finally! Someone supports the notion to not reinvent the wheel

Thanks masterfalcon!

[Klaim]

EDIT: I can go ahead and start on this if we decide to go that way.

Would the idea be to wrap eigen in the implementation of the current Ogre math code interface, or replace all usage of math code by eigen code usage to definitely just use eigen?

[masterfalcon]

I'm inclined to keep it quarantined to the current Ogre math interface if possible.

[vitefalcon]

EDIT: I can go ahead and start on this if we decide to go that way.

Would the idea be to wrap eigen in the implementation of the current Ogre math code interface, or replace all usage of math code by eigen code usage to definitely just use eigen?

The idea is to wrap it to see performance and debugging impact. Then I would debug a computationally intensive demo that already exists. I was thinking of making that the water demo since the water deformation calculations are on the CPU.

[vitefalcon]

I'm inclined to keep it quarantined to the current Ogre math interface if possible.

Yes. Hiding it behind existing interface is the way to go.

[Klaim]

So, just to be clear, the point would be to get performance from the change, not to allow other people to use the same library as ogre separately, right?

It's ok to me, one step at a time. I guess conversion function from Ogre math interface to Eigen would be easy to provide once the change is done anyway.

[masterfalcon]

Where did we land on how to reference the source? Include with Ogre's source or install separately?

[Klaim]

Where did we land on how to reference the source? Include with Ogre's source or install separately?

Well it's a dependency, so... shouldn't it be in the dependency repo? Maybe with a CMake option to point to another directory with eigen sources if the user want to use another dir?
Eigen is fully header-only, right?

[CABAListic]

I'm not against using a 3rd-party math library in principle, but I share Kojack's concerns as to whether Eigen is a good fit for our needs. From the looks of it, it was designed to do much more than what we'd need. I have a feeling that we would be better off with a simpler math library specifically designed for games / 3D graphics. I mean, obviously eigen can handle that, but the template-heavy code will very likely increase compile times and complicate debugging, so we'd have to be really, really sure that those drawbacks are acceptable.

[vitefalcon]

So, just to be clear, the point would be to get performance from the change, not to allow other people to use the same library as ogre separately, right?

It's ok to me, one step at a time. I guess conversion function from Ogre math interface to Eigen would be easy to provide once the change is done anyway.

The point is to use a math library that has been worked on to make it cross-platform, SIMD/NEON capable, etc, that would benefit Ogre in terms of performance, portability and reduce the need of having to allocate resources towards working on 'math' section of Ogre3D.

I too would propose 'one step at a time' approach for this. These steps include:

• Core developers coming to a consensus of whether or not they would like Ogre3D to use an external math library.
• Explore more than one option for a math library and narrow the candidates to 2 or 3 libraries. 2 would be the best but if you're torn between more than 2, then it's always best to select the best with quantitative measurements.
• Either typedef the math datastructures (e.g. typedef Eigen::Vector3f Vector3;), or wrap existing datastructures to use the underlying math structures. Test the same computationally intensive demo for each math library on different machines, platforms and OS.
• Present results and decide on a Math library.
• Implement the usage of Math library into Ogre in the best manner possible, with least intrusion but without compromising on performance caused by wrapping it in existing classes. What I mean by that is, if there's a performance issue by wrapping the selected Math library's structure, then we should go for a typedef approach.

Where did we land on how to reference the source? Include with Ogre's source or install separately?

I'm not sure what you're quoting for your question :S

[masterfalcon]

I'll give it a try this weekend and see what how it goes.

[vitefalcon]

I'm not against using a 3rd-party math library in principle, but I share Kojack's concerns as to whether Eigen is a good fit for our needs. From the looks of it, it was designed to do much more than what we'd need. I have a feeling that we would be better off with a simpler math library specifically designed for games / 3D graphics. I mean, obviously eigen can handle that, but the template-heavy code will very likely increase compile times and complicate debugging, so we'd have to be really, really sure that those drawbacks are acceptable.

Like I stressed before, I'm not trying to push Eigen as the third-party math library. I'm only trying to push the possibility of using a third-party math library. Whether Eigen fits that bill is something we can only decide by testing and measuring. But the very first decision core developers need to make is whether they want to go with a third-party math library or create one.

[Wolfmanfx]

Regarding hiding Eigen behind interfaces would make the template idea useless (performance wise) until the user makes a static build. So i am not sure if we wont kill the math performance. I also vote for an external math (if possible and useful) and to be honest the current one is also "borrowed" from wild magic.
The question is if we could adapt some ideas from bullet or acquire/borrow code from it like we did it with wild magic (of course when the license fits). Eigen seems almost allmighty but when it kills my build times + debug performance this wont work in the long run (more wasted time).

[masterfalcon]

That is a good point. It is very much overkill. I'll do a test with bullet as well. 2.81 got a SIMD patch from Apple and they've gotten contributions from Sony before as well. So they have some good endorsements there.

[Wolfmanfx]

The only thing when we include bullet math we have to absorb it - means it has to fit our naming / code convention but we could apply patches manually from that point on. Yeah makes sense when the get patches from apple/sony

[lunkhound]

Just to comment on the reasons you've given:

[*]Complicates OGRE's licensing status. I tried to understand this: http://www.mozilla.org/MPL/2.0/FAQ.html but about halfway through my eyes glazed over...

Understandably, you're not a lawyer. Neither am I. But saying 'no' based on the fact that you haven't done enough research is not a reason. Here's how I found about mixing of licenses starting from the same page you've previously tried to understand:

You can mix any license with a MPL 2.0 licensed software. ...

Actually I don't know about that...

...and the Covered Software is not Incompatible With Secondary Licenses

Its not clear to me that the MIT license would be considered "compatible" in that sentence. Check this out:

...[MPL is] sitting between the Apache license, which does not require modifications to be shared, and the GNU family of licenses, which requires modifications to be shared under a much broader set of circumstances than the MPL.

This implies that MPL requires modifications to be shared (under some circumstances, but not as often as GPL), which makes it more restrictive than OGRE's license (which doesn't require modifications be shared). If MPL 2 allows you to change the license to something less restrictive simply by bundling it with something else, then that would seem to defeat the whole purpose of it.

[*]Templates. Slower compile times, indecipherable error messages, and unnecessary (for OGRE math).

Eigen consists of over 220 header files. The keyword "template" appears 4281 times. If we limit it to just Eigen/Core (which seems to be the minimum amount of Eigen we could use, i.e. #include <Eigen/Core>) it's still about 100 header files with over 30000 lines of code, and the "template" keyword appearing 2440 times. This is going to slow down compile times of anything that includes it, including anything that #includes stuff from OGRE. Precompiled headers may mitigate that, however.

[vitefalcon]

Eigen consists of over 220 header files. The keyword "template" appears 4281 times. If we limit it to just Eigen/Core (which seems to be the minimum amount of Eigen we could use, i.e. #include <Eigen/Core>) it's still about 100 header files with over 30000 lines of code, and the "template" keyword appearing 2440 times. This is going to slow down compile times of anything that includes it, including anything that #includes stuff from OGRE. Precompiled headers may mitigate that, however.

There clearly seems to be a misunderstanding about templates. By simply adding template files without using anything off it, none of those code get compiled. So that is not a valid point. But if you wanted to use Eigen, you only need to include the relevant header file and not the whole header file. You don't include "Eigen/Core" to just use "Eigen::Vector3f". It's just like adding Ogre.h to all files that tries to use Ogre::Root. It's a plain mistake. So all those statistics mean nothing in this context. Good collection of info though.

[MPL is] sitting between the Apache license, which does not require modifications to be shared, and the GNU family of licenses, which requires modifications to be shared under a much broader set of circumstances than the MPL.

This implies that MPL requires modifications to be shared (under some circumstances, but not as often as GPL), which makes it more restrictive than OGRE's license (which doesn't require modifications be shared). If MPL 2 allows you to change the license to something less restrictive simply by bundling it with something else, then that would seem to defeat the whole purpose of it.

Again, misunderstanding. The statement of "which does (not) require modifications to be shared" is to describe the Apache and GNU family of licenses and not MPL. Please read the whole sentence again:

Q2: Why yet another open source license?
The MPL fills a useful space in the spectrum of free and open source software licenses, sitting between the Apache license, which does not require modifications to be shared, and the GNU family of licenses, which requires modifications to be shared under a much broader set of circumstances than the MPL.

This simply implies that MPL neither enforces sharing nor enforces the notion of not sharing. This makes MPL compatible with Apache-style and GNU-family of licenses. Unlike most licenses that either is compatible with Apache-style or GNU-family licenses.

Its not clear to me that the MIT license would be considered "compatible" in that sentence.

I guess, I just answered that.

[lunkhound]

I'm inclined to keep it quarantined to the current Ogre math interface if possible.

I think one of the most difficult parts of changing out the math library will be dealing with the fact that the current Vector3 and similar classes have exposed members (i.e. x, y, z) which are being directly accessed all over the code. With SIMD, that sort of thing is frowned upon so any SIMD math library is likely to use accessor functions (setX(), getX(), although personally I prefer just x() instead of getX()). I would recommend as a first step, to refactor the existing Vector/Quaternion/etc classes to have these accessors, and fix all the rest of the code to go through the accessors.
Once that part is done, it will be far easier to "plug-in" another math lib by just implementing the current math interface on top of the other library.

There is still the various issues with alignment however.

[vitefalcon]

Yea, wrapping the current x, y, z would be hard. It sounds nice to have it as x(), y() and z(). Probably also have the options of v[0], v[1] and v[2]?

EDIT: Seems like we already have that. It's just a matter of whether or not to use that format, I guess.

[lunkhound]

Eigen consists of over 220 header files. The keyword "template" appears 4281 times. If we limit it to just Eigen/Core (which seems to be the minimum amount of Eigen we could use, i.e. #include <Eigen/Core>) it's still about 100 header files with over 30000 lines of code, and the "template" keyword appearing 2440 times. This is going to slow down compile times of anything that includes it, including anything that #includes stuff from OGRE. Precompiled headers may mitigate that, however.

There clearly seems to be a misunderstanding about templates. By simply adding template files without using anything off it, none of those code get compiled. So that is not a valid point. But if you wanted to use Eigen, you only need to include the relevant header file and not the whole header file. You don't include "Eigen/Core" to just use "Eigen::Vector3f". It's just like adding Ogre.h to all files that tries to use Ogre::Root. It's a plain mistake. So all those statistics mean nothing in this context. Good collection of info though.

From my perusal of the Eigen code, it doesn't look like its setup the way you describe. There is no "Vector3.h" header that I can see. In fact, I can't even find any definition of Vector3f. grepping all of the Eigen source for "Vector3f" turns up some comments in Core/util/memory.h, but that's about it. And headers such as Core/Matrix.h don't include any of the headers on which it depends such as Core/MatrixBase.h.
Ahh! Found where Vector3f is defined, it's actually defined by a nasty macro in Core/Matrix.h:

Code: Select all

#define EIGEN_MAKE_TYPEDEFS(Type, TypeSuffix, Size, SizeSuffix)   \
/** \ingroup matrixtypedefs */                                    \
typedef Matrix<Type, Size, Size> Matrix##SizeSuffix##TypeSuffix;  \
/** \ingroup matrixtypedefs */                                    \
typedef Matrix<Type, Size, 1>    Vector##SizeSuffix##TypeSuffix;  \
/** \ingroup matrixtypedefs */                                    \
typedef Matrix<Type, 1, Size>    RowVector##SizeSuffix##TypeSuffix;

Are you looking at the same version of Eigen? I'm looking at the latest, 3.1.2.
With the version I'm looking at, you certainly CAN'T just include Core/Matrix.h.
The file that includes all the stuff you need is called "Eigen/Core" (no .h).