Hi Barend, On Thu, Mar 26, 2009 at 4:19 AM, Barend Gehrels <barend@geodan.nl> wrote:

Hi Kornel,

...

My goal is to assess the initial interest in such an GSoC proposal idea before preparing and posting a more detailed description.

This is very nice to hear. We (Bruno Lalande and I) are creating a generic geometry library (ggl), which is 2D/3D and could be used for geometry / gis, but also for games. I've more the GIS approach. Bruno has more the generic geometry / game approach.

It would be interesting to work this out further. If you are interested you can contact us via the list or off-list.

If Kornel's GSoC proposal ends up being geared towards extending ggl 3D functionality (which I think would be great), perhaps you and Bruno Lalande could serve as co-mentors for the project? I think something similar was done in the past with Mariano Gabriel Consoni working on Jeremy Pack's Extension / Reflection library - the official Boost mentor was Hartmut Kaiser but Jeremy was also involved in some capacity. Best, Stjepan

On Fri, Mar 27, 2009 at 5:34 PM, Bruno Lalande <bruno.lalande@gmail.com> wrote:

You had the same idea as me and Barend, and like you I think it would be great. Unfortunately we had a private discussion with Kornel about that, and it seems that the idea of working by extending our library (or Luke's one or Brandon's one) doesn't really seduce him. It would have been a pleasure for us to help him in that task.

We did however agree that a common "root" would be nice, and would allow for easier intermixability of the libraries. The reason on not working in the library was that my proposal was basically going a completely different way. -- regards, Kornel Kisielewicz

Kornel Kisielewicz wrote:

On Thu, Mar 26, 2009 at 3:48 PM, Thomas Klimpel <Thomas.Klimpel@synopsys.com> wrote:

...

Kornel Kisielewicz wrote:

...

Sure, Boost has a linear algebra library graph algorithms, and a proposed geometry library, yet what is missing is a high-performance low-dimensional linear algebra library (vectors and matrices up to the 4th dimension ).

Do you know eigen2? What do you think of it? It's not a boost library, but its license seems to be acceptable.

After a quick look at it, it seems nice ( however i wonder about it's performance considering it treats vectors as 4x1 matrices, and all vectors and matrices are defined for any given number of dimensions -- something that UBLAS does already ). What I would want to see however is an optimized library defining 3/4d vectors/matrices and common 3d computational geometry tasks optimized for speed. And additional thing that I'd like it to be is to allow as readable code as possible and to have it integrated with other boost mechanisms.

It sounds to me like such a thing would need to employ archetecture specific techniques such as compiler intrinsics and inline-assembly to be in any way competitive in terms of performance with what probably exists in closed source development shops. Also, these things are best offloaded to the GPU if possible, and that code isn't written in C++. If the thing that makes the library unique is that it provides only a subset of the capabilities of UBLAS or eigen2 that doesn't sound very compelling. Perhaps if you were more specific about which common 3d computational geometry tasks you have in mind, how you would like them to be optimized for speed and whether/how you intend to make them robust to numerical error. Perhaps the focus should be on implementing common geometry primitives in terms of ie. UBLAS where appropriate and then address performance issues in UBLAS when they become apparent rather than reinvent the linear algebra wheel as a premature optimization. If a faster implementation of low-dimensional linear algebra is possible these should become patches to UBLAS specializing its algorithms, rather than a competing library. Luke

I've been using Boost.Thread to implement an asynchronous task execution service, and when I run Valgrind I come across a fair number of reported memory leaks. Most of them are obviously my fault (there are some worker threads not being properly destroyed), but there are a few that I'm not clear from the stack trace whether or not they are under my control. Are there any known memory leaks in Boost.Thread? The only thing that I've identified as a definite leak is in boost::this_thread::disable_interruption - it leaks 8 bytes from a TLS variable whenever it is constructed and destroyed by a non-Boost thread (at least on Linux.) This is obviously irrelevant for practical purposes, but I'm not sure if it's a good idea for something intended to implement a proposed C++ standard library to have known memory leaks. Thanks, Gregory Peele, Jr. Applied Research Associates, Inc. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Joel Falcou Sent: Thursday, March 26, 2009 12:00 PM To: boost@lists.boost.org Subject: Re: [boost] [gsoc] Interest check for 3d geometry proposal Simonson, Lucanus J a écrit :

It sounds to me like such a thing would need to employ archetecture specific techniques such as compiler intrinsics and inline-assembly to be in any way competitive in terms of performance with what probably exists in closed source development shops. Also, these things are best offloaded to the GPU if possible, and that code isn't written in C++. simd intrinsic is actually enough but last time I proposed something on those lines, it was dismissed as useless ....

Gpu are limited by the speed of the bus and you'll end up spending too much time sending data back and forth. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Joel Falcou wrote:

Simonson, Lucanus J a écrit :

...

It sounds to me like such a thing would need to employ archetecture specific techniques such as compiler intrinsics and inline-assembly to be in any way competitive in terms of performance with what probably exists in closed source development shops. Also, these things are best offloaded to the GPU if possible, and that code isn't written in C++. simd intrinsic is actually enough but last time I proposed something on those lines, it was dismissed as useless ....

A new implementation of polygon clipping was dismissed as useless when I proposed it. You just need to find the people who see the value in the idea. In fact, a simd upgrade to UBLAS could be very compelling, however, you won't convince people with an idea. You need to show them working code and data showing the performance benefits. I found the people who saw the value in a new polygon clipping library, implemented it for them and when those who dismissed the idea originally saw the benchmark data they acknowledged that there was value after all. Even without simd, optimized matrix operations that take things like cache-behavior into account are dramatically faster than naïve implementations. This is why people charge money for those things, it is worth it. I know I dismissed the idea of simd boost library originally, but you could easily convince me I was wrong if you show me the evidence to prove it. Regards, Luke

Le Ven 27 mars 2009 03:00, Fernando Cacciola a écrit :

To measure the convenience of using the GPU against the slow down of the bus bottleneck depends on what you offload to the GPU.

The OP want to offoad 4 element vector operation ont he GPU, one at a time ... It doesn't requir emuch more analysis to see it'll fail.

Stating that *G*raphics algorithms, among all things, wouldn't gain much from using the *Graphics*PU can't make sense IMO. Otherwise, there wouldn't be any reason to have a GPU to begin with (or GPUs would still be just dumb renderers as they used to be in the distant past) FWIW you can google for the term GPGPU to see how the field of computing in the GPU is advancing.

We've been digging GPGPU since two years now so we start to knwo when it fails and when it does not. Small amount of data is usually a bad start, small amount of dtata + few operations is road to disaster. Hence my remark concerning the OP idea. FYI, some graphic algorithm horribly fail in term of efficiency on GPU. I don't consider havign a speed-up of 6 or 8 with a GPU for n optical flow algortihm a success. BEst GPGPU alorithm efficiency are achieved with algorithm that mimick the operation density of 3D rendering (database search, N-bod like applciation etc). Offloading a few 1x4 vector multiply won't cut it

On Thu, Mar 26, 2009 at 4:52 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:

Kornel Kisielewicz wrote:

...

On Thu, Mar 26, 2009 at 3:48 PM, Thomas Klimpel <Thomas.Klimpel@synopsys.com> wrote:

It sounds to me like such a thing would need to employ archetecture specific techniques such as compiler intrinsics and inline-assembly to be in any way competitive in terms of performance with what probably exists in closed source development shops.

That's true. However, it's far easier to optimize a 3d specific library, than to optimze uBLAS.

 Also, these things are best offloaded to the GPU if possible, and that code isn't written in C++.

If you need 128kb of data to generate a single vector handled by the GPU it's not always better to take the overhead of sending data back and forth -- sometimes it's a lot more convienient to do the calculations locally.

If the thing that makes the library unique is that it provides only a subset of the capabilities of UBLAS or eigen2 that doesn't sound very compelling.

A subset, and a overset at the same time. Having a base 3d vector/matrix library, I'd like to implement 3d-specific computational geometry algorithms over it. Basically it aims at a different audience than uBLAS. uBLAS is aimed at linear algebra computations with variable size matrices, while the library I propose is geared specifically towards 2D/3D. In this field, most of the code of uBLAS is not needed. Notice that even CGAL has a separate treatment of Point_2 and Point_3 (and deriving geometry) from Point_d. However, the major difference is building a set of 3d-space-specific (e.g. not used/applicable in higher dimensional space) computational geometry algorithms and structures on top of the vector/matrix implementation, directed by the needs of the industry. Also note: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Effective_UBL... section section : Fixed size vector or matrices There we have something called bounded_vector, which should be the solution that we want to have for computer graphics, as we read : "The above runs just as quickly as a hand crafted vector3 which does not use uBLAS". Unfortunately later we read: "The only negative impact is that the vector3 always store a "size" member which in this case is redundant." ... and this is a overhead that is something that can't be accepted from a graphics engine's point of view.

Perhaps if you were more specific about which common 3d computational geometry tasks you have in mind, how you would like them to be optimized for speed and whether/how you intend to make them robust to numerical error.

I can write a detailed proposal once I know that there's at least a remote chance of acceptance in the form of my original proposal. However a generic guideline would be all of the intersection, containment, storing and ordering structures/algorithms that are used in real-time graphics.

Perhaps the focus should be on implementing common geometry primitives in terms of ie. UBLAS where appropriate and then address performance issues in UBLAS when they become apparent rather than reinvent the linear algebra wheel as a premature optimization.  If a faster implementation of low-dimensional linear algebra is possible these should become patches to UBLAS specializing its algorithms, rather than a competing library.

The fundamental design decisions of UBLAS (the one with the size for example) make such implementations hard. Anyway, considering the usage of UBLAS, the project would change to a Computational Geometry library implementation anyway. What I DO want to have however, is a transparent compatibility with UBLAS. -- regards, Kornel Kisielewicz

On Fri, Mar 27, 2009 at 4:31 AM, Patrick Mihelich <patrick.mihelich@gmail.com> wrote:

I hate to rain on your enthusiasm, but I agree with Luke that your high-performance low-dimensional linear algebra library is not very compelling. You will only be reinventing the wheel. This problem is already solved beautifully by Eigen2, which you should take a second look at - unlike uBLAS, it has first-class support for fixed-size vectors/matrices and does very clever SIMD optimizations. There is also Sony's Vector Math library in Bullet, I believe. These have liberal licenses - not so liberal as Boost, but good enough.

It's not much reinventing the wheel -- a 3d vector/matrix/quaternion library without optimizations can be written in under a week, the main work of the proposal would be data structures and algorithms that would be built over it.

A selection of 3-dimensional geometry algorithms could be interesting, though. That would already be meaty enough for a GSOC project. My suggestion would be to work with Barend & Bruno and simply write your algorithms using their primitives, Point etc. (...) and I think you will have much more of an impact integrating with an existing geometry library than writing your own from scratch.

There are some problems with naming conventions ( as to the standard used in CG3D ), and also the fact that only the point class (and maybe segment) would be of any use to me. However this is compelling, as I would be working on the things I planned from almost scratch anyway, but from the outside it would look like expanding something existing ;). -- regards, Kornel Kisielewicz

