On Fri, Mar 17, 2006 at 10:17:53AM -0700, Richard Newman wrote:

Is it reasonable to extend the logic to check for 3D shapes (i.e., spheres instead of circles, etc.)?

It certainly would be a reasonable strategy to get the 2D work you have into the library and treat 3D as a later extension.

Well, 3D is a whole different beast, and is not implemented yet :) What I have is the following (with my name convention, to be changed...): geom_t is an abstract base class with basic functions like: - center -> return the center point of the geometry - box -> return a rectangle encompassing the whole geometry - area -> returns its area then there's the primitive classes that inherits from geom_t: point_t -> a single point in the 2D space circle_t -> represented as a 2D point and a radius rectangle_t -> represented as two points, the upper left and lower right. I'm planning to add polygon and triangle soon. There are also operator>> and << to transfer from and to a stream, and free functions that returns intersections, unions, etc. All coordinates are double. Maybe each primitive should be a template, like: point_t<double> is a point with double floating point coordinates, point_t<int> is with integer coordinates, etc. More ideas are welcome :) Regards, Rodolfo Lima. _______________________________________________________ Yahoo! Acesso Gr�tis - Internet r�pida e gr�tis. Instale o discador agora! http://br.acesso.yahoo.com

On Fri, Mar 17, 2006 at 10:27:00AM -0800, Geoffrey Irving wrote:

It would be better to have a set of nonvirtual classes defining functions like this inline, and then have a template wrapper class to convert one of these into a descendant of the virtual class. This way, someone who wants to use a million spheres (e.g., for a sphere hierarchy), won't suffer from virtual function overhead.

You are right about considering inlining, I'll try to come up a way to have two interfaces, one easily inlined and another virtual, because sometimes is important to have some kind of polymorphism, ie, container of base pointers.

You should probably think carefully about which basic types to use here, especially in terms of small vectors types. I'm not sure if boost has a small vector type yet (I didn't see one in uBLAS), but if so it should definitely be used.

You mean to use small vector to generalize each primitive to n dimensions, right? My only objection is that it would complicate the (for me) basic usage, i.e., 2d (and hopefully 3d) usage. For instance: point_t<double> pt; pt.x = 6.0; pt.y = 3; or rect_t<double> rc; rc.bottom = rc.right = 3; rc.topleft() = point_t<double>(4,5); I would not like to lose that. A more generic way would be: point_t<double, 2> pt; // 2 dimensions pt[0] = 6.0; pt[1] = 4; or whatever..., but for me the first option is preferable. But I'm open to new ideas. ------------ Rodolfo Lima _______________________________________________________ Yahoo! doce lar. Fa�a do Yahoo! sua homepage. http://br.yahoo.com/homepageset.html

On Fri, Mar 17, 2006 at 03:30:28PM -0500, Cliff Green wrote:

I assume you've seen and compared various geometry libraries - in particular CGAL is an excellent cutting edge computational geometry library (in many ways - C++ design techniques, overall functionality, "number kernel" architecture): http://www.cgal.org/

No, I didn't look to other libraries. What I've written suits my (simple) needs, but I'm looking forward to a full blown library helpful to other audiences. I'll have a look into this CGAL and others to get some ideas. I'm pretty confident that with the help of everyone we'll do a great job at this area. Thanks for the advices. Rodolfo Lima. _______________________________________________________ Yahoo! Acesso Gr�tis - Internet r�pida e gr�tis. Instale o discador agora! http://br.acesso.yahoo.com

On Fri, Mar 17, 2006 at 11:08:37PM +0100, Janek Kozicki wrote:

rodolfo@rodsoft.org said: (by the date of Fri, 17 Mar 2006 16:35:40 -0300)

...

pt.x = 6.0; pt.y = 3;

or

pt[0] = 6.0; pt[1] = 4;

you can have both of them:

union { struct { Type x,y,z; }; Type v[3]; };

that's what I used for my small vector3d (and vector2d, quaternion, matrix3) library.

The problem with this approach is that Type cannot have constructors or destructors to get into an union. That's a little too restrictive, I think.

Currently I'm dragging everywhere my library, and I use it in a lot of different projects. Anyway if you are interesed in that 3d stuff let me know, and I'll start a code cleanup to eventually submit it to boost :)

That's exactly why I'm looking forward this geometry library :) Thanks, Rodolfo Lima. _______________________________________________________ Yahoo! Acesso Gr�tis - Internet r�pida e gr�tis. Instale o discador agora! http://br.acesso.yahoo.com

On Sat, Mar 18, 2006 at 10:03:10AM -0000, Andy Little wrote:

"Geoffrey Irving" <irving@cs.stanford.edu> wrote in message news:20060317182700.GG9842@lie.Stanford.EDU...

...

On Fri, Mar 17, 2006 at 03:09:26PM -0300, rodolfo@rodsoft.org wrote:

...

On Fri, Mar 17, 2006 at 10:17:53AM -0700, Richard Newman wrote:

...

Is it reasonable to extend the logic to check for 3D shapes (i.e., spheres instead of circles, etc.)?

It certainly would be a reasonable strategy to get the 2D work you have into the library and treat 3D as a later extension.

In my own work on this I used two namespaces "geometry::two_d" and "geometry::three_d". (I shall put what I have in the vault). I or someone could create a Geometry folder ...?

A place in the vault to share some ideas is welcome. How do we do that? Rodolfo Lima _______________________________________________________ Yahoo! Acesso Gr�tis - Internet r�pida e gr�tis. Instale o discador agora! http://br.acesso.yahoo.com

On Sat, Mar 18, 2006 at 05:52:59PM -0000, Andy Little wrote:

...

A place in the vault to share some ideas is welcome. How do we do that?

Go to The vault and find the login link. The link takes you to information on getting vault access

Thank you, I've created directory "Math - Geometry". If anyone has any ideas, algorithms or data structures, please upload there so we can sort out what can be used. I'm collecting information to create the main scope of the library. Rodolfo Lima _______________________________________________________ Yahoo! Acesso Gr�tis - Internet r�pida e gr�tis. Instale o discador agora! http://br.acesso.yahoo.com

I've put a zip containing some 2D/3D geometry primitives in the Math - Geometry directory:

http://tinyurl.com/mbaol

No docs or tests. Developed using VC7.1. Needs Boost.Typeof which is only available in CVS. The two rc_transform.hpp headers currently also have dependencies on an external angle type so wont compile (unless you download the original pqs http://tinyurl.com/s7hu6) , however I am working to make a set of angle types available as part of my proposed Boost Pqs library: http://tinyurl.com/7m5l8

Hi, I will try to help you with that geometry library, because I want to use boost too, instead of dragging everywhere similar library (with quaternions, and all that 3D stuff). I'm mainly using that library for discrete simulation modelling (shameless plug: http://yade.berlios.de/ ). So I'm comparing your work against mine :) 1. in file vect_def.hpp you have default constructor: vect() : x( static_cast<T>(0) ) , y( static_cast<T>(0) ) , z( static_cast<T>(0) ) {} IMHO it's better to leave values uninitialized, if anyone needs to initialize to anything, he will call the second constructor. Also leaving variable uninitialized when no initialization value is given is the standard behaviour. boost::numeric::ublas leaves vectors uninitialized too. Think about performance when constructing a big array (that will be initialized by the user just after it's constructed...) 2. in file vect.hpp, function magnitude( vect<Value_type> const & v), I think you should add std:: there Value_type result = std::sqrt(v.x * v.x + v.y * v.y + v.z * v.z); Personally I prefer name "length" because it is shorter to type than "magnitude", but naming is not that important ;) 3. speaking of length, a function that returns squared length is very useful too, because it is faster. And people often use squared length when they just compare to get something longer (or shorter) but don't care about the actual length. 4. How about negation? it's operator-(T), it negates the argument. I'm typing this code without actual checking, but you should understand what I mean: template <typename TR> inline vect <BOOST_TYPEOF_TPL(TR())> operator -( vect<TR> const & rhs) { return result(-rhs.x,-rhs.y,-rhs.z); } 5. how about operator-=() ; operator+=() ; operator*=() ; operator/=() ? 6. maybe I don't understand something here, but why do you always declare temporary variable "result" just to return it one line later? Is it necessery for type checking? (function already has declared it's return type). 7. normalize() function is useful, it normalizes the vector and returns its length: (I'm also quick-typing this here): template <typename T> BOOST_TYPEOF_TPL( T() ) normalize( vect<T>& vec ){ typedef BOOST_TYPEOF_TPL( T() ) length_type; length_type length=magnitude(vec); vec.x/=length; vec.y/=length; vec.z/=length; return length; } 8. when working with volumes it is useful to quickly find encompassing volume by performing scalar_max() on all volumes in question: template <typename T> vect<BOOST_TYPEOF_TPL( T() )> scalar_max( const vect<T>& lhs, const vect<T>& rhs ){ return vect<BOOST_TYPEOF_TPL( T() )>( std::max(lhs.x , rhs.x), std::max(lhs.y , rhs.y), std::max(lhs.z , rhs.z) ); } 9. scalar_min() can be sometimes useful too, and to be complete both functions should be added, I think... 10. what is that semicolon at the end of line 107 in vect.hpp? ;)), that '-' in line 106 looks suspicious too ;) 11. unit_cross_product() is useful in openGL, it's just like cross_product, but the result is normalized: template<typename T> vect<BOOST_TYPEOF_TPL( T() * T())> unit_cross_product( const vect<T>& lhs, const vect<T>& rhs ){ vect<BOOST_TYPEOF_TPL( T() * T())> result( lhs.y * rhs.z - lhs.z * rhs.y, lhs.z * rhs.x - lhs.x * rhs.z, lhs.x * rhs.y - lhs.y * rhs.x ); normalize(result); return result; } 12. we have a dot product and cross product, but how about diagonal multiplication of two vectors? template<typename T> vect<BOOST_TYPEOF_TPL( T() * T())> mult_diagonal( vect<T> const & lhs, vect<T> const & rhs ){ return vect<BOOST_TYPEOF_TPL( T() * T())>( lhs.x * rhs.x, lhs.y * rhs.y, lhs.z * rhs.z ); } looks like that's all for now :) In your previous post you mentioned quaternions, but I don't see quaternions in this geometryAL_01.zip file. I'm not using matrices to rotate in my code, but quaternions, so (for now) I don't have suggestions about rc_matrix. I'm only curious why the "rc_" prefix to the name? I'm looking forward to see quaternions.hpp :)) I'll try to switch my program (yade is over 30000 lines of C++ ;) into this library, as a part of helping in getting this library done. So I will be able to perform numreous benchmarks and unit tests to compare both libraries (both compuational correctness and speed). -- Janek Kozicki |

Andy Little said: (by the date of Mon, 20 Mar 2006 14:14:28 -0000)

...

I will try to help you with that geometry library, because I want to use boost too, instead of dragging everywhere similar library (with quaternions, and all that 3D stuff). I'm mainly using that library for discrete simulation modelling (shameless plug: http://yade.berlios.de/ ). So I'm comparing your work against mine :)

Wow. It looks impressive. I note the intention in the schedule; Milestone 4 to "Use physical units, from dimnum or SIunits library". What is the status of that? Naturally having spent some time on proposed Boost Pqs library http://tinyurl.com/7m5l8I would be interested to see if it might be used for this purpose.

well no progress on the front of physical units :) I was searching for some useful physical units library and found those two. I also found your pqs library, but (a year ago) after a brief look at it I decided against it. But now that's the history :) When I have a direct contact with the library author (you), and because Pqs will be a part of boost - suddenly Pqs has huge advantage over other libraries, so I will try to use it :) But not now, it is a future target ;) That URL http://tinyurl.com/7m5l8I is not working....

...

1. in file vect_def.hpp you have default constructor:

How about adding a compile time switch (macro) to enable/disable zero initialisation?. That could also be used to measure the effect of initialisation on performance too.

I like that idea very much.

...

2. in file vect.hpp, function magnitude( vect<Value_type> const & v), I think you should add std:: there

Value_type result = std::sqrt(v.x * v.x + v.y * v.y + v.z * v.z);

The intent is to allow the correct sqrt to be selected by ADL. The quantities in pqs have a sqrt function in boost::pqs namespace. It might be worth adding using std::sqrt though.

hmm, now I remember that I've seen in some boost sources STD with capital letters, for example look at boost/serialization/vector.hpp, there are those lines: #if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) #define STD _STLP_STD #else #define STD std #endif and later STD:: is used. Maybe we should do the same...

...

3. speaking of length, a function that returns squared length is very useful too, because it is faster. And people often use squared length when they just compare to get something longer (or shorter) but don't care about the actual length.

Right. Is that the same as what norm(std::complex) does ?

yes :) I didn't know that, and from STL manual (confirmed by looking at the source code): norm template<class Ty> Ty norm(const complex<Ty>& left); The function returns the squared magnitude of left. this also means that name "magnitude" is more standard than "length"

...

4. How about negation? it's operator-(T), it negates the argument. Yes I should add that.

...

5. how about operator-=() ; operator+=() ; operator*=() ; operator/=() ? Yes I must add those, assuming the argument is an arithmetic type.

yes, exactly :)

...

6. maybe I don't understand something here, but why do you always declare temporary variable "result" just to return it one line later? Is it necessery for type checking? (function already has declared it's return type).

Its an attempt to get the so-called Named Return Value Optimisation: (Heres first reference I found on it in quick search) http://blogs.msdn.com/slippman/archive/2004/02/03/66739.aspx

I've read this article, and it says that this optimisation is meant to help a badly written code. Article says: "What's wrong with this optimization is that you don't know if it will or will not be triggered" There could be a problem with RVO, so better we test it later that there is no burden of extra constructor call (boost is meant to work with various compilers on different platforms) ...

...

7. normalize() function is useful, it normalizes the vector and returns its length: Ok. Is that useful for rotation axis for instance?

yes, eg. for constructing a new quaternion from axis/angle. Or also to get a unit direction vector for a force (in Newton unit ;) to be applied on a body.

...

8. when working with volumes it is useful to quickly find encompassing volume by performing scalar_max() on all volumes in question:

template <typename T> vect<BOOST_TYPEOF_TPL( T() )> scalar_max( const vect<T>& lhs, const vect<T>& rhs ){ return vect<BOOST_TYPEOF_TPL( T() )>( std::max(lhs.x , rhs.x), std::max(lhs.y , rhs.y), std::max(lhs.z , rhs.z) ); }

Ok. Is that sometimes implemented as a logical operator e.g Or is max and And is min? Mind you that may not be comprehensible for vect...

Hm, I've never heard about using operators | and & for vectors for that purpose. But when I think about it, it's maybe reasonable. Also in my code snippet above I used name scalar_max(), although in yade the function is just called max() - I just wasn't sure if that short name would be clear.... Nevertheless this function is useful, and doesn't matter too much how to call it, just ensure it's there. To be honest my vote would go for a name "max()" :) Operators | and & are reasonable too - although they may be not too quick to find when someone is browsing a quick-reference to find what he needs. So whichever you prefer.

...

9. scalar_min() can be sometimes useful too, and to be complete both functions should be added, I think...

Ok.

...

10. what is that semicolon at the end of line 107 in vect.hpp? ;)), that '-' in line 106 looks suspicious too ;)

Yes they are typos. There need to be some tests!

...

11. unit_cross_product() is useful in openGL, it's just like cross_product, but the result is normalized: 12. we have a dot product and cross product, but how about diagonal multiplication of two vectors? Ok. All those should be added..

nice :)

...

looks like that's all for now :) In your previous post you mentioned quaternions, but I don't see quaternions in this geometryAL_01.zip file. I'm not using matrices to rotate in my code, but quaternions, so (for now) I don't have suggestions about rc_matrix. I'm only curious why the "rc_" prefix to the name? I'm looking forward to see quaternions.hpp :))

the rc_ prefix stands for Row-Column format (as opposed to Column-Row format). It might be best to use the OpenGL format but I cant remember which format they use now. Graphics books Other Libs often use the other format to OpenGL. In fact maybe it would be best to have both and with corresponding row and column vectors.

