Re: [boost] [gsoc] Interest check for 3d geometry proposal

Subject: Re: [boost] [gsoc] Interest check for 3d geometry proposal
From: Patrick Mihelich (patrick.mihelich_at_[hidden])
Date: 2009-03-26 23:31:00

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.

Improving the performance of uBLAS could make for a couple of nice GSOC
projects. One would be proper fixed-size matrix support, then
metaprogramming to do loop unrolling when appropriate. Another would be SIMD
autovectorization, but I think this is best done after the first project and
requires something like Joel's SIMD library or Eigen2's SIMD wrappers. It's
also pretty hard. Then again I'm not sure how worthwhile it is for uBLAS to
compete with Eigen2 (and perhaps Joel's NT2 library) at this point.

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. These are already fixed-size and can be
SIMD-accelerated for the 3/4-dimensional case through partial specialization
if you end up with extra time on your hands - much easier than fixing uBLAS,
and I think you will have much more of an impact integrating with an
existing geometry library than writing your own from scratch.

Good luck,
Patrick

On Thu, Mar 26, 2009 at 9:30 AM, Kornel Kisielewicz <
kornel.kisielewicz_at_[hidden]> wrote:

> On Thu, Mar 26, 2009 at 4:52 PM, Simonson, Lucanus J
> <lucanus.j.simonson_at_[hidden]> wrote:
> > Kornel Kisielewicz wrote:
> >> On Thu, Mar 26, 2009 at 3:48 PM, Thomas Klimpel
> >> <Thomas.Klimpel_at_[hidden]> 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_UBLAS
> 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
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>