On Fri, Mar 27, 2009 at 5:03 AM, Fernando Cacciola <fernando.cacciola@gmail.com> wrote:

...

That's true. However, it's far easier to optimize a 3d specific library, than to optimze uBLAS.

Why?

Can you give us a simple but concrete example of the sort of optimization that would be easier in a 3d specific lib instead of uBLAS?

Example : Considering that each vector in uBLAS holds a "size" attribute, you can't count on an array of 4D vectors to be memory aligned for stream processing.

Or by optimization you are referring to a distinct design like having contant-size vectors/matrices?

That mostly. uBLAS has those too, however the additional (unneccessary) size field is very discomforting.

IMO, Luke's point is that you can't even start talking about highy optimized graphics without accountably considering GPU. That is, you can't decide to do a computation in the CPU vs the GPU just because you feel is better... there have to be an objetive measurable rationale behind such as decision.

And it usually is.

But then, a Boost library cannot be implemented in, say, CUDA for example, only in C++, so at the end of the day it might turn out that Boost just isn't the proper place to host such a project.. not if *high* performance is the ultimate goal, since *that* might only be achievable using GPGPU, which can't be expressed in C++.

But the parts that are expressed on the CPU side can be. One example is object hierarchy via oct or kd trees.

Your statement above makes the appearance that you think vector/matrices are specially important for geometric computing... they are not... just look at the support for those within CGAL to get an idea.

Even CGAL has separate classes for 2d/3d versions of their data structures if I may point out ;).

No doubt very simple, and in fact const-sized, vectors/matrices are needed for CG. So uBLAS is indeed overkill.

Yes.

Even the most exotic uses of matrices within CG.. say polar decomposition for key frame animation, are sufficienty uncommon that they could even be left out.

Client-side transformations within 3D space aren't exotic. Mesh transformations for animations aren't either. However that's not the case with vectors.

...

However, the major difference is building a set of 3d-space-specific (e.g. not used/applicable in higher dimensional space) computational geometry algorithms and structures on top of the vector/matrix implementation, directed by the needs of the industry.

