Subject: Re: [boost] [gsoc] Interest check for 3d geometry proposal
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-27 00:03:11
> 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.
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
>> 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
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.
> 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
>> 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
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.
-- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk