Boost logo

Boost :

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.


> 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

Kornel Kisielewicz

Boost list run by bdawes at, gregod at, cpdaniel at, john at