Christian Holmquist wrote:

Something that I miss very much is library for multidimensional/spatial data structures. This is indeed a very broad subject, but there are (to my knowledge) no good libraries out there that can fill in the gap. Most (?) implementations of today live well integrated in larger systems, such as 3d rendering or physics simulation frameworks..

'Foundations of Multidimensional and Metric Data Structures' is a good book on the subject, and if some of these structures would be assembled in a modern c++ library I think it'd be useful

regards, Christian

Good idea. We're working on the Geometry Library including spatial data structures and spatial algorithms. I gauged interest for Boost in January and there was interest. It was published for preview and there were valuable comments how to do it better and more generic. Those comments are being applied now. The library as it was published for preview was two-dimensional. Now it is more generic, it is dimensionless and can be applied for xy-points, latlong-points and also for example 3d-points, although we will only implement the strategies for xy and (as much as possible) for latlong, for the moment. I will sent a new preview to the boost list (don't know exactly when) but even if Boost will not accept the library, or not in the near future, it will still be published and maintained as an Open Source library. Besides the Geometry Library we will rework our current projections into an accompanying Projection Library. Some help would be welcome and the Summer of Code could be very helpful for us. Best regards, Barend ------------------------------------- Barend Gehrels Geodan Holding b.v. Amsterdam, The Netherlands -------------------------------------

On Wed, Mar 5, 2008 at 3:53 PM, Bruno Lalande <bruno.lalande@gmail.com> wrote:

As we're talking about geometry, I have an idea to propose, that came to my mind a couple of times. It would be to have a Boost library that portably handles 3D hardware acceleration capabilities by wrapping the most widely used implementations (I obviously think about OpenGL and Direct3D).

I don't quite understand the need. OpenGL is an open standard and can be used in multiple systems, including windows. Why not use OpenGL directly? If you are to provide a library that can run over OpenGL and Direct3D, it can only be a subset of OpenGL capabilities (those common to Direct3D), so it would be strange working in limiting an already existing library. If the idea is to provide a OpenGL wrapper that is more C++ friendly, that is another story. Or is there a reason to prefer Direct3D under some conditions? David

Hello,

...

I don't quite understand the need. OpenGL is an open standard and can be used in multiple systems, including windows. Why not use OpenGL directly?

There are various reasons to use Direct3D, most having to do with trasportability of some sort. In particular if one wants to move code to an Xbox(360).