Which computational geometry *data structures* can be built on top of a vector/matrix library? I mean, you will need to represent points and vectors, sure, but these are too primitives to say "on top of vectors and matrices".

Structures for commonly used primitives ( spheres, lines, aaboxes, boxes, planes, rays ), following them are intersection and containment tests using those structures, bounding calculations, following them we containment structures ( octrees, kd-trees, BSP, loose octrees, BVH, spatial indexing in general using one of the algoithms, etc ). There's also the topic of tesselation, triangulation, culling, visibility determination etc. I doubt that all could be done in 3 months, but I'm pretty damn sure it would be faster to build them from basic vector blocks then from uBLAS. -- regards, Kornel Kisielewicz

On Fri, Mar 27, 2009 at 12:23 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:

Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:

...

One example is object hierarchy via oct or kd trees.

Would you like to implement these spatial containers?  I think this would be a very useful contribution.  Ideally your implementation would be generic, i.e. usable with fixed-size point types or the variable-size uBLAS types; at the end of the project we would then be able to evaluate the benefit of removing the size field.  2D & 3D please.

This is exactly my intention.

- Although I doubt that wasting a word on a size field has much effect on speed, I would want to avoid it when dealing with large collections of points because of the memory overhead.

I'm not too much worried about the memory, as I am about data alignment. Also, in the case of 4d vectors, you'd have 5 values, which doesn't scale well ( 4*32 bits = 128bits which is nice -- an addition would ruin this niceness ).

- I have using uBLAS for some simple 2D matrix transformation and found it a little bit more difficult than I expected; a special-purpose API, even if implemented as a thin wrapper around uBLAS or something else, would have the benefit of simplifying things for the end user.

Fully agreed. -- regards, Kornel Kisielewicz

On Fri, Mar 27, 2009 at 11:50 AM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:

Kornel Kisielewicz wrote:

...

Also, in the case of 4d vectors, you'd have 5 values, which doesn't scale well ( 4*32 bits = 128bits which is nice -- an addition would ruin this niceness ).

Multiplication by 4 faster than multiplication by 5?  Maybe, but probably premature optimisation :-)

I think he meant that an array of four 4d vectors would fit nicely in the 128 bit registers of a say, a Playstation, whereas an array of four 4d vectors with an additional size member would not. --Michael Fawcett

On Fri, Mar 27, 2009 at 5:26 PM, Emil Dotchevski <emildotchevski@gmail.com> wrote:

The main issue is that most software developers don't need such a library; only game developers do,

What about academics?

but you can't get them to agree on the details. I have worked in the game industry long enough to see that not only each team has their own "math" library that's slightly different than everyone else's, but also many teams periodically end up rewriting it.

While I agree with the experience, I disagree that it supports the statement. Many if not most game developers also write their own shared pointers, their own RTTI, their own threads, own filesystem wrappers, own string classes and even own containers... from the two commercial game engines I had a pleasure to see, those weren't better and usually even worse than those from STL/boost. It's more about the mentality of game programmers who usually have a very high self-esteem, and tend to think "I'll do it better". But that doesn't mean that there are no reasonable game programmers out there, which are already using boost versions of the forementioned libraries, and wish that boost included a 3d geometry oriented library also... -- regards, Kornel Kisielewicz

On Fri, Mar 27, 2009 at 9:42 AM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:

On Fri, Mar 27, 2009 at 5:26 PM, Emil Dotchevski <emildotchevski@gmail.com> wrote:

...

The main issue is that most software developers don't need such a library; only game developers do,

What about academics?

Similar libraries are used by many developers for sure, but in my experience working with academics, their focus is very different.

...

but you can't get them to agree on the details. I have worked in the game industry long enough to see that not only each team has their own "math" library that's slightly different than everyone else's, but also many teams periodically end up rewriting it.

While I agree with the experience, I disagree that it supports the statement. Many if not most game developers also write their own shared pointers, their own RTTI, their own threads, own filesystem wrappers, own string classes and even own containers... from the two commercial game engines I had a pleasure to see, those weren't better and usually even worse than those from STL/boost. It's more about the mentality of game programmers who usually have a very high self-esteem, and tend to think "I'll do it better". But that doesn't mean that there are no reasonable game programmers out there, which are already using boost versions of the forementioned libraries, and wish that boost included a 3d geometry oriented library also...

