Re: [boost] interest on a geometry library

From: Michael Andersen Nexø (nexo_at_[hidden])
Date: 2006-03-26 16:36:21

> Heres some comments from skimming your library  quickly.
> 
Thanks!

> point relative to line utilities e.g left_of are useful useful though I would 
> expect left_of to be able to tell me that the point is on the line too. 
> Presumably it could return 1 == left_of , 0 == on the line , -1 ==right_of etc.
> 
Ah, yes, the classic operator<() vs. strcmp() divide :-)

I don't feel too strongly about this, but personally I think that it
wouldn't make much sense having a left_of returning an strcmp-like int.
At least to me it would be a little unclear what the sign of the int
returned meant. But mostly because the functionality you request is
practically there already:

    What is the placement of p relative to the ray going from a to b?
    cross(b - a, p - a) >  0   // left of
                        == 0   // on the line
                       <  0   // right of

(BTW, left_of etc. was intentionally hidden as an implementation detail
of the convex_hull algorithm, because I wasn't sure whether or not it
would make sense to add this to the general interface when cross product 
was already there...)

> Not much in favour of the cast functions. The need to cast often usually 
> indicates a design problem. In this case I think it may be because specifying a 
> point type is flawed (as I am often fond of repeating ) unless you define 
> addition of points.

Do you mean that distinguishing between point and vectors in the type
system should be avoided altogether? If so, I'm afraid I'm in the other 
camp of that holy war :-)

I personally like the fact that the different semantics of the two are
reflected in the C++ type system. Anyway, if I've understood your
comment correctly I'd be glad to hear your arguments for ditching a
point type altogether. I would simply argue that you guys in the "vector
only" camp could just ignore the point type provided altogether and move 
on, so it isn't really hurting you to leave it in.

I do think you have a valid observation regarding the casts, though: I 
can see now that there are a lot of leftover casting functions from 
experimenting with the signature of the casting functions that should 
just be deleted -- sorry for the noise, I'll clean that up.

The casting functions can easily be deleted without affecting the
library design so I don't see them as an indication of a problem in the
overall design in having both points and vectors in the type system --
you could easily live without them at the expense of performing a copy 
in the few cases where you need to intentionally cross the semantic 
boundary between points and vectors. In my experience, that happens 
rarely, so I guess I'm saying that I could live without the casts, if 
need be.

> 
> Expression template stuff is a general utility is it not? Could be used outside 
> geometry library, so it might be better to split that. 

Are you saying that expression templates could be achieved by somehow
using an "Expression Templates Library" developed independently of this 
geometry library? If so, that sounds interesting -- I'd love to hear 
how. Can you direct me to relevant info on that? Thx.

> The use of promotion_traits etc might soon be superceded by Boost.Typeof which should be 
> available in the next version of the boost distro. Also could be done so as both 
> et and not et could be used together?
> 

I agree totally. In fact, I wouldn't be surprised if my type promotion
rules are wrong in a number of odd corner cases. A lot of this was 
simply written at a time when the geometry classes weren't dependent on 
Boost. But, in this context using BOOST_TYPEOF as you do (and eventually 
using the decltype construct) is obviously to be preferred.

I think it would be quite easy to make ET and non-ET geometry classes
coexist (at the expense of complicating the interface a bit by another 
template parameter). This is a good point that needs consideration.

But, actually I'm not even too convinced that expression templates are 
worth the complexity for the low dimensionalities typically used for 
most geometry-related computations. The few performance tests I've done 
tend to show that the benefits of ET starts to kick in at D>5 or so. 
Maybe the time is better spent elsewhere (e.g. doing SIMD 
implementations for various architectures).

The reason I opted to keep the ET stuff in there is because the method
of implementing it used is so non-obtrusive to the core interface and 
that it can be easily be switched on/off. (BTW, the approach to 
Expression Templates that I've used is blatantly copied from 
Vandevoorde's and Josutti's book. I've found it a very clean way of 
ensuring that the interface of all the expression templates stay the same.)

> Nice to see a GUI based example, though I havent tested it yet. One day maybe in 
> the distant future it will use the cross -platform C++ standard GUI system ;-)
> 

Yeah, the C++ Standard GUI is expected to arrive right after the 
paperless office :-)

No, seriously, I think this is one of the best arguments for the
approach I'm putting forward: creating a STL-like split between the
data types and the algorithms and utilities.

It's naive to believe that all the many graphics subsystems in existence
will start using the same geometry primitives in their interfaces. For 
the foreseeable future, different platforms (even subsystems) will have 
different ways of representing a vector.

Just as we didn't want to rewrite a sorting algorithm for every 
container in existence, we don't want to be having to rewrite our 
geometric algorithms over and over again for every geometric primitive 
on all the different platforms out there.

My approach has been to try and provide geometric primitives that are 
both able work alone *and* work as adapter classes around platform 
specific types with virtually no overhead. These primitives can then be 
used for 1) writing generic geometry-related algorithms, 2) facilitate 
seamless interaction between otherwise incompatible geometry primitives 
from different subsystems.

I'm certain the design I've can be improved vastly, but I think it would 
be regrettable if the overall *design goal* described above was not 
included in a Boost Generic Geometry Library.

> Overall there seems to be  a lot of useful stuff here.
> The previous discussion re the minimum primitives seems to hold (vector,matrix, 
> quaternion).

Setting aside our little discrepancy about points ;-), wouldn't
homogenous coordinates also be worthwhile? I have a feeling that they 
would be hard to implement by means of other primitives?

Also, would there be any difference between boost::quarternion and 
boost::geometry::quarternion? (Please excuse me, I only have very skimpy 
knowledge about quarternions).

> 
> Is anyone interested to start on moving a Boost.Geometry lib forward now?

Absolutely. I'm already putting whatever little time I have into it and 
would love to team up with "kindred spirits" in this forum. But, perhaps 
we need to spend a little bit more time making sure we're on the same 
page regarding the rationale and scope of this library. This would by my 
bullet-point style take on that.

Rationale:

  * Create nice, clean, "Standard C++"-like core geometry primitives,
    such as vector, matrix (and perhaps point, quarternion, homogenous
    vector). These would differ from uBLAS from the fact that their
    sizes were given at compile time (closer to tvmet).
  * Create the necessary traits/adapter infrastructure for writing
    generic algorithms independently of the underlying geometry
    primitives, thus providing a framework for writing:
  * Generic utilities and algorithms lying in the realm of computational
    geometry. Algorithms should be generic in terms of both storage and
    scalar type used for the geometry primitives, and the dimensionality
    (the latter obviously only whenever applicable).

Features that I see as important:

  * Primitives should be template'd on type, dimensionality and storage.
  * Care should be taken in dealing with the limited precision in typical
    scalar types when writing the operators, utilities and algorithms.
    (Adhering to C++ style promotion partly helps with this, but
    allowing for more user control over promotion is probably necessary.)
  * Interaction between primitives with different scalar types should be
    allowed, but truncation warnings should be generated when it is not
    done explicitly by the user.
  * Expression templates are not a design goal in itself, but if the
    interface overhead is small and it is possible to switch it off, it
    should be considered.

Please chip in. The important thing is to see if we can get two or three 
of us aligned sufficiently to get this rolling.

Best regards,
Michael