That's it. What I want is to be able to deliver graphics libraries that don't speak to a specific type of users (namely OpenGL users, even though I'm part of them). Moreover, this kind of library could serve as an extensible framework to "easily" implement support for over implementations. For example I'm currently doing quite the same kind of work to enable a little engine I've written for PSP and then ported to PC, to run on both with the same code.

But 3D graphics is a mine field when it comes to what abstractions, features, and implementations to support. It brings up even worst nightmares than the GUI discussions have brought. I suggest Boost stay clear of such a library at the moment, it's just not worth the pain.

You're probably right and anyway, the need for spatial data structures is much more important than this need (it can even be a precondition to it). Bruno

On Wed, Mar 5, 2008 at 11:55 AM, John Femiani <JOHN.FEMIANI@asu.edu> wrote:

...

...

Something that I miss very much is library for multidimensional/spatial data structures.

I strongly agree with this too. I often develop libraries that are related to 3D geometry, and I always end up regretting that there doesn't exist any somehow "standard" spatial data structure that wouldn't be related to any particular implementation or product. As a consequence it's very difficult in this domain to deliver libraries that are really portable and easily integrable.

What are we talking about-- Meshes? Trees? Didn't somebody work on a half-edge mesh last summer? I personally would love it if somebody would work on interval range trees or kd trees etc. as well as meshes that work with BGL.

Hopefully we could have Bounding Interval Hierarchies, kd-trees, oct-trees, quad-trees, etc...all built on a generic tree framework. I have some code that provides generic iterators (post-order, parent-iterator, child-iterator) that could be extended to pre-order, and breadth-first iterators. They are built on boost:iterator_facade. Adobe also has a generic forest class that seems to be very close to what has been discussed here before when talking about a generic n-ary tree class. I also have some rough code for a Bounding Interval Hierarchy, and a generic n-ary tree, but they are definitely not boost-ified or ready for public use. Some other items - the generic n-ary tree should have a Boost.Intrusive counter-part, the iterators are probably generic enough to live in Boost.Iterators, and there exists SoC tree code that might be able to be used for providing tree rebalancing functions.

Hopefully these can avoid the boost minefield relating to 'point' types because trees only work on coordinates (no need to intepret them as "points" per se), and meshes are entirely topological.

I don't see anything wrong with a CartesianCoordinateConcept that requires x(), y(), z() along with typedefs or something to that effect. I think the consensus that was reached with the "point" discussion is that too many people want too many different things out of a generic point class, but the algorithms are concerned with very few details of the point class, mainly just "expose x, y, and z, and the types of each" - so don't try to make the perfect generic point class, let people use their own. Just provide algorithms that will work with their point classes, as well as the default (very basic) point class provided by the library. --Michael Fawcett

Bruno Lalande wrote:

...

...

Hopefully these can avoid the boost minefield relating to 'point' types

because trees only work on coordinates (no need to intepret them as "points" per se), and meshes are entirely topological.

I don't see anything wrong with a CartesianCoordinateConcept that requires x(), y(), z() along with typedefs or something to that effect. I think the consensus that was reached with the "point" discussion is that too many people want too many different things out of a generic point class, but the algorithms are concerned with very few details of the point class, mainly just "expose x, y, and z, and the types of each" - so don't try to make the perfect generic point class, let people use their own. Just provide algorithms that will work with their point classes, as well as the default (very basic) point class provided by the library.

This is exactly what I think too. The lack is not about the structure (everybody has one and is happy with it) but the algebra applied to them (everybody reinvents the wheel on his own structure). Just one point: requiring named accessors (x(), y(), z()) would bind us to a specific number of dimensions. One very common need is to be dimension-agnostic. In terms of structure we already have that : Boost.Tuple. So the idea would be to have your CartesianCoordinateConcept requiring templated accessors get<0>(), get<1>(), etc... instead, this way the algorithms could work by default on tuples.

Bruno

The Geometry Library as we prepare it for Boost/Open Source takes this approach now, as suggested by Hervé Brönnimann. The accessors as get<0> are useful, but limited: they do not work in loops ("expected compile-time constant expression"). So there have to be also a second accessor get(index). We have the point now defined like this (named "value"). template<typename T, size_t D> class point { public: /* ... */ template <size_t K> inline void value(const T& v) { BOOST_STATIC_ASSERT(K < D); _values[K] = v; } template <size_t K> inline const T& value() const { BOOST_STATIC_ASSERT(K < D); return _values[K]; } inline void value(size_t index, const T& v) { BOOST_ASSERT(index < D); _values[index] = v; } inline const T& value(size_t index) const { BOOST_ASSERT(index < D); return _values[index]; } private: T _values[D]; }; And a derived point like this: template <typename T> class point_xy : public point<T, 2> { public : inline const T& x() const { return value<0>(); } inline const T& y() const { return value<1>(); } inline void x(const T& v) { value<0>(v); } inline void y(const T& v) { value<1>(v); } }; template <typename T> class point_latlong : public point<T, 2> { public : /* ... */ inline const T& lon() const { return value<0>(); } inline const T& lat() const { return value<1>(); } inline void lon(const T& v) { value<0>(v); } inline void lat(const T& v) { value<1>(v); } }; (It is presented like this for clarity here, in GCC this doesn't yet compile and has to be slightly different). For each derived point class we defined some basic strategies. So for point_xy there is a strategy pythagoras to calculate the distance, and for point_latlong there is a strategy greatcircle. For a point_xyz there would be a 3D pythagoras calculation, or that one could be made dimension-independant. In this way the distance algorithm implementation can use the distance-strategy for the point-type, and the distance algorithm is itself coordinate free, works for any point. The strategy_traits class selects the strategy to be used by default. But the library user can also select an own strategy, for example to calculate more precise distances with latlong coordinates. Best regards, Barend

All this sounds really good :-) I followed discussions about the geometry template library, but I hadn't enough time to read them precisely. I hadn't realized it was that close to what I just described.

You said earlier that you were needing some help. Could you be more precise?

Bruno Yes, some help would be welcome.

Based on the valuable comments from the boost list I'm now implementing the changes leading to this new design with xy and latlong points, strategies and algorithms. This is exciting but takes some time of course. Besides this we also planned to Opensource/templatify/boostify our projection algorithms. So in the end it is more work than planned. And of course there might be more rework if more people from different environments will examine the preview. Therefore I was triggered to the Summer of Code request on this list. The preview will soon be published again and it would be nice to get in contact with interested people who like the design and want to help with the "completion" (if a geometry library is ever complete). Barend

...

...

...

Hopefully these can avoid the boost minefield relating to 'point'

...

because trees only work on coordinates (no need to intepret them as

types points"

...

per se), and meshes are entirely topological.

I don't see anything wrong with a CartesianCoordinateConcept that ..... I see good use for:

IndexablePointConcept - supports runtime indexing (array-like access, e.g. vec[0]) TupleAccessConcept - supports boost::get<N>(vec) syntax at a minimum, and we can probably think of more. --Michael Fawcett

So much for avoiding the minefield! I really did not mean to steer this conversation that way. Anyhow I think we are talking about coordinates and not points. What I got out of the past discussions on points was that a "Point" is completely different than the coordinates used to describe it, and that there is this whole slew of semantic issues verses performance tradeoffs regarding things like the fact that vectors are not points, you can not add points, etc. --John _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Hey, I see that this discussion is heading somewhere towards the support for graphics programing (which is a good thing ;) ), but as you were looking for ideas, I thought that I'd mention one other thing which I'm sorely missing in C++ - a good (prefferably mirror-based) reflection facility/library. One that would be supporting both compile-time and (at least partially) dynamic reflection of base types, functions, their parameters, return value, structs, unions, classes and their base classes, attributes and member functions, also the "special" ones like constructors / destructors, instances, variables, and so on. Reflection can be a great tool when doing certain kinds of things, especially persistence-related, like (de)serialization in multiple formats, (de)marshalling during RPCs, but also as a support for scripting, virtual construction, object inspection, custom debugging and much more. In the proces of developing my own reflection library few years ago, I learned that designing such a little-more-than-basic-facility is quite difficult, if you want to reflect more than the types, simple classes their attributes and member functions. Problems start to arise when one is trying to reflect containers, objects behind interfaces (like an implementation of a xml document, or a stream, for example) or objects behind one or even behind multiple proxies and when trying to serialize or send such objects over a network. With such classes/objects it is not obvious what to reflect, the internal implementation, it's public interface, one of it's proxies or whether to allow to switch between these meta-classes. This depends on the context. The implementation of mine partially addressed some of these issues, but it uses many things, that are not implemented in the boost libraries, which I had coded myself and it definitelly needs a major or possible complete redesign and rewrite. Unfortunatelly "they" ;-) want me to finish my PhD thesis so I don't have much free time right now to do that. But I would be glad to lend a hand in the near future and offer my humble expertise in this field if there is any interest ;) I'm aware of the boost.extension/boost.reflection project and as http://boost-extension.blogspot.com/2008/02/back-at-work.html claims, the show is back on the road again ;) so I'm definitelly looking forward to see some progress here too. best regards, -- ________________ ::matus_chochlik