I have not had a game development job for the last 3 or so years but I would be very surprised if things have changed significantly. In part, the problem is in the "I'll do it better" mentality but the other reasons are ignorance (what do you mean shared_ptr doesn't necessarily allocate memory?) and a desire to have control over all critical systems in the game (what would I do if I want shared_ptr to have 16-byte alignment?) Note, I'm not trying to justify this attitude, I'm just stating the facts as I've seen them. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

On Fri, Mar 27, 2009 at 4:50 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:

Kornel Kisielewicz wrote:

...

...

- Although I doubt that wasting a word on a size field has much effect on speed, I would want to avoid it when dealing with large collections of points because of the memory overhead.

I'm not too much worried about the memory, as I am about data alignment.

Why?  Do you have some motivating application where memory doesn't matter but unaligned accesses are expensive?  If you have a motivating application please tell us about it.  My comment that _I_ would want to avoid wasting memory is because I have a memory-constrained application in front of me.  Code for a library like Boost will end up in lots of different applications with different constraints, and it really ought to be "good all round" to satisfy all potential users.

You misunderstood me. What I meant that out of the two problems, having 25% more memory usage, and having to deal with structures that don't align to architecture standards, the latter is more disturbing to me. Not that I like the former, memory is also an important issue here.

...

Also, in the case of 4d vectors, you'd have 5 values, which doesn't scale well ( 4*32 bits = 128bits which is nice -- an addition would ruin this niceness ).

Multiplication by 4 faster than multiplication by 5?  Maybe, but probably premature optimisation :-)

This comes specifically from the architectural point of view. In this case it's about alignment for SIMD instructions, and cache/bus size issues. 128bits is nice, more without a serious reason is not. -- regards, Kornel Kisielewicz

Simonson, Lucanus J wrote:

While I see us focusing on the value of what might be produced in a GSOC project, I think this is the wrong perspective to take.

Really? Do you want to live in a socialistic country where people are so graceful (irony!) to give you some instructive work, because the value produced by your work is not important?

There is a high probability that the only value produced is the student learns some things.

This probability exists indeed, but this is no excuse for not trying to produce value. It's not so easy to produce value, so we sometimes have to learn from our mistakes. So let's not deprive the students of that possibility by declaring that the value of their work is not important.

Instead of asking what helps us we should ask what makes a good learning experience for the student. If you want the project to turn into something real then you need to take responsibility for doing the work yourself after the students run out of time.

Why should I ask somebody to do something, if it's not sufficiently important to me? Perhaps I don't want to directly use the produced source-code verbatim, but I certainly want to benefit from the experiences of the project.

That probably amounts to more work than just doing it yourself from the start. Mentoring should be viewed as akin to charitable giving. Instead of asking what valuable code they can produce, let's ask what valuable experience we can give.

Mentoring has indeed something to do with "charitable giving", but the giving should also include that the project itself is well chosen to start with. If the project is not worth it, we should be honest enough to tell student, instead of secretly thinking that it is not really important. Regards, Thomas

On Fri, Mar 27, 2009 at 3:36 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:

Kornel Kisielewicz wrote:

...

I doubt that all could be done in 3 months, but I'm pretty damn sure it would be faster to build them from basic vector blocks then from uBLAS.

In a previous summer of code the focus on 2D spatial query data structures failed to yield correct or fast implementations, and the API was not suitably generic for boost.  Is it realistic to expect better for 3D spatial query data structures this time around?

I believe so. I believe that I have the neccessary skills to execute a project like that with at least "should be improved but works well" quality.

students run out of time.  That probably ammounts to more work than just doing it yourself from the start.  Mentoring should be viewed as akin to charitable giving.  Instead of asking what valuable code they can produce, lets ask what valuable experience we can give.

Please remember that not all students here are only for the experience or the money. My motivation for example is to take a chance on having code I've written included some day in boost. If I assumed that there's no chance for that, I wouldn't bother -- there's nothing more depressing than writing code that no one cares about. -- regards, Kornel Kisielewicz

Fernando Cacciola wrote:

Hi Kornel,

FWIW, after all this thread I still feel that it not sufficiently clear what you propose to work on, and how do you plan to manage to apparent or actual overlap between your proposal and related projects.

So, can you TOP POST a message with summary of your proposal but with sufficient detail so potential metors can evaluate it?

Make sure to contrast that very carefully with exiting libraries and proposals, inclusing Quaternions (which already exists), Boost.SIMD, Spatial Indexes from Federico Fernandez, GTl and GLL.

One thing boost doesn't have is a fixed-size matrix class, which could be used with boost::array as a building block for a lot of the more game-specific tech involved. Seems to me a boost::matrix class (essentially a 2d boost::array) would be of reasonable scope/difficulty for a GSOC project. If there's time left over, one could investigate making optimized rotations, dot projects, reflections and the like as freestanding functions/operators in a special namespace somewhere. -t

On Fri, Mar 27, 2009 at 2:37 PM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:

On Fri, Mar 27, 2009 at 9:33 PM, troy d. straszheim <troy@resophonic.com> wrote:

...

Fernando Cacciola wrote:

...

Hi Kornel,

FWIW, after all this thread I still feel that it not sufficiently clear what you propose to work on, and how do you plan to manage to apparent or actual overlap between your proposal and related projects.

So, can you TOP POST a message with summary of your proposal but with sufficient detail so potential metors can evaluate it?

Make sure to contrast that very carefully with exiting libraries and proposals, inclusing Quaternions (which already exists), Boost.SIMD, Spatial Indexes from Federico Fernandez, GTl and GLL.

One thing boost doesn't have is a fixed-size matrix class, which could be used with boost::array as a building block for a lot of the more game-specific tech involved.  Seems to me a boost::matrix class (essentially a 2d boost::array) would be of reasonable scope/difficulty for a GSOC project.  If there's time left over, one could investigate making optimized rotations, dot projects, reflections and the like as freestanding functions/operators in a special namespace somewhere.

And this is definitively what I'd also like to do. As it seems an important topic, I'd make it the base of my proposal.

A 2D boost array is an overkill for a boost matrix class. In fact the whole point of a game-developer-centric matrix/vector support is to make the types simple and to the point. For that purpose, all you need is the following types: struct float2 { float x, y; }; struct float3 { float x, y, z; }; struct float4 { float x, y, z, w; }; struct float22 { float a11, a12, a21, a22; }; struct float33 { float a11, a12, a13, a21, a22, a23, a31, a32, a33; }; struct float44 { float a11, a12, a13, a14, a21, a22, a23, a24, a31, a32, a33, a34, a41, a42, a43, a44; }; And a bunch of namespace-scope functions that work with them, for example: float33 matrix( float a11, float a12, float a13, float a21, float a22, float a23, float a31, float a32, float a33 ); float33 float33_zero(); float33 float33_identity(); float33 float33_row_major( float const m[3][3] ); float33 float33_col_major( float const m[3][3] ); float33 float33_row_major( float const m[9] ); float33 float33_col_major( float const m[9] ); float33 float33_rotx( float angle ); float33 float33_roty( float angle ); float33 float33_rotz( float angle ); float33 operator*( float33 const & l, float33 const & r ); .....etc..... For any other application, you'd need a more generic and more abstract interface, but such interface will just get in the way for game development. Also, if your goal is to get a wide spectrum of APIs (engines, middleware, etc.) to talk through a common (boost) game development math interface, it has to be as basic as this. Otherwise you'll run into practical issues (ABI compatibility, etc.) as well as other excuses not to support it. Regardless, I'm skeptical. Chances are, the industry simply won't adopt a common interface for this stuff, no matter what. :) Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

On Sat, Mar 28, 2009 at 5:41 AM, troy d. straszheim <troy@resophonic.com> wrote:

Emil Dotchevski wrote:

...

On Fri, Mar 27, 2009 at 2:37 PM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:

...

On Fri, Mar 27, 2009 at 9:33 PM, troy d. straszheim <troy@resophonic.com> wrote:

...

One thing boost doesn't have is a fixed-size matrix class, which could be used with boost::array as a building block for a lot of the more game-specific tech involved.  Seems to me a boost::matrix class (essentially a 2d boost::array) would be of reasonable scope/difficulty for a GSOC project.  If there's time left over, one could investigate making optimized rotations, dot projects, reflections and the like as freestanding functions/operators in a special namespace somewhere.

And this is definitively what I'd also like to do. As it seems an important topic, I'd make it the base of my proposal.

A 2D boost array is an overkill for a boost matrix class. In fact the whole point of a game-developer-centric matrix/vector support is to make the types simple and to the point.

Well I'd like to stop talking about games, I don't think we're getting anywhere.  We're trying to find a project that fits into boost somewhere and is of appropriate scope for GSOC.   I still maintain that a fixed-size matrix class could be one. This has a well-defined scope and a good chance of success. But maybe somebody can argue that we shouldn't have a fixed-size matrix class?

If the student later uses in game code and finds out it isn't exactly what he wants, fine.

You can't just design some interface and then see if someone is going to use it. You have to address the specific needs of the client. Who and why would use the fixed size matrix class? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