hm, I don't use matrices too much so I don't know. But speaking about OpenGL compatibility rings a bell in my mind about vectors. Many opengl functions take as an argument a pointer to array, like float* or double* or int*. For example this function: ( http://tinyurl.com/kfxwl ) void glVertex3fv( const GLfloat *v ) look at this example code: boost::geometry::three_d::vect vec(0.1,0.2,0.3); glVertex3fv(vec); // shorter to write, faster to call glVertex3f(vec.x,vec.y,vec.z); // longer to write, slower to call, more code cluttering To have this working, we need an operator T*() which returns pointer to an array, which contains actual vector data, like this: template <class T> vect<T>::operator T* () { return v; // [1] } template <class T> vect<T>::operator const T* () const { return v; // [1] } [1] problem however is that we need that data "v" to be returned. Simplest solution is to store this data internally in three_d::vect as an array: template <typename T> struct vect { /* ...*/ T v[3]; } or, to have best of both worlds: template <typename T> struct vect { /* ...*/ union // replace line 35 in vect_def.hpp with those 5 lines, and everything will still commpile { struct { T x,y,z; }; T v[3]; }; } this anonymous union is an idea I took from one of books by Meyers or Sutter (I cannot find it now :/ ). But Rodolfo Lima rightfully noted that:

...

The problem with this approach is that Type cannot have constructors or destructors to get into an union. That's a little too restrictive, I think.

and if we want to make a generally usable small vector we shouldn't have this restriction - because someone may decide to use a custom class to store numbers (for example to acheive greater precision). Here template specializations can help us. We can use anonymous union solution for template specializations like float,double,int,short and leave general template that doesn't use union, but just x y z. With this design operator T*() would be different for general template (either can cast T to double, build an array and return a pointer to it (requires extra fields in the struct vect {}, to store converted values), or can simply return a compiler time error). And the specialized versions of operator T*() would return a pointer to already existing data "v" that contains fields x y z. Other lazy solution is just to always build that array to which pointer is returned (but then we lose whole speed advantage). To have matrices similarly compatibile they also should be stored like that in memory, look at function ( http://tinyurl.com/gnfq8 ): void glLoadMatrixd( const GLdouble *m ); as noted on that webpage: m - A pointer to a 4x4 matrix stored in column-major order as 16 consecutive values. I see that boost::geometry::three_d::rc_matrix_base uses boost::tuple to store data. To have rc_matrix compatilibe with glLoadMatrixd(), we also need a similar operator double*(), which returns pointer to that matrix. Then we can use template specializations for this operator. A general template would generate a compile time error, while specializations for float,int,double,etc could return pointer an array. But that would require big changes in the rc_matrix code, so perhaps it should be reconsidered whether those matrices should be opengl-compatibile or not. (I've never used matrix for opengl, so I won't use that...) But certainly I'd need vector to be opengl-compatibile.

As far as quaternions go I havent used them. I have used matrices firstly because a matrix can encompass a complicated transform such as rotation of an object around an arbitrary line not passing through the origin, whereas AFAIK a quaternion is limited to rotation only, so the object must first be translated so some part of the line is at the origin, then rotated, then translated back, whereas a matrix can express this transform directly in one single object. Is this the case or have I got it wrong? however I am aware that quaternions are meant to be much quicker.

you are right, quaternions are fast when it comes to rotations, but all rotations go around the origin. So sometimes translation is necessary. Also if you haven't used them, it means that I'll have to push for quaterions to get them in. This geometry library without quaternions will be pretty useless for me :) All the fuss is about multiplication of vector by quaternion. But still I don't know how to put them in :) If there is a namespace two_d and three_d, then what? Put them in three_d or four_d (???). Should I extend existing boost::quaternion class by inheriting from it, and adding necessary function calls, or just modify it, hoping that the author of boost::quaternion will accept my modifications?

...

I'll try to switch my program (yade is over 30000 lines of C++ ;) into this library, as a part of helping in getting this library done.

Wow that sounds like a lot of work. It sounds like your own graphics library is sophisticated, so it will be interesting to see some of that and perhaps the work should consist more of incorporating others efforts into yours ;-)

oh, it's not graphics :) Actually opengl part is not too sophisticated, just displaying some opengl primitives. Most important part is where physical calculations are done - collisions of bodies, calculating forces, geometry overlapping, etc... That's where those three_d::vectors and quaterions are used. sorry that this post got so incredibly long ;) -- Janek Kozicki |

Andy Little said: (by the date of Tue, 21 Mar 2006 02:00:43 -0000)

...

sorry that this post got so incredibly long ;)

No problem. I will try to reply to the other parts of your post in more detail soon. Overall I can see a good deal of divergence between your aims and mine. (That is not necessarily a bad thing of course as we would presumably be aiming for the most widespread use). Your applications require very good raw speed performance, which I havent paid enough attention to, but I can see now why you will be obsessed with that from looking at YADE.

I've reconsidered my "raw-speed" attitude, because from experience I've learnt that speed comes often uninvited along with good design. So think about design first, speed comes later :) My elaborate explanations about anonymous union simply demonstrate that full opengl compatibility comes at huge price - it forces internal data structure. A huge no-no in good OO design. Therefore degree of compatibility with opengl should be a design decision/rationale of this library. Fast disply in yade is much less important than geometrical computations themselves - related to physics of the system, not to the graphics.

Overall I have been looking at ease of use. I am currently interested in integrating geometry /vectors with pqs library, but that would increase complexity of the implementation over just using float types as you may see in my current geometry offering and will also affect compile times, so may be a burden giving you no benefit.

I see a big potential here, if I want to use physical units, having them built-in inside the geometry would be pretty useful.

That difference of quaternions v matrices is interesting also. The generic nature of matrix transforms is at the expense of speed. It should be possible to combine both matrix and quaternions transforms somehow of course and I will have to read up on using quaternion.

In fact quaternion stores rotation data in more compact form than matrix. If quaternion is 'messed up' a bit, then rotation angle is just a bit different - hard to notice the difference. If matrix is 'messed up' a bit - it losts symmetry and rotation is iffy. Moreover everytime a vector3d is rotated by quaternion, a 3x3 matrix is built from quaternion (using only operations + - *). And to be honest I haven't benchamrked if quaterions are faster. Many people claim this, but I realized that I shouldn't claim it until I'll make relevant benchmarks.

It strikes me that perhaps more detailed discussion about the goals and rationale of such a library is needed too.

yes, certainly. At first we should decide what entities should appear, how to name them, and how to sort them into namespaces, to begin with, that's my library: - vector2 + - vector3 + - vector4 + - matrix2 + - matrix3 + - matrix4 + - quaternion + - se3 + Other readers of this list are welcome to add more components and "vote" by placing '+' next to it. Of course class names are subject to another discussion :) If you are wondering, se3 is a position/orientation combo - small class which contains only vector3 and a quaternion. It is used to fully describe a placement of an object in 3d space. I'm still not sure whether getting rid of it would make things simpler or not.

As to quanternion...is boost::quanternion not suitable for your applications as it stands?

