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 13:29:34

Kornel Kisielewicz wrote:
> 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.
> 
Agreed.
As I said in another post, for computer graphics you really want points to be 
nothing but tuples (or arrays if you want) of float.
Not even using double instead of float is acceptable on some circles.

> 
> But the parts that are expressed on the CPU side can be. One example
> is object hierarchy via oct or kd trees.
> 
OK, this is spatial partitioning, little to do with linear algebra.

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

Which is my point.. the algebra behind computer graphics is just too simple.

I say this because you presented your proposal as a CG-related algebra toolkit 
being a fundamental, rather than starting, building block for CG.

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

Ha OK...

IMHO those are better categorized as computer graphics data structures 
(geometrical in nature, but nevertheless highly related to computer graphics).

Computational geometry data structures OTOH typically refers to convex hulls, 
alpha shapes, triangulations, voronoi diagrams, polyhedra, etc..

> There's
> also the topic of tesselation, triangulation, culling, visibility
> determination etc.
> 
Whci has I said is treated significantly different in the context of computer 
graphics and geometric computing.

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

It seem to me tht you should *really* consider working on top of Joel Falcou's 
SIMD proposal. *That* seems to cover the basic linear algebra needed for 
computer graphics, including expected optimizations.

Spatial partitioning, fast ear-clipping triangulations (which are the kinds 
mostly used in graphics), containment and coallisions are the sort of higher 
level functionalities that geometric computing libraries typically don't cover.

I would concentrate on *some* of that if I were you, rather than the whole thing 
from the very bottom.

Best

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