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-27 05:46:41

On Fri, Mar 27, 2009 at 5:03 AM, Fernando Cacciola
<fernando.cacciola_at_[hidden]> 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