<snip>

Also, as stated by Mr Glyn Matthews on another thread, the cpp-netlib project (http://cpp-netlib.sourceforge.net) for implementation of clients for handling various protocols like HTTP and ESMTP using </snip> I'm sorry, the link should be http://www.sourceforge.net/projects/cpp-netlib

Yours sincerely, Divye Kapoor Second Year B.Tech(IDD) Computer Science Indian Institute of Technology, Roorkee -- Whether the chicken crossed the road or the road moved beneath the chicken depends upon your frame of reference.

Yes we did. The student (Huseyin Akcan) fell sick in early August and could not finish the project, so we left it at that until he graduated. He now has finished his PhD and is back on an assistant professor position in Izmir, Turkey, and we hope to complete the project (in our timeframe). As for interval range trees or kd trees, they've long been available (generic form) in the CGAL library. They're not hard to implement esp. if you do it inplace: http://photon.poly.edu/~hbr/publi/ilya-thesis/doc/geometry/ static__kd__tree_8hpp.html http://photon.poly.edu/~hbr/publi/ilya-thesis/doc/geometry/ dynamic__kd__tree_8hpp.html I'm sorry I never worked on the release of the code after Ilya finished his MS Thesis. But let me know what you think of the interface and the code... -- Hervé Brönnimann hervebronnimann@mac.com On Mar 5, 2008, at 11:55 AM, John Femiani wrote:

What are we taling about-- Meshes? Trees? Didn't somebody work on a half-edge mesh last summer? I personally would love it if somebody would work on interval range trees or kd trees etc. as well as meshes that work with BGL.