unfortunately not. yesterday I have examined it again, and I see that the author has started working in that direction (quote at bottom of quaternion docs webpage: "Use uBlas for the link with rotations (and move from the example implementation to an efficient one)."). In his example I can see those familiar formulas used to build rotation matrix out of quaternion (in file HSO3.hpp) Perhaps he got discouraged by the fact that ublas is not a good choice for small vectors. -- Janek Kozicki |

"Geoffrey Irving" wrote

Janek Kozicki wrote:

[...]

One dimensional versions are very convenient for debugging and hierarchical template code (building 3d on top of 2d on top of ...). Depending on the rest of the design scalars might be sufficient, though.

Is there any reason to build 3d on top of 2d ?. Is this from an academic point of view where mathematicians enjoy generalising geometry to N dimensions? My own use seems to consist mainly in 3 dimensions, with some 2 dimensions. Generalisation to N dimensions seems to have little practical use ... or does it ?

Specialized versions of matrices are less commonly needed but extremely convenient when you do. They also add a significant benefit in terms of self-documentation and automatic type checking.

If compilation time weren't an issue, it would be quite interesting to build all of these out of a general sparsity small matrix class. With enough trust in the compiler, that could be done by making a zero type and overloading all the arithmetic operators to know about zero, e.g.,

zero operator*(zero a, float b) { return zero(); }

Or even : template <typename TL, typename TR> zero<BOOST_TYPEOF_TPL(TL() * TR) > operator*(zero<TL> a, TR b) { return zero<BOOST_TYPEOF_TPL(Tl() * TR) >(); } This would for instance allow use of the types in my pqs library: http://tinyurl.com/7m5l8 e.g zero<pqs::mass::kg> mass; BOOST_AUTO(force, mass * pqs::acceleration::g); This reminds me somewhat of expression templates too.

It would be great to hear if anyone with more metaprogramming experience has any comments of the feasibility/costs of that approach. I imagine that compilation times alone make this impractical for now, not to mention the complications for anyone trying to read the code.

If matrices are maximum of 4 x4 I would think that compilation times would be acceptable for numeric value anyway. It also happens to fit in somewhat with my own slightly whacky matrices which are more like tuples because not all the elements are the same type. Some are numeric , some are quantities while some are the reciprocal of a quantity. For instance in my geometry library a 2D RC matrix decribing a rotation of 45 degrees about a point 1mm from the x origin and 1 mm from the y origin looks like so: | 0.707107, 0.707107 , 0 m-1 * 1e3 | | -0.707107, 0.707107 , 0 m-1 * 1e3 | | 1 mm , -0.414214 mm, 1 | The units relate to the various transforms. The angular and scaling elements are numeric, while the translation elements have distance units of millimeters and the perspective elements have units of per millimeter ( simply the reciprocal of millimeters represented as m-1 * 1 e3 here). The units provide a useful reference over simply using numeric types. The per millimeter elements and scaling could do with being optimised away in this case though. Maybe I could add an extra integer parameter with a 32 bit int, with two elements for each bit (for a 4 x4 matrix) representing whether that element was a compile time constant (One or Zero or a runtime variable. I would guess that you could then use boost::mpl::if_<Maskint && MyBits == 0,zero, T>::type for each element to get this behaviour. In math operations this would also carry through to the result type of course as in the simple example above.

...

If you are wondering, se3 is a position/orientation combo - small class which contains only vector3 and a quaternion. It is used to fully describe a placement of an object in 3d space. I'm still not sure whether getting rid of it would make things simpler or not.

I would strongly vote for frames. Otherwise people familiar with homogenous coordinates will fall back to using matrix4 and lose on elegance, speed, memory, and robustness (speed only sometimes).

What is a frame? regards Andy Little

On Wed, 2006-03-22 at 21:52 +0100, Janek Kozicki wrote:

yes, certainly. At first we should decide what entities should appear, how to name them, and how to sort them into namespaces, to begin with, that's my library:

- vector2 + - vector3 + - vector4 + - matrix2 + - matrix3 + - matrix4 + - quaternion + - se3 +

Other readers of this list are welcome to add more components and "vote" by placing '+' next to it. Of course class names are subject to another discussion :)

It is a little surprising to see that to begin with, it is not geometrical concepts that you speak of but representations (vectors,quaternions, matrices...). If there is a geometric library (which I would appreciate a lot since like many others I had to craft my own with some strenghts and some weaknesses), I would prefer to speak about geometrical concepts first and their relationship, the implementation in terms of vectors (which I approve wrt a an implementation with a struct), matrices, ... should come after. So I'll somewhat oppose to your proposal (and the following ones): N is the dimension. namespace notation is just notational not a proposal. Euclidean::Point<N> Euclidean::Line<N> // not very different from projective line ?? Euclidean::SemiLine<N> Euclidean::Segment<N> Euclidean::Simplex<N> Euclidean::Basis<N> Affine:: same as Euclidean except maybe for Basis?? Projective::Point<N> Projective::Line<N> Projective::Basis<N> SemiLines, Segments and Simplices are more complicated to define... Constructors::{ most are obvious but some may not be... an Affine Point from a Projective one is not always possible}. Transformations:: { Rotations, Translations, Scales, Affine, Euclidean, Projective,.... In my experience, this is the most difficult to properly design except if one wants to pay always for the most general projective transform even for the simpler ones. } Distances:: { Point-Point, Point-Line, Point-Segment, Line-Segment, Line-Line, .... and depends of the geometry and possibly on a "Metric". } Miscellanous:: { BoundingBoxes, Statistics, Volumes, Areas, Adding Noise .... } Theo.

On Thu, 2006-03-23 at 11:58 +0000, Paul Giaccone wrote:

Theodore Papadopoulo wrote:

...

So I'll somewhat oppose to your proposal (and the following ones):

N is the dimension. namespace notation is just notational not a proposal.

Euclidean::Point<N> Euclidean::Line<N> // not very different from projective line ?? Euclidean::SemiLine<N>

One minor correction (with no criticism intended), before this becomes reality:

