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

Subject: Re: [boost] [gsoc] Interest check for 3d geometry proposal
From: Kornel Kisielewicz (kornel.kisielewicz_at_[hidden])
Date: 2009-03-26 12:30:07

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