On Sat, Mar 28, 2009 at 7:37 PM, troy d. straszheim <troy@resophonic.com> wrote:

Same reasons that you would use a 2d C array, I suppose.  You'd prefer the C++ version for the iterators, range-checking, the ability to choose row/column major storage format,  etc.

This thread is now 50 emails long and the student is basically back where he started.  We have a certain obligation to steer him towards something appropriate for GSOC.

To be perfectly honest, that's how it seems -- I started with a simple and modest proposal of a fixed-size vector and matrix library, went through a big circle with spatial indexing and other stuff, just to get back into a discussion about fixed matrices and vectors, what was ditched as a bad idea in the beginning :) ( forgive the smiley ) And to add something more merithorical to the discussion: I see a need, and I see a place in boost for a library that provides: a) an fixed-sized matrix<dim,dim,traits> class, that works for any dimension but is also hand-optimized for dimensions <= 4, b) an fixed-sized vector?<dim,traits> class that works for any dimension but is also hand-optimized for dimensions <= 4, * c) operators for readable operations on vectors and matrices d) mechanisms to almost invisibly (painlessly) allow converting those classes for use with uBLAS, other math libraries, array and multi-array types, and math libraries in progress and possibly: e) defining a common root for computational geometry, 3D and 2D boost libraries f) using additional libraries like Boost.SIMD to boost (no pun intended) performance * a new name would be probably be needed? The reason I see a need for a separate vector class instead of array is to allow type safety for operator handling for vector math. Also, vectors might need comparison policy. -- regards, Kornel Kisielewicz

On Mon, Mar 30, 2009 at 2:09 PM, Joel Falcou <joel.falcou@u-psud.fr> wrote:

Kornel Kisielewicz a écrit :

...

And to add something more merithorical to the discussion: I see a need, and I see a place in boost for a library that provides: a) an fixed-sized matrix<dim,dim,traits> class, that works for any dimension but is also hand-optimized for dimensions <= 4, b) an fixed-sized vector?<dim,traits> class that works for any dimension but is also hand-optimized for dimensions <= 4, *

Just being picky here. I don't like when matrix/vector libraries specify two types for both matrix and vector cause it becomes hard or unreadable to differentiate vector which are 1xN from vector begin Nx1. A global matrix<Type,Dim1,Dim2 = 1,...DimN=1> is , IMHO, better as you can compile-time check that your matrix/vector outer dimensions matches for operator like gemm.

Agreed. That's a much nicer solution. Hence, the whole library could be named matrix, and we wouldn't have problems with naming the vectors. -- regards, Kornel Kisielewicz

On Sat, Mar 28, 2009 at 7:54 PM, Patrick Mihelich <patrick.mihelich@gmail.com> wrote:

I think a fixed-size matrix class would be a great GSoC project. Or base of a larger project for the really ambitious student :). Many extra points if it is able to piggy-back on Joel's SIMD library. Lack of good fixed-size support is one reason I abandoned uBLAS.

Who and why would use the fixed size matrix class?

This seems like a strange question coming from a game developer. Fixed-size matrix can be dramatically more efficient since you can stack-allocate it and make optimal use of SIMD instructions. I use Eigen2's fixed-size vectors/matrices all the time.

I think you misunderstood my question. It was in reply to something along the lines of "we can write it and even if it isn't good for game developers, that's fine." My point was that game developers are the primary audience for such a library. See my previous post: http://article.gmane.org/gmane.comp.lib.boost.devel/187988. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Ross Levine Sent: 30 March 2009 04:09 To: boost@lists.boost.org Subject: Re: [boost] [gsoc] fixed size matrix class? (was: Interest check for 3d geometry proposal)

I guess I'll be a voice of dissent. I personally think a fixed 2d matrix is too easy. It seems all you would have to do is either use a flat boost::array of Rows * Columns or the like, and copy boost::array's interface. This is from someone who is programming a game and already made a 2d matrix class.

Well it might be easy - but IMO the most useful GSoC projects are those that have limited objectives - but actually get finished. There has been a lot of discussion about projects that sound way too ambitious for the time available for a GSoC. Testing and documentation take more time and effort than people usually estimate for. It would be useful to have even a 2D library in a reviewable state. If there is any time left over, other 3, 4 and other fixed N can be explored or tackled? Paul --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com E-mail message checked by Spyware Doctor (6.0.0.386) Database version: 5.12070 http://www.pctools.com/uk/spyware-doctor-antivirus/

Ross Levine wrote:

I guess I'll be a voice of dissent. I personally think a fixed 2d matrix is too easy. It seems all you would have to do is either use a flat boost::array of Rows * Columns or the like, and copy boost::array's interface. This is from someone who is programming a game and already made a 2d matrix class.

I do, however, think that a fixed-size n-dimensional matrix would be better for GSoC, and can see the value in that. It would be difficult, though, without varidic templates.

On the other hand, you're not going to mentor the student. A gsoc project that gets finished, reviewed and committed to trunk is 10x better than one coded and partially documented, dumped into the "here's what I wrote this summer" google code repo. How hard the project is to *code* is only a small part of the problem. The hard part is getting the tests written, learning the build system, writing thousands of emails like this one, writing docs, etc. GSOC is as much training for this process as it is learning to code new stuff. -t

I apologize for being late to the thread but I'd like to invite folks to take a look at cvalarray in the boost vault. I wrote this a few years ago and has been in active use in our organization for years now and I've seen it around the net-mostly in raytracing circles. (Actually, I've seen it referenced as boost::cvalarray because they obtained it from the vault) I basically accomplishes the "small fixed sized numeric array" requirement and can be used as base for small matrix class as well. There is an internal version here that also uses SIMD (intel) for the underlying operations. I asked for an interest check on the list many moons ago but I only seemed to get a lukewarm reception. In any case, it is complete, uses expression templates to eliminate temporaries, requires nothing outside of the language, is self-contained in one file, and is well tested. Unless there is heartburn with the interface or underlying implementation, It basically just needs to be boostified and integrated into the build system. Take a look and see if it either meets your needs or could be used as a jumping off point. Mike On Mon, 30 Mar 2009, troy d. straszheim wrote:

troy d. straszheim wrote:

...

Ross Levine wrote:

...

I guess I'll be a voice of dissent. I personally think a fixed 2d matrix is too easy. It seems all you would have to do is either use a flat boost::array of Rows * Columns or the like, and copy boost::array's interface. This is from someone who is programming a game and already made a 2d matrix class.

I do, however, think that a fixed-size n-dimensional matrix would be better for GSoC, and can see the value in that. It would be difficult, though, without varidic templates.

On the other hand, you're not going to mentor the student. A gsoc project that gets finished, reviewed and committed to trunk is 10x better than one coded and partially documented, dumped into the "here's what I wrote this summer" google code repo. How hard the project is to *code* is only a small part of the problem. The hard part is getting the tests written, learning the build system, writing thousands of emails like this one, writing docs, etc. GSOC is as much training for this process as it is learning to code new stuff.

-t

I take it back, sorry if my tone was off there. Having read more of the thread, I agree with you...

-t _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

----- Original Message ----- From: "troy d. straszheim" <troy@resophonic.com> To: <boost@lists.boost.org> Sent: Saturday, March 28, 2009 1:41 PM Subject: Re: [boost] [gsoc] fixed size matrix class? (was: Interest check for 3d geometry proposal)

Emil Dotchevski wrote:

...

On Fri, Mar 27, 2009 at 2:37 PM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:

...

On Fri, Mar 27, 2009 at 9:33 PM, troy d. straszheim <troy@resophonic.com> wrote:

...

One thing boost doesn't have is a fixed-size matrix class, which could be used with boost::array as a building block for a lot of the more game-specific tech involved. Seems to me a boost::matrix class (essentially a 2d boost::array) would be of reasonable scope/difficulty for a GSOC project. If there's time left over, one could investigate making optimized rotations, dot projects, reflections and the like as freestanding functions/operators in a special namespace somewhere. And this is definitively what I'd also like to do. As it seems an important topic, I'd make it the base of my proposal.

A 2D boost array is an overkill for a boost matrix class. In fact the whole point of a game-developer-centric matrix/vector support is to make the types simple and to the point.

Well I'd like to stop talking about games, I don't think we're getting anywhere. We're trying to find a project that fits into boost somewhere and is of appropriate scope for GSOC. I still maintain that a fixed-size matrix class could be one. This has a well-defined scope and a good chance of success. But maybe somebody can argue that we shouldn't have a fixed-size matrix class?

+1 I don't use to use Matrix, but if Boost don't have a fixed-size matrix, this will be always usefull. Vicente

The Configurable Math Library (http://www.cmldev.net) may also be a library to look into. It has a good user base ranging from corporate to hobby users, and is released under the Boost 1.0 license. I'm one of the developers, so if you need more info, feel free to e-mail me. Cheers, Demian