Euclidean::HalfLine<N>

or

Euclidean::Ray<N>

would be the correct geometrical terms for "SemiLine".

No problem names were not meant to be normative and fortunately you understood what I meant. Thank's for the correction. Theo.

On Thu, 2006-03-23 at 14:33 +0000, Andy Little wrote:

Would I be right in saying that only entities of the same dimension can be added so SpaceType and dimension can be alternatively be seen as a container rather than a parameter:

Euclidean::N::Point Euclidean::N::Line Euclidean::N::SemiLine Euclidean::N::Segment Euclidean::N::Simplex Euclidean::N::Basis

namespace Euclidean { namespace N{

Point a = Point(); a = Euclidean::N_plus_1::Point(); // Error ! }}

???

No you are right.... And actually my own (not particularly interesting) geometry library evolved as Geometry2D and Geometry3D namespaces mimicking somewhat your view. Unfortunately, I had to consider afterward higher dimensional geometries and templated namespaces (sorry I'm introducing implementation details here, which is clearly not the way I believe the discussion should evolve) just do not exist yet (and I'm not sure they will ever be). And after a while, you realize that templates (for this purpose at least) are your friend, just for code sharing reasons.... That's why I favoured having the dimension as the last (templated) parameter, because some implementations details can be shared.... But in essence you are right, and if templated namespaces existed, I would have preferred your organisation. Not that having the dimension last, does not change the fact that you cannot assign an N+1 Point to an N point... Theo.

On Thu, Mar 23, 2006 at 10:51:42AM +0100, Theodore Papadopoulo wrote:

On Wed, 2006-03-22 at 21:52 +0100, Janek Kozicki wrote: Euclidean::Point<N> Euclidean::Line<N> // not very different from projective line ?? Euclidean::SemiLine<N> Euclidean::Segment<N> Euclidean::Simplex<N>

I like this way of representing them. And for instance, Point<2> can be a specialization that adds members x and y, them being references to coord[0] and coord[1], same thing with Point<3>. As those geometry classes are (and will) be used a lot, the main usage should be kept trivial and simple (or as others may say: KISS methodology). using namespace euclidean; template <unsigned D, class T> struct point { T coord[D]; // someone wrote about a smallvector type... }; template <class T> struct point<2, T> { point() : x(coord[0]), y(coord[1]) {} point(const T &_x, const T &_y) : x(coord[0]=_x), y(coord[1]=_y) {} T coord[2]; T &x, &y; }; something similar for rects template <unsigned D, class T> point<D, T> cross(const point<D, T> &pt1, const point<D, T> &pt2) { return // cross product, we should add specializations for each // dimension } template <unsigned D, class T> T dot(const point<D, T> &pt1, const point<D, T> &pt2) { return // same thing, specializations for each dimension } point<2,double> pt1(3,4); point<2> pt2(5,6); point<2,double> pt3 = cross(pt1, pt2); double d = dot(pt2, pt3); rect<2,double> rc(p2, pt3); double a = rc.area(); // or area(rc)? []s Rodolfo Lima _______________________________________________________ Yahoo! doce lar. Fa�a do Yahoo! sua homepage. http://br.yahoo.com/homepageset.html

"Jason Hise" wrote

If anyone is interested, I have already completed a library for the math that a geometry library would require for my game engine. It supports the following types, along with all of the most commonly used operations that they should naturally support:

Sounds great! [...]

The code has been uploaded to the boost vault (http://boost-consulting.com/vault, geometry_math.zip).

Would it probably be easier for potential users if everything geometry related was in the "Math -Geometry" subdirectory, which has already helpfully ben provided by Rodolfo Lima for the purpose? http://tinyurl.com/fs52z FWIW I ( somewhat farsightedly IMO) allowed for avoidance of potential name collisons in my offering by helpfully suffixing my version with my initials AL! (Looking at it I should add some more stuff describing the library and add my name in the associated info text too). Meanwhile your library sounds very interesting so I hope to get a chance to look at it now! regards Andy Little

"Jason Hise" wrote

Andy Little wrote:

...

Meanwhile your library sounds very interesting so I hope to get a chance to look at it now!

Enjoy :)

I've had a quick look. It looks like a very classical matrix library. There are some issues #include <entropy/linear_algebra.hpp> using entropy::vector; int main() { vector<double,2> v1(1.,2.,3.); } This causes the program to crash when run, so I presume some compile time asserts would be mandatorry. Overall though it looks very clean. In fact its almost the exact opposite of my own geometry library in the vault. This brings me to a problem I have been wrestling with: As author of pqs physical quantities library I am pretty much required to implement a geometry library so that it can use physical quantities as value_types, but I dont feel it reasonable that I should impose that on everybody. The fact that my library allows use of physical quantities as value_types has repurcussions in terms of the interface (no operator[]) and the implementation (Look at the comparative zip file sizes). I think maybe the best option would be to withdraw my own library as a candidate for The Boost.Geometry library and rather create a pqs geometry library as part of the (tentative Boost) pqs distro. That would, I believe, help to move a Boost.Geometry library forward. Of course anyone that strongly disagrees.. please say so ... regards Andy Little

Andy Little wrote:

What exactly does using physical quantities entail? Is the problem that performing matrix multiplication results in the types of the physical quantities becoming mangled, and if so couldn't you just make matrices use untyped units while allowing the vectors to keep their types?

I guess I really need to provide some detailed documentation about it, but that is unlikely to happen soon as I have too much else to do. A 3D vector needs to be converted to a homogeneous vector before it can be multiplied by a matrix. Lets assume a 3d length vector. it might have elements x == 1mm, y == 2 mm, and Z == 3 mm To convert that to a homogeneous vector requires multiplying each element by a constant which is kept in the 4th element of the homogeneous vector. In the case of a numeric homogeneous vector the constant is numeric naturally (usually, but not necessarily, with value of 1) but in the case of a physical quantity vector the type of the constant is the reciprocal of the type of the quantity comprising the original vector. Assuming units of meters the constant would be in units of meters to_power -1. The homogeneous vector is suitable for multiplication by a 4 x 4 transform matrix, but the types in the matrix are required to give a matrix of the same type in multiplication of two matrices and to be multipliable by the vector. The elements of the resulting matrix also have various different types . The following is actual stream output for for a RC matrix describing a rotation of 45 degrees about a point 1mm from thex origin and 1 mm from the y origin (repeated from a previous post) The matrix is the result of concatenating a translation , a rotation and another translation of course | 0.707107, 0.707107 , 0 m-1 * 1e3 | | -0.707107, 0.707107 , 0 m-1 * 1e3 | | 1 mm , -0.414214 mm, 1 | The units relate to the various transforms. The units provide a useful reference over simply using numeric types. Note however that its not possible to iterate over the rows and columns with operator []. Of course the big question is whether it is worth going to all this trouble. Why not just use numeric types? I dont have an answer to that except to say that I have found it extremely interesting to find out how far it is possible to go in using physical quantities over numeric types. There is probably a positive benefit in catching errors in complicated equations. The other feature is that it is simply more satisfying to be modelling using physical quantities directly in equations. Thats difficult to quantify, but its maybe similar to the difference between a high level language and a low level language or between watching television in colour and black and white. Thats the upside. I seem to be modelling reality a bit better. The downside is that the implementation is much more complicated. Thats partly a result of C++'s current lack of features (Joking!) which result in a lot of extra typing, though Arkadiy Vertleybs Boost.Typeof library has already provided a good indication that decltype and auto would help a lot. The other features such as Concepts would also help I think. Nevertheless I think thats is a big practical issue with pqs in general.

For instance (note that I am using row vectors and assuming the meta function remove_units has been implemented):

Sure... To a mathematician and probably many physicists thats much easier, but to me its just not sexy. I mean remove the units and you are back with doubles. I do sometimes wonder if this is like the Emperor has no clothes thing but as I said before I prefer not to justify whether what I'm doing with the geometry stuff in pqs is useful or generally practical and thats why I would prefer to develop it separately and keep it within the pqs library. ( OTOH I have had some feedback especially from mechanical engineers and physicists that get it!) regards Andy Little

Andy Little wrote:

I think the clue to speed is that quaternion uses a 3x3 matrix whereas a transform matrix to do same job would be 4x4 (which is a lot more calcs many redundant!), though 4x4 matrix can hold information about perspective and translation which a quaternion cant AFAIK. Also 1 matrix can hold an arbitarily complex transform by concatenating (multiplying) a series of matrices of simpler transforms. e.g any sequence of rotations, translations, scalings, perspective transformations, mirror etc.

I'm really *not* experienced on the argument (i've done some graphic programming just as an hobby), but this is what Allegro (a great game-oriented graphics-but-not-just-graphics library) says on the subject (from the allegro:quaternion info page): "Quaternions are an alternate way to represent the rotation part of a transformation, and can be easier to manipulate than matrices. As with a matrix, you can encode a geometric transformations in one, concatenate several of them to merge multiple transformations, and apply them to a vector, but they can only store pure rotations. The big advantage is that you can accurately interpolate between two quaternions to get a part-way rotation, avoiding the gimbal problems of the more conventional euler angle interpolation." A quick wikipedia search reveals that the above gimbal problem is the gimbal lock (from the wikipedia page on euler angles): "Unit quaternions, also known as Euler-Rodrigues parameters, provide another mechanism for representing 3D rotations. This is equivalent to the special unitary group description. Quaternions are generally quicker for most calculations, conceptually simpler to interpolate, and are not subject to gimbal lock. Much high speed 3D graphics programming (gaming, for example) uses quaternions because of this." In turn the gimbal lock is (still according to wikipedia): "In gyroscopic devices controlled by Euler mechanics or Euler angles, gimbal lock is caused by the alignment of two of the three gimbals together so that one of the rotation references (pitch/yaw/roll, often yaw) is cancelled. This would require a reset of the gimbals using an outside reference. It may also be described as the situation when all three gyros hit the limits of their ability to move within the sensing mechanism - they hit hard stops and stop moving around." It seems that this happens (I do not pretend to understand everythings :) not only with physical devices but also in code. BTW, allegro provides some great animated examples that show the difference of rotations done with matrices and with quaternions. In the end, quaternions are not used just because they are faster, but because they avoid errors in corner cases. HTH -- Giovanni P. Deretta

"Giovanni P. Deretta" wrote [snip explanation of quaternions]

In the end, quaternions are not used just because they are faster, but because they avoid errors in corner cases.

Thanks (and to Jason Hise) for the information re quaternions. FWIW boost boost has a quaternion class http://www.boost.org/libs/math/quaternion/quaternion.html Even some preliminary info on rotations: http://www.boost.org/libs/math/quaternion/HSO3.hpp Is it possible to reuse Boost.Quaternion in a geometry library or are there problems associated with that? regards Andy Little

...

My elaborate explanations about anonymous union simply demonstrate that full opengl compatibility comes at huge price - it forces internal data structure. A huge no-no in good OO design.

Not necessarily, if what you're primarily interested in doing is OpenGL. I think there is a middle ground that is OpenGL-friendly without being OpenGL-centric.

vec2 a two component floating-point vector vec3 a three component floating-point vector ... ivec4 a four component integer vector

With C++ templates one could represent all those in one class template

They could, but from an OpenGL point of view, it would also be nice to have typedefs that have the type and dimension built into the typename, OpenGL-style. Such as vertex2i, vertex2f, vertex3d. (The OpenGL API has variants such as glVertex2i, glVertex2f, etc) Along with that, a boost::gl namespace could wrap the entire OpenGL API glVertex2i(x,y) -> boost::gl::vertex(v) glVertex2f(x,y) -> boost::gl::vertex(v) glVertex3d(x,y) -> boost::gl::vertex(v)

Secondly, the OpenGL?vec? family above is used IIRC as a standard container for different purposes, such as a vertex, or a color, but IMO it would be more 'user friendly' to create a color type and a vertex type and only convert them to their low level OpenGL ?vec? equivalents for output,

More "user friendly" could be debated, but certainly more statically type-safe to have color3f and vertex3f versus vector3f for both. But, it is often useful to treat colors as vectors for interpolation, so there needs to be conversions. Here is an interesting question: Should there be a normal that behaves differently to a vector? (or vertex?) In the case of 4x4 matrix transformation, the translation is applied to vertecies, but not normals.

The general thrust of the above is that I would prefer to end up with a User Orientated design as opposed to a design which provides low level primitives of indeterminate meaning (eg using the same vector type to hold a vertex and a color as raw Open GL does).

OpenGL accepts either arrays or named x,y,z parameters, but I would like to clarify that OpenGL is a C API with no structures or types except for GLfloat, GLdouble, etc.

The downside of using higher level Concepts is that One may end up with a lot of structurally similar looking entities. The upside may be that what we are really discussing is Concepts which might correspond with the SoCalled Generic Programming approach. A simple example of the difference.

In the OpenGL context I'm interested in doing certain things in a concise efficient way. Genericity does not necessarily serve that purpose. It seems to me that an OpenGL-centric layer based on a templated generic library might serve both purposes, but I havn't seen that actually put into practice. :-) My intuition is that the genericity of templates isn't a good match for the specifically crafted OpenGL API that is rooted in assumptions about computer graphics hardware. A wrapper namespace might be a good way to harmonise between the general mathematical viewpoint and the specificness of OpenGL.

...

Fast disply in yade is much less important than geometrical computations themselves - related to physics of the system, not to the graphics.

That depends what your job is. Mine happens to be feeding OpenGL with information. Cheers, Nigel Stewart

Andy Little wrote:

Pragmatically what I'm interested in is finding some basic Graphics capability, which is cross-platform and available, just because that is the natural output format for geometry and would be very helpful for a geometry library. I have heard that GLUT could provide this basic functionality. Is that the case?

GLUT is a wrapper around the platform-dependent parts of OpenGL, but not by itself capable of any graphic output. It needs OpenGL itself for that. Let me elaborate. OpenGL requires a graphics context. However, OpenGL itself provides no means of obtaining one, as such an action is inherently platform-dependent and thus misplaced in a platform-independent library such as OpenGL. The means of obtaining a context differ from platform to platform. Win32 offers WGL, the X Windows System offers GLX, and Macintosh offers AGL. Other platforms may have yet more such system libraries. GLUT is primarily a unified wrapper around these platform-dependent libraries. In addition, GLUT provides a few functions to draw some graphics primitives, such as cubes, cones, and teapots, and functions to handle menus. Sebastian Redl

Andy Little wrote:

"Geoffrey Irving" <irving@cs.stanford.edu> wrote in message news:20060317182700.GG9842@lie.Stanford.EDU...

...

On Fri, Mar 17, 2006 at 03:09:26PM -0300, rodolfo@rodsoft.org wrote:

...

On Fri, Mar 17, 2006 at 10:17:53AM -0700, Richard Newman wrote:

...

Is it reasonable to extend the logic to check for 3D shapes (i.e., spheres instead of circles, etc.)?

It certainly would be a reasonable strategy to get the 2D work you have into the library and treat 3D as a later extension.

In my own work on this I used two namespaces "geometry::two_d" and "geometry::three_d". (I shall put what I have in the vault). I or someone could create a Geometry folder ...?

[...]

...

...

All coordinates are double. Maybe each primitive should be a template, like: point_t<double> is a point with double floating point coordinates, point_t<int> is with integer coordinates, etc.

Templatization of the float type is good, and again point_t should probably be a general purpose small vector type.

I'm not at all familiar with the math involved, but I imagine that the capabilities could be extended for n-dimensionality if the template types were vectors. Template specializations for 2 and 3-D would assure specific performance, but really any geometry type calculations in n-dimensions would work: intersections of hypercubes and hyperspheres, etc. I'm sure this is beyond the scope of an inaugural library, but still an interesting extension. Because of this possibility, I would argue that vector support (as tuples for the point specifications) is valuable. Kind regards, Richard Newman

Nigel Stewart wrote:

...

I'm not at all familiar with the math involved, but I imagine that the capabilities could be extended for n-dimensionality if the template types were vectors.

So, how is a cross product defined and computed in 2D or 4D? :-)

