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

Subject: Re: [boost] [gsoc] Interest check for 3d geometry proposal
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-27 00:03:11

Hi Kornel,

> 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.
> 
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?

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

>>  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.
> 
The key being *sometimes*

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.

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++.

>> 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. 

Computational geometry algorithms use some very basic linear algebra building 
blocks, that's for sure, but they use quite a few others as well, and much more 
important.

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.

> 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. 

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

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.

> In this field, most of the code of uBLAS
> is not needed. 

Right.

> 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.
 >
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".

It is on top of numbers as well. And containers. Etc...

Vectors and matrices aren't the most interesting building blocks of geometric 
computing libraries.

>> 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.

If you don't write more details of what you propose and how that relates to all 
similar proposals you won't get much of a positive response.

> However a generic guideline would be all of the intersection,
> containment, storing and ordering structures/algorithms that are used
> in real-time graphics.
> 

Keep in mind that computer graphics and geometric computing are different 
fields... there is some overlap in certain types of functionality but they have 
underlying different requirements.

In computer graphics, space and speed efficiency is *much* more important than 
robustness, while in geometric computing is just the opposite.

For example, for most computer graphics applications, points CAN'T be anything 
more fancy than a tuple of floats, with even strict alignment requirements so 
that arrays of points have certain storage capabilities and they can be 
interfaced to the GPU directly. You hardly distinguish between points and 
vectors in a graphics engine for example.

The OpenGL API for instance is specifically desgined with those requirements in 
mind.

In a geometric computing library on the other hand a point type can very well be 
a sophisticated template whith particular properties (such as having a dual rep 
with coordinates or expression trees).
Vectors are typically distinct types with mathematically sound interoperation 
rules with points.

Algorithms have different robustness requirements because speed is THE priority 
in most computer graphics application.
For example, many real time renderers expose some defects at certain frames due 
to robusntess issues in computations for culling, clipping, etc... but those are 
typically inmediately overriden by a new correct frame, so it hardly matters.
And even if it does, it can't be solved at the expense of runtime overhead.

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com