As the orthogonal complement to the outer product in M dimensions, obviously ! ;-) Regards, Stefan

"Nigel Stewart" wrote

Something similarly scoped to my own C++ math/geometry functionality would be of great interest...

http://www.nigels.com/glt/doc/group___math.html

Bounding box, ray, plane, 3x3 matrix, 4x4 matrix, 2d, 3d and 4d vectors...

It looks very interesting. I am unclear as to your intents with it though. Are you suggesting that code as a basis for a boost effort? AFAIK there would be difficulties re the license as a basis for a boost library I think. The OpenGL stuff is very interesting (see below re a viewer). I think there needs to be a cut off between geometry and graphics though. Its difficult to know where that cut off is, though I would have thought a bounding box , ray etc would be clearly graphics rather than geometry? I would guess that an initial aim for the project could be to identify the minimal essential geometry primitives/ and functions. There are for instance various ways to represent a line and so on. But some features keep cropping up e.g I'm glad to see the matrices, though it looks like quaternions must be included too. OTOH a geometry library makes much more sense if you can see what you are doing visually, so a simple portable Viewer based on OpenGL might also be a useful basic requirement. As I understand it its relatively easy and portable to do this using GLUT ( though I guess you'd know a lot more about that ? ), Maybe a cross-platform stand alone graphics viewer would be a good pre-requisite to a geometry project... regards Andy Little

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